时间戳

首页 > 解决方案 > 如何手动遵循计算器的 C++ 语法？

c++ - 如何手动遵循计算器的 C++ 语法？

问题描述

我正在关注 Bjarne Stroustrup 使用 C++ 编写的 PPP，但我很难理解他的计算器介绍性语法（第 189-192 页），如下所示：

// a simple expression grammar
Expression:
    Term
    Expression "+" Term // addition
    Expression "-" Term // subtraction

Term:
    Primary
    Term "*" Primary // multiplication
    Term "/" Primary // division
    Term "%" Primary // remainder (modulo)

Primary:
    Number
    "(" Expression ")"

Number:
    floating-point-literal

首先我们解析 2，它是一个浮点文字，它是一个 Number，它是 Primary，它是一个 Term，它是一个 Expression。图表

然后我们去解析 2 + 3 图表：

2 是一个浮点字面量，它是一个 Number，它是 Primary，它是一个 Term，它是一个 Expression

3 是一个浮点文字，它是一个 Number，它是一个 Primary，它是一个 Term。为什么这本书在这里停止解析，“3”目前符合所有条件成为表达式？

当我尝试手动执行此操作时，我只能在忽略“+”并将 3 解析为 Term 以匹配需求表达式“+” Term 时得出与给定图表匹配的结论。

此外，如果我尝试进一步外推以解析 9 + 3 * 2，而不是向前看 *，我将无法完成语法，因为 9+3 （显然）是一个有效的表达式，没有要相乘的语法。 .

标签： c++

解决方案

我想您遇到的主要问题与您从下到上阅读它的事实有关。书中的箭头表示信息流，而不是解析顺序。

下面是我们感兴趣的语法（供参考）：

Expression:
    Term
    Expression "+" Term
    Expression "-" Term

Term:
    Primary
    Term "*" Primary
    Term "/" Primary
    Term "%" Primary

Primary:
    Number
    "(" Expression ")"

Number:
    floating-point-literal

以下段落试图概述在这种语法的情况下以及更一般的设置中的解析过程。

解析表达式：一个简单的例子

上面的语法给出了解析Expression. Expression被称为语法公理。这意味着为了解析任何给定的表达式，我们必须从Expression规则开始。

让我们考虑表达式2 + 3。解析过程如下：

  1. 我们匹配2 + 3的规则Expression。它必须是 a Term, 形式Expression "+" Term的表达式或形式的表达式Expression "-" Term。原来它是一个Expression "+" Term.
  2. 2 + 3我们匹配with的左侧Expression。
    • 唯一可能的规则2是Term。
    • 2然后我们根据 的规则进行匹配Term。2不包含"*", 也不"/", 也不"%"。因此它必须是一个Primary.
    • 我们继续执行 的规则Primary。由于它不包含任何括号，2因此必须是Number.
    • 最后，我们有2一个floating-point-literal.
  3. 2 + 3我们匹配with的右侧Term。
    • 至于2，3必须是Primary。
    • 同样，遵循与上述相同的路径，3推导出为 a Number，然后是 a floating-point-literal。

最后，2 + 3是形式的表达floating-point-literal "+" floating-point-literal。

解析表达式：复杂表达式

我们现在知道如何解析一个简单的表达式。但是更复杂的呢，比如(2 - 1) + 9 * 3？上述技术也适用于这种情况。这是解析过程的展开版本：

  1. (2 - 1) + 9 * 3是形式Expression "+" Term。
  2. 我们将左侧与 的规则相匹配Expression。
    • (2 - 1)是 a Term（因为它不包含"+"也不"-"）。
    • 同样，(2 - 1)是一个Primary。
    • (2 - 1)是形式"(" Expression ")"。通过使用与 for 完全相同的过程2 + 3，我们最终得到"(" floating-point-literal "-" floating-point-literal ")".
  3. 我们将右侧与 的规则相匹配Term。
    • 9 * 3是形式Term "*" Primary。
    • 9我们根据规则匹配Term并继续，直到我们得到一个floating-point-literal.
    • 我们匹配3的规则，Primary也得到了floating-point-literal一些细化。
    • 最后，9 * 3是Term的形式floating-point-literal "*" floating-point-literal。
  4. 最后，(2 - 1) + 9 * 3减少到"(" fp - fp ")" "+" fp "*" fp。

推荐阅读