Python PLY Yacc - 解析复数除法
Python PLY Yacc - Parsing division of complex numbers
我正在 Python 中实现一个计算器，以便能够对实数和复数进行一些数学运算。
我有一个使用 PLY 的 lexer/parser，我正在为复数创建自己的 class，自愿忽略 Python 已经有复数的内置类型这一事实数字。
解析器工作正常，除了这种情况：
42i/2i
我的解析器是这样解释这种情况的：
42i/2i = (42*i)/(2*i) = 21
正如您在上面看到的，每个复数都像一个块，实部与虚部密不可分。但数学真理是不同的。您可能知道，这种情况应按以下方式处理：
42i/2i = 42*i/2*i = -21
我应该调整我的解析器规则以获得正确的结果，但我不知道该怎么做。
这是一个最小的可重现示例：
import ply.lex as lex
import ply.yacc as yacc
tokens = (
'NUMBER',
'DIVIDE',
'IMAGINE',
)
########################## LEXER ##########################
t_DIVIDE = r'\/'
def t_NUMBER(t):
r'\d+(\.\d+)?'
t.value = int(t.value)
return t
def t_IMAGINE(t):
r'i'
t.value = Complex(0, 1)
return t
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
########################## PARSER #########################
def p_expression_binop(t):
'''expression : expression DIVIDE expression'''
t[0] = t[1] / t[3]
print(t[0])
def p_expression_number(t):
'''expression : NUMBER
| IMAGINE'''
t[0] = t[1]
def p_expression_imaginary(t):
'''expression : NUMBER IMAGINE'''
t[0] = t[1] * t[2]
def p_error(t):
print("Syntax error!")
###################### COMPLEX CLASS ######################
class Complex(object):
def __init__(self, real, imag=0):
self.real = real
self.imag = imag
def __str__(self):
string = ''
if self.real != 0:
if self.real % 1 == 0 : self.real = int(self.real)
string += str(self.real)
if self.imag != 0:
if self.imag % 1 == 0 : self.imag = int(self.imag)
if self.real != 0:
string += ' + ' if self.imag > 0 else ' - '
else:
string += '' if self.imag > 0 else '-'
if abs(self.imag) != 1:
string += str(abs(self.imag)) + 'i'
else:
string += 'i'
return string or '0'
def __mul__(self, other):
return Complex(self.real * other.real - self.imag * other.imag,
self.imag * other.real + self.real * other.imag)
def __rmul__(self, other):
return self.__mul__(other)
def __truediv__(self, other):
if isinstance(other, (float,int)):
other = Complex(other)
s1, s2, o1, o2 = self.real, self.imag, other.real, other.imag
r = float(o1 ** 2 + o2 ** 2)
return Complex((s1 * o1 + s2 * o2) / r, ( s2 * o1 - s1 * o2) / r)
def __rtruediv__(self, other):
if isinstance(other, (float,int)):
other = Complex(other)
return other.__truediv__(-self)
########################## MAIN ##########################
lexer = lex.lex()
while True:
try:
s = raw_input('> ')
except:
s = input('> ')
if s:
parser = yacc.yacc()
parser.parse(s)
有什么帮助吗？非常感谢！
您的程序中缺少一件事：
precedence = (
('left', 'DIVIDE'),
)
没有它，Ply 在生成解析器时会产生移位减少冲突，因为产生式
expression : expression DIVIDE expression
我提到这一点只是因为手头的问题是运算符优先级之一，尽管所讨论的运算符是不可见的：产生式中包含的隐式乘法运算符：
expression : NUMBER IMAGINE
即使没有优先级声明，第二个产生式也不会导致任何解析冲突，但那是因为它不够通用，无法实际解析有用的表达式。例如，考虑你的例子
42i/4i
如您所说，您的解析器将其解释为
[expression: [expression: 42 i]
/
[expression: 4 i] ]
但您希望它被解释为：
[expression: [expression: [expression: 42 i]
/
[expression: 4]
i]
]
但是很明显最外层的expression不能从你的文法中生成，因为你的文法要求隐式乘法的左手运算符是一个NUMBER，而在这个解析中它是显然是 expression.
在我们添加产品之前
expression : expression IMAGINE
我们或许应该尝试想象所有可能的用例。其中之一应该 spring 立即引起注意：4i<sup>2</sup>（省略了您选择哪个运算符来表示求幂的详细信息） .
不正确的“融合数-虚数”语法会将其视为 4i 的平方（即 -16），但普遍接受的解析是 i 的四倍（即 -4)。这将对应于 parse
[expression: [expression: 4]
[expression: [expression: i]
POWER
[expression: 2]]]
其中隐式乘法的右手参数不是虚数，而是表达式。
因此，您的首要任务是确定通用隐式乘法在您的语言中的表现如何。以下所有内容都有效吗？ （有些要求您的词法分析器丢弃空格）
4i
i4
(4*5)i
4(7+i)
(4+i)(7-i)
i i
4 i
4 7
您可能会怀疑最后几个，但我敢猜测其中的大部分不会引起任何意外。如果需要，我们稍后可以看看如何拒绝两个连续数字的情况，但看起来最合理的隐式乘法规则至少类似于最一般的：
expression : expression expression
此外，它与除法或显式乘法具有完全相同的优先级和结合性。
但这给我们留下了一个问题：当没有运算符时，如何将运算符放在优先级 table 中？简短的回答是，你不能。有一些或多或少有用的技巧，但最简单和最易读的替代方法是编写语法，以便优先级明确。
我不会再深入探讨这种风格了，因为它在其他地方已经被打死了，你可以在整个互联网上找到例子（其中大部分使用名为 term 和 factor，我在这里没有使用它，因为我认为它们的含义非常晦涩，以至于很多人都把它们弄反了）。我会写出带有动作函数的 PLY 风格的语法。
关于动作函数的一个注意事项：Ply 允许您将两个作品与相同的动作结合起来。这很方便，但这并不意味着您应该这样做：
def p_additive(p):
""" additive : additive '+' multiplicative
additive : additive '-' multiplicative
multiplicative : multiplicative '*' value
multiplicative : multiplicative '/' value
...
"""
if p[2] == '+' then:
p[0] = p[1] + p[3]
else if p[2] == '-' then:
p[0] = p[1] - p[3]}
else if p[2] == '*' then:
p[0] = p[1] * p[3]}
else if p[2] == '/' then:
p[0] = p[1] / p[3]}
要了解这有多愚蠢，请考虑解析器到达那里的过程。首先，解析器准确地找出匹配的产生式。假设产量是 expression : additive '-' multiplicative。然后它查找从产生式到函数的对应关系，并找到上面的函数（如果产生式涉及任何其他二元运算符，它会找到完全相同的函数）。所以它调用了那个函数，此时关于哪个产品匹配的信息实际上已经丢失了。
这意味着该功能必须做的第一件事是找出减少了哪些产量，这已经被弄清楚了。然后它通过一次检查一个运算符和它知道的运算符来做到这一点，这完全是在浪费周期。
我希望这足以解释为什么以下语法不使用这样的函数。如果您正在编写一个 Ply 解析器动作函数并且您发现自己使用 if 语句来检查哪个产生式被匹配，您应该立即考虑使用两个（或更多）不同的动作函数来代替。 （如果操作具有共同特征，请考虑将它们分解为一个子函数。结果可能更具可读性和可维护性。）
注：我这里用的是Python的复数。无论您不这样做的原因是什么，除了向解析器添加一堆代码之外，它对解析练习的影响为零。
import ply.lex as lex
import ply.yacc as yacc
### Lexer
# This lexer uses literal character tokens wherever possible. They're
# easier, faster, and more readable.
# (https://www.dabeaz.com/ply/ply.html#ply_nn11)
literals = '()+-*/^i'
t_ignore = ' \t'
tokens = ( 'NUMBER', )
def t_NUMBER(t):
"(?:\d+(?:\.\d*)?|\.\d+)(?:[Ee][+-]?\d+)?"
t.value = float(t.value)
return t
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
### Parser
# Use this function for any unit production which just passes
# its value through.
def p_unit(p):
""" expression : additive
additive : multiplicative
multiplicative : exponential
exponential : value
value : NUMBER
"""
p[0] = p[1]
def p_plus(p):
""" additive : additive '+' multiplicative """
p[0] = p[1] + p[3]
def p_minus(p):
""" additive : additive '-' multiplicative """
p[0] = p[1] - p[3]
# Compare this production with the next one.
def p_implicit_times(p):
""" multiplicative : multiplicative exponential """
p[0] = p[1] * p[2]
def p_times(p):
""" multiplicative : multiplicative '*' exponential """
p[0] = p[1] * p[3]
# TODO: catch errors
def p_divide(p):
""" multiplicative : multiplicative '/' exponential """
p[0] = p[1] / p[3]
# This one is right-associative.
# TODO: catch errors
def p_power(p):
""" exponential : value '^' exponential """
p[0] = p[1] ** p[3]
def p_i(p):
""" value : 'i' """
p[0] = 1J # Python's way of writing 0+1i
def p_paren(p):
""" value : '(' expression ')' """
p[0] = p[2]
def p_error(t):
print("Syntax error at " + str(t))
### Very simple driver
import sys
lexer = lex.lex()
parser = yacc.yacc()
while True:
try:
print(parser.parse(input('> ')))
except EOFError:
break
except:
print(sys.exc_info()[1])
查看我从 parser.out:
中提取的语法可能会有用
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> exponential
Rule 4 exponential -> value
Rule 5 value -> NUMBER
Rule 6 additive -> additive + multiplicative
Rule 7 additive -> additive - multiplicative
Rule 8 multiplicative -> multiplicative exponential
Rule 9 multiplicative -> multiplicative * exponential
Rule 10 multiplicative -> multiplicative / exponential
Rule 11 exponential -> value ^ exponential
Rule 12 value -> i
Rule 13 value -> ( expression )
好的，现在让我们考虑一个重要的情况，我们确实需要修改隐式乘法的语法以避免冲突。问题是看似无害的表达式 4 - 2。现在，假设我们的语法实现了一元减号（上面的语法没有实现）。在那种情况下，将有两种解析表达式的方法：作为减法，以及作为两个子表达式 4 和 -2.
的隐式乘积
显然，第二种解释是错误的，这意味着我们不能允许一元表达式作为隐式乘法产生式的第二个参数。
幸运的是，我们已经放弃了尝试使用优先声明来消除语法歧义的想法。如果我们想弄清楚如何修改
expression : expression expression
这样第二个表达式就不能以一元减运算符开头，我们就有大麻烦了。
另一个幸运的是，在标准代数符号中，求幂运算符是右结合的，并且在左侧的绑定比一元减号更紧密，因此 -2<sup>4</sup> 的计算结果为 -16 (-(2<sup>4</sup>)) 而不是 16 (( -2)<sup>4</sup>).
当我们把它们放在一起时，允许一元减号的修改几乎是微不足道的。我们将一元减号插入其逻辑所属的优先级层次结构中，与求幂处于同一级别。 [见注释 1] 但我们需要做一个例外，以便隐式乘法产生式不能将一元负表达式作为其右手参数。为此，我们需要将关卡分成两部分，如下所示：
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> unary
Rule 4 unary -> exponential
Rule 5 exponential -> value
Rule 6 value -> NUMBER
Rule 7 additive -> additive + multiplicative
Rule 8 additive -> additive - multiplicative
Rule 9 multiplicative -> multiplicative exponential
Rule 10 multiplicative -> multiplicative * unary
Rule 11 multiplicative -> multiplicative / unary
Rule 12 unary -> - unary
Rule 13 exponential -> value ^ unary
Rule 14 value -> i
Rule 15 value -> ( expression )
备注
- 你会发现许多语法坚持不同的优先级，但如果你稍微考虑一下，你会发现由于求幂是右结合的，它可以与一元减号共享一个优先级。如果不清楚，这可能是优先声明往往会造成混淆这一事实的额外证据，除非在非常简单的用途中。
我正在 Python 中实现一个计算器，以便能够对实数和复数进行一些数学运算。
我有一个使用 PLY 的 lexer/parser，我正在为复数创建自己的 class，自愿忽略 Python 已经有复数的内置类型这一事实数字。
解析器工作正常，除了这种情况：
42i/2i
我的解析器是这样解释这种情况的：
42i/2i = (42*i)/(2*i) = 21
正如您在上面看到的，每个复数都像一个块，实部与虚部密不可分。但数学真理是不同的。您可能知道，这种情况应按以下方式处理：
42i/2i = 42*i/2*i = -21
我应该调整我的解析器规则以获得正确的结果，但我不知道该怎么做。 这是一个最小的可重现示例：
import ply.lex as lex
import ply.yacc as yacc
tokens = (
'NUMBER',
'DIVIDE',
'IMAGINE',
)
########################## LEXER ##########################
t_DIVIDE = r'\/'
def t_NUMBER(t):
r'\d+(\.\d+)?'
t.value = int(t.value)
return t
def t_IMAGINE(t):
r'i'
t.value = Complex(0, 1)
return t
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
########################## PARSER #########################
def p_expression_binop(t):
'''expression : expression DIVIDE expression'''
t[0] = t[1] / t[3]
print(t[0])
def p_expression_number(t):
'''expression : NUMBER
| IMAGINE'''
t[0] = t[1]
def p_expression_imaginary(t):
'''expression : NUMBER IMAGINE'''
t[0] = t[1] * t[2]
def p_error(t):
print("Syntax error!")
###################### COMPLEX CLASS ######################
class Complex(object):
def __init__(self, real, imag=0):
self.real = real
self.imag = imag
def __str__(self):
string = ''
if self.real != 0:
if self.real % 1 == 0 : self.real = int(self.real)
string += str(self.real)
if self.imag != 0:
if self.imag % 1 == 0 : self.imag = int(self.imag)
if self.real != 0:
string += ' + ' if self.imag > 0 else ' - '
else:
string += '' if self.imag > 0 else '-'
if abs(self.imag) != 1:
string += str(abs(self.imag)) + 'i'
else:
string += 'i'
return string or '0'
def __mul__(self, other):
return Complex(self.real * other.real - self.imag * other.imag,
self.imag * other.real + self.real * other.imag)
def __rmul__(self, other):
return self.__mul__(other)
def __truediv__(self, other):
if isinstance(other, (float,int)):
other = Complex(other)
s1, s2, o1, o2 = self.real, self.imag, other.real, other.imag
r = float(o1 ** 2 + o2 ** 2)
return Complex((s1 * o1 + s2 * o2) / r, ( s2 * o1 - s1 * o2) / r)
def __rtruediv__(self, other):
if isinstance(other, (float,int)):
other = Complex(other)
return other.__truediv__(-self)
########################## MAIN ##########################
lexer = lex.lex()
while True:
try:
s = raw_input('> ')
except:
s = input('> ')
if s:
parser = yacc.yacc()
parser.parse(s)
有什么帮助吗？非常感谢！
您的程序中缺少一件事：
precedence = (
('left', 'DIVIDE'),
)
没有它，Ply 在生成解析器时会产生移位减少冲突，因为产生式
expression : expression DIVIDE expression
我提到这一点只是因为手头的问题是运算符优先级之一，尽管所讨论的运算符是不可见的：产生式中包含的隐式乘法运算符：
expression : NUMBER IMAGINE
即使没有优先级声明，第二个产生式也不会导致任何解析冲突，但那是因为它不够通用，无法实际解析有用的表达式。例如，考虑你的例子
42i/4i
如您所说，您的解析器将其解释为
[expression: [expression: 42 i]
/
[expression: 4 i] ]
但您希望它被解释为：
[expression: [expression: [expression: 42 i]
/
[expression: 4]
i]
]
但是很明显最外层的expression不能从你的文法中生成，因为你的文法要求隐式乘法的左手运算符是一个NUMBER，而在这个解析中它是显然是 expression.
在我们添加产品之前
expression : expression IMAGINE
我们或许应该尝试想象所有可能的用例。其中之一应该 spring 立即引起注意：4i<sup>2</sup>（省略了您选择哪个运算符来表示求幂的详细信息） .
不正确的“融合数-虚数”语法会将其视为 4i 的平方（即 -16），但普遍接受的解析是 i 的四倍（即 -4)。这将对应于 parse
[expression: [expression: 4]
[expression: [expression: i]
POWER
[expression: 2]]]
其中隐式乘法的右手参数不是虚数，而是表达式。
因此，您的首要任务是确定通用隐式乘法在您的语言中的表现如何。以下所有内容都有效吗？ （有些要求您的词法分析器丢弃空格）
4i
i4
(4*5)i
4(7+i)
(4+i)(7-i)
i i
4 i
4 7
您可能会怀疑最后几个，但我敢猜测其中的大部分不会引起任何意外。如果需要，我们稍后可以看看如何拒绝两个连续数字的情况，但看起来最合理的隐式乘法规则至少类似于最一般的：
expression : expression expression
此外，它与除法或显式乘法具有完全相同的优先级和结合性。
但这给我们留下了一个问题：当没有运算符时，如何将运算符放在优先级 table 中？简短的回答是，你不能。有一些或多或少有用的技巧，但最简单和最易读的替代方法是编写语法，以便优先级明确。
我不会再深入探讨这种风格了，因为它在其他地方已经被打死了，你可以在整个互联网上找到例子（其中大部分使用名为 term 和 factor，我在这里没有使用它，因为我认为它们的含义非常晦涩，以至于很多人都把它们弄反了）。我会写出带有动作函数的 PLY 风格的语法。
关于动作函数的一个注意事项：Ply 允许您将两个作品与相同的动作结合起来。这很方便，但这并不意味着您应该这样做：
def p_additive(p):
""" additive : additive '+' multiplicative
additive : additive '-' multiplicative
multiplicative : multiplicative '*' value
multiplicative : multiplicative '/' value
...
"""
if p[2] == '+' then:
p[0] = p[1] + p[3]
else if p[2] == '-' then:
p[0] = p[1] - p[3]}
else if p[2] == '*' then:
p[0] = p[1] * p[3]}
else if p[2] == '/' then:
p[0] = p[1] / p[3]}
要了解这有多愚蠢，请考虑解析器到达那里的过程。首先，解析器准确地找出匹配的产生式。假设产量是 expression : additive '-' multiplicative。然后它查找从产生式到函数的对应关系，并找到上面的函数（如果产生式涉及任何其他二元运算符，它会找到完全相同的函数）。所以它调用了那个函数，此时关于哪个产品匹配的信息实际上已经丢失了。
这意味着该功能必须做的第一件事是找出减少了哪些产量，这已经被弄清楚了。然后它通过一次检查一个运算符和它知道的运算符来做到这一点，这完全是在浪费周期。
我希望这足以解释为什么以下语法不使用这样的函数。如果您正在编写一个 Ply 解析器动作函数并且您发现自己使用 if 语句来检查哪个产生式被匹配，您应该立即考虑使用两个（或更多）不同的动作函数来代替。 （如果操作具有共同特征，请考虑将它们分解为一个子函数。结果可能更具可读性和可维护性。）
注：我这里用的是Python的复数。无论您不这样做的原因是什么，除了向解析器添加一堆代码之外，它对解析练习的影响为零。
import ply.lex as lex
import ply.yacc as yacc
### Lexer
# This lexer uses literal character tokens wherever possible. They're
# easier, faster, and more readable.
# (https://www.dabeaz.com/ply/ply.html#ply_nn11)
literals = '()+-*/^i'
t_ignore = ' \t'
tokens = ( 'NUMBER', )
def t_NUMBER(t):
"(?:\d+(?:\.\d*)?|\.\d+)(?:[Ee][+-]?\d+)?"
t.value = float(t.value)
return t
def t_error(t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
### Parser
# Use this function for any unit production which just passes
# its value through.
def p_unit(p):
""" expression : additive
additive : multiplicative
multiplicative : exponential
exponential : value
value : NUMBER
"""
p[0] = p[1]
def p_plus(p):
""" additive : additive '+' multiplicative """
p[0] = p[1] + p[3]
def p_minus(p):
""" additive : additive '-' multiplicative """
p[0] = p[1] - p[3]
# Compare this production with the next one.
def p_implicit_times(p):
""" multiplicative : multiplicative exponential """
p[0] = p[1] * p[2]
def p_times(p):
""" multiplicative : multiplicative '*' exponential """
p[0] = p[1] * p[3]
# TODO: catch errors
def p_divide(p):
""" multiplicative : multiplicative '/' exponential """
p[0] = p[1] / p[3]
# This one is right-associative.
# TODO: catch errors
def p_power(p):
""" exponential : value '^' exponential """
p[0] = p[1] ** p[3]
def p_i(p):
""" value : 'i' """
p[0] = 1J # Python's way of writing 0+1i
def p_paren(p):
""" value : '(' expression ')' """
p[0] = p[2]
def p_error(t):
print("Syntax error at " + str(t))
### Very simple driver
import sys
lexer = lex.lex()
parser = yacc.yacc()
while True:
try:
print(parser.parse(input('> ')))
except EOFError:
break
except:
print(sys.exc_info()[1])
查看我从 parser.out:
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> exponential
Rule 4 exponential -> value
Rule 5 value -> NUMBER
Rule 6 additive -> additive + multiplicative
Rule 7 additive -> additive - multiplicative
Rule 8 multiplicative -> multiplicative exponential
Rule 9 multiplicative -> multiplicative * exponential
Rule 10 multiplicative -> multiplicative / exponential
Rule 11 exponential -> value ^ exponential
Rule 12 value -> i
Rule 13 value -> ( expression )
好的，现在让我们考虑一个重要的情况，我们确实需要修改隐式乘法的语法以避免冲突。问题是看似无害的表达式 4 - 2。现在，假设我们的语法实现了一元减号（上面的语法没有实现）。在那种情况下，将有两种解析表达式的方法：作为减法，以及作为两个子表达式 4 和 -2.
显然，第二种解释是错误的，这意味着我们不能允许一元表达式作为隐式乘法产生式的第二个参数。
幸运的是，我们已经放弃了尝试使用优先声明来消除语法歧义的想法。如果我们想弄清楚如何修改
expression : expression expression
这样第二个表达式就不能以一元减运算符开头，我们就有大麻烦了。
另一个幸运的是，在标准代数符号中，求幂运算符是右结合的，并且在左侧的绑定比一元减号更紧密，因此 -2<sup>4</sup> 的计算结果为 -16 (-(2<sup>4</sup>)) 而不是 16 (( -2)<sup>4</sup>).
当我们把它们放在一起时，允许一元减号的修改几乎是微不足道的。我们将一元减号插入其逻辑所属的优先级层次结构中，与求幂处于同一级别。 [见注释 1] 但我们需要做一个例外，以便隐式乘法产生式不能将一元负表达式作为其右手参数。为此，我们需要将关卡分成两部分，如下所示：
Rule 1 expression -> additive
Rule 2 additive -> multiplicative
Rule 3 multiplicative -> unary
Rule 4 unary -> exponential
Rule 5 exponential -> value
Rule 6 value -> NUMBER
Rule 7 additive -> additive + multiplicative
Rule 8 additive -> additive - multiplicative
Rule 9 multiplicative -> multiplicative exponential
Rule 10 multiplicative -> multiplicative * unary
Rule 11 multiplicative -> multiplicative / unary
Rule 12 unary -> - unary
Rule 13 exponential -> value ^ unary
Rule 14 value -> i
Rule 15 value -> ( expression )
备注
- 你会发现许多语法坚持不同的优先级，但如果你稍微考虑一下，你会发现由于求幂是右结合的，它可以与一元减号共享一个优先级。如果不清楚，这可能是优先声明往往会造成混淆这一事实的额外证据，除非在非常简单的用途中。