Shift/reduce 与歧义语法冲突
Shift/reduce conflict with ambiguous grammar
由于 yacc 报告 6 shift/reduce 冲突，我已经被一些模棱两可的语法困扰了一段时间。我查看了 y.output 文件并试图了解如何查看状态并找出如何修复歧义语法但无济于事。我理所当然地坚持我应该如何解决这些问题。我看了很多关于堆栈溢出的问题，看看其他人的解释是否能帮助我解决我的问题，但这对我也没有太大帮助。作为记录，我不能使用任何优先级定义指令，例如 %left 来解决解析冲突。
有人可以指导我如何更改语法来解决 shift/reduce 冲突，从而帮助我吗？也许通过尝试解决其中一个问题并向我展示其背后的思考过程？我知道语法很长很重，为此我提前道歉。如果有人愿意为此腾出空闲时间，将不胜感激，但我意识到我可能无法做到这一点。
无论如何，这是我的语法问题（它是对 MiniJava 语法的轻微扩展）：
Grammar
0 $accept: program $end
1 program: main_class class_decl_list
2 main_class: CLASS ID '{' PUBLIC STATIC VOID MAIN '(' STRING '[' ']' ID ')' '{' statement '}' '}'
3 class_decl_list: class_decl_list class_decl
4 | %empty
5 class_decl: CLASS ID '{' var_decl_list method_decl_list '}'
6 | CLASS ID EXTENDS ID '{' var_decl_list method_decl_list '}'
7 var_decl_list: var_decl_list var_decl
8 | %empty
9 method_decl_list: method_decl_list method_decl
10 | %empty
11 var_decl: type ID ';'
12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list statement_list RETURN exp ';' '}'
13 formal_list: type ID formal_rest_list
14 | %empty
15 formal_rest_list: formal_rest_list formal_rest
16 | %empty
17 formal_rest: ',' type ID
18 type: INT
19 | BOOLEAN
20 | ID
21 | type '[' ']'
22 statement: '{' statement_list '}'
23 | IF '(' exp ')' statement ELSE statement
24 | WHILE '(' exp ')' statement
25 | SOUT '(' exp ')' ';'
26 | SOUT '(' STRING_LITERAL ')' ';'
27 | ID '=' exp ';'
28 | ID index '=' exp ';'
29 statement_list: statement_list statement
30 | %empty
31 index: '[' exp ']'
32 | index '[' exp ']'
33 exp: exp OP exp
34 | '!' exp
35 | '+' exp
36 | '-' exp
37 | '(' exp ')'
38 | ID index
39 | ID '.' LENGTH
40 | ID index '.' LENGTH
41 | INTEGER_LITERAL
42 | TRUE
43 | FALSE
44 | object
45 | object '.' ID '(' exp_list ')'
46 object: ID
47 | THIS
48 | NEW ID '(' ')'
49 | NEW type index
50 exp_list: exp exp_rest_list
51 | %empty
52 exp_rest_list: exp_rest_list exp_rest
53 | %empty
54 exp_rest: ',' exp
这里是 y.output 中存在 shift/reduce 冲突的相关状态。
State 58
7 var_decl_list: var_decl_list . var_decl
12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list . statement_list RETURN exp ';' '}'
INT shift, and go to state 20
BOOLEAN shift, and go to state 21
ID shift, and go to state 22
ID [reduce using rule 30 (statement_list)]
$default reduce using rule 30 (statement_list)
var_decl go to state 24
type go to state 25
statement_list go to state 69
State 76
38 exp: ID . index
39 | ID . '.' LENGTH
40 | ID . index '.' LENGTH
46 object: ID .
'[' shift, and go to state 64
'.' shift, and go to state 97
'.' [reduce using rule 46 (object)]
$default reduce using rule 46 (object)
index go to state 98
State 100
33 exp: exp . OP exp
34 | '!' exp .
OP shift, and go to state 103
OP [reduce using rule 34 (exp)]
$default reduce using rule 34 (exp)
State 101
33 exp: exp . OP exp
35 | '+' exp .
OP shift, and go to state 103
OP [reduce using rule 35 (exp)]
$default reduce using rule 35 (exp)
State 102
33 exp: exp . OP exp
36 | '-' exp .
OP shift, and go to state 103
OP [reduce using rule 36 (exp)]
$default reduce using rule 36 (exp)
State 120
33 exp: exp . OP exp
33 | exp OP exp .
OP shift, and go to state 103
OP [reduce using rule 33 (exp)]
$default reduce using rule 33 (exp)
我们已经做到了。对于这个语法的长度和 shift/reduce 冲突的数量，我再次表示歉意。我似乎无法理解如何通过更改相关语法来修复它们。任何帮助将不胜感激，但如果没有人有时间浏览如此庞大的 post，我会理解。如果有人需要更多信息，请随时询问。
基本问题是，在解析 method_decl 正文时，它无法分辨 var_decl_list 在哪里结束，statement_list 在哪里开始。这是因为当lookahead是ID时，它不知道那是另一个var_decl的开始还是第一个statement的开始，它需要减少一个空语句在它开始处理 statement_list.
之前
您可以通过多种方式处理此问题：
为类型 ID 和其他 ID 使用词法分析器 return 不同的标记——这样，差异将告诉解析器下一步是什么。
不需要在语句列表的开头有一个空语句。将语法更改为：
statement_list: statement | statement_list statement ;
opt_statement_list: statement_list | %empty ;
并在 method_decl 规则中使用 opt_statement_list。这解决了在开始解析语句之前必须减少空 statement_list 的问题。这是一个称为 "unfactoring" 语法的过程，因为您正在用多种变体替换规则。它使语法更加复杂，在这种情况下，并不能解决问题，它只是移动它；然后，您会在 [ 前瞻中看到 statement: ID . index 和 type: ID 之间的 shift/reduce 冲突。这个问题也可以通过分解来解决，但是更难。
所以这提出了通过分解来解决 shift-reduce 冲突的一般想法。基本思想是摆脱导致 reduce half 的 shift reduce 冲突的规则，用上下文更受限制的规则代替它，这样就不会触发冲突。上面的例子很容易被"replace a 0-or-more recursive repeat with a 1-or-more recursive repeat and an optional rule"解决。如果以下上下文意味着您可以轻松解决 0-case 应该合法的时间（仅当下一个标记在这种情况下为 } 时），这对于重复的 epsilon 规则的移位减少冲突非常有效。）
第二次冲突比较激烈。这里的冲突是减少 type: ID，而前瞻是 [。所以我们需要复制类型规则，直到没有必要为止。类似于：
type: simpleType | arrayType ;
simpleType: INT | BOOLEAN | ID ;
arrayType: INT '[' ']' | BOOLEAN '[' ']' | ID '[' ']'
| arrayType '[' ']' ;
将“'[' ']' 后缀的 0 次或多次重复”替换为“1 次或多次”，并出于类似原因起作用（将减少推迟到看到 '[' ']' 之后，而不是之前要求它.) 关键是当前瞻是 '[' 时，simpleType: ID 规则永远不需要减少，因为它只在其他上下文中有效。
由于 yacc 报告 6 shift/reduce 冲突，我已经被一些模棱两可的语法困扰了一段时间。我查看了 y.output 文件并试图了解如何查看状态并找出如何修复歧义语法但无济于事。我理所当然地坚持我应该如何解决这些问题。我看了很多关于堆栈溢出的问题，看看其他人的解释是否能帮助我解决我的问题，但这对我也没有太大帮助。作为记录，我不能使用任何优先级定义指令，例如 %left 来解决解析冲突。
有人可以指导我如何更改语法来解决 shift/reduce 冲突，从而帮助我吗？也许通过尝试解决其中一个问题并向我展示其背后的思考过程？我知道语法很长很重，为此我提前道歉。如果有人愿意为此腾出空闲时间，将不胜感激，但我意识到我可能无法做到这一点。
无论如何，这是我的语法问题（它是对 MiniJava 语法的轻微扩展）：
Grammar
0 $accept: program $end
1 program: main_class class_decl_list
2 main_class: CLASS ID '{' PUBLIC STATIC VOID MAIN '(' STRING '[' ']' ID ')' '{' statement '}' '}'
3 class_decl_list: class_decl_list class_decl
4 | %empty
5 class_decl: CLASS ID '{' var_decl_list method_decl_list '}'
6 | CLASS ID EXTENDS ID '{' var_decl_list method_decl_list '}'
7 var_decl_list: var_decl_list var_decl
8 | %empty
9 method_decl_list: method_decl_list method_decl
10 | %empty
11 var_decl: type ID ';'
12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list statement_list RETURN exp ';' '}'
13 formal_list: type ID formal_rest_list
14 | %empty
15 formal_rest_list: formal_rest_list formal_rest
16 | %empty
17 formal_rest: ',' type ID
18 type: INT
19 | BOOLEAN
20 | ID
21 | type '[' ']'
22 statement: '{' statement_list '}'
23 | IF '(' exp ')' statement ELSE statement
24 | WHILE '(' exp ')' statement
25 | SOUT '(' exp ')' ';'
26 | SOUT '(' STRING_LITERAL ')' ';'
27 | ID '=' exp ';'
28 | ID index '=' exp ';'
29 statement_list: statement_list statement
30 | %empty
31 index: '[' exp ']'
32 | index '[' exp ']'
33 exp: exp OP exp
34 | '!' exp
35 | '+' exp
36 | '-' exp
37 | '(' exp ')'
38 | ID index
39 | ID '.' LENGTH
40 | ID index '.' LENGTH
41 | INTEGER_LITERAL
42 | TRUE
43 | FALSE
44 | object
45 | object '.' ID '(' exp_list ')'
46 object: ID
47 | THIS
48 | NEW ID '(' ')'
49 | NEW type index
50 exp_list: exp exp_rest_list
51 | %empty
52 exp_rest_list: exp_rest_list exp_rest
53 | %empty
54 exp_rest: ',' exp
这里是 y.output 中存在 shift/reduce 冲突的相关状态。
State 58
7 var_decl_list: var_decl_list . var_decl
12 method_decl: PUBLIC type ID '(' formal_list ')' '{' var_decl_list . statement_list RETURN exp ';' '}'
INT shift, and go to state 20
BOOLEAN shift, and go to state 21
ID shift, and go to state 22
ID [reduce using rule 30 (statement_list)]
$default reduce using rule 30 (statement_list)
var_decl go to state 24
type go to state 25
statement_list go to state 69
State 76
38 exp: ID . index
39 | ID . '.' LENGTH
40 | ID . index '.' LENGTH
46 object: ID .
'[' shift, and go to state 64
'.' shift, and go to state 97
'.' [reduce using rule 46 (object)]
$default reduce using rule 46 (object)
index go to state 98
State 100
33 exp: exp . OP exp
34 | '!' exp .
OP shift, and go to state 103
OP [reduce using rule 34 (exp)]
$default reduce using rule 34 (exp)
State 101
33 exp: exp . OP exp
35 | '+' exp .
OP shift, and go to state 103
OP [reduce using rule 35 (exp)]
$default reduce using rule 35 (exp)
State 102
33 exp: exp . OP exp
36 | '-' exp .
OP shift, and go to state 103
OP [reduce using rule 36 (exp)]
$default reduce using rule 36 (exp)
State 120
33 exp: exp . OP exp
33 | exp OP exp .
OP shift, and go to state 103
OP [reduce using rule 33 (exp)]
$default reduce using rule 33 (exp)
我们已经做到了。对于这个语法的长度和 shift/reduce 冲突的数量，我再次表示歉意。我似乎无法理解如何通过更改相关语法来修复它们。任何帮助将不胜感激，但如果没有人有时间浏览如此庞大的 post，我会理解。如果有人需要更多信息，请随时询问。
基本问题是，在解析 method_decl 正文时，它无法分辨 var_decl_list 在哪里结束，statement_list 在哪里开始。这是因为当lookahead是ID时，它不知道那是另一个var_decl的开始还是第一个statement的开始，它需要减少一个空语句在它开始处理 statement_list.
您可以通过多种方式处理此问题：
为类型 ID 和其他 ID 使用词法分析器 return 不同的标记——这样，差异将告诉解析器下一步是什么。
不需要在语句列表的开头有一个空语句。将语法更改为：
statement_list: statement | statement_list statement ; opt_statement_list: statement_list | %empty ;并在
method_decl规则中使用opt_statement_list。这解决了在开始解析语句之前必须减少空statement_list的问题。这是一个称为 "unfactoring" 语法的过程，因为您正在用多种变体替换规则。它使语法更加复杂，在这种情况下，并不能解决问题，它只是移动它；然后，您会在[前瞻中看到statement: ID . index和type: ID之间的 shift/reduce 冲突。这个问题也可以通过分解来解决，但是更难。
所以这提出了通过分解来解决 shift-reduce 冲突的一般想法。基本思想是摆脱导致 reduce half 的 shift reduce 冲突的规则，用上下文更受限制的规则代替它，这样就不会触发冲突。上面的例子很容易被"replace a 0-or-more recursive repeat with a 1-or-more recursive repeat and an optional rule"解决。如果以下上下文意味着您可以轻松解决 0-case 应该合法的时间（仅当下一个标记在这种情况下为 } 时），这对于重复的 epsilon 规则的移位减少冲突非常有效。）
第二次冲突比较激烈。这里的冲突是减少 type: ID，而前瞻是 [。所以我们需要复制类型规则，直到没有必要为止。类似于：
type: simpleType | arrayType ;
simpleType: INT | BOOLEAN | ID ;
arrayType: INT '[' ']' | BOOLEAN '[' ']' | ID '[' ']'
| arrayType '[' ']' ;
将“'[' ']' 后缀的 0 次或多次重复”替换为“1 次或多次”，并出于类似原因起作用（将减少推迟到看到 '[' ']' 之后，而不是之前要求它.) 关键是当前瞻是 '[' 时，simpleType: ID 规则永远不需要减少，因为它只在其他上下文中有效。