LL 数学解析器

• 下载演示项目 - 130.62 KB

引言

本文的主要任务是展示形式语言理论构建在实际应用中的实现。在下面描述的案例中，它将是一个数学解析器（库），用于评估给定的有效数学表达式并返回相应的结果。在脚本语言中，您会发现此算法已实现（它实际上定义在动态编程语言核心行为中 - “一切都在运行时进行评估”）。最常见的是，它被定义为 eval 方法。

在静态编程语言的情况下，我们应该定义一个算法来执行给定字符串的语义（根据符号表）和语法（解析）分析。主要有两种形式语言理论的基本方法可以执行此任务：LL 自顶向下解析器，它从左到右解析输入，并构建句子的左most 推导；以及 LR 解析器，它从左到右读取输入并生成右most 推导。本文将要解释的解析器是使用 C# 编写的 LL 解析器。

背景（Chomsky 层级）

存在无数合法的数学表达式。为了能够区分无效句子和有效句子，我们需要定义一套精确的规则，这些规则又会定义一个*形式文法*（就像在任何自然语言中一样，为了构建正确的句子，我们应该学习它的语法）。这个*文法*，如果被证明属于 LL 文法类别，将能够生成所有可能的有效序列并识别无效序列。值得一提的是，它不描述这些句子的含义，只描述可以应用于它们的规则。如果您正在寻找关于 LL 文法的详细解释，请参考与Chomsky 层级相关的材料，特别是Type-2 文法（上下文无关文法）。点击此处获取详细回顾。

波兰后缀表示法

解析器（基于形式文法）告诉我们输入字符串是否符合定义的规则后，我们将面临根据数学优先级规则计算表达式的问题。以下是一个简单的例子

4*3^(2)  =  36 ('^' stands for power sign)
4*3^(2) !=  122

人们可以轻松计算上面表达式的值，因为他们知道每个运算的优先级。这就是为什么我们将从末尾开始计算，先将 3 提高到 2 的幂，然后乘以 4。然而，机器无法学会这一点；这就是波兰后缀表示法（PPN 或逆波兰表示法）派上用场的地方。它允许我们将给定的表达式转换为一个等效的表达式，其中运算将从左到右顺序执行。想象一下，之前的例子被重写为

(2)^3*4

在这种情况下，可以忽略优先级，因为按顺序我们将获得正确的结果。这就是 PPN 的用途。重要的是要注意，我们将使用*后缀*表示法，因为使用中缀表示法的主要困难在于我们仍然可能在其中包含括号，这意味着优先级顺序问题并未解决。因此，在求值器中，使用后缀表示法更为可取。幸运的是，PPN 字符串是使用*解析二叉树*构建的，而该树又在我们解析器检查输入表达式是否有效时构建。完成此检查后，我们将拥有该树的内存副本，这将允许我们构建 PPN 序列。以下是一个 PPN 表达式的例子

4*3^(2) == 2 3 ^ 4 * (PPN)

构建 PPN 序列后，我们还需要一个*解释器*来执行实际的数学表达式计算。逆波兰表示法解释器是基于堆栈的。*操作数*被压入堆栈，直到遇到*运算符*，然后弹出最后两个项，执行运算，并将结果压回堆栈。我们将在稍后看一个求值器示例。有关更详细的解释，请参考波兰表示法主题。

二叉树

由于 LL(1) 文法帮助我们构建解析树（当然，它是一棵二叉树），我们现在可以使用**左 - 右 - 根**遍历来遍历它，并构建所需的 PPN 表达式。如果您不熟悉二叉树，请参考任何相关的主题。

构建文法

在稍后将要解释的数学解析器中，我们将标记（终结符，不能分解为更小单元的符号）集合定义如下

VT = {+, -, *,  /,  ^, ( , ), a}, 
  where  ' ^ ' stands for power, and  
         'a' stand for any real constant.

文法实际定义了输入表达式的转换（推导）规则。在开始编写这些规则之前，我们必须考虑这样一个事实：优先级（数学上）更高的推导必须放在我们推导树的最深叶子节点；因此，我们必须从数学上不太重要的标记（从数学观点来看， '+' 和 '-' 运算；最高优先级属于一元加减运算）开始编写规则。

