我正在Python中实现一个计算器,以便能够对实数和复数进行一些数学运算。
我有一个使用PLY的词法分析器/解析器,我正在为复数创建自己的类,但自愿忽略了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
我们可能应该尝试想象所有可能的用例。并且其中之一应该立即浮现在脑海:
4i2
(省略了您选择代表幂运算符的详细信息)。
[不正确的“融合数-虚数”语法将看到它是4i
的平方(即-16),但通常接受的解析是i
的平方(即-4)的四倍。那将对应于解析]
[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
此外,它具有与除法或显式乘法完全相同的优先级和关联性。
但是这给我们带来了一个问题:如果没有运算符,如何将运算符放在优先级表中?简短的答案是,你不能。有一些技巧或多或少起作用,但是最简单,最易读的替代方法是编写语法,使优先顺序明确。
我不会再采用这种风格,因为它在其他地方被打死了,您在互联网上查找示例也没有问题(大多数示例使用名为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
为了使第二个表达式不能以一元减号开头,我们会遇到很大麻烦。
作为另一招,在标准的代数符号中,幂运算符是右缔合的,并且比一元减符更紧密地绑定在左侧,因此-24
的值为-16(-(24)
)而不是16([ C0])。
当我们将它们放在一起时,允许一元负的修改几乎是微不足道的。我们在逻辑上所属的优先级层次中插入一元减号,与求幂的级别相同。 [请参见注释1]但是我们需要做一个例外,以便隐式乘法产生不能将一元减表达式作为其右手参数。为此,我们需要将关卡分为两部分,如下所示:
(-2)4
注意