1

我有以下 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 无法决定是将下一个符号移到堆栈上还是使用给定规则减少堆栈。

  1. 我的语法有歧义吗？

  2. 规则“trailed: trailed arglist”和“statement: NAME arglist COLON expression SEMICOLON”之间的决定不应该没有冲突，因为前者从来没有冒号，而后者总是有？

  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

正如建议的那样没有帮助。与 active的第二条规则仍然存在冲突statement，并且一旦注释掉该规则，就不会给出任何冲突。

4

3 回答 3

2

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

要解决此问题，您需要重构语法，这样在您到达COLON. 使用此语法，您可以通过将trailed规则重构为始终需要至少一个 arglist 并制作NAME没有arglist单独expression规则的 a 来做到这一点：

trailed:
    NAME arglist
    | trailed arglist;

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

现在，当您获得输入时NAME OPAREN ...，还不需要减少任何内容——您只需转换到匹配 an 的规则，arglist并且在匹配 the 之后arglist，您可以看到下一个标记并决定这是函数调用还是函数定义。

于 2014-02-02T21:55:16.350 回答
1

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

简化的语法文件

%token OPAREN CPAREN 名称加逗号分号冒号

%%
程序：
    | 程序声明；

参数列表：
    OPAREN CPAREN
    | OPAREN 表达式列表 CPAREN;

尾随：     
    姓名
    | 尾随 arglist；

表达：
    尾随
    | 表达式 PLUS 尾随；

表达式列表：
    表达      
    | 表达式列表 COMMA 表达式；

陈述：     
    表达式分号
    |NAME arglist COLON 表达式 SEMICOLON;

给出以下报告：

状态 3 冲突：1 班次/减少

……

状态 3

    3 参数列表：. OPAREN CPAREN
    4 | . OPAREN 表达式列表 CPAREN
    5 尾随： NAME 。[OPAREN、PLUS、分号]
   12 语句：名称。arglist 冒号表达式 分号

    OPAREN 换档，进入状态 7

    OPAREN [使用规则 5 减少（尾随）]
    $default 使用规则 5 减少（尾随）

    arglist 进入状态 8

在报告的开头有导致错误的解析器状态，然后你可以看到解析状态的详细信息。这个文件也很有趣，因为它实际上解释了解析器在每个步骤中所做的事情。

冲突发生在

语句：NAME arglist COLON 表达式 SEMICOLON；

和

语句：表达式；
表达式：尾随；
尾随：姓名| 尾参数列表；
于 2014-02-02T15:26:01.197 回答
0

给定源语法：

%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，但其中的描述与MichaelMoser在他的回答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 时，它无法推断它是在一个trailed后面跟着一个的arglist还是在statement一个名字后面跟着一个的arglist。在它到达冒号之前，它无法确定差异，因为距离太远，无法通过一个前瞻标记来确定。

这使得纯 Yacc 无法解析语法，因为 Yacc 只能向前看一个标记。（我不确定这是否使它模棱两可或其他原因——“在 Yacc 中不起作用”涵盖了这种情况。Bison 提供的 GLR 语法可能会有所帮助。）

于 2014-02-02T19:44:55.027 回答