#	规则	注释
1	E->E+T	表达式 + 项
2	E->E-T	表达式 - 项
3	E->T	某些表达式可以被视为仅为项
4	T->T*P	项 * 幂
5	T->T/P	项 / 幂
6	T->P	某些项可以被视为仅为幂
7	P->P^F	幂 ^ 因子
8	P->F	某些幂可以被视为仅为因子
9	F-> -F	此推导代表一元负号
10	F-> +F	此推导代表一元正号
11	F->a	因子可以被视为一个常数
12	F->(E)	因子可以被视为括号内的表达式

该文法显而易见的问题（使该文法不属于 LL(1) 类的问题）是

1. 我们有不止一个以相同符号开头的产生式（推导）（产生式 1 && 2, 4 && 5）。这个问题可以通过应用*左因子分解规则*轻松解决。
2. 左递归（产生式 1, 2, 4, 5, 7）。需要消除。

我刚刚指出了我们需要使用的算法，以便后者属于 LL(1) 类。实际转换超出了本文的范围，因此我将跳过它（如果您仍然对此感兴趣，请随时给我发邮件，我会给您发送实际证明）。在最后阶段（在对文法应用所有必需的理论更改后），我们将能够构建 LL(1) 解析表（它将精确告诉计算机要对每个特定输入字符应用什么*推导*）。另外，值得注意的是，在构建 LL(1) 解析表之前，我们需要构建首选符号集（使用First 和 Follow 集）。

LL(1) 解析表

从文法中开发的实际表格可以在上图看到。如果您不熟悉其用法，请查阅任何可用材料，或查看图中的下一个示例。

• V - 代表推进 (adVance)
• $$ - 代表接受 (Accept)

在使用此预测解析表时，我们可以

1. 推导出二叉树，这将帮助我们
2. 定义波兰后缀表达式，进而
3. 求值我们的数学表达式.

让我们举例验证我们的 LL(1) 解析表并构建解析树。

'a+a*a^-a'

堆栈机的初始状态是 E$（其中 $ 代表堆栈结束），这意味着我们从公理 E（E - 表达式）推导表达式。输入流的第一个字符是 a（输入字符串的第一个字符）。为了以某种方式向解析表发出输入字符串已结束的信号，我们将 $ 符号附加到字符串的末尾（a+a*a^-a$）。如果整个输入字符串从语法角度来看是有效的，那么最后，我们的机制将达到最终接受状态（堆栈机中的 $，输入带中的 $）。推导过程如下

1. 查看解析表中堆栈机中的*第一个*字符（E）和输入带的第一个字符（a）之间的交叉点。我们可以看到它是 TW 单元格。将 TW 推入堆栈。
2. 遵循 LL(1) 解析表规则，直到达到 $$ 状态。
3. 如果在解析过程中遇到空单元格，则表示输入字符串无效。

解析树

到目前为止，我们已经建模了一个*语法/语义解析器*，它只能控制给定的表达式是否为有效的数学表达式。如果序列无效，我们的 LL(1) 表将在一个空单元格处停止，正如我之前提到的。使用前面的例子，我们可以构建*解析树*，进而构建*波兰后缀表示法*字符串。使用此字符串，我们将执行实际的求值，这将返回数学函数的值。

树

如果我们使用 LRR 算法（左 - 右 - 根）遍历此树，从*叶子*（没有子节点的节点）获取字符，我们将构建*波兰后缀表示法*字符串。遍历后的字符串将包含以下字符序列

'a a a 0 a - ^ * +'

逆波兰表示法求值器

正如我之前解释的，*逆波兰表示法*求值器是基于堆栈的。操作数被压入堆栈，直到计算机找到运算符（+, -, *, /, ^）。之后，弹出前两个值，并完成求值。结果被压回堆栈。假设对于前面的表达式 a = 2。

2+2*2^-2 = 2.5

首先，计算机应该执行一元负号运算。之后，将 2 提高到 -2 的幂。结果乘以 2，最后加到 2。

如您所见，求值是正确的。LL(1) 解析表有效。

MathObj 项目

包含数学解析器实际实现的归档中，我们可以找到*MathParserDataStructures*项目。以下类图描述了将执行上述所有理论工作的主要类

