编译器设计 YACC BNF语法中 允许字段为空 的冲突问题

|

终结符说明:
数字 NUMBER
标识符 INDENTIFI
( LP
) RP
{ LC
} RC

功能需求：
args_list 是函数的参数列表，
实际用途中，可能有多个参数， 可能有1个参数，可能没有参数。
为了兼容上述情景，设计 args_list 的语法为下：
1:空，
2:单字符，
3:左边为1与2组合，右边单字符.

BNF 描述如下：

1
2
3
4
args_list       :
                | INDENTIFI
                | args_list INDENTIFI
                ;

问题描述:
YACC 解释时 有冲突！

YACC 文件内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
chunli@ubuntu:~/lab/yacc/$ cat example.y
%{
#include <stdio.h>

%}

%token NUMBER INDENTIFI LP RP LC RC

%%

function_args   :INDENTIFI LP args_list RP
                {
                    // 函数的名形式， 形如下:
                    // foo(int a, double b)
                    // foo(const char *str)
                    // foo(float)
                    // foo()
                }
                ;

args_list       :
                {
                    // 允许参数匹配空参数
                }
                | INDENTIFI
                {
                    // 形如 int
                }
                | args_list INDENTIFI
                {
                    // ... char
                }
                ;


%%
chunli@ubuntu:~/lab/yacc/$

YACC 分析结果：
哦嚯?! YACC 有警告 …

1
2
3
chunli@ubuntu:~/lab/yacc/$ yacc -v example.y
example.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
chunli@ubuntu:~/lab/yacc/$

YACC 异常分析
y.output 是 yacc 输出的调试信息文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
chunli@ubuntu:~/lab/yacc/$ vim y.output

State 3 conflicts: 1 shift/reduce


Grammar

    0 $accept: function_args $end

    1 function_args: INDENTIFI LP args_list RP

    2 args_list: %empty
    3          | INDENTIFI
    4          | args_list INDENTIFI

...省略

State 3

    1 function_args: INDENTIFI LP . args_list RP

    INDENTIFI  shift, and go to state 5

    INDENTIFI  [reduce using rule 2 (args_list)]
    $default   reduce using rule 2 (args_list)

    args_list  go to state 6

分析：

$accept 代表当前输入的标记
$default 代表 向前看时下一个标记
$end 代表结束标记

可以看到 y.output文件头直接报告 状态3 存在 1 个 移进/规约 的 冲突

来看看 是什么地方导致的 shift/reduce conflicts ?

在 State 3 中

当遇到 INDENTIFI 标记，规约为 规则2(args_list)
当遇到 无论什么 标记，规约为 规则2(args_list)

再看看看 rule 2:
2 args_list: %empty

当遇到 INDENTIFI时， 要么向上规约为args_list， 要么向下移进。
那么到底是要 shift 还是 reduce呢 ？

改正之后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
chunli@ubuntu:~/lab/yacc/$ cat example.y
%{
#include <stdio.h>

%}

%token NUMBER INDENTIFI LP RP LC RC

%%
function_args   :INDENTIFI LP args_list RP
                {
                    // 函数的名形式， 形如下:
                    // foo(int a, double b)
                    // foo(const char *str)
                    // foo(float)
                    // foo()
                }
                ;

args_list       :
                {
                    // 允许参数匹配空参数
                }
                | args_list INDENTIFI
                {
                    // ... char
                }
                ;
%%
chunli@ubuntu:~/lab/yacc/$ yacc -v example.y
chunli@ubuntu:~/lab/yacc/$

将 args_list中的规则删除一部分， 可以达到 上述功能需求。
改正之后的 args_list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
args_list       :
                {
                    // 允许参数匹配空参数
                    // foo 为 function_的名字
                    // 匹配 foo()

                }
                | args_list INDENTIFI
                {
                    // foo 为 function_的名字
                    // 匹配 foo(int)
                    // 匹配 foo(int a)
                    // 匹配 foo(const int a)
                }
                ;

1. 支持参数为空，如 foo()
2. 支持参数1个， 如 foo(int)
2. 支持参数2个， 如 foo(int a)
2. 支持参数3个， 如 foo(const int a)