python - Python优先顺序：某些非和+表达式中的语法错误

我相信这是在 Python 开发的早期做出的选择。允许按照您的预期进行解析没有理论上的障碍3 + not 2，但 Python 恰好不允许这样做。

与这里似乎普遍的看法相反，它与运算符优先级算法无关。尽管使用运算符优先级（稍微不准确）作为文档辅助工具，但实际的 Python 算法使用上下文无关文法，并且使用的上下文无关文法明确指定以运算符为首的表达式not不能用作算术的操作数操作也不是比较。结果，表达式很简单- not False，True == not False也会产生语法错误。

这是Python 参考手册中的语法摘录。该语法用于生成 Python 解析器，因此具有权威性，即使它作为文档不完全可读。为了使模式更明显，我将产生的间隔分开：（我也遗漏了很多产生，并非所有这些都是完全不相关的。如果您寻求更多细节，请查阅原件。）

not_test: 'not' not_test | comparison

comparison: expr       ( comp_op                expr )*
expr:       xor_expr   ( '|'                    xor_expr )*
xor_expr:   and_expr   ( '^'                    and_expr )*
and_expr:   shift_expr ( '&'                    shift_expr )*
shift_expr: arith_expr ( ('<<'|'>>')            arith_expr )*
arith_expr: term       ( ('+'|'-')              term )*
term:       factor     ( ('*'|'@'|'/'|'%'|'//') factor)*

factor:     ( '+'|'-'|'~') factor | power
power:      atom_expr  ['**' factor]

您可以从该语法中看到，以开头的所有作品comparison都不能包含not_expression. 这就是定义notrelative 相对于比较运算符的优先级（因此not a == b相当于not (a == b)）。但这不仅可以防止not a作为运算符被误解析为==; 它还防止not a被用作的右手运算符==，这就是为什么True == not False是语法错误而不是重言式的原因。

并且由于该摘录中的所有其他运算符比比较运算符绑定得更紧密，它们都与具有相同的关系not。

某些语言（如从 C 派生的语言）不会not以这种方式降低的优先级。在 C 中，布尔否定运算符!与任何其他一元运算符具有相同的优先级，因此它比比较运算符（或算术运算符）绑定得更紧密。因此，在 C 中，! a < b确实意味着(!a) < b，即使这可能没有那么有用。但是许多其他语言，包括大多数 SQL 方言，NOT在优先级图表中的位置与 Python 相同：在二进制布尔运算符和比较运算符之间。[注 2] 此外，大多数 SQL 方言确实允许将其NOT用作比较运算符的操作数。尽管如此，所有这些语法都基于相同的上下文无关形式主义。[注3]

那么他们是怎么做到的呢？编写一个明确的上下文无关语法，not即使在比较和算术语法的操作数中也可以用作一元运算符，这是一项具有挑战性的练习，阅读该语法也很重要。然而，一种非常古老的解析技术使得创建解析器几乎是微不足道的。该技术称为“运算符优先级”，您几乎可以在每个现代解析框架中找到它。然而，正如我们将看到的，它经常被误解，并且并不总是得到很好的实施。

例如，这是一个在Sly的帮助下编写的简单 AST 构建器。这是一个文件，但为了便于阅读，我将其拆分为三个代码块。首先，词法分析器，在这里并不真正相关：

from sly import Lexer, Parser

class CalcLexer(Lexer):
    tokens = { NAME, NUMBER, POW, LE, GE, NE, AND, OR, NOT, TRUE, FALSE }
    ignore = ' \t'
    literals = { '=', '<', '>', '+', '-', '*', '/', '(', ')' }

    # Multicharacter symbol tokens
    LE = r'<='
    GE = r'>='
    NE = r'!= | <>'
    POW = r'\*\*'

    # Keyword tokens (and identifiers)
    NAME = r'[a-zA-Z_][a-zA-Z0-9_]*'
    NAME['and']   = AND
    NAME['false'] = FALSE
    NAME['not']   = NOT
    NAME['or']    = OR
    NAME['true']  = TRUE

    @_(r'\d+')
    def NUMBER(self, t):
        t.value = int(t.value)
        return t

    @_(r'\n+')
    def newline(self, t):
        self.lineno += t.value.count('\n')

    def error(self, t):
        print("Illegal character '%s'" % t.value[0])
        self.index += 1

现在，解析器。注意靠近顶部的优先级定义：

class CalcParser(Parser):
    tokens = CalcLexer.tokens

    precedence = (
        ('left', OR),
        ('left', AND),
        ('right', NOT),
        ('left', '=', NE),
        ('left', '<', LE, GE, '>'),
        ('left', '+', '-'),
        ('left', '*', '/'),
        ('right', UMINUS),
        ('right', POW),
    )

    @_('expr')
    def statement(self, p):
        print(p.expr)

    @_('expr OR expr')
    @_('expr AND expr')
    @_('expr "=" expr')
    @_('expr NE expr')
    @_('expr "<" expr')
    @_('expr LE expr')
    @_('expr GE expr')
    @_('expr ">" expr')
    @_('expr "+" expr')
    @_('expr "-" expr')
    @_('expr "*" expr')
    @_('expr "/" expr')
    @_('expr POW expr')
    def expr(self, p):
        return [p[1], p.expr0, p.expr1]

    @_('"-" expr %prec UMINUS')
    @_('NOT expr')
    def expr(self, p):
        return [p[0], p.expr]

    @_('"(" expr ")"')
    def expr(self, p):
        return p.expr

    @_('NUMBER')
    @_('NAME')
    @_('TRUE')
    @_('FALSE')
    def expr(self, p):
        return p[0]

