python实现 编译原理上机实验试题

编写的比较简单：

一、实验目的

          通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术，如何针对确定的有限状态自动机进行编程序；熟悉和掌握程序设计语言的语法分析程序的设计原理、熟悉和掌握算符优先分析方法。

二、实验要求

          本实验要求：①要求能熟练使用一种程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）；③要编写出完成相应任务的程序并在计算机上准确地运行；④实验结束后要写出上机实验报告。

三、实验题目

          针对下面文法G(S)：

S→ v = E

E→E+E│E-E│E*E│E/E│（E）│ v │ i

       其中，v为标识符，i为整型或实型数。要求完成

      ① 使用自动机技术实现一个词法分析程序；

KW={'var':1,'int':2,'#':3,'=':4,'+':5,'-':6,'*':7,'/':8,'(':9,')':10}#var=>标识符 int=>数字 #=>结束标记
words=input('输入语句:')
index=0
flag=1
if(words[-1] != '#'):
    print("error:输入表达式应以#结尾!")
    flag=0
while(index+1<len(words) and flag==1):
    ch=words[index]
    if(ord(ch) in range(ord('a'),ord('z')+1) or ord(ch) in range(ord('A'),ord('Z')+1)):
        #该字符为字母
        Crs=ch
        if(ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
            if(Crs in KW.keys()):
                print('({},\'{}\')'.format(KW[Crs],Crs))
                index+=1
            else:
                print('({},\'{}\')'.format(1,Crs))
                index+=1
        else:
            while(ord(words[index+1]) in range(ord('a'),ord('z')+1) or ord(words[index+1]) in range(ord('A'),ord('Z')+1)):
                Crs=Crs+words[index+1]
                index+=1
                if(words[index+1]=='#' or ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
                    if(Crs in KW.keys()):
                        print('({},\'{}\')'.format(KW[Crs],Crs))
                        index+=1
                        break
                    else:
                        print('({},\'{}\')'.format(1,Crs))
                        index+=1
                        break
    elif(ch==' '):
        #该字符为空格
        while(words[index+1]==' '):
            index+=1
        index+=1
    elif(ch in ['=','+','-','*','/','(',')']):
        #该字符为运算符
        index+=1
        print('({},\'{}\')'.format(KW[ch],ch))
    elif(ch in ['0','1','2','3','4','5','6','7','8','9']):
        #该字符为数字
        num=ch
        while(words[index+1] in ['0','1','2','3','4','5','6','7','8','9']):
            num=num+words[index+1]
            index+=1
        index+=1
        print('({},{})'.format(2,num))
    if(words[index]=='#'):
        print('(3,\'#\')')
        break
#输入：#结尾的算符表达式

      效果：

② 使用算符优先分析方法实现其语法分析程序；

OPE={                                                       #操作符优先级字典
    '+':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '-':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '*':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '/':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '(':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'=','#':'err'},
    ')':{'+':'>','-':'>','*':'>','/':'>','(':'err',')':'>','#':'>'},
    '#':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'err','#':'='}
    }
KW={'var':1,'int':2,'#':3,'=':4,'+':5,'-':6,'*':7,'/':8,'(':9,')':10}#var=>标识符 int=>数字 #=>结束标记
LAN={'E+E':'E','E-E':'E','E*E':'E','E/E':'E','(E)':'E','var':'E','int':'E'}
opeStack=list()#栈列表
words=input('输入语句:')
index=0
while(index+1<len(words)):
    ch=words[index]
    if(ch=='#'):
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
        if(index==0):
            opeStack.append(ch)
            index+=1
        else:
            index+=1
            opeStack.append(ch)
            Sl=len(opeStack)-1
            while(opeStack[Sl]=='E'):
             Sl-=1
            while(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(LAN[a3+a2+a1])
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl]=='E'):
                    Sl-=1
            break
    elif(ord(ch) in range(ord('a'),ord('z')+1) or ord(ch) in range(ord('A'),ord('Z')+1)):
        #该字符为字母
        Crs=ch
        if(ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
            if(Crs in KW.keys()):
                index+=1
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                opeStack.append('var')
            else:
                index+=1
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                opeStack.append('var')
        else:
            while(ord(words[index+1]) in range(ord('a'),ord('z')+1) or ord(words[index+1]) in range(ord('A'),ord('Z')+1)):
                Crs=Crs+words[index+1]
                index+=1
                if(words[index+1]=='#' or ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
                    if(Crs in KW.keys()):
                        index+=1
                        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                        opeStack.append('var')
                        #print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
                        break
                    else:
                        index+=1
                        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                        opeStack.append('var')
                        #print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
                        break
    elif(ch==' '):
        #该字符为空格
        while(words[index+1]==' '):
            index+=1
        index+=1
    elif(ch in ['=','+','-','*','/','(',')']):
        #该字符为运算符
        index+=1
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
        if(opeStack[len(opeStack)-1] in ['var','int']):
            t=opeStack.pop()
            opeStack.append(LAN[t])
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
        Sl=len(opeStack)-1
        while(opeStack[Sl]=='E'):
             Sl-=1
        if(OPE[opeStack[Sl]][ch]=='<'):
            opeStack.append(ch)
        elif(OPE[opeStack[Sl]][ch]=='>'):
            a1=opeStack.pop()
            a2=opeStack.pop()
            a3=opeStack.pop()
            opeStack.append(LAN[a3+a2+a1])
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
            Sl=len(opeStack)-1
            while(opeStack[Sl]=='E' and Sl>=0):
                Sl-=1
            while(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(LAN[a3+a2+a1])
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl]=='E' and Sl>=0):
                    Sl-=1
            opeStack.append(ch)
    elif(ch in ['0','1','2','3','4','5','6','7','8','9']):
        #该字符为数字
        num=ch
        while(words[index+1] in ['0','1','2','3','4','5','6','7','8','9']):
            num=num+words[index+1]
            index+=1
        index+=1
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),num,words[index:]))
        opeStack.append('int')
        if(index+1>=len(words)):
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
ch='#'
Sl=len(opeStack)-1
if(opeStack[len(opeStack)-1] in ['var','int']):
            t=opeStack.pop()
            opeStack.append(LAN[t])
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
while(opeStack[Sl]=='E'):
    Sl-=1
while(OPE[opeStack[Sl]][ch]=='>'):
    a1=opeStack.pop()
    a2=opeStack.pop()
    a3=opeStack.pop()
    opeStack.append(LAN[a3+a2+a1])
    print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
    Sl=len(opeStack)-1
    while(opeStack[Sl]=='E'):
        Sl-=1
if(''.join(opeStack)=='#E'):
    print('接收')
#在每次入栈时输出栈内元素，剩余符号，当前输入符号
#最后剩余符号为空，当前元素为#，栈内归约只剩下#E时则判断接受输入串
#输入：以#开始和结尾的运算式，可存在变量

     效果：

 

③ 在语法分析过程中同时完成常量表达式的计算。

OPE={                                                       #操作符优先级字典
    '+':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '-':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '*':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '/':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '(':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'=','#':'err'},
    ')':{'+':'>','-':'>','*':'>','/':'>','(':'err',')':'>','#':'>'},
    '#':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'err','#':'='}
    }
KW={'var':1,'int':2,'#':3,'=':4,'+':5,'-':6,'*':7,'/':8,'(':9,')':10}#var=>标识符 int=>数字 #=>结束标记
LAN={'E+E':'E','E-E':'E','E*E':'E','E/E':'E','(E)':'E'}
VAL={}
def calcul(n1,o,n2):
    if(o=='+'):
        return repr(int(n1)+int(n2))
    elif(o=='-'):
        return repr(int(n2)-int(n1))
    elif(o=='*'):
        return repr(int(n1)*int(n2))
    elif(o=='/'):
        return repr(int(int(n2)/int(n1)))
    elif(n1==')' and n2=='('):
        return o
opeStack=list()#栈列表
words=input('输入语句:')
index=0
while(index+1<len(words)):
    ch=words[index]
    if(ch=='#'):
        if(index==0):
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
            opeStack.append(ch)
            index+=1
        else:
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
            index+=1
            opeStack.append(ch)
            Sl=len(opeStack)-1
            while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
             Sl-=1
            while(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(calcul(a1,a2,a3))
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
                    Sl-=1
            break
    elif(ch==' '):
        #该字符为空格
        while(words[index+1]==' '):
            index+=1
        index+=1
    elif(ch in ['=','+','-','*','/','(',')']):
        #该字符为运算符
        index+=1
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
        Sl=len(opeStack)-1
        while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
             Sl-=1
        if(OPE[opeStack[Sl]][ch]=='<'):
            opeStack.append(ch)
        elif(OPE[opeStack[Sl]][ch]=='>'):
            a1=opeStack.pop()
            a2=opeStack.pop()
            a3=opeStack.pop()
            opeStack.append(calcul(a1,a2,a3))
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
            Sl=len(opeStack)-1
            while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#'] and Sl>=0):
                Sl-=1
            while(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(calcul(a1,a2,a3))
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl]  not in ['=','+','-','*','/','(',')','#'] and Sl>=0):
                    Sl-=1
            opeStack.append(ch)
    elif(ch in ['0','1','2','3','4','5','6','7','8','9']):
        #该字符为数字
        num=ch
        while(words[index+1] in ['0','1','2','3','4','5','6','7','8','9']):
            num=num+words[index+1]
            index+=1
        index+=1
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),num,words[index:]))
        opeStack.append(num)
        if(index+1>=len(words)):
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
ch='#'
Sl=len(opeStack)-1
while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
    Sl-=1
while(OPE[opeStack[Sl]][ch]=='>'):
    a1=opeStack.pop()
    a2=opeStack.pop()
    a3=opeStack.pop()
    opeStack.append(calcul(a1,a2,a3))
    print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
    Sl=len(opeStack)-1
    while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
        Sl-=1
print('结果为：{}'.format(opeStack[1]))
#只能进行整数运算 输入：以#开始和结尾的运算式

效果：

附加：在语法分析过程中同时完成常量表达式的计算+可以实现变量

OPE={                                                       #操作符优先级字典
    '+':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '-':{'+':'>','-':'>','*':'<','/':'<','(':'<',')':'>','#':'>'},
    '*':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '/':{'+':'>','-':'>','*':'>','/':'>','(':'<',')':'>','#':'>'},
    '(':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'=','#':'err'},
    ')':{'+':'>','-':'>','*':'>','/':'>','(':'err',')':'>','#':'>'},
    '#':{'+':'<','-':'<','*':'<','/':'<','(':'<',')':'err','#':'='}
    }
KW={'var':1,'int':2,'#':3,'=':4,'+':5,'-':6,'*':7,'/':8,'(':9,')':10}#var=>标识符 int=>数字 #=>结束标记
LAN={'E+E':'E','E-E':'E','E*E':'E','E/E':'E','(E)':'E'}
VAL={}
def calcul(n1,o,n2):
    if(o=='+'):
        return repr(int(n1)+int(n2))
    elif(o=='-'):
        return repr(int(n2)-int(n1))
    elif(o=='*'):
        return repr(int(n1)*int(n2))
    elif(o=='/'):
        return repr(int(int(n2)/int(n1)))
    elif(n1==')' and n2=='('):
        return o
opeStack=list()#栈列表
words=input('输入语句:')
index=0
while(index+1<len(words)):
    ch=words[index]
    if(ch=='#'):
        if(index==0):
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
            opeStack.append(ch)
            index+=1
        else:
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
            index+=1
            opeStack.append(ch)
            Sl=len(opeStack)-1
            while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
             Sl-=1
            while(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(calcul(a1,a2,a3))
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
                    Sl-=1
            break
    elif(ord(ch) in range(ord('a'),ord('z')+1) or ord(ch) in range(ord('A'),ord('Z')+1)):
        #该字符为字母
        Crs=ch
        if(ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
            index+=1
            if(Crs in VAL.keys()):
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                opeStack.append(VAL[Crs])
            else:
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),Crs,words[index:]))
                opeStack.append(Crs)
        else:
            while(ord(words[index+1]) in range(ord('a'),ord('z')+1) or ord(words[index+1]) in range(ord('A'),ord('Z')+1)):
                Crs=Crs+words[index+1]
                index+=1
                if(words[index+1]=='#' or ord(words[index+1]) not in range(ord('a'),ord('z')+1) and ord(words[index+1]) not in range(ord('A'),ord('Z')+1)):
                    index+=1
                    if(Crs in VAL.keys()):
                        opeStack.append(VAL[Crs])
                    else:
                        opeStack.append(Crs)
                    #print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
                    break
    elif(ch==' '):
        #该字符为空格
        while(words[index+1]==' '):
            index+=1
        index+=1
    elif(ch in ['=','+','-','*','/','(',')']):
        #该字符为运算符
        if(ch == '='):
            ch=words[index+1]
            num=ch
            index+=1
            while(words[index+1] in ['0','1','2','3','4','5','6','7','8','9']):
                num=num+words[index+1]
                index+=1
            index+=1
            tpl=opeStack.pop()
            VAL[tpl]=num
        else:
            index+=1
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),ch,words[index:]))
            Sl=len(opeStack)-1
            while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
                 Sl-=1
            if(OPE[opeStack[Sl]][ch]=='<'):
                opeStack.append(ch)
            elif(OPE[opeStack[Sl]][ch]=='>'):
                a1=opeStack.pop()
                a2=opeStack.pop()
                a3=opeStack.pop()
                opeStack.append(calcul(a1,a2,a3))
                print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                Sl=len(opeStack)-1
                while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#'] and Sl>=0):
                    Sl-=1
                while(OPE[opeStack[Sl]][ch]=='>'):
                    a1=opeStack.pop()
                    a2=opeStack.pop()
                    a3=opeStack.pop()
                    opeStack.append(calcul(a1,a2,a3))
                    print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
                    Sl=len(opeStack)-1
                    while(opeStack[Sl]  not in ['=','+','-','*','/','(',')','#'] and Sl>=0):
                        Sl-=1
                opeStack.append(ch)
    elif(ch in ['0','1','2','3','4','5','6','7','8','9']):
        #该字符为数字
        num=ch
        while(words[index+1] in ['0','1','2','3','4','5','6','7','8','9']):
            num=num+words[index+1]
            index+=1
        index+=1
        print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),num,words[index:]))
        opeStack.append(num)
        if(index+1>=len(words)):
            print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}'.format(''.join(opeStack),words[index],words[index:]))
ch='#'
Sl=len(opeStack)-1
while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
    Sl-=1
while(OPE[opeStack[Sl]][ch]=='>'):
    a1=opeStack.pop()
    a2=opeStack.pop()
    a3=opeStack.pop()
    opeStack.append(calcul(a1,a2,a3))
    print('栈内元素:{}\t\t当前符号:{}\t剩余符号:{}\t归约'.format(''.join(opeStack),ch,words[index:]))
    Sl=len(opeStack)-1
    while(opeStack[Sl] not in ['=','+','-','*','/','(',')','#']):
        Sl-=1
print('结果为：{}'.format(opeStack[1]))
#只能进行整数运算 输入：以#开始和结尾的运算式

效果：