CNxiaolin 2018-11-27 12:19
浏览 726

一道python实现简单编译器的问题

请基于四则运算简单语法,增加带符号(正号或负号)数的语法,并修改所给的程序,实现对带符号数四则运算的求值。

为支持带符号数的编译,在教材案例基础上,添加了:

*signop = oneOf('+ -'),用于标示正副符号。

增加了符号的运算优先级的设定:表示signop的优先级最高,单操作数运算符,且是右结合的,识别出符号数后,由EvalSignOp类进行处理。
arith_expr = operatorPrecedence(operand,
[(signop, 1, opAssoc.RIGHT, EvalSignOp),
(multop, 2, opAssoc.LEFT, EvalMultOp),
(plusop, 2, opAssoc.LEFT, EvalAddOp),
])
EvalSignOp类:处理符号数的类,以识别出来的符号tokens列表的第0项为处理对象,该项包含了符号及数值。因此,类初始化函数中要从tokens[0]中提取出sign和value。在eval方法中,根据sign和value得到实际的值。
请在指定位置编写程序,完成EvalSignOp类的定义。

相关知识
程序设计语言的语法定义了一个程序的组成结构或组织形式,即构成语言的各个部分之间的组合规则,但不涉及这些部分的特定含义,也不涉及使用者。如在英语中“Cat dog boy”是不满足语法的句子,因为英语语法中未定义形为“”的句子。又例如,Python表达式“3.2+3.2”是语法正确的,但是“3.2 3.2”不是语法正确的。

语义表示满足语法的程序的含义,即各个语法单元的特定含义。如“I was born on the 30th February”,语法上是正确的,但是语义上是错误的,因为2月没有30号。又例如,Python表达式“3.2/'abc'”语法上是正确的,但是语义上是错误的,因为Python的语义定义不允许用一个数去除以一个字符串。程序设计语言的语义包括静态语义和动态语义。静态语义指的是在编写程序时就可以确定的含义,而动态语义则必须在程序运行时才可以确定的含义。语义不清,计算机就无法知道所要解决问题的步骤,也就无法执行程序。

用自然语言描述程序设计语言的语法,存在不同程度的二义性。这种模糊、不确定的方式无法精确定义一门程序设计语言。最著名的文法描述形式是由Backus定义Algol60语言时提出的Backus-Naur范式(Backus-Naur Form, BNF)及其扩展形式EBNF。

下面以各程序设计语言都常见的实数四则运算语法表示为例,简单介绍EBNF范式。

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
nonzero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
integer = nonzero, { digit } ;
real = integer, ".", integer
operand = integer | real
operator = "+" | "-" | "*" | "/";
expression = operand | "(", expression, operator, expression, ")";
上述EBNF定义中,“=”的含义是定义,如digit定义为0~9的数字,“|”表示或,即digit可以是0~9的任一数字,“,”表示字符拼接,“;”是结束符,“{}”表示重复出现,可以是0次,也可以是多次。因此,上述EBNF定义了实数和整数的四则算术运算,整数是由0~9的数字构成的字符串,允许有前0;实数是由两个整数中间夹一个“.”构成。四则运算的表达式可以是一个数,即operand,也可以由括号括起的由运算符拼接两个表达式而成。

基于该EBNF定义,利用Python的pyparsing库,可以为其定义的四则运算表达式实现一个编译器,识别表达式,并求表达式的值。main函数是进行EBNF解析的主要函数,可以看到,与EBNF定义相对应,利用pyparsing提供的机制,对EBNF定义进行了表述转换,例如,integer是0~9数字构成的无前0的字符串,在main 函数中integer定义为"0"|Word(nums[1:],nums),即无前0的数字串。实数定义成由整数数字串、小数点和数字串构成的数字串。

def main(strExpr):
integer = "0"|Word(nums[1:],nums)
real = Combine(integer + "." + Word(nums))
variable = Word(alphas)
operand = real | integer | variable
multop = oneOf('* / // %')
plusop = oneOf('+ -')
operand.setParseAction(EvalConstant)
arith_expr = operatorPrecedence(operand,
[(multop, 2, opAssoc.LEFT, EvalMultOp),
(plusop, 2, opAssoc.LEFT, EvalAddOp),
])
ret = arith_expr.parseString(strExpr, parseAll=True)[0]
result = ret.eval()
return result
上述定义的main函数中EvalConstant等以Eval开头的是一系列类,用于在识别出相应的语法结构时采取相应的动作。例如EvalConstant用于在识别出一个整数或实数时,创建一个EvalConstant对象。Eval系列类定义如下所示。

