1

我一直在使用 ply 编写一个 LALR 解析器，并且在尝试解析乘法时遇到了不一致。

由于完整的解析器链接长达数千行，我不会在此处包含它，但我创建了一个简单的演示：

import ply.lex as lex
import ply.yacc as yacc

tokens = (
    'int',
    'times',
    'plus',
)

precedence = (
    ('left', 'plus'),
    ('left', 'times'),
)

t_ignore = ' \t\n '
t_int = r' \d+ '
t_plus = r' \+ '
t_times = ' \* '

def p_int(args):
    'expr : int'
    args[0] = int(args[1])

def p_times(args):
    '''expr : expr times expr
            | expr expr %prec times'''
    if len(args) == 3:
        args[0] = args[1] * args[2]
    elif len(args) == 4:
        args[0] = args[1] * args[3]

def p_plus(args):
    'expr : expr plus expr'
    args[0] = args[1] + args[3]

lex.lex()
parser = yacc.yacc()

while True:
    s = raw_input('>> ')
    print " = ", parser.parse(s)

PLY 没有报告移位/减少冲突或减少/减少冲突，但我得到以下不一致：

    >>  1 + 2 3
     =  9
    >>  1 + 2 * 3
     =  7

这对我来说似乎很奇怪，因为显式和隐式时间规则具有相同的优先级。但我认为这可能是因为 PLY 为“times”令牌分配了优先级，因此将其转移到堆栈上，以支持使用 p_plus 规则减少表达式。我怎样才能解决这个问题？

编辑：更简单的演示。

4

2 回答 2

1

快速破解：将int令牌添加到优先级规范（具有时间优先级）。然后int令牌将被适当地转移到符号堆栈上。那是（根据原始问题），

precedence = (
    ('left', 'plus'),
    ('left', 'times', 'int'),
)

这可行，但在处理可能大量的标记（左括号、符号、浮点数等）时会很混乱。

>>  1 + 2 3
 =  7

我仍然想知道是否有更优雅的解决方案。

于 2013-04-22T23:51:50.900 回答
0

有一个更合适的解决方案：放弃运算符优先级并以通常的方式定义非终结符号expr, term, 和factor。原因？隐含乘法没有作为优先级决策基础的特征标记，并且您不想手动恢复非终结符的第一组。此外，随着你语法的增长，第一组也会随之增长。

在 BNF 中，考虑类似于：

expr -> term | expr + term | expr - term
term -> factor | term * factor | term factor | term / factor
factor -> number | variable | ( expr )

顺便说一句，您可能想要创建一个额外的非终结层来表示这样一个事实，即隐式邻接乘法通常被认为具有比除法更高的优先级，而显式乘法通常被解释为具有相同的优先级.

这并不特定于任何特定的解析器生成器框架。

于 2019-07-13T07:54:43.813 回答