Shift/Reduce C 变体语法冲突
Shift/Reduce conflict on C variation grammar
我正在为类似 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 ';'
问题是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
在第三个标记之前看起来相同并不重要。
真正的问题是很难弄清楚空的类型。
我正在为类似 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 ';'
问题是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
在第三个标记之前看起来相同并不重要。
真正的问题是很难弄清楚空的类型。