本学期编译原理的一个大作业,我的选题是算术表达式的词法语法语义分析,当时由于学得比较渣,只用了递归下降的方法进行了分析。
首先,用户输入算术表达式,其中算术表达式可以包含基本运算符,括号,数字,以及用户自定义变量。
词法分析,检查单词变量是否正确;语法分析,检查算术表达式语法是否正确并输出生成语法树;语义分析,输出四元表达式。
最终效果图:
例如输入:
词法分析结果:
语法分析结果:
语义分析结果:
算术表达式的组成语法如下:
无符号整数 = 〈数字〉{〈数字〉}
〈标识符〉= 〈字母〉{〈字母〉|〈数字〉}
表达式〉= [+|-]〈项〉{〈加减运算符〉〈项〉}
〈项〉= 〈因子〉{〈乘除运算符〉〈因子〉}
〈因子〉= 〈标识符〉|〈无符号整数〉|'('〈表达式〉')'
〈加减运算符〉= +|-
〈乘除运算符〉= *|/
注意:
#标识符以字母开头,仅包含字母和数字
#字母包含大写和小写字母
符号文法表示:
Indentifer: 标识符 digit:数字 M:表达式
项:T 因子:F
M -> +E|-E|E
E -> E+T|E-T|T
T -> T*F|T/F|F
F -> (E)|indentifer|digit
消除左递归,改进文法:
1. M -> +E|-E|E
2. E -> TE~
3. E~ -> +TE~|-TE~|&
4. T -> FT~
5. T~ -> *FT~|/FT~|&
6. F -> (E)|indentifer|digit
运算符:(,) , + , - , * , / 类别码:3
标识符:〈字母〉{〈字母〉|〈数字〉} 类别码:1
无符号整数:〈数字〉{〈数字〉} 类别码:2
依次接受所输入的字符串,根据 DFA 进行判断单词类型,将单词及符号内码存入符号表字典,将单词存入单词栈
1. 如若接收到字母说明为标识符,接着一直接受字母和数字,直到出现非数字和非字母符号
2. 如若在运算符后接收到数字,则说明为无符号整数,一直接受直到出现非数字符号
3. 如若接受到运算符,则继续处理
简单绘制的 DFA:
符号表:dic={}
单词栈:table=[] 输入数据
2. 语法分析
为文法中的每一个非终结符号设计对应的处理程序,处理程序按照具体的文法接受顺序设计,每当程序选择其中一个文法时,将其保存并打印出来,若单词栈中的所有单词都被接受,则说明语法正确,其他情况,则说明语法错误
dic={} #符号表
table=[] #单词栈
wenfa=[] #字符串文法
3. 语义分析与中间代码生成
这里我运用的依旧是递归下降的思想,我并没有利用语法分析的结果,而是利用词法分析的结果为每一个非终结符号设计相应的程序, 当结果足够生成四元式时,将其输出。将结果赋给给临时变量,传递给父项。
table=[] #单词栈
siyuan=[] #四元式
源码:
- #-*- coding=utf-8 -*-
- letter='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
- number='0123456789'
- operater='+-*/()'
- dic={} #符号表
- table=[] #单词栈
- wenfa=[] #字符串文法
- siyuan=[] #四元式
- ##################################### 词法分析 ######################################
- def cifa(string): #词法分析
- print ''
- m=0
- state=0 #1:为标识符 2:为数字串 3:为运算符
- for i in range(len(string)):
- if string[i] in operater : #如果是运算符
- if state==1: #state=1表明其前面的为标识符
- print string[m:i],'是标识符,类型码:1'
- dic[string[m:i]]=1
- table.append(string[m:i])
- elif state==2: #state=2表明其前面的为数字
- print string[m:i],'是数字,类型码:2'
- dic[string[m:i]]=2
- table.append(string[m:i])
- m=i+1
- state=3
- print string[i],'是运算符,类型码:3'
- dic[string[i]]=3
- table.append(string[i])
- elif string[i] in number: #如果是数字
- if i==m: #判断此时的数字是否为整数的第一个数字,若是则改变状态为无符号整数
- state=2
- elif string[i] in letter: #如果是字母
- if state==2: #判断此时的状态,若state=2表明状态为无符号整数,而整数内不能包含字母,故报错
- print '词法分析检测到错误,数字串中不能包含字母'
- exit(0)
- if i==m: #判断此时的字母是否为标识符的第一个字母,若是则改变状态为标识符
- state=1
- else: #当输入的字符均不符合以上判断,则说明为非法字符,故报错
- print '词法分析检测到非法字符'
- exit(0)
- if state==1: #当字符串检查完后,若字符串最后部分为标识符,应将其print出来
- print string[m:],'是标识符,类型码:3'
- dic[string[m:]]=1
- table.append(string[m:])
- elif state==2: #若字符串最后部分为无符号整数,应将其print出来
- print string[m:],'是无符号整数,类型码:2'
- dic[string[m:]]=2
- table.append(string[m:])
- table.append('#')
- print '字符栈:',table,'\n词法正确'
- ################################### 语法分析 #####################################
- '''
- 基本文法:
- M -> +E|-E|E
- E -> TE~
- E~ -> +TE~|-TE~|&
- T -> FT~
- T~ -> *FT~|/FT~|&
- F -> (E)|indentifer|digit
- '''
- class yufa(): #语法分析程序
- def __init__(self):
- self.i=0 #栈指针
- try: #用异常处理程序捕获程序的错误,出现异常则报错
- self.m()
- except:
- print '\n语法分析程序检查到错误'
- exit(0)
- def m(self): #PM程序
- if(table[self.i]=='+'):
- self.i+=1
- wenfa.append('M -> +E')
- self.e()
- elif(table[self.i]=='-'):
- self.i+=1
- wenfa.append('M -> -E')
- self.e()
- else:
- wenfa.append('M -> E')
- self.e()
- if(self.i is not len(table)-1): #语法分析结束时,若单词栈指针与单词表长度不相等,报错
- print "\n语法分析程序检查到错误,'('前应该有运算符"
- exit(0)
- else:
- print '\n字符串语法是:' #若一切正确,则输出语法树文法
- for i in wenfa:
- print i
- print '语法正确'
- def e(self): #PE程序
- wenfa.append('E -> TE1')
- self.t()
- self.e1()
- def e1(self): #PE1程序
- if(table[self.i]=='+'):
- self.i+=1
- wenfa.append('E1 -> +TE1')
- self.t()
- self.e1()
- elif(table[self.i]=='-'):
- self.i+=1
- wenfa.append('E1 -> -TE1')
- self.t()
- self.e1()
- else:
- wenfa.append('E1 -> &')
- def t(self): #PT程序
- wenfa.append('T -> FT1')
- self.f()
- self.t1()
- def t1(self): #PT1程序
- if(table[self.i]=='*'):
- self.i+=1
- wenfa.append('T1 -> *FT1')
- self.f()
- self.t1()
- elif(table[self.i]=='/'):
- self.i+=1
- wenfa.append('T1 -> /FT1')
- self.f()
- self.t1()
- else:
- wenfa.append('T1 -> &')
- def f(self): #PF程序
- if(table[self.i]=='('):
- wenfa.append('F -> (E)')
- self.i+=1
- self.e()
- if(table[self.i]!=')'):
- raise Exception
- self.i+=1
- elif(dic[table[self.i]]==1):
- wenfa.append('F -> Indentifer '+str(table[self.i]))
- self.i+=1
- elif(dic[table[self.i]]==2):
- wenfa.append('F -> Digit '+str(table[self.i]))
- self.i+=1
- else:
- raise Exception #若均不符合,则引出异常
- ####################################### 语义分析 #######################################
- class yuyi:
- def __init__(self):
- print '\n语义分析结果(四元式):'
- self.i=0 #栈指针
- self.flag=0 #记录临时变量T数目
- self.m()
- for i in siyuan: #输出四元式结果
- print i
- def m(self): #PM程序
- if(table[self.i]=='+'):
- self.i+=1
- ret1=self.e()
- siyuan.append('(+,0,'+ret1+',out)')
- self.flag+=1
- elif(table[self.i]=='-'):
- self.i+=1
- ret2=self.e()
- siyuan.append('(-,0,'+ret2+',out)')
- self.flag+=1
- else:
- ret3=self.e()
- siyuan.append('(=,'+ret3+',0,out)')
- def e(self): #PE程序
- ret1=self.t()
- ret2,ret3=self.e1()
- if(ret2!='&'): #若ret2不为&,则可以产生四元式,否则将变量传递给父项
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return 'T'+str(self.flag)
- else:
- return ret1
- def e1(self): #PE1程序
- if(table[self.i]=='+'):
- self.i+=1
- ret1=self.t()
- ret2,ret3=self.e1()
- if(ret2=='&'):
- return '+',ret1
- else:
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return '+','T'+str(self.flag)
- elif(table[self.i]=='-'):
- self.i+=1
- ret1=self.t()
- ret2,ret3=self.e1()
- if(ret2=='&'):
- return '-',ret1
- else:
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return '-','T'+str(self.flag)
- else:
- return '&','&'
- def t(self): #PT程序
- ret1=self.f()
- ret2,ret3=self.t1()
- if(ret2!='&'):
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return 'T'+str(self.flag)
- else:
- return ret1
- def t1(self): #PT1程序
- if(table[self.i]=='*'):
- self.i+=1
- ret1=self.f()
- ret2,ret3=self.t1()
- if(ret2=='&'):
- return '*',ret1
- else:
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return '*','T'+str(self.flag)
- elif(table[self.i]=='/'):
- self.i+=1
- ret1=self.f()
- ret2,ret3=self.t1()
- if(ret2=='&'): #若ret2不为&,则可以产生四元式,否则将变量传递给父项
- return '/',ret1
- else:
- self.flag+=1
- siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')
- return '/','T'+str(self.flag)
- else:
- return '&','&'
- def f(self): #PF程序
- if(table[self.i]=='('):
- self.i+=1
- ret1=self.e()
- self.i+=1
- return str(ret1)
- elif(dic[table[self.i]]==1): #当为标识符时,传递给父项
- temp=self.i
- self.i+=1
- return table[temp]
- elif(dic[table[self.i]]==2): #当为整数时,传递给父项
- temp=self.i
- self.i+=1
- return table[temp]
- ####################################### 主程序 #######################################
- if __name__=='__main__':
- string=raw_input('请输入表达式:')
- cifa(string)
- yufa()
- yuyi()
来源: