Flex/Bison 语法冲突 解读

|

背景

某项目编译系统关键字， 在lex中被强制识别为某 token，

后来发现， 而此关键字 也会出现在其他语法中， 但是被lex强制识别为了 token， 导致编译失败！

如：
某系统的语法识别， 将文本中的 uint32,int32, uint64, int64, ipv4. ipv6. time, mac 等识别为数据类型，
ipv4 一开始被lex强制定义为某数据的数据解码器，
后期发现在非数据解码器的地方， 需要将 ipv4 作为一种数据类型。
结果就是， ipv4 无法出现在预期的地方， 总是被lex识别为 数据解码器。
类似的 ipv6, time 关键字也是一样的现象。

Bison 冲突

bison 发现了4处 冲突

1
2
3
4
[root@localhost src]# bison -v --report=all -d sdt_grammar.y 
[root@localhost src]# bison -v -d sdt_grammar.y                 # 或者
sdt_grammar.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
[root@localhost src]#

–report=all 可以得到更多信息

xxx.output

打开 sdt_grammar.output
这里看到了完整的 BNF 语法描述

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Grammar

    0 $accept: sdt $end

    1 sdt: mode rule_header payload_matcher rule_action
    2    | mode rule_header payload_matcher '$' rule_body rule_action
    3    | COMMENT_LINE

    4 mode: IDENTIFIER

    5 payload_matcher: %empty
    6                | '#' payload_and_expression

    7 payload_and_expression: payload_match_expression
    8                       | payload_match_expression ',' payload_and_expression

    9 payload_match_expression: payload_expression
   10                         | '!' payload_expression
   11                         | NUMBER ':' payload_expression
   12                         | NUMBER ':' '!' payload_expression
   13                         | IDENTIFIER '=' NUMBER

   14 payload_expression: payload_expression_atomic
   15                   | payload_expression payload_expression_atomic
   16                   | payload_expression payload_expression_atomic_not

   17 payload_expression_atomic_not: '!' IDENTIFIER
   18                              | '!' hex_payload

   19 payload_expression_atomic: IDENTIFIER
   20                          | hex_payload

   21 hex_payload: HEX_TEXT

   22 rule_body: expression ';'
   23          | logical_and_expression ';'

   24 rule_action: %empty
   25            | rule_action IDENTIFIER LP RP ';'
   26            | rule_action ACTION LP rule_action_args RP ';'
   27            | rule_action ACTION_survive LP action_survive_args RP ';'

   28 rule_action_args: rule_action_arg
   29                 | rule_action_arg ',' rule_action_args

   30 rule_action_arg: NUMBER
   31                | FLOAT
   32                | IDENTIFIER
   33                | QUOTE_TEXT
   34                | dyn_mask_hex

   35 dyn_mask_hex: HEX_TEXT

   36 action_survive_args: IDENTIFIER RELATIONAL_OPERATOR NUMBER
   37                    | action_survive_args ',' IDENTIFIER RELATIONAL_OPERATOR NUMBER

   38 rule_header: IDENTIFIER '@' host_ip ':' port dir host_ip ':' port
   39            | NUMBER '@' host_ip ':' port dir host_ip ':' port
   40            | '*' '@' host_ip ':' port dir host_ip ':' port   

   ...

状态解读:

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
38
39
40
41
42
State 0

    0 $accept: . sdt $end

    COMMENT_LINE  shift, and go to state 1
    IDENTIFIER    shift, and go to state 2

    sdt   go to state 3
    mode  go to state 4
    

State 1

    3 sdt: COMMENT_LINE .

    $default  reduce using rule 3 (sdt)


State 2

    4 mode: IDENTIFIER .

    $default  reduce using rule 4 (mode)


State 3

    0 $accept: sdt . $end

    $end  shift, and go to state 5


State 4

    1 sdt: mode . rule_header payload_matcher rule_action
    2    | mode . rule_header payload_matcher '$' rule_body rule_action

    IDENTIFIER  shift, and go to state 6
    NUMBER      shift, and go to state 7
    '*'         shift, and go to state 8

    rule_header  go to state 9

解读 State 0 :

  1. State 0 表示当前状态没有任何输入的状态,
  2. . 代表在当前输入的 光! 标! 位! 置!
  3. 移进指示: 如果遇到一个 COMMENT_LINE 转移到 [状态1]
  4. 移进指示: 如果遇到一个 IDENTIFIER 转移到 [状态2]
  5. 归约指示: 如果遇到一个 sdt 转移到 [状态3]
  6. 归约指示: 如果遇到一个 mode 转移到 [状态4]

解读 State 1 :

  1. State 1 表示当前已经得到 COMMENT_LINE,
  2. . 代表在当前输入的 光! 标! 位! 置!
  3. 归约指示: 默认 转移到 [语法规则3]

解读 State 2 :

  1. State 2 表示当前已经得到 IDENTIFIER,
  2. . 代表在当前输入的 光! 标! 位! 置!
  3. 归约指示: 默认 转移到 [语法规则4]

冲突

在文件的开始处, 可以看到 有4处状态存在问题

1
2
3
4
State 30 conflicts: 1 shift/reduce
State 45 conflicts: 1 shift/reduce
State 81 conflicts: 1 shift/reduce
State 108 conflicts: 1 shift/reduce

