PLY 解析器 - 方程分配

Question

我正在使用 PLY 创建一个计算器。我希望能够将方程分配给字典，因为我能够将变量分配给另一个字典。

我分配变量的方式：x = 10（在字典中 x 是键，10 是值）

我希望能够分配等式的方式：fun(x) = x + 42（在字典中 fun 将是键，元组 ('x', 'x+10') 将是值）。

它正在使用此写作 fun|x| = x + 42（注意此处的 'pipe' 符号）。但它不适用于括号。

我怎样才能让它以正确的方式工作？

到目前为止，这是我的代码：

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

################################## LEXER ################################

tokens = (
    'NAME',
    'NUMBER',
)

t_NAME      = r'[a-zA-Z]+'
literals    = '+=-*/|()'
t_ignore    = " \t"

def t_NUMBER(t):
    r'(?:\d+(?:\.\d*)?)'
    t.value = int(t.value)
    return t

def t_error(t):
    print('Illegal character \'{}\''.format(t.value[0]))
    t.lexer.skip(1)

################################## PARSER ################################

functions = {}
variables = {}

def p_operations(p):
    """ statement : expression
    expression : fifth
    fifth : fourth
    fourth : third
    third : second
    second : first
    first : NUMBER
    """
    p[0] = p[1]

def p_plus(p):
    """ fifth : fifth '+' fourth """
    if isinstance(p[1], str) or isinstance(p[3], str):
        p[0] = str(p[1]) + p[2] + str(p[3])
    else:
        p[0] = p[1] + p[3]

def p_minus(p):
    """ fifth : fifth '-' fourth """
    if isinstance(p[1], str) or isinstance(p[3], str):
        p[0] = str(p[1]) + p[2] + str(p[3])
    else:
        p[0] = p[1] - p[3]

def p_implicit_times(p):
    """ fourth : fourth second """
    if isinstance(p[1], str) or isinstance(p[2], str):
        p[0] = str(p[1]) + str(p[2])
    else:
        p[0] = p[1] * p[2]

def p_times(p):
    """ fourth : fourth '*' third """
    if isinstance(p[1], str) or isinstance(p[3], str):
        p[0] = str(p[1]) + p[2] + str(p[3])
    else:
        p[0] = p[1] * p[3]

def p_divide(p):
    """ fourth : fourth '/' third """
    if isinstance(p[1], str) or isinstance(p[3], str):
        p[0] = str(p[1]) + p[2] + str(p[3])
    else:
        p[0] = p[1] / p[3]

def p_unary_minus(p):
    """ third : '-' third """
    if isinstance(p[2], str):
        p[0] = '-' + p[2]
    else:
        p[0] = -p[2]

def p_power(p):
    """ second : first '^' third """
    if isinstance(p[1], str) or isinstance(p[3], str):
        p[0] = str(p[1]) + p[2] + str(p[3])
    else:
        p[0] = p[1] ** p[3]

def p_block(p):
    """ first : '(' expression ')' """
    p[0] = p[2]


################################ PROBLEM HERE ############################

def p_statement_assign(p):
    ''' statement : NAME '=' expression '''
    variables[p[1]] = p[3]
    p[0] = p[3]

def p_function_assign(p):
    ''' statement : NAME '|' expression '|' '=' expression '''
    functions[p[1]] = (p[3], p[6])
    p[0] = functions[p[1]]

def p_variable_expr(p):
    ''' first : NAME '''
    try : 
        p[0] = variables[p[1]]
    except:
        p[0] = p[1]

def p_error(t):
    print("Syntax error!")

################################## MAIN #################################

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

while True:
    try:
        question = raw_input('>>> ')
    except:
        question = input('>>> ')

    answer = parser.parse(question)
    if answer is not None:
        print(answer)

Answer 1

