1

来自Stephen C. Johnson 的 Yacc 介绍：

使用正确的递归规则，例如

    seq     :       item
            |       item  seq
            ;

解析器会大一点，从右到左可以看到和减少项目。更严重的是，如果读取很长的序列，解析器中的内部堆栈将面临溢出的危险。因此，用户应该在合理的地方使用左递归。

我知道 Yacc 会生成 LR 解析器，所以我尝试手动解析一些简单的右递归语法。到目前为止，我看不到问题所在。任何人都可以举一个例子来证明这些问题吗？

4

2 回答 2

2

解析器大小不是一个严重的问题（大多数时候）。

运行时堆栈大小可能是一个问题。麻烦的是，右递归规则意味着直到解析器到达序列末尾才能减少堆栈，而使用左递归规则，每次语法遇到一个seq item，它可以减少堆栈上的项目数.

传统上，令牌堆栈是固定的并且大小有限。因此，一个右递归规则，例如要处理的规则：

IF <cond> THEN
    <stmt-list>
ELSIF <cond> THEN
    <stmt-list>
ELSIF <cond> THEN
    <stmt-list>
ELSE
    <stmt-list>
ENDIF

将限制语法可以接受的 ELIF 子句链中的术语数量。

假设语法：

if_stmt: if_clause opt_elif_clause_list opt_else_clause ENDIF
    ;
if_clause: IF condition THEN stmt_list
    ;
opt_elif_clause_list: /* Nothing */
    | elif_clause opt_elif_clause_list  /* RR */
    ;
elif_clause: ELIF condition THEN stmt_list 
    ;
opt_else_clause: /* Nothing */
    |   ELSE stmt_list
    ;
stmt_list: stmt
    | stmt_list stmt       /* LR */
    ;

我似乎记得很久以前（十年或更久以前）对此进行过一些测试，而我当时使用的 Yacc 结合语言语法，类似于上面的，意味着大约 300 ELIF 子句，解析器停止（我认为它在控制下停止，认识到它已经用完了空间，而不是因为空间耗尽而崩溃）。

于 2013-10-22T19:20:19.513 回答
2

我完全不确定他为什么说正确的递归解析器会更大——一般来说，它的状态机中需要的状态会少一个（如果有的话应该让它更小），但真正的问题是正确的递归语法需要无限的堆栈空间，而左递归语法需要常量空间（O(n) 空间 vs O(1) 空间）。

现在 O(n) vs O(1) 可能听起来很重要，但取决于你在做什么，它可能并不重要。特别是，如果您将整个输入读入内存以进行处理，则 O(n) 空间完全压倒了左右递归的 O(n) 与 O(1) 区别。如果您使用的是仍然具有固定解析器堆栈的特别旧版本的 yacc，这可能会出现问题，但最近版本的 yacc（伯克利 yacc，野牛）会根据需要自动扩展其解析堆栈，因此唯一的限制是可用的记忆。

于 2013-10-22T23:13:33.820 回答