由于超前令牌限制,转换/减少yacc中的冲突？

Question

我一直试图解决一个看似简单的转变/减少冲突,但无济于事.当然,如果我忽略冲突,解析器工作正常,但如果我重新组织我的规则,我会觉得更安全.在这里,我简化了一个相对复杂的语法到单一冲突:

statement_list
  : statement_list statement 
  | 
  ;

statement
  : lvalue '=' expression
  | function
  ;

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

expression
  : lvalue
  | function
  ;

function
  : IDENTIFIER '(' ')'
  ;

使用yacc中的verbose选项,我得到此输出文件描述具有上述冲突的状态:

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(lookahead是()之后,它不知道这是否是第一个语句的结尾((是第二个语句的开头),或者这是一个函数.所以它转移(继续解析函数),这与上面的示例输入有关.

如果扩展function为允许括号内的参数并expression允许实际表达式,事情会变得更糟,因为前瞻性要求是无限的 - 解析器需要一直到第二个=以确定这不是函数调用.

这里的基本问题是没有帮助标点符号来帮助解析器找到语句的结尾.由于作为有效语句开头的文本也可以出现在有效语句的中间,因此查找语句边界很难.