65.9K
CodeProject 正在变化。 阅读更多。
Home

数学函数教程：第 3 部分

charles922
starIconstarIconstarIconstarIconstarIcon

5.00/5 (1投票)

2018年5月31日

CPOL

7分钟阅读

viewsIcon

8420

downloadIcon

229

数学函数教程：第 3 部分

引言

在数学函数导师第 2 部分中，介绍了递归下降解析器（RDP）来评估表达式。我收到的关于第 2 部分的电子邮件指出，RDP 可能有点难以理解。正如 Herb Schildt 在C++ 完整参考手册第 967 页中所说：

如果你现在有点困惑，不要觉得难过。

为了阐明 RDP 的工作原理，在第 3 部分中，我开发了一个小程序，允许你逐个方法调用地逐步执行 RDP，帮助你理解发生了什么。虽然它不能替代研究 RDP 代码，但我认为它会很有用，因为它演示了 RDP 的工作原理。

控制台程序

为简单起见，这是一个 Windows 控制台项目。我目前使用的是 24 英寸的 ASUS 显示器，并将控制台窗口的宽度和高度设置为 150 和 60。我也成功地在 HP 笔记本电脑上运行过。根据你的颜色偏好和显示器，你可以在TestParserProgram.cs中更改以下内容

	private const int ScreenWidth = 150;
	private const int ScreenHeight = 60;
	...
	Console.SetBufferSize(ScreenWidth, ScreenHeight);
	Console.ForegroundColor = ConsoleColor.Cyan;
	Console.BackgroundColor = ConsoleColor.Black;

Using the Code

下载并解压项目，然后使用 Visual Studio 打开 _RDPInst.sln_。它包含两个项目：

  1. RDPInstLib - 递归下降解析器 (RDP)。这与第 2 部分中的 RDP 相同，但进行了如下所述的修改。“Inst”是“Instrumented”的缩写。
  2. RDPInst - 用于执行带检测的解析器的主控制台程序，TestParserProgram.cs。

按F6键构建解决方案。

堆栈帧

RDP 的主要修改是添加了一个 List<MyStackFrame> MyStackFrameList。 MyStackFrame 类（我给它这个名称是为了不与 System.Diagnostics.StackFrame 混淆）包含 RDP 评估表达式时感兴趣的项目

public class MyStackFrame
{
	public DateTime Timestamp { get; set; }
	public int StackLevel { get; set; }
	public String Op { get; set; }
	public String Method { get; set; }
	public String Token { get; set; }
	public RecursiveDescentParserInstrumented.TokenType TokenType { get; set; }
	public Double SaveResult { get; set; }
	public Double PartialResult { get; set; }
	public Double Result { get; set; }
	public int ExprNdx { get; set; }
}

顾名思义，递归下降解析器利用递归，将值推入堆栈。当它这样做时，会创建一个 MyStackFrame 对象并将其添加到 myStackFrameList 中。当 RDP 完成表达式评估后，TestParserProgram 会遍历该列表，实际上是“回放”方法和值。

解析简介

解析器的核心是其语法，此处以一种称为EBNF 的符号表示

1       <Expression> := [ "-" ]  <Term> { ("+" | "-")  <Term> }
2       <Term>       :=  <Factor> { ( "*" | "/" | "%" )  <Factor> }
3       <Factor>     :=  <RealNumber> | "("  <Expression> ")"
4       <RealNumber> := <Digit>{<Digit>} | {<Digit>} "." {<Digit>}
5       <Digit>      := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

如果对 EBNF 不熟悉，这个语法定义可能会让人望而生畏，但让我们考虑表达式 **1 + 2 * 3** 并将其分解为语法的*符号*。让我们看看语法的第 5 行。请记住 ":=" 表示“定义为”，垂直条 "|" 表示“或”，第 5 行读作*“一个数字被定义为 0 或 1 或 2 — 依此类推 — 或 9”*。在 EBNF 语法中，0、1、2...9 被称为*终结符*，而 <Digit> 和 < 和 > 中的其他项是*非终结符*。知道 EBNF 中的大括号表示任意数量的项，第 4 行可以读作*“一个 <RealNumber> 被定义为任意数量的 <Digit>”*，或者*“一个 <RealNumber> 被定义为任意数量的 <Digit>，一个小数点，后面跟着任意数量的 <Digit>。”*因此，表达式中的 1、2 和 3 被识别为名为 <RealNumber> 的非终结符。

