Shift/Reduce C 变体语法冲突

Question

我正在为类似 C 的语法编写解析器，但我遇到了 shift/reduce 冲突问题：

基本上，语法接受一系列可选的全局变量声明，后跟函数。

我有以下规则：

program: global_list function_list;

type_name : TKINT /* int */
          | TKFLOAT /* float */
          | TKCHAR /* char */

global_list : global_list var_decl ';'
            |
            ;

var_decl : type_name NAME;

function_list : function_list function_def
              |
              ;

function_def : type_name NAME '(' param_list ')' '{' func_body '}' ;

我知道我有问题，因为语法无法决定下一个 type_name NAME 属于 global_list 还是 function_list，默认情况下它期望 global_list

例如：

int var1;

int foo(){}

error: unexpcted '(', expecting ';'

Answer 1

问题是function_def只能出现在function_list之后，这意味着解析器需要减少一个空的function_list（使用产生式function_list → ε ) 才能识别 function_def。此外，它需要仅通过查看空生产之后的令牌来做出该决定。由于该标记（type_name）可以作为 var_decl 或 function_def 的开始，因此解析器无法决定。

即使留下再多一个代币的决定也无济于事；直到第三个令牌才能做出正确的决定。所以你的语法没有歧义，而是LR(3).

不同类型的可能为空列表的序列总是会产生此问题。相比之下，非空列表的序列则不然，因此解决该问题的第一种方法是消除 ε-产生式。

首先，我们扩展顶级定义，明确两个列表都是可选的：

program: global_list function_list;
       | global_list
       | function_list
       |
       ;

然后我们让两种列表类型都非空：

global_list
       : var_decl
       | global_list var_decl
       ;

function_list
       : function_def
       | function_list function_def
       ;

其余语法不变。

type_name : TKINT /* int */
          | TKFLOAT /* float */
          | TKCHAR /* char */

var_decl : type_name NAME;

function_def : type_name NAME '(' param_list ')' '{' func_body '}' ;

值得注意的是，如果可以穿插声明，就不会出现这个问题。真的有必要在任何函数之前定义所有全局变量吗？如果没有，您可以只使用一个列表类型，这也不会产生冲突：

program: decl_list ;

decl_list:
         | decl_list var_decl;
         | decl_list function_def
         ;

这两种解决方案都有效，因为自下而上的解析器可以等到减少产生式结束，以便决定哪个是正确的减少； var_decl 和 function_def 在第三个标记之前看起来相同并不重要。

真正的问题是很难弄清楚空的类型。

Shift/Reduce C 变体语法冲突

Shift/Reduce conflict on C variation grammar

parsing

bison

yacc