6

我了解 LL 递归下降解析器如何处理这种形式的规则：

A = B*;

有一个简单的循环，它根据前瞻令牌是否与第一组 B 中的终端匹配来检查是否继续循环。但是，我对基于表的 LL 解析器很好奇：这种形式的规则如何在那里工作？据我所知，处理这样的重复的唯一方法是通过右递归，但在不需要右关联解析树的情况下，这会破坏关联性。

我想知道，因为我目前正在尝试编写一个基于 LL(1) 表的解析器生成器，但我不确定如何在不更改预期解析树形状的情况下处理这样的情况。

4

2 回答 2

2

语法

让我们将您的 EBNF 语法扩展为简单的 BNF 并假设它b是一个终端并且<e>是一个空字符串：

A -> X
X -> BX
X -> <e>
B -> b

该文法产生b任意长度的终端字符串。

LL(1) 表

要构造表，我们需要生成第一个和后续集（构造一个 LL(1) 解析表）。

第一套

First(α)是从任何语法符号字符串派生的字符串开始的终端集合α。

First(A) : b, <e>
First(X) : b, <e>
First(B) : b

跟随集

Follow(A)是可以立即出现在非终结符右侧的终结符集合 a A。

Follow(A) : $
Follow(X) : $
Follow(B) : b$

桌子

我们现在可以基于集合构造表，$是输入标记的结束。

+---+---------+----------+
|   |    b    |    $     |
+---+---------+----------+
| A | A -> X  | A -> X   |
| X | X -> BX | X -> <e> |
| B | B -> b  |          |
+---+---------+----------+

解析器操作始终取决于解析堆栈的顶部和下一个输入符号。

  1. 解析堆栈顶部的终端：
    1. 匹配输入符号：出栈，前进到下一个输入符号
    2. 不匹配：解析错误
  2. 解析堆栈顶部的非终结符：
    1. 解析表包含生产：将生产应用到堆栈
    2. 单元格为空：解析错误
  3. $在解析堆栈的顶部：
    1. $是输入符号：接受输入
    2. $不是输入符号：解析错误

样本解析

让我们分析一下输入bb。初始解析堆栈包含开始符号和结束标记A $。

+-------+-------+-----------+
| Stack | Input |  Action   |
+-------+-------+-----------+
| A $   | bb$   | A -> X    |
| X $   | bb$   | X -> BX   |
| B X $ | bb$   | B -> b    |
| b X $ | bb$   | consume b |
| X $   | b$    | X -> BX   |
| B X $ | b$    | B -> b    |
| b X $ | b$    | consume b |
| X $   | $     | X -> <e>  |
| $     | $     | accept    |
+-------+-------+-----------+

结论

如您所见，A = B*可以毫无问题地解析表单的规则。生成的输入具体解析树bb将是：

解析树

于 2014-12-03T13:22:36.130 回答
1

是的，这绝对是可能的。重写 BNF 和构建解析表的标准方法对于弄清楚解析器应该如何工作很有用——但据我所知，你要问的是如何避免递归部分，这意味着你会得到 AST 的倾斜二叉树/链表形式。

如果您正在手动编码解析器，您可以简单地使用循环，使用解析表中指示递归调用的前瞻来决定再次绕过循环。（即，您可以只使用while这些前瞻作为条件。）然后对于每次迭代，您只需将构造的子树附加为当前父级的子级。那么，在您的情况下，A将获得几个直系B子女。

现在，据我了解，您正在构建一个解析器生成器，并且通过计划 BNF 遵循标准过程可能是最简单的。但是，这不是真正的问题。毕竟，迭代和递归之间没有实质性区别。您只需要有一类“辅助规则”，它不会引入新的 AST 节点，而是将它们的结果附加到触发它们的非终结符的节点上。因此，当将重复变为X -> BX，而不是构造X节点时，您的规则将orX的子列表（无论哪个触发它）扩展为它自己的孩子。你最终还是会有几个孩子，而且看不到节点。AXABX

于 2018-07-27T14:11:13.973 回答