解决 ply yacc 中的 shift/reduce 冲突
Resolving shift/reduce conflicts in ply yacc
Ply 报告说它在使用我输入的构建 LALR 解析器的语法时遇到了很多 shift/reduce 冲突。
现在我正在努力解决这些冲突，但无论我做什么都会让情况变得更糟。首先，我使用 C 语言（我的语法几乎与编程语言语法相同，例如 C 和 Python 的混合）优先级 table 在我的解析器中设置 precedence tuple 与该顺序相同：
precedence = (
# ('left', 'ELSE'),
# ('left', 'ID')
# ('left', 'INTEGERNUMBER')
# ('left', 'FLOATNUMBER')
# ('left', 'SEMICOLON')
# ('left', 'ERROR')
('left', 'COMMA'),
('right', 'ASSIGN'),
('left', 'OR'),
('left', 'AND'),
('left', 'EQ', 'NE'),
('left', 'GE', 'GT'),
('left', 'LE', 'LT'),
('left', 'SUM', 'SUB'),
('left', 'MUL', 'DIV', 'MOD'),
('right', 'NOT'),
('left', 'LCB', 'RCB'), #left curly brace...
('left', 'LSB', 'RSB'), #left square bracket..
('left', 'LRB', 'RRB'), #left round bracket...
)
它确实有帮助并消除了 90 次冲突中的大约 40 次。下一步我试图从包含左递归的语法中删除左递归。我使用在线工具为一两个作品做了这个，但它增加了很多 shift-reduce 冲突和一些 reduce/reduce 冲突，我不太擅长这些事情所以我怀疑我是否应该继续消除所有产品中的所有左递归以查看结果或早期的不良结果是一个停止标志。
我也进行了一些搜索，了解到左递归不会破坏 LALR 语法，precedence 和 associativity 足以解决这些冲突。
以下是其中有数十起冲突的州之一：
state 82
(45) exp -> exp operator exp .
(45) exp -> exp . operator exp
(46) exp -> exp . relop exp
(54) operator -> . OR
(55) operator -> . AND
(56) operator -> . SUM
(57) operator -> . SUB
(58) operator -> . MUL
(59) operator -> . DIV
(60) operator -> . MOD
(65) relop -> . GT
(66) relop -> . LT
(67) relop -> . NE
(68) relop -> . EQ
(69) relop -> . LE
(70) relop -> . GE
! shift/reduce conflict for OR resolved as shift
! shift/reduce conflict for AND resolved as shift
! shift/reduce conflict for SUM resolved as shift
! shift/reduce conflict for SUB resolved as shift
! shift/reduce conflict for MUL resolved as shift
! shift/reduce conflict for DIV resolved as shift
! shift/reduce conflict for MOD resolved as shift
! shift/reduce conflict for GT resolved as shift
! shift/reduce conflict for LT resolved as shift
! shift/reduce conflict for NE resolved as shift
! shift/reduce conflict for EQ resolved as shift
! shift/reduce conflict for LE resolved as shift
! shift/reduce conflict for GE resolved as shift
RSB reduce using rule 45 (exp -> exp operator exp .)
SEMICOLON reduce using rule 45 (exp -> exp operator exp .)
COMMA reduce using rule 45 (exp -> exp operator exp .)
RRB reduce using rule 45 (exp -> exp operator exp .)
OR shift and go to state 54
AND shift and go to state 55
SUM shift and go to state 56
SUB shift and go to state 57
MUL shift and go to state 58
DIV shift and go to state 59
MOD shift and go to state 60
GT shift and go to state 61
LT shift and go to state 62
NE shift and go to state 63
EQ shift and go to state 64
LE shift and go to state 65
GE shift and go to state 66
! OR [ reduce using rule 45 (exp -> exp operator exp .) ]
! AND [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUM [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUB [ reduce using rule 45 (exp -> exp operator exp .) ]
! MUL [ reduce using rule 45 (exp -> exp operator exp .) ]
! DIV [ reduce using rule 45 (exp -> exp operator exp .) ]
! MOD [ reduce using rule 45 (exp -> exp operator exp .) ]
! GT [ reduce using rule 45 (exp -> exp operator exp .) ]
! LT [ reduce using rule 45 (exp -> exp operator exp .) ]
! NE [ reduce using rule 45 (exp -> exp operator exp .) ]
! EQ [ reduce using rule 45 (exp -> exp operator exp .) ]
! LE [ reduce using rule 45 (exp -> exp operator exp .) ]
! GE [ reduce using rule 45 (exp -> exp operator exp .) ]
operator shift and go to state 52
relop shift and go to state 53
以下是我认为与上述状态相关的一些作品：
exp → lvalue=exp | exp operator exp |exp relop exp|
const | lvalue | ID(explist) | LRB exp RRB | ID() | SUB exp | NOT exp
operator → OR | AND | SUM | SUB | MUL | DIV | MOD
relop → GE | LT | NE | EQ | LE | GE
const → INTEGERNUMBER | FLOATNUMBER | TRUE | FALSE
lvalue → ID | ID LSB exp RSB
编辑： 下面是完整的警告列表：
WARNING: Conflicts:
WARNING:
WARNING: shift/reduce conflict for VOID in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 0 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 0 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 45 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 45 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 45 resolved as shift
WARNING: shift/reduce conflict for RETURN in state 72 resolved as shift
WARNING: shift/reduce conflict for WHILE in state 72 resolved as shift
WARNING: shift/reduce conflict for FOR in state 72 resolved as shift
WARNING: shift/reduce conflict for IF in state 72 resolved as shift
WARNING: shift/reduce conflict for PRINT in state 72 resolved as shift
WARNING: shift/reduce conflict for ID in state 72 resolved as shift
WARNING: shift/reduce conflict for LRB in state 72 resolved as shift
WARNING: shift/reduce conflict for SUB in state 72 resolved as shift
WARNING: shift/reduce conflict for NOT in state 72 resolved as shift
WARNING: shift/reduce conflict for LCB in state 72 resolved as shift
WARNING: shift/reduce conflict for INTEGERNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for FLOATNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for TRUE in state 72 resolved as shift
WARNING: shift/reduce conflict for FALSE in state 72 resolved as shift
WARNING: shift/reduce conflict for OR in state 82 resolved as shift
WARNING: shift/reduce conflict for AND in state 82 resolved as shift
WARNING: shift/reduce conflict for SUM in state 82 resolved as shift
WARNING: shift/reduce conflict for SUB in state 82 resolved as shift
WARNING: shift/reduce conflict for MUL in state 82 resolved as shift
WARNING: shift/reduce conflict for DIV in state 82 resolved as shift
WARNING: shift/reduce conflict for MOD in state 82 resolved as shift
WARNING: shift/reduce conflict for GT in state 82 resolved as shift
WARNING: shift/reduce conflict for LT in state 82 resolved as shift
WARNING: shift/reduce conflict for NE in state 82 resolved as shift
WARNING: shift/reduce conflict for EQ in state 82 resolved as shift
WARNING: shift/reduce conflict for LE in state 82 resolved as shift
WARNING: shift/reduce conflict for GE in state 82 resolved as shift
WARNING: shift/reduce conflict for OR in state 83 resolved as shift
WARNING: shift/reduce conflict for AND in state 83 resolved as shift
WARNING: shift/reduce conflict for SUM in state 83 resolved as shift
WARNING: shift/reduce conflict for SUB in state 83 resolved as shift
WARNING: shift/reduce conflict for MUL in state 83 resolved as shift
WARNING: shift/reduce conflict for DIV in state 83 resolved as shift
WARNING: shift/reduce conflict for MOD in state 83 resolved as shift
WARNING: shift/reduce conflict for GT in state 83 resolved as shift
WARNING: shift/reduce conflict for LT in state 83 resolved as shift
WARNING: shift/reduce conflict for NE in state 83 resolved as shift
WARNING: shift/reduce conflict for EQ in state 83 resolved as shift
WARNING: shift/reduce conflict for LE in state 83 resolved as shift
WARNING: shift/reduce conflict for GE in state 83 resolved as shift
WARNING: shift/reduce conflict for ELIF in state 121 resolved as shift
在此先感谢您。
由于 + 和 * 在句法上不同，您不能将它们归为一个句法类别 (operator)。
它们在语法上的不同正是因为运算符具有不同的优先级。 （或者，更准确地说，我们通常将句法差异描述为优先级差异）。例如，表达式 a - b * c 和 a - b - c 在句法上 不同，因为在第一个表达式中， N - N 的语法允许第二个 N 覆盖 b * c，而在第二个 b - c 中不允许作为第二个 N 的扩展。因此，将所有运算符收集到一个 operator 非终结符中会以某种方式混淆不同的句法结构，从而无法使用语法生成正确的解析。
为了使用优先声明来解决歧义语法，您必须使实际的运算符标记在产生式中可见：
exp: exp '+' exp | exp '-' exp | exp '*' exp …
(注意：我在上面使用了引用的文字标记，而不是坚持使用名称。文字标记的使用更具可读性，并且在您的词法分析器描述中需要更少的样板文件。它还允许 Ply 创建更高效的词法分析器。见 the Ply manual.)
不要试图消除左递归。没有左递归，就无法正确编写左结合运算符（也就是说，大多数运算符）的语法。 LALR 解析器更喜欢左递归规则。他们不是你的问题。
Ply 报告说它在使用我输入的构建 LALR 解析器的语法时遇到了很多 shift/reduce 冲突。
现在我正在努力解决这些冲突，但无论我做什么都会让情况变得更糟。首先，我使用 C 语言（我的语法几乎与编程语言语法相同，例如 C 和 Python 的混合）优先级 table 在我的解析器中设置 precedence tuple 与该顺序相同：
precedence = (
# ('left', 'ELSE'),
# ('left', 'ID')
# ('left', 'INTEGERNUMBER')
# ('left', 'FLOATNUMBER')
# ('left', 'SEMICOLON')
# ('left', 'ERROR')
('left', 'COMMA'),
('right', 'ASSIGN'),
('left', 'OR'),
('left', 'AND'),
('left', 'EQ', 'NE'),
('left', 'GE', 'GT'),
('left', 'LE', 'LT'),
('left', 'SUM', 'SUB'),
('left', 'MUL', 'DIV', 'MOD'),
('right', 'NOT'),
('left', 'LCB', 'RCB'), #left curly brace...
('left', 'LSB', 'RSB'), #left square bracket..
('left', 'LRB', 'RRB'), #left round bracket...
)
它确实有帮助并消除了 90 次冲突中的大约 40 次。下一步我试图从包含左递归的语法中删除左递归。我使用在线工具为一两个作品做了这个，但它增加了很多 shift-reduce 冲突和一些 reduce/reduce 冲突，我不太擅长这些事情所以我怀疑我是否应该继续消除所有产品中的所有左递归以查看结果或早期的不良结果是一个停止标志。
我也进行了一些搜索，了解到左递归不会破坏 LALR 语法，precedence 和 associativity 足以解决这些冲突。
以下是其中有数十起冲突的州之一：
state 82
(45) exp -> exp operator exp .
(45) exp -> exp . operator exp
(46) exp -> exp . relop exp
(54) operator -> . OR
(55) operator -> . AND
(56) operator -> . SUM
(57) operator -> . SUB
(58) operator -> . MUL
(59) operator -> . DIV
(60) operator -> . MOD
(65) relop -> . GT
(66) relop -> . LT
(67) relop -> . NE
(68) relop -> . EQ
(69) relop -> . LE
(70) relop -> . GE
! shift/reduce conflict for OR resolved as shift
! shift/reduce conflict for AND resolved as shift
! shift/reduce conflict for SUM resolved as shift
! shift/reduce conflict for SUB resolved as shift
! shift/reduce conflict for MUL resolved as shift
! shift/reduce conflict for DIV resolved as shift
! shift/reduce conflict for MOD resolved as shift
! shift/reduce conflict for GT resolved as shift
! shift/reduce conflict for LT resolved as shift
! shift/reduce conflict for NE resolved as shift
! shift/reduce conflict for EQ resolved as shift
! shift/reduce conflict for LE resolved as shift
! shift/reduce conflict for GE resolved as shift
RSB reduce using rule 45 (exp -> exp operator exp .)
SEMICOLON reduce using rule 45 (exp -> exp operator exp .)
COMMA reduce using rule 45 (exp -> exp operator exp .)
RRB reduce using rule 45 (exp -> exp operator exp .)
OR shift and go to state 54
AND shift and go to state 55
SUM shift and go to state 56
SUB shift and go to state 57
MUL shift and go to state 58
DIV shift and go to state 59
MOD shift and go to state 60
GT shift and go to state 61
LT shift and go to state 62
NE shift and go to state 63
EQ shift and go to state 64
LE shift and go to state 65
GE shift and go to state 66
! OR [ reduce using rule 45 (exp -> exp operator exp .) ]
! AND [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUM [ reduce using rule 45 (exp -> exp operator exp .) ]
! SUB [ reduce using rule 45 (exp -> exp operator exp .) ]
! MUL [ reduce using rule 45 (exp -> exp operator exp .) ]
! DIV [ reduce using rule 45 (exp -> exp operator exp .) ]
! MOD [ reduce using rule 45 (exp -> exp operator exp .) ]
! GT [ reduce using rule 45 (exp -> exp operator exp .) ]
! LT [ reduce using rule 45 (exp -> exp operator exp .) ]
! NE [ reduce using rule 45 (exp -> exp operator exp .) ]
! EQ [ reduce using rule 45 (exp -> exp operator exp .) ]
! LE [ reduce using rule 45 (exp -> exp operator exp .) ]
! GE [ reduce using rule 45 (exp -> exp operator exp .) ]
operator shift and go to state 52
relop shift and go to state 53
以下是我认为与上述状态相关的一些作品：
exp → lvalue=exp | exp operator exp |exp relop exp|
const | lvalue | ID(explist) | LRB exp RRB | ID() | SUB exp | NOT exp
operator → OR | AND | SUM | SUB | MUL | DIV | MOD
relop → GE | LT | NE | EQ | LE | GE
const → INTEGERNUMBER | FLOATNUMBER | TRUE | FALSE
lvalue → ID | ID LSB exp RSB
编辑： 下面是完整的警告列表：
WARNING: Conflicts:
WARNING:
WARNING: shift/reduce conflict for VOID in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 0 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 0 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 0 resolved as shift
WARNING: shift/reduce conflict for INTEGER in state 45 resolved as shift
WARNING: shift/reduce conflict for FLOAT in state 45 resolved as shift
WARNING: shift/reduce conflict for BOOLEAN in state 45 resolved as shift
WARNING: shift/reduce conflict for RETURN in state 72 resolved as shift
WARNING: shift/reduce conflict for WHILE in state 72 resolved as shift
WARNING: shift/reduce conflict for FOR in state 72 resolved as shift
WARNING: shift/reduce conflict for IF in state 72 resolved as shift
WARNING: shift/reduce conflict for PRINT in state 72 resolved as shift
WARNING: shift/reduce conflict for ID in state 72 resolved as shift
WARNING: shift/reduce conflict for LRB in state 72 resolved as shift
WARNING: shift/reduce conflict for SUB in state 72 resolved as shift
WARNING: shift/reduce conflict for NOT in state 72 resolved as shift
WARNING: shift/reduce conflict for LCB in state 72 resolved as shift
WARNING: shift/reduce conflict for INTEGERNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for FLOATNUMBER in state 72 resolved as shift
WARNING: shift/reduce conflict for TRUE in state 72 resolved as shift
WARNING: shift/reduce conflict for FALSE in state 72 resolved as shift
WARNING: shift/reduce conflict for OR in state 82 resolved as shift
WARNING: shift/reduce conflict for AND in state 82 resolved as shift
WARNING: shift/reduce conflict for SUM in state 82 resolved as shift
WARNING: shift/reduce conflict for SUB in state 82 resolved as shift
WARNING: shift/reduce conflict for MUL in state 82 resolved as shift
WARNING: shift/reduce conflict for DIV in state 82 resolved as shift
WARNING: shift/reduce conflict for MOD in state 82 resolved as shift
WARNING: shift/reduce conflict for GT in state 82 resolved as shift
WARNING: shift/reduce conflict for LT in state 82 resolved as shift
WARNING: shift/reduce conflict for NE in state 82 resolved as shift
WARNING: shift/reduce conflict for EQ in state 82 resolved as shift
WARNING: shift/reduce conflict for LE in state 82 resolved as shift
WARNING: shift/reduce conflict for GE in state 82 resolved as shift
WARNING: shift/reduce conflict for OR in state 83 resolved as shift
WARNING: shift/reduce conflict for AND in state 83 resolved as shift
WARNING: shift/reduce conflict for SUM in state 83 resolved as shift
WARNING: shift/reduce conflict for SUB in state 83 resolved as shift
WARNING: shift/reduce conflict for MUL in state 83 resolved as shift
WARNING: shift/reduce conflict for DIV in state 83 resolved as shift
WARNING: shift/reduce conflict for MOD in state 83 resolved as shift
WARNING: shift/reduce conflict for GT in state 83 resolved as shift
WARNING: shift/reduce conflict for LT in state 83 resolved as shift
WARNING: shift/reduce conflict for NE in state 83 resolved as shift
WARNING: shift/reduce conflict for EQ in state 83 resolved as shift
WARNING: shift/reduce conflict for LE in state 83 resolved as shift
WARNING: shift/reduce conflict for GE in state 83 resolved as shift
WARNING: shift/reduce conflict for ELIF in state 121 resolved as shift
在此先感谢您。
由于 + 和 * 在句法上不同，您不能将它们归为一个句法类别 (operator)。
它们在语法上的不同正是因为运算符具有不同的优先级。 （或者，更准确地说，我们通常将句法差异描述为优先级差异）。例如，表达式 a - b * c 和 a - b - c 在句法上 不同，因为在第一个表达式中， N - N 的语法允许第二个 N 覆盖 b * c，而在第二个 b - c 中不允许作为第二个 N 的扩展。因此，将所有运算符收集到一个 operator 非终结符中会以某种方式混淆不同的句法结构，从而无法使用语法生成正确的解析。
为了使用优先声明来解决歧义语法，您必须使实际的运算符标记在产生式中可见：
exp: exp '+' exp | exp '-' exp | exp '*' exp …
(注意：我在上面使用了引用的文字标记，而不是坚持使用名称。文字标记的使用更具可读性，并且在您的词法分析器描述中需要更少的样板文件。它还允许 Ply 创建更高效的词法分析器。见 the Ply manual.)
不要试图消除左递归。没有左递归，就无法正确编写左结合运算符（也就是说，大多数运算符）的语法。 LALR 解析器更喜欢左递归规则。他们不是你的问题。