Python 优先顺序：某些 not 和 + 表达式中的语法错误
Python precedence order: SyntaxError in certain not and + expressions
在Python中，为什么
3 + not 2
导致语法错误，而
not 3 + 2
解析正常？我在 https://docs.python.org/3/reference/expressions.html#operator-precedence 看到 not 低于 +，但对我来说，这并不能真正解释为什么它不能解析 3 + not 2。
这个问题是通过调查
触发的
parses fine? I see at https://docs.python.org/3/reference/expressions.html#operator-precedence that not is lower than +, but to me, that doesn't really explain why it can't parse 3 + not 2.
意味着你尝试像 (3 + not) 2 这样计算，这是错误的：“not”运算符不适合“+”运算符作为操作数。
没错：
not is lower than +
所以：
not 3 + 2 => not (3 + 2) => not 5 => False
因此：
3 + not 2 => (3 + not) 2 => ERROR
因为not有取一个参数:
>>> not
File "<stdin>", line 1
not
^
SyntaxError: invalid syntax
我相信这是在 Python 开发的早期做出的选择。允许 3 + not 2 按照您的预期进行解析在理论上没有障碍，但 Python 恰好不允许这样做。
与这里的普遍看法相反，它与运算符优先级算法无关。尽管使用运算符优先级（稍微不准确）作为文档辅助，但实际的 Python 算法使用 context-free 语法，并且使用的 context-free 语法明确指定以 [= 为首的表达式17=] 运算符不能用作算术运算或比较的操作数。因此，像 - not False 和 True == not False 这样简单的表达式也会产生语法错误。
这是来自 the Python reference manual 的语法摘录。此语法用于生成 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]
从该语法可以看出，none 以 comparison 开头的产生式可以包含 not_expression。这就是定义 not 相对于比较运算符的优先级的原因（因此 not a == b 等同于 not (a == b)）。但这不仅可以防止 not a 被误认为是 == 的运算符；它还可以防止 not a 被用作 == 的 right-hand 运算符，这就是为什么 True == not False 是语法错误而不是重言式。
并且由于该摘录中的所有其他运算符比比较运算符绑定得更紧密，因此它们都与 not 具有相同的关系。
有些语言（比如从 C 派生的语言）不会以这种方式降低 not 的优先级。在 C 中，布尔否定运算符 ! 与任何其他一元运算符具有相同的优先级，因此它比比较运算符（或算术运算符）绑定得更紧密。因此，在 C 中，! a < b 确实意味着 (!a) < b，尽管这可能没有那么有用。但是许多其他语言，包括大多数 SQL 方言，将 NOT 放在与 Python 相同级别的优先级图中：二元布尔运算符和比较运算符之间。 [注 2] 此外，大多数 SQL 方言 do 允许使用 NOT 作为比较运算符的操作数。 none尽管如此，所有这些语法都基于相同的 context-free 形式主义。 [注3]
那么他们是怎么做到的呢？写出一个明确的 context-free 语法，允许 not 用作一元运算符，即使在比较和算术语法的操作数中也是一项具有挑战性的练习，阅读该语法也是 non-trivial。然而，一种非常古老的解析技术使得创建解析器变得几乎微不足道。该技术称为“运算符优先级”，几乎在每个现代解析框架中都会发现它。然而，正如我们将要看到的，它经常被误解，而且并不总是得到很好的实施。
例如，这是在 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) 解析器），通常使用 so-called "operator-precedence" 解析器，这首先在1963 年在 Robert W. Floyd 的一篇论文中，句法分析和运算符优先级 [注 4]。运算符优先解析器是 [shift-reduce 解析器]，其移位和归约操作是基于“优先关系”矩阵执行的，由解析器堆栈顶部的运算符和下一个出现的运算符索引输入流。矩阵中的每个条目都具有四个可能值之一：
- ⋖，表示输入的符号要平移。
- ⋗，表示堆栈符号应该减少。
- ≐，表示堆栈符号和前瞻符号属于同一个产生式。
- 空，表示语法错误。
尽管它们与比较运算符相似，但 Floyd 描述的优先关系甚至不是偏序，因为它们既不传递也不反对称。但在大多数实用语法中，它们可以简化为数值比较，有两个主要警告：
原始关系矩阵包含空条目，表示非法语法。将关系简化为数值比较，为每个条目提供一个定义的值，因此生成的解析器将无法检测到一些语法错误。
因为优先关系并不是真正的比较，所以一般不可能用单一的数值映射来表示。你需要用到“左优先”和“右优先”两个函数，一个用于左边的运算符，一个用于右边的运算符。
从某种意义上说，第一个问题并没有那么严重，因为弗洛伊德算法本身并不一定能检测出所有语法错误。实际上，运算符优先级解析消除了不同 non-terminals 之间的差异；所有归约动作都会产生一种通用的 non-terminal，这可能会丢失区分不同句法情况所需的信息。如果信息丢失导致无法在两种不同的缩减之间做出决定，则无法使用运算符优先级解析文法。但更常见的是信息丢失导致无法检测到语法错误，这可能被认为是可以接受的。
无论如何，弗洛伊德算法变得非常流行。它被用于为多种语言构建解析器，并产生了一些仍在流行使用的范例，例如调车场算法。
一般来说，计算优先矩阵然后将其简化为一对函数很难手工完成。但在一个特定领域——代数表达式——结果非常直观，以至于它们已经取代了原来的定义。如果你想解析一个没有括号和一元运算符的代数表达式，你可以通过简单地将运算符分组到优先级别来实现。每个级别都分配了两个连续的整数（没有两个级别使用相同的整数），用作左值和 right-precedence 值。
为了区分左运算符和right-associative运算符，有两个整数：对于left-associative级别，left-precedence是两个整数中的较大者；对于 right-associative 级别，right-precedence 更大。
这不是唯一的解决方案。你会发现很多其他的。例如，将其描述为带有 two-state 枚举（关联性）的单个整数是很常见的，如果比较的两个整数相等，则考虑关联性。这种“简化”通常不适用于运算符优先语法，因为不能简单地将括号和一元运算符从语言中删除。但如果在应用优先规则的上下文中，解析框架已经处理了括号，这可能是可以接受的。
使用运算符优先解析器处理括号没有问题。当您坚持符号的左和 right-precedence 是连续的整数（或单个整数和一个标志）时，问题就出现了：
( 总是 移入堆栈，这意味着它的右优先级高于任何运算符的左优先级。- 当
(在栈顶时，没有运算符导致它减少，这意味着它的左优先级低于任何运算符的右优先级。 （最终被匹配减少)）。
一元运算符也有类似的不对称性。前缀运算符也总是移位，因为没有前面的 non-terminal 减少。但是，如 NOT 的情况所示，该运算符的优先级不一定高于任何后续运算符。所以它的左优先级和右优先级可以相差很大。
(待续)
备注：
如果我们只是想检查表达式的语法，我们可以消除 not_test 和 factor 中的递归产生式，这可能会造成混淆。我们可以改写：
not_test: ( 'not' )* comparison
factor: ( '+'|'-'|'~'|atom_expr '**')* atom_expr
但这不会产生正确的解析，因为它没有将运算符与其参数相关联。例如，必须对 right-to 应用求幂。此外，我们通常无法通过某种方式将一系列 not 前缀运算符合并为单个运算符来评估 not。
这只是为了展示任意运算符的优先级。确实没有通用标准；甚至有些语言的所有运算符都具有相同的优先级，因此分组严格从右到左。
新的Python解析器实际上是一个解析表达式语法（PEG），也是形式主义pyparsing的实现。 PEG 与 context-free 语法完全不同，但在这个特定的小角落，差异并不重要。
令人愤慨的是，ACM（这篇文章首次出现在其期刊上）认为收取 15 美元是合理的，人们可以阅读近 60 年前发表的 18 页论文。这是一个 linkpaywall，以防你觉得有用。
在Python中，为什么
3 + not 2
导致语法错误，而
not 3 + 2
解析正常？我在 https://docs.python.org/3/reference/expressions.html#operator-precedence 看到 not 低于 +，但对我来说，这并不能真正解释为什么它不能解析 3 + not 2。
这个问题是通过调查
parses fine? I see at https://docs.python.org/3/reference/expressions.html#operator-precedence that not is lower than +, but to me, that doesn't really explain why it can't parse 3 + not 2.
意味着你尝试像 (3 + not) 2 这样计算，这是错误的：“not”运算符不适合“+”运算符作为操作数。
没错：
notis lower than+
所以：
not 3 + 2 => not (3 + 2) => not 5 => False
因此：
3 + not 2 => (3 + not) 2 => ERROR
因为not有取一个参数:
>>> not
File "<stdin>", line 1
not
^
SyntaxError: invalid syntax
我相信这是在 Python 开发的早期做出的选择。允许 3 + not 2 按照您的预期进行解析在理论上没有障碍，但 Python 恰好不允许这样做。
与这里的普遍看法相反，它与运算符优先级算法无关。尽管使用运算符优先级（稍微不准确）作为文档辅助，但实际的 Python 算法使用 context-free 语法，并且使用的 context-free 语法明确指定以 [= 为首的表达式17=] 运算符不能用作算术运算或比较的操作数。因此，像 - not False 和 True == not False 这样简单的表达式也会产生语法错误。
这是来自 the Python reference manual 的语法摘录。此语法用于生成 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]
从该语法可以看出，none 以 comparison 开头的产生式可以包含 not_expression。这就是定义 not 相对于比较运算符的优先级的原因（因此 not a == b 等同于 not (a == b)）。但这不仅可以防止 not a 被误认为是 == 的运算符；它还可以防止 not a 被用作 == 的 right-hand 运算符，这就是为什么 True == not False 是语法错误而不是重言式。
并且由于该摘录中的所有其他运算符比比较运算符绑定得更紧密，因此它们都与 not 具有相同的关系。
有些语言（比如从 C 派生的语言）不会以这种方式降低 not 的优先级。在 C 中，布尔否定运算符 ! 与任何其他一元运算符具有相同的优先级，因此它比比较运算符（或算术运算符）绑定得更紧密。因此，在 C 中，! a < b 确实意味着 (!a) < b，尽管这可能没有那么有用。但是许多其他语言，包括大多数 SQL 方言，将 NOT 放在与 Python 相同级别的优先级图中：二元布尔运算符和比较运算符之间。 [注 2] 此外，大多数 SQL 方言 do 允许使用 NOT 作为比较运算符的操作数。 none尽管如此，所有这些语法都基于相同的 context-free 形式主义。 [注3]
那么他们是怎么做到的呢？写出一个明确的 context-free 语法，允许 not 用作一元运算符，即使在比较和算术语法的操作数中也是一项具有挑战性的练习，阅读该语法也是 non-trivial。然而，一种非常古老的解析技术使得创建解析器变得几乎微不足道。该技术称为“运算符优先级”，几乎在每个现代解析框架中都会发现它。然而，正如我们将要看到的，它经常被误解，而且并不总是得到很好的实施。
例如，这是在 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) 解析器），通常使用 so-called "operator-precedence" 解析器，这首先在1963 年在 Robert W. Floyd 的一篇论文中，句法分析和运算符优先级 [注 4]。运算符优先解析器是 [shift-reduce 解析器]，其移位和归约操作是基于“优先关系”矩阵执行的，由解析器堆栈顶部的运算符和下一个出现的运算符索引输入流。矩阵中的每个条目都具有四个可能值之一：
- ⋖，表示输入的符号要平移。
- ⋗，表示堆栈符号应该减少。
- ≐，表示堆栈符号和前瞻符号属于同一个产生式。
- 空，表示语法错误。
尽管它们与比较运算符相似，但 Floyd 描述的优先关系甚至不是偏序，因为它们既不传递也不反对称。但在大多数实用语法中，它们可以简化为数值比较，有两个主要警告：
原始关系矩阵包含空条目，表示非法语法。将关系简化为数值比较，为每个条目提供一个定义的值，因此生成的解析器将无法检测到一些语法错误。
因为优先关系并不是真正的比较，所以一般不可能用单一的数值映射来表示。你需要用到“左优先”和“右优先”两个函数，一个用于左边的运算符，一个用于右边的运算符。
从某种意义上说，第一个问题并没有那么严重，因为弗洛伊德算法本身并不一定能检测出所有语法错误。实际上，运算符优先级解析消除了不同 non-terminals 之间的差异；所有归约动作都会产生一种通用的 non-terminal，这可能会丢失区分不同句法情况所需的信息。如果信息丢失导致无法在两种不同的缩减之间做出决定，则无法使用运算符优先级解析文法。但更常见的是信息丢失导致无法检测到语法错误，这可能被认为是可以接受的。
无论如何，弗洛伊德算法变得非常流行。它被用于为多种语言构建解析器，并产生了一些仍在流行使用的范例，例如调车场算法。
一般来说，计算优先矩阵然后将其简化为一对函数很难手工完成。但在一个特定领域——代数表达式——结果非常直观，以至于它们已经取代了原来的定义。如果你想解析一个没有括号和一元运算符的代数表达式，你可以通过简单地将运算符分组到优先级别来实现。每个级别都分配了两个连续的整数（没有两个级别使用相同的整数），用作左值和 right-precedence 值。
为了区分左运算符和right-associative运算符，有两个整数：对于left-associative级别，left-precedence是两个整数中的较大者；对于 right-associative 级别，right-precedence 更大。
这不是唯一的解决方案。你会发现很多其他的。例如，将其描述为带有 two-state 枚举（关联性）的单个整数是很常见的，如果比较的两个整数相等，则考虑关联性。这种“简化”通常不适用于运算符优先语法，因为不能简单地将括号和一元运算符从语言中删除。但如果在应用优先规则的上下文中，解析框架已经处理了括号，这可能是可以接受的。
使用运算符优先解析器处理括号没有问题。当您坚持符号的左和 right-precedence 是连续的整数（或单个整数和一个标志）时，问题就出现了：
(总是 移入堆栈，这意味着它的右优先级高于任何运算符的左优先级。- 当
(在栈顶时，没有运算符导致它减少，这意味着它的左优先级低于任何运算符的右优先级。 （最终被匹配减少)）。
一元运算符也有类似的不对称性。前缀运算符也总是移位，因为没有前面的 non-terminal 减少。但是，如 NOT 的情况所示，该运算符的优先级不一定高于任何后续运算符。所以它的左优先级和右优先级可以相差很大。
(待续)
备注：
如果我们只是想检查表达式的语法，我们可以消除
not_test和factor中的递归产生式，这可能会造成混淆。我们可以改写：not_test: ( 'not' )* comparison factor: ( '+'|'-'|'~'|atom_expr '**')* atom_expr但这不会产生正确的解析，因为它没有将运算符与其参数相关联。例如，必须对 right-to 应用求幂。此外，我们通常无法通过某种方式将一系列
not前缀运算符合并为单个运算符来评估not。这只是为了展示任意运算符的优先级。确实没有通用标准；甚至有些语言的所有运算符都具有相同的优先级，因此分组严格从右到左。
新的Python解析器实际上是一个解析表达式语法（PEG），也是形式主义
pyparsing的实现。 PEG 与 context-free 语法完全不同，但在这个特定的小角落，差异并不重要。令人愤慨的是，ACM（这篇文章首次出现在其期刊上）认为收取 15 美元是合理的，人们可以阅读近 60 年前发表的 18 页论文。这是一个 linkpaywall，以防你觉得有用。