最后，一个简单的驱动程序：

if __name__ == '__main__':
    try:
        import readline
    except:
        pass

    lexer = CalcLexer()
    parser = CalcParser()
    while True:
        try:
            text = input('calc > ')
        except EOFError:
            break
        if text:
            parser.parse(lexer.tokenize(text))

和一个快速测试，这表明它具有（希望）预期的行为：

$ python3 calc.py
calc > 3+4
['+', 3, 4]
calc > 3+not 4
['+', 3, ['not', 4]]
calc > not 3 + 4
['not', ['+', 3, 4]]
calc > not 3*4<7
['not', ['<', ['*', 3, 4], 7]]
calc > not 3*4<7 and not true
['and', ['not', ['<', ['*', 3, 4], 7]], ['not', 'true']]

在 LR 解析变得实用之前（使用 Frank deRemer 的有效算法来构造 LALR(1) 解析器），通常使用所谓的“运算符优先级”解析器，这在 1963 年由 Robert W. Floyd 的一篇论文中首次描述,句法分析和运算符优先级[注4]。运算符优先级解析器是 [shift-reduce 解析器]，其移位和归约动作基于“优先关系”矩阵执行，由解析器堆栈顶部的运算符和输入中下一个出现的运算符索引溪流。矩阵中的每个条目都有四个可能值之一：

⋖，表示输入符号要移位。
⋗，表示堆栈符号应该减少。
≐，表示堆栈符号和前瞻符号属于同一个产生式。
empty，表示语法错误。

尽管它们与比较运算符相似，但 Floyd 描述的优先关系甚至不是偏序，因为它们不是传递的，也不是反对称的。但在大多数实用语法中，它们可以简化为数字比较，有两个主要警告：

原始关系矩阵包含空条目，表示非法语法。减少与数值比较的关系会给每个条目一个定义的值，因此生成的解析器将无法检测到一些语法错误。
因为优先关系并不是真正的比较，所以通常不可能用单个数字映射来表示它们。您需要使用两个函数，“左优先”和“右优先”，一个用于左侧运算符，另一个用于右侧运算符。

从某种意义上说，这些问题中的第一个并没有那么严重，因为弗洛伊德的算法本身并不一定能检测出所有的语法错误。实际上，运算符优先级解析消除了不同非终结符之间的差异；所有归约动作都会产生一种通用的非终结符，它可能会丢失区分不同句法情况所需的信息。如果信息丢失导致无法在两种不同的归约之间做出决定，则无法使用运算符优先级解析语法。但更常见的是信息丢失导致无法检测到语法错误，这可能被认为是可以接受的。

无论如何，弗洛伊德的算法变得非常流行。它被用来为许多语言构建解析器，并产生了一些仍在流行使用的范例，例如调车场算法。

一般来说，计算一个优先矩阵然后将其简化为一对函数是很难手工完成的。但在一个特定领域——代数表达式——结果非常直观，以至于它们已经取代了最初的定义。如果要解析没有括号和一元运算符的代数表达式，只需将运算符分组到优先级即可。每个级别都分配了两个连续的整数（并且没有两个级别使用相同的整数），用作左右优先级值。

有两个整数来区分左关联运算符和右关联运算符：对于左关联级别，左优先级是两个整数中较大的一个；对于右关联级别，右优先级更大。

这不是唯一的解决方案。你会发现很多其他人。例如，很常见的是将其描述为单个整数，并带有两个状态的枚举（关联性），如果比较的两个整数相等，则考虑关联性。这种“简化”通常不适用于运算符优先级语法，因为括号和一元运算符不能简单地从语言中移除。但是，如果在应用优先规则的上下文中，解析框架已经处理了括号，这可能是可以接受的。

使用运算符优先级解析器处理括号没有问题。当您坚持符号的左右优先级是连续整数（或单个整数和一个标志）时，就会出现问题：

(总是移到堆栈上，这意味着它的右优先级高于任何运算符的左优先级。
当(位于栈顶时，没有运算符会导致它被归约，这意味着它的左优先级低于任何运算符的右优先级。（它最终被匹配减少)）。

一元运算符具有类似的不对称性。前缀运算符也总是移位，因为没有前面的非终结符可以减少。但是，如图NOT所示，运算符的优先级不一定高于任何后续运算符。所以它的左优先级和右优先级可以相差很大。

（未完待续）

笔记：

如果我们只是想检查表达式的语法，我们可以消除 and 中的递归产生not_test式factor，这可能会造成混淆。我们可以改为：
```
not_test:              ( 'not' )* comparison
factor:                ( '+'|'-'|'~'|atom_expr '**')* atom_expr
```
但这不会产生正确的解析，因为它不会将运算符与其参数相关联。例如，从右到左应用取幂是必不可少的。此外，我们通常不能通过not某种方式将not前缀运算符序列合并为单个运算符来进行评估。
这只是为了展示任意运算符优先级是如何的。确实没有通用标准；甚至有些语言中所有运算符都具有相同的优先级，因此分组严格从右到左。
新的 Python 解析器实际上是 Parsing Expression Grammar (PEG)，也是形式主义的pyparsing实现。PEG 与上下文无关语法完全不同，但在这个特殊的小角落里，差异并不重要。
令人愤慨的是，ACM（这篇文章首次出现在其期刊上）认为收取 15 美元的费用是合理的，这样人们就可以阅读近 60 年前发表的一篇 18 页的论文。这是付费专区的链接，以防您觉得有用。

python - Python优先顺序：某些非和+表达式中的语法错误

问题描述

解决方案

笔记：

推荐阅读