3

如果我们有一种仅由原子元素和一元和二元运算符组成的语言：

atomic elements: a b c
unary operators: ! ~ + -
binary operators: + - / *

然后我们可以定义一个语法：

ATOM := a | b | c
UNOP := ! | ~ | + | -
BINOP := + | - | / | *
EXPR := ATOM | UNOP EXPR | EXPR BINOP EXPR

然而，这种语法会导致不明确的解析树（以及由于左递归导致的递归下降解析器中的无限循环）。

所以我们添加一个优先表：

Precendence 1: unary+ unary- ~ ! (Right to Left)
Precendence 2: * / (Left to Right)
Precendence 3: binary+ binary- (Left to Right)

我的问题是我们可以通过什么算法或程序获取优先表并为递归下降解析器（不是左递归）生成适当的语法。

优先表是操作员组和相关方向（L->R 或 R<-L）的有序列表。答案是将其作为输入并产生语法作为输出。

4

2 回答 2

3

描述任意优先级的通用语法可以使用基于表的 LALR 解析器进行解析，并且可以使用 yacc 生成。但这并不意味着当您希望使用递归下降解析器时一切都会丢失。

递归下降解析器只能验证语法是否正确。构建语法树是另一回事，应该在树构建级别处理优先级。

因此，请考虑以下可以解析中缀表达式的没有左递归的语法。没有什么特别的没有优先的迹象：

Expr := Term (InfixOp Term)*
InfixOp := '+' | '-' | '*' | '/'
Term := '(' Expr ')'
Term := identifier

（右侧使用的符号类似于正则表达式，使用大驼峰写的替换规则，使用小驼峰引用或写标记的规则）。

在构建语法树时，您有一个当前节点，您可以向其中添加新节点。

大多数情况下，当您解析规则时，您会在当前节点上创建一个新的子节点并使该子节点成为当前节点。完成解析后，您将进入父节点。

现在，当您解析InfixOp规则时，应该采取不同的做法。您应该为相关节点分配优先级强度。Expr节点具有最弱的优先级，而所有其他运算符具有更强的优先级。

处理中缀优先级

解析InfixOp规则时，请执行以下操作：

  1. 当当前节点的优先级强于传入节点的优先级时，继续上一级（使父节点成为当前节点）。

  2. 然后插入传入节点的节点作为当前节点的最后一个子节点的父节点并使其成为当前节点。

由于Expr节点声明具有最弱的优先级，它将最终停止爬升。

让我们看一个例子：A+B*C

!在使用当前令牌后，当前节点始终标记为。

Parsed: none

Expr!

Parsed: A

Expr!
|
A

Parsed: A+

Expr
|
+!
|
A

Parsed: A+B

  Expr
  |
  +!
 / \
A   B

Parsed: A+B*

  Expr
  |
  +
 / \
A   *!
   /
  B

Parsed: A+B*C

  Expr
  |
  +
 / \
A   *!
   / \
  B   C

如果您以后序方式遍历它，您将获得可用于评估它的表达式的反向波兰符号。

或者反过来一个例子：A*B+C

Parsed: none

Expr!

Parsed: A

Expr!
|
A

Parsed: A*

Expr
|
*!
|
A

Parsed: A*B

  Expr
  |
  *!
 / \
A   B

Parsed: A*B+

  Expr
  |
  +!
  |
  *
 / \
A   B

Parsed: A*B+C

    Expr
    |
    +!
   / \
  *   C
 / \
A   B

处理关联性

有些运算符是左结合的，而另一些是右结合的。例如，在 C 语言家族中，+是左结合的，而=是右结合的。

实际上，整个关联性归结为对相同优先级的运算符的处理。对于爬升时的左结合运算符，当您遇到具有相同优先级的运算符时，会继续上升。对于右结合运算符，遇到相同的运算符时停止。

（演示所有技术需要太多空间，我建议在一张纸上尝试一下。）

处理前缀和后缀运算符

在这种情况下，您需要稍微修改语法：

Expr := PrefixOp* Term PostfixOp* (InfixOp PrefixOp* Term PostfixOp*)*
InfixOp := '+' | '-' | '*' | '/'
Term := '(' Expr ')'
Term := identifier

遇到前缀运算符时，只需将其作为新子节点添加到当前节点，并将新子节点作为当前节点，无论优先级，无论是强运算符还是弱运算符，都会正确，优先级攀登规则中缀运算符确保正确性。

对于后缀运算符，您可以使用我在中缀运算符中描述的相同优先级攀登，唯一的区别是我们没有后缀运算符的右侧，因此它只有 1 个孩子。

处理三元运算符

C 语言家族有?:三元运算符。关于语法树构建，您可以将?和:作为单独的中缀运算符处理。但是有一个窍门。您为 创建的节点?应该是一个不完整的三元节点，这意味着您执行通常的优先级攀爬并放置它，但是这个不完整的节点将具有最低的优先级，这可以防止更弱的运算符（例如逗号运算符）越过它。当你到达时，:你必须爬到第一个不完整的三元节点（如果没有找到，则报告语法错误），然后将其更改为具有正常优先级的完整节点，并使其成为当前节点。如果在当前分支上存在不完整的三元节点时意外到达表达式的末尾，再次报告语法错误。

所以a , b ? c : d被解释为a , (b ? c : d)。

但是a ? c , d : e将被解释为a ? (c , d) : e，因为我们阻止了逗号越过 ?。

处理数组索引和函数调用

尽管出现后缀，但它们是中缀运算符，右侧有句法强制括号术语，数组索引和函数调用也是如此。

于 2015-05-09T15:37:25.147 回答
2

将运算符优先语法转换为语法 [1] 很容易LR(1)，但生成的语法将使用左递归来解析左关联运算符。消除左递归很容易——例如，使所有运算符右结合——但是虽然生成的语法识别相同的语言，但解析树是不同的。

事实证明，稍微修改递归下降解析器以处理优先关系并不难。该技术是由Vaughan Pratt发明的，本质上是使用调用堆栈来替代经典调车场算法中的显式堆栈。

Pratt 解析似乎正在经历某种复兴，你可以找到很多关于它的博客文章；一部相当不错的作品是Eli Bendersky的作品。Pratt 在 1970 年代初设计了这个程序，大约在同一时间，Frank deRemer 证明了LR(1)解析是实用的。Pratt 对形式解析的实用性和不灵活性持怀疑态度。我认为从那时起，这场辩论就一直在酝酿之中。Pratt 解析器确实简单而灵活，但另一方面，很难证明它们是正确的（或者它们解析了特定的正式描述的语法）。另一方面，尽管bison最近获得了对 GLR 解析的支持，这使得它使用起来可能不那么烦躁，尽管事实上bison- 生成的解析器实际上解析了他们声称要解析的语法，仍然有许多人同意 Pratt 的声明（从 1973 年开始），即正式的解析方法“不那么易于使用并且使用起来不那么愉快”。

[1] 在实践中，所有 yacc-derivatives 和许多其他 LR 解析器生成器都将接受优先关系来消除歧义；生成的语法表更小，涉及的单元减少更少，因此如果您要使用解析器生成器，没有特别好的理由不使用此技术。

于 2012-12-20T17:19:42.933 回答