parsing - 基于表的 LL 解析器可以在没有右递归的情况下处理重复吗？

Question

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

A = B*;

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

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

Answer 1

语法

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

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

此文法产生终端字符串 b的任何长度。

LL(1) 表

要构建表，我们需要生成第一个和后续集合 ( constructing an LL(1) parsing table )。

第一套
First(α)是从任何文法符号串 α 派生的串开始的终结符集.

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

跟随集
Follow(A)是一组终端 a 可以
立即出现在非终结符的右侧 A .

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

table

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

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

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

解析堆栈顶部的终端:

匹配输入符号:pop stack，前进到下一个输入符号

不匹配:解析错误

解析堆栈顶部的非终结符:

解析表包含生产:将生产应用于堆栈

单元格为空:解析错误

$在解析堆栈的顶部:

$是输入符号:接受输入

$不是输入符号:解析错误

样本解析

让我们分析输入 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将是: