解决 shift/reduce 表达式语法冲突

Question

我是 bison 的新手，我正在尝试制作语法解析表达式。我现在面临 shift/reduce 冲突，我无法解决。

语法如下：

%left "[" "("
%left "+"

%%

expression_list : expression_list "," expression
                | expression 
                | /*empty*/
                ;


expression :  "(" expression ")"  
           |  STRING_LITERAL      
           |  INTEGER_LITERAL           
           |  DOUBLE_LITERAL
           |  expression "(" expression_list ")" /*function call*/
           |  expression "[" expression "]" /*index access*/
           |  expression "+" expression         
           ;

这是我的语法，但我面临 shift/reduce 与这两个规则 "(" expression ")" 和 expression "(" expression_list ")" 的冲突。我该如何解决这个冲突？

编辑：我知道我可以使用优先级攀升来解决这个问题，但我不想这样做，因为这只是表达式语法的一小部分，表达式语法的大小会使用优先级攀升来爆炸.

Answer 1

所提供的语法中没有shift-reduce冲突，所以我认为它只是完整语法的摘录。特别是，如果真正的语法包括：

，恰恰会出现提到的shift/reduce冲突。

%start program
%%
program: %empty
       | program expression

在那种情况下，您将运行陷入歧义，因为给定，例如 a(b)，解析器无法判断它是单个调用表达式还是两个连续的表达式，首先是单个变量，第二个是带括号的表达式。为了避免这个问题，你需要有一些分隔表达式（语句）的标记。

还有一些其他问题：

expression_list : expression_list "," expression
                | expression 
                | /*empty*/
                ;

这允许表达式列表为 ,foo（如 f(,foo)），这可能是不可取的。更好的是

arguments: %empty
         | expr_list
expr_list: expr
         | expr_list ',' expr

并且优先级可能是倒过来的。通常人们希望像 call 和 index 这样的后缀运算符比算术运算符绑定得更紧密，所以它们应该放在最后。否则a+b(7)就是(a+b)(7)，这是非常规的

解决 shift/reduce 表达式语法冲突

Solving shift/reduce conflict in expression grammar

parsing

bison

shift-reduce-conflict