Bison reduce/reduce 语法冲突

Question

我正在用 bison 构建语法，我有一个 r/r 冲突（我知道它在哪里），但我不知道如何解决它。我将不胜感激任何可能的帮助。

我的代码中包含冲突的部分是：

orismos2: %empty
|orismos orismos2
|error {yyerrok;yyclearin;};

orismos: orismosmetablitwn
|orismossunartisis
|prwtotuposunartisis;

orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON ;

tuposdedomenwn: INT
|BOOL
|STRING;

listametablitwn: ID nid ;

nid: %empty
|pid nid
|error {yyerrok;yyclearin;};

pid: COMMA ID ;

orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn;

prwtotuposunartisis: kefalidasunartisis SEMICOLON;

kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET;

typos_synartisis: INT
|BOOL
|VOID;

我已经制作了一个输出文件，我可以在其中看到所有的冲突。

包含冲突的文件部分是：

State 21 conflicts: 1 reduce/reduce
State 22 conflicts: 1 reduce/reduce


Grammar

   10 orismos2: %empty
   11         | orismos orismos2
   12         | error

   13 orismos: orismosmetablitwn
   14        | orismossunartisis
   15        | prwtotuposunartisis

   16 orismosmetablitwn: tuposdedomenwn listametablitwn SEMICOLON

   17 tuposdedomenwn: INT
   18               | BOOL
   19               | STRING

   20 listametablitwn: ID nid

   21 nid: %empty
   22    | pid nid
   23    | error

   24 pid: COMMA ID

   25 orismossunartisis: kefalidasunartisis tmimaorismwn tmimaentolwn

   26 prwtotuposunartisis: kefalidasunartisis SEMICOLON

   27 kefalidasunartisis: typos_synartisis ID OPENBRACKET c CLOSEBRACKET

   28 typos_synartisis: INT
   29                 | BOOL
   30                 | VOID


State 21

   17 tuposdedomenwn: INT .
   28 typos_synartisis: INT .

    ID        reduce using rule 17 (tuposdedomenwn)
    ID        [reduce using rule 28 (typos_synartisis)]
    $default  reduce using rule 17 (tuposdedomenwn)


State 22

   18 tuposdedomenwn: BOOL .
   29 typos_synartisis: BOOL .

    ID        reduce using rule 18 (tuposdedomenwn)
    ID        [reduce using rule 29 (typos_synartisis)]
    $default  reduce using rule 18 (tuposdedomenwn)

我真的什么都试过了，但我无法消除冲突...欢迎任何想法或建议！

非常感谢！！

Answer 1

关键在这里：……

orismos → (13) orismosmetablitwn → (16) tuposdedomenwn listametablitwn
orismos → (14) orismossunartisis → (25) kefalidasunartisis … → (27) typos_synartisis …
orismos → (15) prwtotuposunartisis → (26) kefalidasunartisis … → (27) typos_synartisis …

另外：

tuposdedomenwn → NUMBER | BOOL | STRING
listametablitwn → ID …
kefalidasunartisis → typos_synartisis ID …
typos_synartisis → NUMBER | BOOL | VOID

因此，这里是 orismos 的一些推导：

orismos → orismosmetablitwn → tuposdedomenwn listametablitwn → NUMBER ID …
orismos → orismossunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID …
orismos → prwtotuposunartisis → kefalidasunartisis … → typos_synartisis … → NUMBER ID …

假设我们处于可能 orismis 的上下文中，我们刚刚看到 NUMBER，现在正在查看 ID。以上三种推导都是可能的。但是有一个小问题：在第一个中，NUMBER 是从 tuposdedomenwn 派生的，而在后两个中，它是从 typos_synartisis 派生的。在我们对 ID 做任何事情之前，我们需要知道要减少两个推导中的哪一个，但是在我们看到令牌 after 之前我们无法知道这一点ID.

这意味着语法需要两个先行标记，因此 LALR(1) 解析器无法解析它。

最简单的解决方案是将表示类型集的两个非终结符组合起来，创建一个允许所有四种可能性的非终结符：

tuposdedomenwn: NUMBER | BOOL | STRING | VOID

然后您必须稍后进行语义检查，以验证未声明变量 VOID 或未声明函数 STRING。（为什么你的函数不能 return 字符串？这似乎有点局限。）这种接受语言上标然后在 AST 构造期间甚至之后进行语义检查的策略非常普遍；例如，这是在使用变量之前强制声明的唯一方法。

但是如果您不想进行语义检查，您可以通过创建由数据类型和 ID 组成的非终结符来简单地推迟缩减。这将导致类似：

tupodedomenon_kai_metavlites
       : INT ID
       | BOOL ID
       | STRING ID
       | tupodedomenon_kai_metavlites ',' ID

tupo_synartisis_kai_metavliton
       : INT ID
       | BOOL ID
       | VOID ID

orismos: orismosmetablitwn
       | orismossunartisis
       | prwtotuposunartisis

orismosmetablitwn
       : tupodedomenon_kai_metavlites ';'

orismossunartisis
       : kefalidasunartisis tmimaorismwn tmimaentolwn

prwtotuposunartisis
       : kefalidasunartisis ';'

kefalidasunartisis
       : tupo_synartisis_kai_metavliton '(' c ')'

有了这个改变，就没有必要减少 NUMBER（或其他类型）； ID 可以移动，然后根据以下标记执行减少到一种或另一种可能性：作为变量声明，如果以下标记是 ; 或 ,，如果以下标记为 (.

，则作为函数声明

Bison reduce/reduce 语法冲突

Bison reduce/reduce conflict in grammar

compiler-construction

grammar

bison

reduce-reduce-conflict