定位到 第1处的冲突

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
State 30

    9 payload_match_expression: payload_expression .  [$end, IDENTIFIER, ACTION_survive, ACTION, '$', ',']
   15 payload_expression: payload_expression . payload_expression_atomic
   16                   | payload_expression . payload_expression_atomic_not
   17 payload_expression_atomic_not: . '!' IDENTIFIER
   18                              | . '!' hex_payload
   19 payload_expression_atomic: . IDENTIFIER
   20                          | . hex_payload
   21 hex_payload: . HEX_TEXT

    IDENTIFIER  shift, and go to state 44
    HEX_TEXT    shift, and go to state 25
    '!'         shift, and go to state 47

    IDENTIFIER  [reduce using rule 9 (payload_match_expression)]
    $default    reduce using rule 9 (payload_match_expression)

    payload_expression_atomic_not  go to state 48
    payload_expression_atomic      go to state 49
    hex_payload                    go to state 32

解读 State 30 :

  1. State 30 表示当前已经得到 payload_expression,

  2. .代表在当前输入的 光! 标! 位! 置!

  3. 移进指示: 如果遇到一个 IDENTIFIER 转移到 [状态44]

  4. 移进指示: 如果遇到一个 HEX_TEXT 转移到 [状态25]

  5. 移进指示: 如果遇到一个 ‘!’ 转移到 [状态47]

  6. 归约指示: 如果遇到一个 IDENTIFIER 转移到 [语法规则9]

  7. 归约指示: 默认什么也没有 转移到 [语法规则9]

  8. 归约指示: 如果遇到一个 payload_expression_atomic_not 转移到 [语法规则48]

  9. 归约指示: 如果遇到一个 payload_expression_atomic 转移到 [语法规则49]

  10. 归约指示: 如果遇到一个 hex_payload 转移到 [语法规则32]

冲突原因:

在 State 30 , 位于已经得到 payload_expression的状态,
再输入一个 IDENTIFIER 会得到 歧义.
此处的 IDENTIFIER 对应着两个 转移,

一个 是 payload_match_expression 的向下移进模式 payload_expression_atomic 内的 IDENTIFIER

1
2
3
4
5
9 payload_match_expression: payload_expression          向下

14 payload_expression: payload_expression_atomic        向下

19 payload_expression_atomic: IDENTIFIER                此处

注意: 这里是 payload_match_expression 向内展开, 最终得到依然是 payload_match_expression.

一个 是 payload_match_expression 的向上归约模式 payload_expression_atomic 内的 IDENTIFIER

1
2
3
4
5
6
7
8
9
10
11
12
1 sdt: mode rule_header payload_matcher rule_action # 向上 邻接 rule_action

5 payload_matcher: %empty                           # 向上
6                | '#' payload_and_expression

7 payload_and_expression: payload_match_expression  # 向上

9 payload_match_expression: payload_expression      # 向上


24 rule_action: %empty                              # rule_action内部存在 IDENTIFIER 可以匹配 -- 冲突
25            | rule_action IDENTIFIER LP RP ';'

注意: 这里是 payload_match_expression 内上收缩, 最终转换为 payload_matcher.
在 payload_matcher 后面的 rule_action,
rule_action 内展开 会出现一个需要 IDENTIFIER的模式.

冲突本质:

在 State 30 : 位于已经得到 payload_expression 的状态,
payload_expression . 输入光标处于 payload_expression 模式后面,
如果下一个 token 是 IDENTIFIER, 存在二义性, 既可以向下移进， 又可以向上规约。
bison 发出冲突警告！

IDENTIFIER 的 移入/归约冲突

解决:

IDENTIFIER 的 移进/规约 只能二选一，
要么 保留 IDENTIFIER 的 移进模式。
要么 保留 IDENTIFIER 的 规约模式。

参考2

1
2
3
4
5
6
7
8
9
10
11
12
State 13

    1 sdt: MODE rule_header payload_matcher . rule_body_pattern rule_action_pattern CR
   23 rule_body_pattern: . %empty  [CR, 'C', 'A', 'B']
   24                  | . 'C' rule_body

    'C'  shift, and go to state 34

    'C'       [reduce using rule 23 (rule_body_pattern)]
    $default  reduce using rule 23 (rule_body_pattern)

    rule_body_pattern  go to state 35

%empty [CR, ‘C’, ‘A’, ‘B’] 代表 后面的可选 token 是 CR, ‘C’, ‘A’, ‘B’
在 State 13 光标位于 '.'时，
当出现 ‘C’ 是应该 shift， 还是 reduce ?

参考3

1
2
3
4
5
6
7
8
9
10
11
12
State 13

    1 sdt: MODE rule_header payload_matcher . rule_body_pattern rule_action_pattern
   23 rule_body_pattern: . %empty  [$end, 'C', 'A', 'B']
   24                  | . 'C' rule_body

    'C'  shift, and go to state 34

    'C'       [reduce using rule 23 (rule_body_pattern)]
    $default  reduce using rule 23 (rule_body_pattern)

    rule_body_pattern  go to state 35

%empty [$end, ‘C’, ‘A’, ‘B’] 代表 后面的可选 token 是 $end, ‘C’, ‘A’, ‘B’
在 State 13 光标位于 '.'时，
当出现 ‘C’ 是应该 shift， 还是 reduce ?