YACC 移位/减少冲突:函数调用与函数定义

Question

我有以下 lex 定义：

[a-zA-Z][a-zA-Z0-9_]*       return NAME;
,              return COMMA;
:              return COLON;
;              return SEMICOLON;
(              return OPAREN;
)              return CPAREN;
+              return PLUS;

以及以下 yacc 生产规则：

program: 
| program statement;
arglist:
OPAREN CPAREN
| OPAREN expressionlist CPAREN;
trailed:
NAME
| trailed arglist;
expression:
trailed
| expression PLUS trailed;
expressionlist:
expression
| expressionlist COMMA expression;
statement:
expression SEMICOLON
|NAME arglist COLON expression SEMICOLON;

如果我注释掉最后一条规则，一切都编译得很好。与最后一条规则发生冲突：

yacc: 1 shift/reduce conflict.

所以我想，yacc 无法决定是将下一个符号移动到堆栈上还是使用 give 规则减少堆栈。

1. 我的语法模棱两可吗？

规则"尾随：尾随的arglist">

2. 和"语句：名称arglist冒号表达式分号"之间的决定不应该没有冲突，因为前者从来没有冒号，而后者总是有？

3. 这与前瞻缓冲区的大小有关吗？

4. 如何修复此语法以将"a (b) ();"和"a (b， c)： b + c;"解析为有效语句？

5. 如何以更详细的方式回溯冲突？

----编辑

关于迈克尔·莫泽的回答：

改变

arglist:
OPAREN CPAREN
| OPAREN expressionlist CPAREN;
expressionlist:
expression
| expressionlist COMMA expression;

自

arglist: OPAREN expressionlist CPAREN;
expressionlist:
| expressionlist COMMA expression; //this now allows for expression lists like ,a,b but NVM

正如建议的那样无济于事。冲突仍然与第二条规则一起出现，statement活跃，一旦注释该规则，就不会产生冲突。

Answer 1

正如其他人所指出的，问题在于您需要多个前瞻标记来区分函数定义和函数调用。 所写语法的问题在于，它需要在减少规则trailed: NAME和在看到NAME后statement: NAME arglist COLON expression SEMICOLON在OPAREN前瞻时切换以匹配规则之间做出决定。 但是它直到看到arglist之后才能决定，看看它后面是否有COLON(这就是这两种情况的区别)。

要解决此问题，您需要重构语法，以便在您到达COLON之前无需减少仅存在于一个替代方案上的任何内容。 使用此语法，您可以通过重构trailed规则以始终要求至少一个 arglist 来实现此目的，并使没有arglistNAME成为单独的expression规则：

trailed:
NAME arglist
| trailed arglist;
expression:
NAME
| trailed
| expression PLUS NAME
| expression PLUS trailed;

现在，当您获得输入NAME OPAREN ...时，还不需要减少任何东西 - 您只需切换到与arglist匹配的规则，并且在匹配arglist后，您可以看到下一个令牌并决定这是函数调用还是函数定义。

Answer 2

如果要调试shift/reduce错误，则将--report=all --report-file=pars.report添加到bison命令行，生成的pars.report文件将使您清楚。

简化的语法文件

%令牌 OPAREN CPAREN 名称加逗号分号冒号 %% 程序： |计划声明; 参数列表： 欧帕伦 |OPAREN expressionlist CPAREN; 落后：     名字 |尾随的arglist; 表达： 落后 |表达式加尾随; 表达式列表： 表达      |表达式列表逗号表达式; 陈述：     表达式分号 |名称参数列表冒号表达式分号;

给出以下报告：

状态 3 冲突：1 个移位/减少 .... 状态 3 3 参数列表： .欧帕伦 4 | .OPAREN expressionlist CPAREN 5 尾随：名称。 [欧帕伦，加号，分号]  12 语句：名称。arglist 冒号表达式分号 OPAREN 移位，并转到状态 7 OPAREN [使用规则 5(尾随)减少] $default使用规则 5(尾随)减少 arglist 转到状态 8

在报告开始时，有导致错误的解析器状态，然后向下，您可以看到解析状态的详细信息。这个文件也很有趣，因为它实际上解释了解析器在每个步骤中正在做什么。

冲突是

语句：名称参数列表冒号表达式分号;

和

语句：表达式; 表达式 ： 尾随; 尾随 ： 名称 |尾巴阿格利斯特;

Answer 3

给定源语法：

%token COLON COMMA CPAREN NAME OPAREN PLUS SEMICOLON
%%
program: 
| program statement
;
arglist:
OPAREN CPAREN
| OPAREN expressionlist CPAREN
;
trailed:
NAME
| trailed arglist
;
expression:
trailed
| expression PLUS trailed
;
expressionlist:
expression
| expressionlist COMMA expression
;
statement:
expression SEMICOLON
| NAME arglist COLON expression SEMICOLON
;

我从bison -v xyz.y那里得到的报告给出了xyz.y: conflicts: 1 shift/reduce，但xyz.output中的描述与迈克尔·莫泽在他的回答中报告的有些不同。

State 3 conflicts: 1 shift/reduce
…
state 3
5 trailed: NAME .
12 statement: NAME . arglist COLON expression SEMICOLON
OPAREN  shift, and go to state 7
OPAREN    [reduce using rule 5 (trailed)]
$default  reduce using rule 5 (trailed)
arglist  go to state 8

这意味着当语法读取 NAME 并获取 OPAREN 时，它无法推断它是在后跟arglist的trailed中，还是在 NAME 后跟arglist的statement中。 在到达冒号之前，它将无法确定差异，而结肠太远了，无法通过一个展望标记来确定。

这使得语法无法用普通 Yacc 解析，因为 Yacc 只能向前看一个令牌。 (我不确定这是否使它模棱两可或其他原因 - "在Yacc中不起作用"涵盖了这种情况。 Bison提供了可能会有所帮助的GLR语法。