<Factor>（第 3 行）被定义为 <RealNumber> 或带括号的表达式；对于我们的示例，<Factor> 将简单地是 <RealNumber>。<Term>（第 2 行）被定义为一个 <Factor>，并可选地乘以（或除以，或取模）另一个 <Factor>，在我们的例子中，2 * 3 是第一个 <Term>，其值为 6。1 也是一个 <RealNumber>，将是我们的第二个 <Term>（没有可选的 *、/ 或 %）。在语法的第 1 行，<Expression> 被定义为一个 <Term> 加上（或减去）另一个 <Term>。因此我们的 <Expression> 现在简化为第一个 <Term>，即 6，加上第二个 <Term>，即 1，结果为 7。幸运的是，Schildt 先生已经完成了开发识别此语法的代码的工作！

在代码中，表达式从左到右求值，解析器通过 `GetToken` 方法将其分解为*标记*。在此示例中，有 5 个标记，其中三个是 `TokenType Number`：1、2、3，以及两个 `TokenType Delimiter` 运算符：+ 和 *。由于语法规定 2 和 3 必须在任何加法之前相乘，因此 1 和 + 被放置在堆栈上，在 2 和 3 相乘（得到 6）之后，添加 1 得到最终值 7。让我们看看它的实际运行。

运行程序

构建程序后，按 CTRL+F5 “不调试启动”。应出现一个控制台窗口，其中显示提示“输入带检测解析器的表达式（按 Enter 退出）>”（务必将控制台的高度和宽度设置为适当的大小）。输入要解析的表达式，然后持续按 Enter 键，直到表达式完成。当您按 Enter 键时，程序正在遍历 `myStackFrameList`。在左侧，您可以观察方法调用以及操作（加法、减法、幂运算等）的结果。在右侧是堆栈；您可以观察数字如何被推入堆栈，然后在遇到运算符（例如 +、^ 或 *）时被弹出，显示当前结果。请注意左下方如何显示表达式，并带有指向当前正在处理的标记的插入符号。

例如，让我们使用上面我们看过的表达式。在屏幕左下角的提示符处，键入 **1 + 2 * 3** 并按 Enter 键 3 次。下面的屏幕截图显示了结果：

Running_1

请注意 1 如何被放置在右侧的堆栈中。左下角的插入符号指向表达式中的 +。现在再按 Enter 键 3 次，注意 2 和 3 已被推入堆栈。再按 Enter 键一次，结果 6 被放置在堆栈顶部，替换了 2 和 3。回想一下语法中乘法在加法之前执行。再按 Enter 键两次，注意 1 和 6 已相加得到 7，如下图所示：

Running_2

再次按 Enter 键显示这是我们的最终结果，此时，您可以输入另一个表达式，或者在没有表达式的情况下按 Enter 键退出。

从左到右，显示的项目是

  1. 堆栈帧编号
  2. 方法执行时的时间戳（秒和毫秒）
  3. 正在执行的方法名称
  4. 正在评估的令牌
  5. 令牌类型 (参见 enum TokenType)
  6. 保存结果 - 先前 EvalMultiplyDivide、EvalExponent 或 EvalUnaryOp 的第一个结果
  7. 算术运算符（+、-、*、/、%、^）
  8. 部分结果 - 先前 EvalMultiplyDivide、EvalExponent 或 EvalUnaryOp 的第二个结果
  9. 算术运算的结果
  10. 堆栈上的值

文章顶部的屏幕截图显示了一个更复杂的表达式，(6 * cos(pi / 3) + sqrt((2 - -3) * (10 - 5))) ^ (5 % 3)，在按 Enter 键 22 次之后。此时，6 * cos(pi / 3) 已评估为 3，并位于堆栈底部。2 - -3 已评估为 5，并位于堆栈顶部。请注意 3 前面的减号是*一元减号*。如果您继续按 Enter 键，您可以看到表达式的其余部分是如何评估的，包括幂运算和带括号的表达式。

结论

语法是定义语言或表达式解析器的关键。像本文中描述的手写递归下降解析器是实现代码以识别语法的一种方式。另外，还有诸如ANTLR之类的工具可以生成代码。

历史

  • 版本 3.0.0.0
© . All rights reserved.