解决 shift/reduce 个冲突
Solving shift/reduce conflicts
我正在使用 PLY to parse this 语法。我为链接规范中使用的 EBNF 实现了元语法，但 PLY 报告了多个 shift/reduce 冲突。
语法：
Rule 0 S' -> grammar
Rule 1 grammar -> prod_list
Rule 2 grammar -> empty
Rule 3 prod_list -> prod
Rule 4 prod_list -> prod prod_list
Rule 5 prod -> id : : = rule_list
Rule 6 rule_list -> rule
Rule 7 rule_list -> rule rule_list
Rule 8 rule -> rule_simple
Rule 9 rule -> rule_group
Rule 10 rule -> rule_opt
Rule 11 rule -> rule_rep0
Rule 12 rule -> rule_rep1
Rule 13 rule -> rule_alt
Rule 14 rule -> rule_except
Rule 15 rule_simple -> terminal
Rule 16 rule_simple -> id
Rule 17 rule_simple -> char_range
Rule 18 rule_group -> ( rule_list )
Rule 19 rule_opt -> rule_simple ?
Rule 20 rule_opt -> rule_group ?
Rule 21 rule_rep0 -> rule_simple *
Rule 22 rule_rep0 -> rule_group *
Rule 23 rule_rep1 -> rule_simple +
Rule 24 rule_rep1 -> rule_group +
Rule 25 rule_alt -> rule | rule
Rule 26 rule_except -> rule - rule_simple
Rule 27 rule_except -> rule - rule_group
Rule 28 terminal -> SQ string_no_sq SQ
Rule 29 terminal -> DQ string_no_dq DQ
Rule 30 string_no_sq -> LETTER string_no_sq
Rule 31 string_no_sq -> DIGIT string_no_sq
Rule 32 string_no_sq -> SYMBOL string_no_sq
Rule 33 string_no_sq -> DQ string_no_sq
Rule 34 string_no_sq -> + string_no_sq
Rule 35 string_no_sq -> * string_no_sq
Rule 36 string_no_sq -> ( string_no_sq
Rule 37 string_no_sq -> ) string_no_sq
Rule 38 string_no_sq -> ? string_no_sq
Rule 39 string_no_sq -> | string_no_sq
Rule 40 string_no_sq -> [ string_no_sq
Rule 41 string_no_sq -> ] string_no_sq
Rule 42 string_no_sq -> - string_no_sq
Rule 43 string_no_sq -> : string_no_sq
Rule 44 string_no_sq -> = string_no_sq
Rule 45 string_no_sq -> empty
Rule 46 string_no_dq -> LETTER string_no_dq
Rule 47 string_no_dq -> DIGIT string_no_dq
Rule 48 string_no_dq -> SYMBOL string_no_dq
Rule 49 string_no_dq -> SQ string_no_dq
Rule 50 string_no_dq -> + string_no_dq
Rule 51 string_no_dq -> * string_no_dq
Rule 52 string_no_dq -> ( string_no_dq
Rule 53 string_no_dq -> ) string_no_dq
Rule 54 string_no_dq -> ? string_no_dq
Rule 55 string_no_dq -> | string_no_dq
Rule 56 string_no_dq -> [ string_no_dq
Rule 57 string_no_dq -> ] string_no_dq
Rule 58 string_no_dq -> - string_no_dq
Rule 59 string_no_dq -> : string_no_dq
Rule 60 string_no_dq -> = string_no_dq
Rule 61 string_no_dq -> empty
Rule 62 id -> LETTER LETTER id
Rule 63 id -> LETTER DIGIT id
Rule 64 id -> LETTER
Rule 65 id -> DIGIT
Rule 66 rest_of_id -> LETTER rest_of_id
Rule 67 rest_of_id -> DIGIT rest_of_id
Rule 68 rest_of_id -> empty
Rule 69 char_range -> [ UNI_CH - UNI_CH ]
Rule 70 empty -> <empty>
冲突：
id : LETTER LETTER id
| LETTER DIGIT id
| LETTER
| DIGIT
.
state 4
(62) id -> LETTER . LETTER id
(63) id -> LETTER . DIGIT id
(64) id -> LETTER .
! shift/reduce conflict for LETTER resolved as shift
! shift/reduce conflict for DIGIT resolved as shift
LETTER shift and go to state 10
DIGIT shift and go to state 9
| reduce using rule 64 (id -> LETTER .)
- reduce using rule 64 (id -> LETTER .)
( reduce using rule 64 (id -> LETTER .)
SQ reduce using rule 64 (id -> LETTER .)
DQ reduce using rule 64 (id -> LETTER .)
[ reduce using rule 64 (id -> LETTER .)
$end reduce using rule 64 (id -> LETTER .)
) reduce using rule 64 (id -> LETTER .)
: reduce using rule 64 (id -> LETTER .)
? reduce using rule 64 (id -> LETTER .)
* reduce using rule 64 (id -> LETTER .)
+ reduce using rule 64 (id -> LETTER .)
! LETTER [ reduce using rule 64 (id -> LETTER .) ]
! DIGIT [ reduce using rule 64 (id -> LETTER .) ]
id 规则应该保证作品的 ID 以字母开头。
下一个冲突：
rule_alt : rule '|' rule
.
state 113
(25) rule_alt -> rule | rule .
(25) rule_alt -> rule . | rule
(26) rule_except -> rule . - rule_simple
(27) rule_except -> rule . - rule_group
! shift/reduce conflict for | resolved as shift
! shift/reduce conflict for - resolved as shift
( reduce using rule 25 (rule_alt -> rule | rule .)
SQ reduce using rule 25 (rule_alt -> rule | rule .)
DQ reduce using rule 25 (rule_alt -> rule | rule .)
LETTER reduce using rule 25 (rule_alt -> rule | rule .)
DIGIT reduce using rule 25 (rule_alt -> rule | rule .)
[ reduce using rule 25 (rule_alt -> rule | rule .)
) reduce using rule 25 (rule_alt -> rule | rule .)
$end reduce using rule 25 (rule_alt -> rule | rule .)
| shift and go to state 76
- shift and go to state 74
! | [ reduce using rule 25 (rule_alt -> rule | rule .) ]
! - [ reduce using rule 25 (rule_alt -> rule | rule .) ]
连接到一个熟悉的人：
rule_except : rule '-' rule_simple
| rule '-' rule_group
我该如何解决这些问题？
首先，你显然是盲目地翻译了语法。您需要标记输入流。
通常情况下，id 之类的东西会被词法分析器识别为终端，而不是作为语法的一部分进行解析
id : LETTER LETTER id
| LETTER DIGIT id
| LETTER
| DIGIT
看起来你在 terminal 下的所有内容都不应该是语法的一部分。
其次，您在语法中使用了正确的递归。虽然 LALR 同时适用于左递归和右递归，但使用左递归会得到更小的表。
假设您有输入字符串 AA
如果你坚持解析标识符，你会想要更像
的东西
id : id LETTER
| id DIGIT
| LETTER
最后，Shift-Reduce冲突不一定是基于。它们经常出现在要由运算符先例解析的数值表达式中。
Reduce-Reduce 冲突总是不好的。
您真的应该认真考虑使用通常的 scanner/parser 架构。否则，您将不得不找到一种方法来处理空白。
实际上，您似乎完全忽略了空格。这意味着解析器看不到 three consecutive identifiers 之间的空格。它会将它们 运行 一起视为 asoupofundifferentiatedletters，并且它无法知道原始意图是什么。这会使您的语法非常含糊，因为在语法中，两个标识符可以相互跟随，假设某些东西会导致它们彼此区分。而歧义语法总是导致LR冲突。
让词法分析器识别标识符（和其他多字符标记）容易得多。否则，您将不得不重写语法以识别所有允许使用空格的地方（例如 (identifer1|identifier2) 中的标点符号周围）或必需的地方（例如 two identifiers）。
使用正则表达式在扫描器中识别标识符还将消除语法和标识符的其他问题：
id -> LETTER LETTER id
id -> LETTER DIGIT id
id -> LETTER
这些规则要求 id 是奇数个字符，其中数字仅出现在偶数位置。所以 a1b 将是 id，而不是 ab1 或 ab 或 a1。我确定那不是你的意思。
你似乎在试图避免左递归。相反，你应该拥抱左递归。自下而上的解析器，如 PLY，喜欢左递归。 （它们处理右递归，但是以过度使用解析器堆栈为代价。）所以你真正想要的是：
id: LETTER | id LETTER | id DIGIT
语法中还有其他地方需要进行类似的更改。
另一个冲突是由于您对运算符优先级的非正统处理引起的，这也可能是您试图避免左递归的结果。与代数运算符一样，EBNF 运算符可以使用简单的优先级方案进行解析。但是，由于 "invisible" 连接运算符，优先声明（%left 和朋友）的使用会很复杂。通常，您会发现在标准 expr/factor/term 代数语法中使用显式优先级更容易。在您的情况下，等效项类似于：
item: id
| terminal
| '(' rule ')'
term: item
| item '*'
| item '+'
| item '?'
seq : term
| seq term
alt : seq
| alt '|' seq
except: term '-' term
rule: alt
| except
上面对except的处理对应的是缺少-运算符的优先级信息。这是通过有效地禁止 - 和 | 运算符在没有显式括号的情况下的任何混合来表达的。
你也会发现这里有一个shift/reduce冲突：
# The following will create a problem
prod: id "::=" rule
prod_list
: prod
| prod_list prod
（注意：我用左递归编写的事实不会造成问题。）
这不是模棱两可的，但它不能用单个先行标记从左到右解析。它需要两个标记，因为在看到 id 之后的标记之前，您无法知道 id 是否是当前正在解析的序列的一部分，或者是新产品的开始：如果它是 ::=，那么 id 是新作品的开始，不应移入当前规则。该问题的通常解决方案是对词法分析器进行黑客攻击：词法分析器被一个函数包装，该函数保留一个额外的先行标记，以便它可以将 id ::= 作为 definition 类型的单个标记发出。在其他 SO 问题中有许多针对各种 LR 解析器的这种 hack 示例。
说了这么多，我真的不明白你为什么要为 EBNF 构建一个解析器来解析 XML。从 EBNF 构建一个工作解析器基本上就是 PLY 所做的，除了它没有实现 "E" 部分，所以你必须重写使用 ?、*、+ 和 - 运算符。这可以自动处理，虽然 - 运算符一般来说并不平凡，但它不会简单。恕我直言，将少数 EBNF 规则重写为 BNF，然后只使用 PLY 会更容易。但如果您正在寻找挑战，那就去吧。
我正在使用 PLY to parse this 语法。我为链接规范中使用的 EBNF 实现了元语法，但 PLY 报告了多个 shift/reduce 冲突。
语法：
Rule 0 S' -> grammar
Rule 1 grammar -> prod_list
Rule 2 grammar -> empty
Rule 3 prod_list -> prod
Rule 4 prod_list -> prod prod_list
Rule 5 prod -> id : : = rule_list
Rule 6 rule_list -> rule
Rule 7 rule_list -> rule rule_list
Rule 8 rule -> rule_simple
Rule 9 rule -> rule_group
Rule 10 rule -> rule_opt
Rule 11 rule -> rule_rep0
Rule 12 rule -> rule_rep1
Rule 13 rule -> rule_alt
Rule 14 rule -> rule_except
Rule 15 rule_simple -> terminal
Rule 16 rule_simple -> id
Rule 17 rule_simple -> char_range
Rule 18 rule_group -> ( rule_list )
Rule 19 rule_opt -> rule_simple ?
Rule 20 rule_opt -> rule_group ?
Rule 21 rule_rep0 -> rule_simple *
Rule 22 rule_rep0 -> rule_group *
Rule 23 rule_rep1 -> rule_simple +
Rule 24 rule_rep1 -> rule_group +
Rule 25 rule_alt -> rule | rule
Rule 26 rule_except -> rule - rule_simple
Rule 27 rule_except -> rule - rule_group
Rule 28 terminal -> SQ string_no_sq SQ
Rule 29 terminal -> DQ string_no_dq DQ
Rule 30 string_no_sq -> LETTER string_no_sq
Rule 31 string_no_sq -> DIGIT string_no_sq
Rule 32 string_no_sq -> SYMBOL string_no_sq
Rule 33 string_no_sq -> DQ string_no_sq
Rule 34 string_no_sq -> + string_no_sq
Rule 35 string_no_sq -> * string_no_sq
Rule 36 string_no_sq -> ( string_no_sq
Rule 37 string_no_sq -> ) string_no_sq
Rule 38 string_no_sq -> ? string_no_sq
Rule 39 string_no_sq -> | string_no_sq
Rule 40 string_no_sq -> [ string_no_sq
Rule 41 string_no_sq -> ] string_no_sq
Rule 42 string_no_sq -> - string_no_sq
Rule 43 string_no_sq -> : string_no_sq
Rule 44 string_no_sq -> = string_no_sq
Rule 45 string_no_sq -> empty
Rule 46 string_no_dq -> LETTER string_no_dq
Rule 47 string_no_dq -> DIGIT string_no_dq
Rule 48 string_no_dq -> SYMBOL string_no_dq
Rule 49 string_no_dq -> SQ string_no_dq
Rule 50 string_no_dq -> + string_no_dq
Rule 51 string_no_dq -> * string_no_dq
Rule 52 string_no_dq -> ( string_no_dq
Rule 53 string_no_dq -> ) string_no_dq
Rule 54 string_no_dq -> ? string_no_dq
Rule 55 string_no_dq -> | string_no_dq
Rule 56 string_no_dq -> [ string_no_dq
Rule 57 string_no_dq -> ] string_no_dq
Rule 58 string_no_dq -> - string_no_dq
Rule 59 string_no_dq -> : string_no_dq
Rule 60 string_no_dq -> = string_no_dq
Rule 61 string_no_dq -> empty
Rule 62 id -> LETTER LETTER id
Rule 63 id -> LETTER DIGIT id
Rule 64 id -> LETTER
Rule 65 id -> DIGIT
Rule 66 rest_of_id -> LETTER rest_of_id
Rule 67 rest_of_id -> DIGIT rest_of_id
Rule 68 rest_of_id -> empty
Rule 69 char_range -> [ UNI_CH - UNI_CH ]
Rule 70 empty -> <empty>
冲突：
id : LETTER LETTER id
| LETTER DIGIT id
| LETTER
| DIGIT
.
state 4
(62) id -> LETTER . LETTER id
(63) id -> LETTER . DIGIT id
(64) id -> LETTER .
! shift/reduce conflict for LETTER resolved as shift
! shift/reduce conflict for DIGIT resolved as shift
LETTER shift and go to state 10
DIGIT shift and go to state 9
| reduce using rule 64 (id -> LETTER .)
- reduce using rule 64 (id -> LETTER .)
( reduce using rule 64 (id -> LETTER .)
SQ reduce using rule 64 (id -> LETTER .)
DQ reduce using rule 64 (id -> LETTER .)
[ reduce using rule 64 (id -> LETTER .)
$end reduce using rule 64 (id -> LETTER .)
) reduce using rule 64 (id -> LETTER .)
: reduce using rule 64 (id -> LETTER .)
? reduce using rule 64 (id -> LETTER .)
* reduce using rule 64 (id -> LETTER .)
+ reduce using rule 64 (id -> LETTER .)
! LETTER [ reduce using rule 64 (id -> LETTER .) ]
! DIGIT [ reduce using rule 64 (id -> LETTER .) ]
id 规则应该保证作品的 ID 以字母开头。
下一个冲突：
rule_alt : rule '|' rule
.
state 113
(25) rule_alt -> rule | rule .
(25) rule_alt -> rule . | rule
(26) rule_except -> rule . - rule_simple
(27) rule_except -> rule . - rule_group
! shift/reduce conflict for | resolved as shift
! shift/reduce conflict for - resolved as shift
( reduce using rule 25 (rule_alt -> rule | rule .)
SQ reduce using rule 25 (rule_alt -> rule | rule .)
DQ reduce using rule 25 (rule_alt -> rule | rule .)
LETTER reduce using rule 25 (rule_alt -> rule | rule .)
DIGIT reduce using rule 25 (rule_alt -> rule | rule .)
[ reduce using rule 25 (rule_alt -> rule | rule .)
) reduce using rule 25 (rule_alt -> rule | rule .)
$end reduce using rule 25 (rule_alt -> rule | rule .)
| shift and go to state 76
- shift and go to state 74
! | [ reduce using rule 25 (rule_alt -> rule | rule .) ]
! - [ reduce using rule 25 (rule_alt -> rule | rule .) ]
连接到一个熟悉的人：
rule_except : rule '-' rule_simple
| rule '-' rule_group
我该如何解决这些问题？
首先，你显然是盲目地翻译了语法。您需要标记输入流。
通常情况下，id 之类的东西会被词法分析器识别为终端，而不是作为语法的一部分进行解析
id : LETTER LETTER id
| LETTER DIGIT id
| LETTER
| DIGIT
看起来你在 terminal 下的所有内容都不应该是语法的一部分。
其次，您在语法中使用了正确的递归。虽然 LALR 同时适用于左递归和右递归，但使用左递归会得到更小的表。
假设您有输入字符串 AA
如果你坚持解析标识符，你会想要更像
的东西id : id LETTER
| id DIGIT
| LETTER
最后，Shift-Reduce冲突不一定是基于。它们经常出现在要由运算符先例解析的数值表达式中。
Reduce-Reduce 冲突总是不好的。
您真的应该认真考虑使用通常的 scanner/parser 架构。否则，您将不得不找到一种方法来处理空白。
实际上，您似乎完全忽略了空格。这意味着解析器看不到 three consecutive identifiers 之间的空格。它会将它们 运行 一起视为 asoupofundifferentiatedletters，并且它无法知道原始意图是什么。这会使您的语法非常含糊，因为在语法中，两个标识符可以相互跟随，假设某些东西会导致它们彼此区分。而歧义语法总是导致LR冲突。
让词法分析器识别标识符（和其他多字符标记）容易得多。否则，您将不得不重写语法以识别所有允许使用空格的地方（例如 (identifer1|identifier2) 中的标点符号周围）或必需的地方（例如 two identifiers）。
使用正则表达式在扫描器中识别标识符还将消除语法和标识符的其他问题：
id -> LETTER LETTER id
id -> LETTER DIGIT id
id -> LETTER
这些规则要求 id 是奇数个字符，其中数字仅出现在偶数位置。所以 a1b 将是 id，而不是 ab1 或 ab 或 a1。我确定那不是你的意思。
你似乎在试图避免左递归。相反，你应该拥抱左递归。自下而上的解析器，如 PLY，喜欢左递归。 （它们处理右递归，但是以过度使用解析器堆栈为代价。）所以你真正想要的是：
id: LETTER | id LETTER | id DIGIT
语法中还有其他地方需要进行类似的更改。
另一个冲突是由于您对运算符优先级的非正统处理引起的，这也可能是您试图避免左递归的结果。与代数运算符一样，EBNF 运算符可以使用简单的优先级方案进行解析。但是，由于 "invisible" 连接运算符，优先声明（%left 和朋友）的使用会很复杂。通常，您会发现在标准 expr/factor/term 代数语法中使用显式优先级更容易。在您的情况下，等效项类似于：
item: id
| terminal
| '(' rule ')'
term: item
| item '*'
| item '+'
| item '?'
seq : term
| seq term
alt : seq
| alt '|' seq
except: term '-' term
rule: alt
| except
上面对except的处理对应的是缺少-运算符的优先级信息。这是通过有效地禁止 - 和 | 运算符在没有显式括号的情况下的任何混合来表达的。
你也会发现这里有一个shift/reduce冲突：
# The following will create a problem
prod: id "::=" rule
prod_list
: prod
| prod_list prod
（注意：我用左递归编写的事实不会造成问题。）
这不是模棱两可的，但它不能用单个先行标记从左到右解析。它需要两个标记，因为在看到 id 之后的标记之前，您无法知道 id 是否是当前正在解析的序列的一部分，或者是新产品的开始：如果它是 ::=，那么 id 是新作品的开始，不应移入当前规则。该问题的通常解决方案是对词法分析器进行黑客攻击：词法分析器被一个函数包装，该函数保留一个额外的先行标记，以便它可以将 id ::= 作为 definition 类型的单个标记发出。在其他 SO 问题中有许多针对各种 LR 解析器的这种 hack 示例。
说了这么多，我真的不明白你为什么要为 EBNF 构建一个解析器来解析 XML。从 EBNF 构建一个工作解析器基本上就是 PLY 所做的，除了它没有实现 "E" 部分，所以你必须重写使用 ?、*、+ 和 - 运算符。这可以自动处理，虽然 - 运算符一般来说并不平凡，但它不会简单。恕我直言，将少数 EBNF 规则重写为 BNF，然后只使用 PLY 会更容易。但如果您正在寻找挑战，那就去吧。