如何修改我的解析器计算器语法以继续计算先前的结果？

Question

我正在尝试使用 PLY 在 Python 中制作解析器计算器。我从一些 PLY 示例代码开始，然后从那里开始工作。我要添加的是继续计算先前结果的功能。因此，如果您键入“4 + 5”，结果为 9。如果您随后键入“* 2 - 3”，新结果应为 15，但对于我的代码，它是 -9，因为它首先解析“2 - 3”，什么时候应该首先解析'9 * 2'。当我使用乘法或除法作为第一个运算符对之前的结果进行计算时，会出现此问题。

如我的代码摘录所示，我尝试优先考虑使用先前结果的表达式，但我仍然遇到同样的问题。

'r'是一个变量，存储了之前的结果。

tokens = (
    'NUMBER',
)

literals = ['=', '+', '-', '*', '/', '(', ')']

precedence = (
    ('left', '+', '-'),
    ('right', 'RADD', 'RSUB'),
    ('left', '*', '/'),
    ('right', 'RMUL', 'RDIV'),
    ('right', 'UMINUS'),
)

def p_statement_expr(p):
    'statement : expression'
    p[0] = p[1]

def p_expression_binop(p):
    '''expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression'''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

def p_expression_cont(p):
    '''statement : '+' expression %prec RADD
                  | '-' expression %prec RSUB
                  | '*' expression %prec RMUL
                  | '/' expression %prec RDIV '''
    if p[1] == '+':
        p[0] = r + p[2]
    elif p[1] == '-':
        p[0] = r - p[2]
    elif p[1] == '*':
        p[0] = r * p[2]
    elif p[1] == '/':
        p[0] = r / p[2]   

def p_expression_uminus(p):
    "expression : '(' '-' expression ')' %prec UMINUS"

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

def p_expression_number(p):
    "expression : NUMBER"
    p[0] = p[1]

我还尝试将语法更改为

p_expression_cont(p):
'''expression : '+' expression %prec MORADD
              | '-' expression %prec MORSUB
              | '*' expression %prec MORMUL
              | '/' expression %prec MORDIV '''

这解决了我最初的问题，但现在像“++-*++/23”这样的东西是可以解析的，这显然是我不想要的。如何修改我的语法以便在使用之前的结果时得到正确的计算？

Answer 1

使用 PLY（或任何其他类似 yacc 的解析器生成器）很容易做到这一点，但重要的是要对您要解析的事物的性质有一些了解。

直觉上，像 * 2 - 3 这样的续行应该被解析为好像它被写成 <prev> * 2 - 3 ，其中 <prev> 是一个非终结符，它以某种方式表示先前的值。

对于简单的情况，我们可以定义

expression : '$'

以便前一个值由显式标记 $ 表示。然后剩下的语法就可以了。

当然，目的是用户不必键入 $（尽管实际上，他们可能会发现它很有用。见下文。）所以我们需要

expression: prev

其中非终结符 prev 必须表示空标记序列。由零输入标记表示的非终结符没有问题，但显然我们需要限制可能发生这种情况的情况。所以我们不能只添加：

prev :

语法，因为这将导致您已经遇到的问题：它使 2**4 有效，就好像它是 2*<prev>*4.

显然，我们希望语法只在语句的开头制造一个空的 <prev>。剩下的只是弄清楚如何做到这一点。

假设我们有两种expression：一种允许左侧为空，另一种不允许。我们如何定义这两个非终端？

第二个就是通常的定义：

expression : expression '+' expression
expression : expression '-' expression
expression : expression '*' expression
expression : expression '/' expression
expression : '-' atom                    # See note below
expression : atom
atom : NUMBER
atom : '(' expression ')'

（我将 atom 作品分开，原因如下所示）。

现在，左手操作数可能是隐式的表达式呢？这些非常相似：

expr_cont : expr_cont '+' expression
expr_cont : expr_cont '-' expression
expr_cont : expr_cont '*' expression
expr_cont : expr_cont '/' expression
expr_cont : atom

但是还有一种情况：

expr_cont :

在前四个产生式中，我们说在带有运算符的expr_cont中，右手操作数必须是普通的expression，但左手操作数可以是带有隐式左操作数的表达式。在上一个产生式中，我们允许隐式左手操作数（但仅限于这种表达式）。显式左手操作数——数字和带括号的表达式——是相同的，因此我们可以重用上面创建的 atom 非终结符。

关于一元减号的注意事项： 在原来的语法中，一元减号只允许在括号内使用，其优先级是错误的。原来的制作是：

expression: '(' '-' expression ')' %prec UMINUS

在这个产生式中，声明优先级完全没有意义，因为产生式本身从来没有歧义。（它明确地被括号括起来，所以当遇到右括号时它必须减少。）括号内一元减号的应用也是明确的，但不正确：产生式有效地指定一元减号应用于整个表达式括在括号中，因此 (-4 - 2) 将计算为 -2 (-(4-2)) 而不是预期的 -6。

上述语法中应用的简单修复明确指出一元减号的操作数是 atom，而不是 expression。因此，-4 - 2 必须解析为 (-4) - 2，因为 4 - 2 不能是 atom。但是，该修复删除了以一元减号开头的表达式必须括在括号中的要求。

一元减号产生式只在 expression 而不是 expr_cont 的事实意味着以减号开头的连续表达式将被这样解析，这大概是限制的意图.

现在实施很简单：

precedence = (
    ('left', '+', '-'),
    ('left', '*', '/'),
)

# We can use the same function for all unit productions which pass
# through the semantic value of the right-hand symbol.
# (A unit production is one whose right-hand side has a single symbol.)
def p_unit(p):
    '''statement  : expr_cont
       expression : atom
       expr_cont  : atom
       atom       : NUMBER
    '''
    p[0] = p[1]

# Personally, I would write this as four functions, one for each operator,
# rather than executing the chain of if statements every time.
def p_expression_binop(p):
    '''expression : expression '+' expression
                  | expression '-' expression
                  | expression '*' expression
                  | expression '/' expression
       expr_cont  : expr_cont  '+' expression
                  | expr_cont  '-' expression
                  | expr_cont  '*' expression
                  | expr_cont  '/' expression

    '''
    if p[2] == '+':
        p[0] = p[1] + p[3]
    elif p[2] == '-':
        p[0] = p[1] - p[3]
    elif p[2] == '*':
        p[0] = p[1] * p[3]
    elif p[2] == '/':
        p[0] = p[1] / p[3]

def p_expression_uminus(p):
    '''expresion : '-' atom
    '''
    p[0] = -p[2]

def p_atom_group(p):
    '''atom : '(' expression ')'
    '''
    p[0] = p[2]

def p_expr_previous(p):
    '''expr_cont : 
    '''
    p[0] = r   # "previous" would be a better variable name than r

如上所述，在某些情况下，用户可能会发现使用明确的书写方式很方便 "the previous value"。例如，假设他们想查看 <prev>²+1 的结果。或者假设他们只是想覆盖默认的算术优先级来计算 (<prev> - 3) * 2。通过允许使用 $ 作为显式 "previous value" 标记，可以轻松提供这两种方法。将其添加到文字列表后，只需修改最后一个解析器函数即可：

def p_expr_previous(p):
    '''expr_cont  : 
                  | '$'
       expression : '$'
    '''
    p[0] = r   # "previous" would still be a better variable name than r

如何修改我的解析器计算器语法以继续计算先前的结果？

How do I modify my parser calculator grammar to continue calculations on previous result?

python

parsing

ply

calculator