由于前瞻标记限制而转移/减少 yacc 中的冲突？

Question

我一直在尝试解决看似简单的转移/减少冲突，但无济于事。当然，如果我忽略冲突，解析器就可以正常工作，但如果我重新组织规则，我会感觉更安全。在这里，我将相对复杂的语法简化为单个冲突：

statement_list
  : statement_list statement 
  | 
  ;

statement
  : lvalue '=' expression
  | function
  ;

lvalue
  : IDENTIFIER
  | '(' expression ')'
  ;

expression
  : lvalue
  | function
  ;

function
  : IDENTIFIER '(' ')'
  ;

通过 yacc 中的详细选项，我得到了描述具有上述冲突的状态的输出文件：

state 2

    lvalue  ->  IDENTIFIER .   (rule 5)
    function  ->  IDENTIFIER . '(' ')'   (rule 9)

    '('  shift, and go to state 7

    '('  [reduce using rule 5 (lvalue)]
    $default reduce using rule 5 (lvalue)

感谢您的帮助。

Answer 1

问题在于，这需要 2 个令牌前瞻才能知道何时到达语句末尾。如果您有以下形式的输入：

ID = ID ( ID ) = ID

在解析器移动第二个 ID 之后（先行是 (），它不知道这是否是第一个语句的结尾（( ，这对于上面的示例输入来说是错误的。

是第二个语句的开头），或者这是一个函数，因此它会转移（继续解析函数），如果您扩展 function 允许括号内的参数和表达式允许实际表达式，事情会变得更糟，因为所需的前瞻是无限的——解析器需要一直到达第二个= 来确定这不是函数调用。

这里的基本问题是没有辅助标点符号来帮助解析器找到语句的结尾，因为作为有效语句开头的文本也可以出现在中间。对于一个有效的语句，找到语句边界是很困难的。