基于表的LL解析器可以处理没有右递归的重复吗？
chb*_*er0 6 parsing parser-generator ll-grammar
我理解LL递归下降解析器如何处理这种形式的规则:
A = B*;
根据前瞻标记是否与第一组B中的终端匹配,使用一个简单的循环检查是否继续循环.但是,我对基于表的LL解析器感到好奇:这种形式的规则如何在那里工作？据我所知,在一个中处理重复的唯一方法是通过右递归,但是在不需要右关联解析树的情况下会混淆相关性.
我想知道,因为我正在尝试编写一个LL(1)基于表的解析器生成器,我不知道如何在不改变预期的解析树形状的情况下处理这样的情况.
语法
\n\n让我们将 EBNF 语法扩展为简单的 BNF 并假设它b是一个终端并且<e>是一个空字符串：
A -> X\nX -> BX\nX -> <e>\nB -> b\n该语法生成b任意长度的终结符字符串。
LL(1) 表
\n\n为了构建该表，我们需要生成第一个和后续集合（构建 LL(1) 解析表）。
\n\n第一组
\n\nFirst(\xce\xb1)是从任何语法符号字符串派生的字符串开始的终结符集合\xce\xb1。
First(A) : b, <e>\nFirst(X) : b, <e>\nFirst(B) : b\n跟随集
\n\nFollow(A)是一组可以直接出现在非终结符右侧的终结符 a A。
Follow(A) : $\nFollow(X) : $\nFollow(B) : b$\n桌子
\n\n$我们现在可以根据输入标记的结尾来构建表格。
+---+---------+----------+\n| | b | $ |\n+---+---------+----------+\n| A | A -> X | A -> X |\n| X | X -> BX | X -> <e> |\n| B | B -> b | |\n+---+---------+----------+\n解析器的操作始终取决于解析堆栈的顶部和下一个输入符号。
\n\n- \n
- 解析堆栈顶部的终端:\n\n
- \n
- 匹配输入符号：弹出堆栈，前进到下一个输入符号 \n
- 不匹配：解析错误 \n
\n - 解析堆栈顶部的非终结符:\n\n
- \n
- 解析表包含产生式：将产生式应用于堆栈 \n
- 单元格为空：解析错误 \n
\n $在解析堆栈的顶部:\n\n- \n
$是输入符号：接受输入 \n$不是输入符号：解析错误 \n
\n
示例解析
\n\n让我们分析一下输入bb。初始解析堆栈包含开始符号和结束标记A $。
+-------+-------+-----------+\n| Stack | Input | Action |\n+-------+-------+-----------+\n| A $ | bb$ | A -> X |\n| X $ | bb$ | X -> BX |\n| B X $ | bb$ | B -> b |\n| b X $ | bb$ | consume b |\n| X $ | b$ | X -> BX |\n| B X $ | b$ | B -> b |\n| b X $ | b$ | consume b |\n| X $ | $ | X -> <e> |\n| $ | $ | accept |\n+-------+-------+-----------+\n结论
\n\nA = B*正如您所看到的，可以毫无问题地解析表单的规则。输入的结果具体解析树bb将是：
- 这个答案使用标准的右递归过程。问题在于避免右递归以及由此产生的 AST 与 EBNF 不匹配。 (2认同)