class EvalConstant():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
try:
return int(self.value)
except:
return float(self.value)
def operatorOperands(tokenlist):
it = iter(tokenlist)
while 1:
try:
o1 = next(it)
o2 = next(it)
yield (o1, o2)
except StopIteration:
break
class EvalMultOp():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
prod = self.value[0].eval()
for op, val in operatorOperands(self.value[1:]):
if op == '*':
prod *= val.eval()
if op == '/':
prod /= val.eval()
return prod
class EvalAddOp():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
sum = self.value[0].eval()
for op, val in operatorOperands(self.value[1:]):
if op == '+':
sum += val.eval()
if op == '-':
sum -= val.eval()
return sum
由上述代码可知每个类有一个eval方法,用来对识别出来的语法元素进行语义解释,例如,EvalConstant的eval方法将识别出来的整数或实数数字串分别转换为整数或实数。EvalAddOp的eval方法对识别出来的加(减)法字符串中的运算数,根据运算符(加或减)的不同,做相应的运算。EvalMultOp的eval方法功能是类似的。

以各种四则运算表达式字符串为参数运行main函数,即可得到该表达式的值。例如main(‘1+2+3+4’)结果是10。

编程要求
本关的编程任务是补全11-2.py文件中EvalSignOp类的__init__函数和eval函数,以实现简单编译器的要求。具体要求如下:

本关要求通过补全11-2.py文件中EvalSignOp类的__init__函数和eval函数来实现对带符号数四则运算的求值。
具体请参见后续测试样例。
本关涉及的代码文件11-2.py的代码框架如下:

from pyparsing import Word, nums, alphas, Combine, oneOf, opAssoc, operatorPrecedence
class EvalConstant():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
try:
return int(self.value)
except:
return float(self.value)
class EvalSignOp(object):
def init(self, tokens):
# 请在此添加代码,补全函数__init__
#-----------Begin----------
#------------End-----------
def eval(self):
# 请在此添加代码,补全函数eval
#-----------Begin----------
#------------End-----------
def operatorOperands(tokenlist):
it = iter(tokenlist)
while 1:
try:
o1 = next(it)
o2 = next(it)
yield (o1, o2)
except StopIteration:
break
class EvalMultOp():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
prod = self.value[0].eval()
for op, val in operatorOperands(self.value[1:]):
if op == '*':
prod = val.eval()
if op == '/':
prod /= val.eval()
return prod
class EvalAddOp():
def init(self, tokens):
self.value = tokens[0]
def eval(self):
sum = self.value[0].eval()
for op, val in operatorOperands(self.value[1:]):
if op == '+':
sum += val.eval()
if op == '-':
sum -= val.eval()
return sum
def main(strExpr):
integer = "0"|Word(nums[1:],nums)
real = Combine(integer + "." + Word(nums))
variable = Word(alphas)
operand = real | integer | variable
multop = oneOf('
/ // %')
plusop = oneOf('+ -')
signop = oneOf('+ -')
operand.setParseAction(EvalConstant)
arith_expr = operatorPrecedence(operand,
[(signop, 1, opAssoc.RIGHT, EvalSignOp),
(multop, 2, opAssoc.LEFT, EvalMultOp),
(plusop, 2, opAssoc.LEFT, EvalAddOp),
])
ret = arith_expr.parseString(strExpr, parseAll=True)[0]
result = ret.eval()
return result
if name == '__main__':
exprs = ['-12*(3*(-3))-100+(-55)', '90/(-12-(-13))', '1+2+3+4+(-10)-(-11)']
for expr in exprs:
print(main(expr))

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥60 版本过低apk如何修改可以兼容新的安卓系统
    • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
    • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
    • ¥50 有数据,怎么用matlab求全要素生产率
    • ¥15 TI的insta-spin例程
    • ¥15 完成下列问题完成下列问题
    • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
    • ¥15 YoloV5 第三方库的版本对照问题
    • ¥15 请完成下列相关问题!
    • ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?