本学期编译原理的一个大作业，我的选题是算术表达式的词法语法语义分析，当时由于学得比较渣，只用了递归下降的方法进行了分析。
首先，用户输入算术表达式，其中算术表达式可以包含基本运算符，括号，数字，以及用户自定义变量。
词法分析，检查单词变量是否正确；语法分析，检查算术表达式语法是否正确并输出生成语法树；语义分析，输出四元表达式。
最终效果图：
例如输入：
词法分析结果：
语法分析结果：
语义分析结果：
算术表达式的组成语法如下：
无符号整数 ＝ 〈数字〉{〈数字〉}
〈标识符〉＝ 〈字母〉{〈字母〉｜〈数字〉}
表达式〉＝ [＋｜－]〈项〉{〈加减运算符〉〈项〉}
〈项〉＝ 〈因子〉{〈乘除运算符〉〈因子〉}
〈因子〉＝ 〈标识符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’
〈加减运算符〉＝ ＋｜－
〈乘除运算符〉＝ ＊｜／
注意：
#标识符以字母开头，仅包含字母和数字
#字母包含大写和小写字母
符号文法表示：
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
1.词法分析
单词类别定义
运算符：( , ) , + , - , * , / 类别码：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()