1

我正在阅读《Flex and Bison》一书以了解解析器生成器的工作原理，并且有示例：

calclist: /* nothing */
        | calclist exp EOL { printf("= %d\n", $1); }
        ;

exp: factor
   | exp ADD factor { $$ = $1 + $3; } 
   | exp SUB factor { $$ = $1 - $3; }
   ;

factor: term
      | factor MUL term { $$ = $1 * $3; } 
      | factor DIV term { $$ = $1 / $3; }
      ;

term: NUMBER
    | ABS term { $$ = $2 >= 0? $2 : - $2; }
    ;

并且在书中说，上面的语法通过使用单独的非终结符号具有隐含的优先级。但它是如何工作的？假设我们有以下示例：（1 + 3 * 2空格只是跳过）我们读取第一个令牌1，它将被推送到堆栈，NUMBER或者它会通过语法“冒泡”多长时间term？factor从哪个语法规则检查下一个标记？为什么这种语法乘法的优先级高于加法？

4

2 回答 2

2

由于分解语法（单独的非终结符），这具有“隐式”优先级（而不是显式）的原因确实正如文本所说的那样。

完成您的示例1 + 3 * 2，将自己想象成进行解析的计算机，按照“按字母顺序”执行的每条指令。为了找到“exp”（表达式），您必须首先找到一个因子。（您的其他选择是从找到一个“exp”开始，但必须找到一个“因素”。）所以你必须找到一个因素......但这样做你必须找到一个“术语”，因为一个因素要么是术语，或本身以术语开头的因素。所以现在你必须找到一个词，要么是 aNUMBER要么是关键字ABS。因此，您可以“接受”（用语法术语）1实际上是 a 的NUMBER，并且您已经在解析的第一部分取得了成功——找到了一个术语。（您现在1从令牌流中删除+

既然你有一个术语，你也有一个因素（根据定义），但是为了“完成有一个因素的动作”，你需要尝试更长的匹配：一个因素后跟MUL或DIV，然后是一些东西。您的下一个标记是+：它不是 MUL 也不是 DIV。因此，您被迫停止解析因子并返回整个解析链，因为您的因子：1是一个因子，下一个标记仍然是+.

既然你有了一个因子，你就有了一个 exp（根据定义），但是为了“完成拥有 exp 的动作”，你需要再次尝试更长的匹配：一个 exp 后跟ADDor SUB，然后是一些东西. 下一个令牌实际上仍然+是 ADD ...所以您必须继续执行该exp ADD factor { $$ = $1 + $3 };规则。

在这一点上，您（作为解析器）将迄今为止的整个事情推入堆栈并再次开始工作以寻找合适的非终结符——在这种情况下，另一个“因素”。所以你现在从一个因素的规则开始。您必须查找“术语”，如果找到，请尝试执行包含MULor的较长版本的规则DIV。当您完成这部分工作时，您会看到*令牌确实是 MUL，您将不得不采用更长的规则，使“因素”结果使用factor MUL term { $$ = $1 * $3; }规则的一部分。这将接受（又名吃掉/用完）3 * 2序列并返回6“因子”的值，让您完成推入解析堆栈的规则。

返回到 push 状态后，您通过添加 1 并接受（吃掉）完整的表达式来完成“1 +”的解析。当然 1 + 6 是 7，这样你的语法就会返回正确的值。

于 2012-03-10T21:15:02.673 回答
2

优先级是 ADD 和 SUB 的操作数为因数的结果，只有因数包含 MUL 和 DIV 运算符。ADD 不与 MUL 竞争，因为 MUL 被封装在一个术语中。

从解析器的角度考虑这一点：在解析器考虑它与 ADD 运算符的关系之前，必须对术语表达式进行归约，而这种归约消除了 MUL 运算符。

给定A + X * Y，X * Y表达式被简化为term不再表达*运算符的单个语法符号，因此+运算符没有优先级问题；现在只是A + term。

顺便说一句，语法使用非常规的颠倒术语。

这些是术语：A + B + C

这些是因素：A*B*C

添加项（“系列项”），乘以因子（“整数或多项式的因子”）。

真的是这本教科书上的吗？无论如何，请尝试Aho、Sethi、Ullman 的编译器：原理、技术和工具。（1988 年但经典）。

于 2012-03-11T00:49:16.447 回答