您允许隐式乘法。这意味着 f(x) 可以被解析为乘积，在这种情况下，根据隐式乘法规则，f 必须减少为 fourth。但是如果要解析成赋值，就需要留成一个NAME。这是一个 shift-reduce 冲突，可以很容易地在 parser.out:

中看到

state 3

    (16) statement -> NAME . = expression
    (17) statement -> NAME . ( expression ) = expression
    (18) first -> NAME .

  ! shift/reduce conflict for ( resolved as shift

你在这里看到的是，当解析器看到 NAME 后跟 ( 时，它不知道是否将 NAME 减少到 first （以及随后到 second，等等，直到 fourth)，期望语句是一个简单的计算，或者移动 (，从而承诺将其视为函数定义。

您可能已经遇到过类似的问题，因为函数定义的自然语法是：

statement : NAME '(' NAME ')' '=' expression

但您已将第二个 NAME 替换为 expression。这将以接受有问题的函数定义 (f(a+3) = 2a).

为代价避免 ) 之前的 shift-reduce 冲突

可以做类似的事情来避免这种 shift-reduce 冲突（但这是一个非常临时的解决方案）：

statement : fourth '(' expression ')' '=' expression

即 "works" 在接受正确表达式的意义上。但它也默默地（或有点默默地）接受了很多其他的表达方式：

这个不错：

>>> f(a) = a + 3
('a', 'a+3')

但是这些很奇怪：

>>> -f(a) = a + 3
('a', 'a+3')
>>> 3f(a) = a + 3
('a', 'a+3')
>>> 3f(a+2) = a + 3
('a+2', 'a+3')

或者，您可以忽略 shift-reduce 冲突，因为默认情况下 PLY 会执行 shift（如 parser.out: "resolved as shift" 中所述）。这将阻止解析器接受上面奇怪的例子，但它也会错误地解析一些看起来合理的表达式：

这些似乎合适：

>>> f(a) = a + 3
('a', 'a+3')
>>> -f(a) = a + 3
Syntax error!
a+3
>>> 3f(a) = a + 3
Syntax error!
a+3

但我们可能希望打印 105:

>>> a=7
7
>>> a(2a+1)
Syntax error!

如果你不介意的话，你现在可以停止阅读了。

你的语法没有歧义，如果你把定义语法写得更具体，也不会歧义:

statement : NAME '(' NAME ')' '=' expression

或者，如果您想允许具有多个参数的函数：

statement : NAME '(' name_list ')' '=' expression
name_list : NAME
name_list : name_list ',' NAME

但不是LR(1)，要做到LR(1)会非常困难。上面建议的两种语法都是 LR(4)，并且由于理论上每个 LR(k) 文法都可以机械地转换为（非常臃肿且难以阅读）LR(1) 文法，因此必须存在解决方案。不过，它不会很漂亮。

（您使用的实际语法 expression 不是任何 k 的 LR(k)，因为 expression 可以任意长并且解析器必须查看参数列表之外的内容从而决定是否减少第一个NAME.)

由于语法明确，您可以用 GLR/GLL/Earley/etc 解析它。解析器，但 PLY 不生成那些，而且我不知道 Python 解析器生成器会生成（尽管这并不意味着不存在）。有多种适用于其他语言的 GLR 解析器生成器。

但是，对于 PLY，您最好的选择可能是使用上面显示的通用语法作为临时解决方案，然后通过检查语义操作来解决接受错误定义的问题。

但是，该检查将有点棘手，除非您硬着头皮改用生成 AST 的解析器而不是立即求值，正如我们已经讨论过多次的那样。如果语义值是 AST，那么可以直接验证 p[1] 和 p[3] 都是

的动作函数中的简单名称

statement : fourth '(' expression ')' '=' expression

我想，人类的聪明才智是无限的，您可能会找到其他一些可以让您进行测试的 hack。但是，当它在极端情况下失败时，不要期望得到太多同情。

PLY 解析器 - 方程分配

PLY parser - equation assignation

python

parsing

equation

ply