PLY(EBNF) 中丢弃表达式的语法导致二进制表达式被视为一元表达式

Question

我正在为 python 的一个子集编写解析器（使用 PLY）。它包括：int、name、add、unarysub、assignments 和 function_calls。

到目前为止我有以下语法：

# Grammar for P0:
# statements := statement+
# statement := simple_statement
# simple_statement := assignment | d_expression
# assignment := NAME ['=' expression]
# d_expression := expression
# expression := sum
# sum := sum '+' term | term
# term := factor
# factor := '+' factor | '-' factor | primary
# primary: primary '(' [arguments] ') | atom
# atom := INT | NAME
# arguments := args | empty
# args := arg | arg ',' args
# arg := expression

它几乎适用于我需要的所有情况。但是，我在处理上面的 discard expressions(d_expression) 时遇到了麻烦。 Python 支持丢弃表达式。例如，python 将 x = 1 + 2 和 1 + 2 都视为有效程序。前者在python AST中得到一个Assign节点，而后者在python AST中得到一个Expr节点（被丢弃，因此得名discard expression）。

我试图在我的解析器中模拟这种行为，但是在实现这个特性时，我的解析器将 1 - 2 视为两个 Expr 节点的列表（Expr(Constant(value=1)，Expr(UnaryOp(op=USub(), operand=Constant(value=2)） .这是一种不正确的行为，它应该会引发语法错误，因为我的语法中没有 expression MINUS expression。我不确定我哪里出错了，感谢您的帮助。

下面是我的解析器的代码实现：

class MyParser:
    tokens = MyLexer.tokens

    precedence = (
        ('left', 'PLUS', 'MINUS'),
        ('right', 'UMINUS'),
    )

    def __init__(self):
        self.lexer = P0Lexer()
        self.parser = yacc.yacc(module=self)

    def p_module(self, p):
        '''
        module : statements
        '''
        p[0] = Module(body=p[1])
        logging.info(ast.dump(p[0]))

    def p_statements(self, p):
        '''
        statements : statement
                   | statement statements
        '''
        if len(p) == 2:
            p[0] = [p[1]]
        else:
            p[0] = [p[1]] + p[2]
        for i in p[0]:
            logging.info(ast.dump(i))

    def p_statement(self, p):
        '''
        statement : simple_statement
        '''
        p[0] = p[1]
        logging.info(ast.dump(p[0]))

    def p_simple_statement(self, p):
        '''
        simple_statement : assignment
        '''
        p[0] = p[1]
        logging.info(ast.dump(p[0]))
    
    def p_assignment(self, p):
        '''
        assignment : NAME EQUALS expression
        '''
        p[0] = Assign(targets=[Name(id=p[1], ctx=Store())], value=p[3])
        logging.info(ast.dump(p[0]))

    # def p_d_expression(self, p):
    #     '''
    #     d_expression : expression
    #     '''
    #     p[0] = Expr(value=p[1])
    #     logging.info(ast.dump(p[0]))

    def p_expression(self, p):
        '''
        expression : sum
        '''
        p[0] = p[1]
        logging.info(ast.dump(p[0]))

    def p_sum(self, p):
        '''
        sum : sum PLUS term
            | term
        '''
        if len(p) == 2:
            p[0] = p[1]
        else:
            p[0] = BinOp(left=p[1], op=Add(), right=p[3])
        logging.info(ast.dump(p[0]))

    def p_term(self, p):
        '''
        term : factor
        '''
        p[0] = p[1]
        logging.info(ast.dump(p[0]))

    def p_factor(self, p):
        '''
        factor : MINUS factor %prec UMINUS
               | primary
        '''
        if len(p) == 2:
            p[0] = p[1]
        else:
            if p[1] == '+':
                p[0] = UnaryOp(op=UAdd(), operand=p[2])
            else:
                p[0] = UnaryOp(op=USub(), operand=p[2])
        logging.info(ast.dump(p[0]))

    def p_primary(self, p):
        '''
        primary : primary LPAREN arguments RPAREN
                | atom
        '''
        if len(p) == 2:
            p[0] = p[1]
        else:
            p[0] = Call(func=p[1], args=p[3])
        logging.info(ast.dump(p[0]))

    def p_arguments(self, p):
        '''
        arguments : args 
                 | empty
        '''
        if len(p) == 2:
            p[0] = p[1] if p[1] is not None else []
        else:
            p[0] = []
        for i in p[0]:
            logging.info(ast.dump(i))

    def p_args(self, p):
        '''
        args : arg
            | arg COMMA args
        '''
        if len(p) == 2:
            p[0] = [p[1]]
        else:
            p[0] = [p[1]] + p[3]
        for i in p[0]:
            logging.info(ast.dump(i))

    def p_arg(self, p):
        '''
        arg : expression
        '''
        p[0] = p[1]
        logging.info(ast.dump(p[0]))

    def p_atom(self, p):
        '''
        atom : INT
             | NAME
        '''
        if isinstance(p[1], int):
            p[0] = Constant(value=p[1])
        else:
            p[0] = Name(id=p[1], ctx=Load())
        logging.info(ast.dump(p[0]))

    def p_empty(self, p):
        '''
        empty :
        '''
        pass

    def p_error(self, p):
        if p:
            logging.error("Syntax error at '%s'" % p.value)
        else:
            logging.error("Syntax error at EOF")
        exit(1)

Answer 1

我怀疑这里的问题是

statements := statement+

是你的罪魁祸首。这允许您放置任意两个 statements side-by-side 并将其视为 statements。如果是这样，那么 1 - 2 确实是一个有效的 statements，因为正如您所指出的，这可以分解为语句 1 和 -2，每个是一个 discard-expression.

以其他编程语言为例可能有助于了解如何解决此问题。在 C、C++ 或 Java 等语言中，可以将表达式制成语句，因为存在

效果的语法规则

statement := expression ;

以 ; 作为分隔符。这意味着如果你要找到类似

1 + 2 2 + 3;

在 C/C++/Java 程序中，这将是语法错误，因为虽然 1 + 2 和 2 + 3 是表达式，但这些表达式不是语句他们后面没有分号。另一方面，在这些语言中写

是合法的

1 + 2; 2 + 3;

在一行中，组成两个语句的两个表达式之间有一个明确的分隔符。

现在让我们看看Python。 Python 不允许你写

1 + 2 2 + 3

并将其计为两个表达式。为什么不？好吧，如果您查看 the Python grammar，您可以在将一系列简单语句解析为 simple_stmts 表达式的方式中看到这一点。（Python使用解析表达式语法而不是CFG，所以语法有点不同。）

simple_stmts:
    | simple_stmt !';' NEWLINE
    | ';'.simple_stmt+ [';'] NEWLINE

换句话说，一个simple_stmts是

A simple_stmt 后跟一个换行符，或者
一系列 simple_stmt，以分号分隔，后跟一个换行符。

这些规则中的每一个都在表达式之间给出了明确的分隔符，换行符或分号（或两者）。

所以从这个意义上说，我怀疑这个问题根本上不是关于删除表达式的问题，而是关于如何允许多个语句彼此分开的问题。在用作语句的每个表达式之后需要某种定界符 - 例如换行符或分号应该可以解决这个问题。

Answer 2

感谢@templatetypdef。我允许没有分隔符的两个表达式。

我通过引入这个产生式解决了它：

simple_stmts:
    | simple_stmt !';' NEWLINE  # Not needed, there for speedup
    | ';'.simple_stmt+ [';'] NEWLINE

PLY(EBNF) 中丢弃表达式的语法导致二进制表达式被视为一元表达式

Grammar for discard expression in PLY(EBNF) is causing binary expression to be treated as a unary expression

python

parsing

ply