执行实际求值的主要类是 MathObj 类。它为用户提供了查找任何给定有效数学表达式值的功能。MathParserBinaryTree 类将保存解析树的内存结构。该树由 MathParserTreeNode 对象构建，这些对象本身具有 Nonterminal 或 Operation 值。为了访问树中的节点，我使用了访问者模式。树遍历使用 Left-Right-Root 递归算法执行。

Using the Code

MathObj 类的主要操作是 Evaluate 方法。它接受以下参数

1. mathInput:String - 输入本身（例如：“x+y”）。
2. vars:char[] - 表达式中使用的字符变量数组（例如，{'x','y'}）。
3. varsValues:double[] - 变量值（例如，{2.5,2.6}）。

此计算的结果将是 5.1。

您可能会认为一个更好的类设计可能是一个将 MathObj 类定义为 static 的架构。但我选择了不同的方式，因为大多数时候，人们希望计算函数在某个区间上的值。在这种情况下，字符串输入将保持不变（以及其中的变量 char[]），只有变量的值会改变。因为理论算法的最大开销在于构建解析树，所以我选择只构建一次（并将其状态持久化在内存中）。如果方法第二次调用时字符串未更改，将使用先前构建的波兰后缀表示法来计算表达式的值（这种*持久化状态*的理念使算法的求值速度大大加快）。

/// <summary>
/// Evaluate the mathematical expression.
/// <summary/>
/// <param name="mathInput">Mathematical expression </param>
/// <param name="vars">Character variables
///      contained within the expression[x,y,z etc.] </param>
/// <param name="varsValues">Coresponding values
///     of character variables within the expression </param>
/// <returns> The result of evaluation </returns>
/// <exception cref="MathParserException">MathParserException </exception>
/// <exception cref="ArgumentException">ArgumentException </exception>
public virtual double Evaluate(string mathInput, char[] vars, double[] varsValues)
{
    if (String.IsNullOrEmpty(mathInput))
        throw new ArgumentException("String mathInput is empty or null");

    if (this._mathInput == mathInput)
        _persistState = true;
    else
    {
        this._mathInput = mathInput;
        _persistState = false;
    }

    if (_varsAndValues.Count != 0)
        _varsAndValues.Clear();
    if (vars != null && varsValues != null)
    {
        if (vars.Length != varsValues.Length)
            throw new ArgumentException(
              "vars and varsValues arrays length are not equal");    
        for (int i = 0; i < vars.Length; i++)
            this._varsAndValues.Add(vars[i], varsValues[i]);   
    }
    double retVal;
    try
    {

        if (!_persistState)
        {
            //semantic transform (building the tree)
            this.SemanticTransform();
            this._polishPostfixExpression = 
              new Operation[this._sizeOfPolishPostfixExpression]; //
            this.GeneratePolishPostfixExpression();
        }
        retVal = this.CalculateValue();
    }
    catch (MathParserException)
    {
        throw;
    }
    return retVal;
}

请运行MathParser.v.3示例应用程序，以查看 MathObj 的用法。

输出

下载部分提供的项目的核心输出是MathParser.dll库。此外，我们还可以找到一个非常简单的示例项目。它允许绘制数学函数的图形。请注意，函数仅依赖于一个变量 x : f(x)。

结论

尽管有许多其他项目（包括 CodeProject 上的项目）都探讨了静态编程语言中动态函数求值的问题，但没有一个项目涉及到理论部分。我决定发布我的解决方案，以便读者能够理解形式语言理论在特定问题中的实际实现。本文清晰地将纯粹的理论构建映射到实际示例，我选择使代码尽可能贴近描述部分使用的抽象术语。您可能会认为，在内存成本方面，我应该使用矩阵而不是真正的树结构来设计解析树，但正如我已经写过的，我试图使算法尽可能贴近理论。我使用了许多理论术语，您可以进一步探索并为您特定的问题进行调整/使用。这里，我将它们列出，以便您可以进一步谷歌搜索/探索它们

• 形式语言理论
• Chomsky 层级
• LL(1) 文法
• 上下文无关文法
• 解析器（语法/语义分析器）
• 波兰后缀表示法
• 左因子分解规则
• 预测解析表
• 首选符号集
• First 和 Follow 集
• 二叉树
• 二叉树遍历
• 左-根-右遍历

历史

• 2010年1月18日：初次发布
• 2010年1月20日：更新源代码