转移/减少与模糊语法的冲突

Question

由于yacc报告了6次转移/减少冲突，我已经暂时停留在一些含糊不清的语法上一段时间了。我查看了y.output文件并尝试了解如何查看状态并找出解决模糊语法的方法，但无济于事。我合理地坚持我应该如何解决这些问题。我已经看了很多关于堆栈溢出的问题，看看其他人的解释是否会帮助我解决我的问题，但这对我没有多大帮助。为了记录，我不能使用任何优先级定义指令，如%left来解决解析冲突。

有人能够通过指导我如何改变语法来解决转变/减少冲突来帮助我吗？也许通过尝试解决其中一个问题并向我展示其背后的思考过程？我知道语法很长很重，我提前为此道歉。如果有人愿意腾出空闲时间，我将不胜感激，但我意识到我可能无法拥有它。

无论如何，这是我的语法问题（它是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中具有转换/减少冲突的相关状态。

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)

我们终于得到它了。我再次为这个语法的长度和转换/减少冲突的数量道歉。我似乎无法理解如何通过改变有问题的语法来解决它们。如果没有人有时间浏览如此庞大的帖子，我会理解，任何帮助都会得到充分的体会。如果有人需要更多信息，请不要犹豫。

Answer 1

基本的问题是，当解析method_decl体时，它无法分辨var_decl_list结束和statement_list开始的位置。这是因为当前瞻是ID时，它不知道这是否是另一个var_decl的开始或第一个statement的开始，并且它需要在它开始处理statement_list之前减少空语句。

您可以通过多种方式处理此问题：

• 让词法分析器为类型ID和其他ID返回不同的标记 - 这样，差异将告诉解析器下一个。
• 在语句列表的开头不需要空语句。将语法更改为：

  statement_list: statement | statement_list statement ;
  opt_statement_list: statement_list | %empty ;

  并在opt_statement_list规则中使用method_decl。这解决了在开始解析语句之前必须减少空statement_list的问题。当您使用多个变体替换规则时，这是一个称为“解构”语法的过程。它使语法更复杂，在这种情况下，不解决问题，它只是移动它;然后你会看到statement: ID . index和type: ID在[前瞻之间的转移/减少冲突。这个问题也可以通过解构来解决，但更难。

---

因此，这提出了通过不重构来解决shift-reduce冲突的一般想法。基本思想是摆脱导致减少一半减少冲突的规则，将其替换为在上下文中更受限制的规则，因此不要触发冲突。上面的例子可以通过“用一个或多个递归重复和一个可选规则替换一个0或更多的递归重复”来轻松解决。如果以下上下文意味着您可以轻松解决0-case应该合法的情况（仅在下一个令牌是}的情况下），这适用于重复的epsilon规则的shift-reduce冲突。

第二次冲突更加艰难。这里的冲突是在前瞻是type: ID时减少[。所以我们需要复制类型规则，直到没有必要。就像是：

type: simpleType | arrayType ;
simpleType: INT | BOOLEAN | ID ;
arrayType: INT '[' ']' | BOOLEAN '[' ']' | ID '[' ']'
         | arrayType '[' ']' ;

用“1或更多”替换“0或更多重复的'[' ']'后缀”，并且出于类似的原因工作（将减少推迟到看到'[' ']'之后，而不是之前要求它。）关键是simpleType: ID规则永远不需要当前瞻是'['时减少，因为它仅在其他情况下有效。