北邮 编译原理 语义分析实验报告

编译原理第六章语义分析目录TOC\o"1-5"\h\z1.实验题目和要求22.实验分析和思考3翻译方案4LR实现自底向上分析（摘自语法分析实验）5构造识别所有活前缀的DFA5构造LR分析表65.S属性定义的自底向上实现75.1.扩充分析栈75.2.改造分析程序75.3.编程实现76.运行结果截图：131.实验题目和要求题目：语义分析程序的设计与实现。实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。ETE+TIE-TITTTT*FIT/FIFFTidI(E)Inum实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。写出满足要求的语法制导定义或翻译方案。编写分析程序，实现对表达式的类型进行检查和求值，并输出：分析过程中所有产生式。识别出的表达式的类型。识别出的表达式的值。实验方法：可以选用以下两种方法之一。①自己编写分析程序。②利用YACC自动生成工具。2.实验分析和思考由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。id认为是定义的变量名，假设是26个小写字母，它们的值存于一个数组里。将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。哈希实现输入的映射，模拟词法分析的记号流。输入格式为每个num和id对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。由于只具有综合属性，故可以用S属性的自底向上翻译实现，利用LR分析程序来实现，只需扩充分析站和改造分析程序。PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。3.翻译方案ETE+T{E.val=E.val+T.val,print("ETE+T")}11{if(E.type==T.type)E.type=T.type;1elseE.type=type_error;}ETE一T{E.val=E.val一T.val,print("ETE一T")}11{if(E.type==T.type)E.type=T.type;elseE.type=type_error;}ETT{E.val=T.val,print("ETT"),E.type=T.type}TTT*F{T.val=T.val*F.val,print("TTT*F")}11{if(T.type==F.type)T.type=F.type;1elseT.type=type_error;}TTT/F{T.val=T.val/F.val,print("TTT/F")}11{if(T1.type==F.type)T.type=F.type;elseT.type=type_error;}TTF{T.val=F.val,print("TTF"),T.type=F.type}FTid{F.val=id.val,print("FTid"),F.type=id.type}FT(E){F.val=E.val,print("FT(E)"),F.type=E.type}FTnum{F.val=num.val,print("FTnum"),F.type=num.type}LR实现自底向上分析（摘自语法分析实验）4.1.构造识别所有活前缀的DFA构造扩展文法E'TEETE+TIE-TITTTT*FIT/FIFFTidI(E)InumFIRST和FOLLOW集如下I3：TtF-Io：EJ•E»EfTE>-E-TE»TT»T*FT->-T/FT->-FF»idF>-(E)F»num开始Ii：・EtE-讣I3：TtF-Io：EJ•E»EfTE>-E-TE»TT»T*FT->-T/FT->-FF»idF>-(E)F»num开始Ii：・EtE-讣EtE*TnumI6:F->(-E)E->E->Etr>FtF->Ft氏E4TTPFT/'FFid(E)numF->id•k：F^num•E->EiTT->TtT->F->FtF->-M（S）T+FT/FFid(E)numI|2:EtE卜T・T->T・水FT->T-/F11*7-—5：E^E--TT-}•T*F1T>•T/FT>>FFt•idF->•ffi)•num△【13：E->E-T•TtT•E->T•TtT・*FTtT・/F-7:空TtT・/FIic：F->(E)•L5T->T+•FFt-idFt•(E)Ft•num11Q：T->T/-FFt-idF》・(E)F->•numT14:T->T1F-LjETTT/iETFFIRSTid,(,numid,(,numid,(,numFOLLOW$,),+,-$,),+,-,*,/$,),+,-,*,/构造识别所有活前缀的DFA如下

4.2.构造LR分析表ETE+T(1)TTT*F(4)FTid(7)ETE-T(2)TTT/F(5)FT(E)(8)ETT(3)TTF(6)FTnum(9)状态actiongoto+—*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r8S属性定义的自底向上实现5.1.扩充分析栈多定义一个结构栈数组，结构里有两个变量，一个为val,一个为type。实现时，val其实是定义了两个变量,一个表示int时的值，一个表示real时的值，因为无法公用一个类型的变量。定义type只有三种，一种为int,一种为real,一种为type_error。val由外部提供。可通过数组搜索。5.2.改造分析程序在归约时完成类型检查和求值。之所以与归约联系，是因为每一次归约决定着所用的是哪一个产生式。acc时打印最终求值结果和表达式类型。5.3.编程实现#include<cmath>#include<stack>#include<vector>#include<string〉#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestdconstintSconstintS=1constintR=2constintACC=3constintVtnum=9constintVnnum=3constintStatenum=17constintformulanum=10constintMaxinput=1024constintmaxstack=2500inttokenMax_inputintlenintpointerstringfmformula_numintf_vnformula_numintflenformulanum//移进//归约//分析成功//终结符和$数//非终结符数//状态数//扩展文法产生式数目//输入记号流长度//栈的最大高度//记号流//记号流长度//定义指向输入串的指针//存放对应的产生式//产生式对应的左部的非终结符//产生式的长度stackstackVint>st//定义栈struetaction{intrs//初始化表项的动作为0即出错，R归约S移进ACC成功intno}act[State_num]Vt_num]//action表表项intgtoState_num[Vn_num|//goto表表项struetattri{inttype//int-1,real-2,type_error-0inti_valdoubler_val}valmax_stackintv_topvoidinitial_table(){//初始化分析表memse(act,0,sizeof(act))memse(gto,1,sizeof(gto))//动作表actionac[0][4]={S,4}act[0][5]={S,6}act[0][6]={S,5}ac[1][0]={S,7}act[1][1]={S,8}act[1][8].rs=ACCac[5][4]={S,4}act[5][5]={S,6}act[5][6]={S,5}ac[7][4]={S,4}act[7][5]={S,6}act[7][6]={S,5}ac[8][4]={S,4}act[8][5]={S,6}act[8][6]={S,5}ac[9][4]={S,4}act[9][5]={S,6}act[9][6]={S,5}ac[10][4]={S,4}act[10][5]={S,6}act[10][6]={S,5}ac[11][0]={S,7}act[11][1]={S,8}act[11][7]={S,16}ac[3][0]==act[3][1]==act[3][2]:=act[3][3]==act[3][7]s=act[3][8]=s{R,6}ac[4][0]s=act[4][1]s=act[4][2]==act[4][3]==act[4][7]==act[4][8]=={R,7}ac[6][0]==act[6][1]==act[6][2]:=act[6][3]==act[6][7]s=act[6][8]=s{R,9}TOC\o"1-5"\h\zact[14][0]=act141act142act143act147actRacU15][0]=act151act152act153act157actRact[16][0]=act161act162act163act167actRact[2][2]={S,9}act[2][3]={S,10}act[2][0]=act[2][1]=act[2][7]=act[2][8]={R,3}ac[12][2]={S,9}act[12][3]={S,10}act[12][0]=act[12][1]=act[12][7]=act[12][8]={R,1}ac[13][2]={S,9}act[13][3]={S,10}act[13][0]=act[13][1]=act[13][7]=act[13][8]={R,2}//转移表gotogt[9][2]=14gt[10][2]=15gt[11][2]=16gt[7][1]=12gto[7][2]:=3gt[8][1]=13gto[8][2]:=3gt[5][0]=11gto[5][1]:=2gto[5][2]=3gt[0][0]=1gto[0][1]==2gto[0][2]=3//产生式存入fm数组//记录产生式对应的左部的非终结符f_vn//记录产生式右部的长度flenf[1]=="E->E+T\n"f__vn：1]:=0flen[1]:=3f[2]=="E->E-T\n"f__vn：2]:=0flen[2]:=3f[3]=="E->T\n"f_vn[3]==0flen[3]==1f[4]=="T->T*F\n"f_vn[4]:=1flen[4]:=3f[5]=="T->T/F\n"f_vn[5]:=1flen[5]:=3f[6]=="T->F\n"f_vn[6]==1flen[6]=:1f[7]=="F->id\n"f_vn[7]==2flen[7]==1f[8]=="F->(E)\n"f_vn[8]:=2flen[8]:=3f[9]=="F->num\n"fvn[9]:=2flen[9]:=1}/*初始化num和id表项的值*/voidinitial_entry(){//id:A-M为int,N-Z为real//num:a-m为int,n-z为real//值为A/a:0,N/n:0.00}voidlexi_input(){//调用词法分析程序//+-*/idnum()$分别对应从0到8的整数//A-Z为id(4),a-z为num(5)//'a'-97,'A'-65//处理输入字符串将记号流存到token[]数组里//并将记号流长度赋给len//eg:(a+b)*c/(L-E)//token={6,97,0,98,7,2,99,3,6,76,1,69,7};//len=13;//eg:O-N+n//token={79,1,78,0,110};//len=5;//eg:O-M+m//token={79,1,77,0,109};//len=5;}

voiderror(){put("ERROR")//错误处理程序}intmain(){initial_table)initial_entry)lexi_input)tokenlen]=Vt_num1le++while(!stempty())stpop()//清空栈stpush(0)//0状态入栈pointe=0//指针指向输入记号流的第一个记号v_top1//属性值指针intcur_state,cur_tokeninti,jdo{cur_statest,topcur_token=token[pointer]//当前指针指向的输入符号if(cur_token>='a'&&cur_token<='z')cur_token=5elseifcur_token>='A'&&cur_token<='Z')cur_token=4ifact[cur_state][cur_token|.rs==S){/*移进，只需让val也同步移进*/.push(cur_token).push(act[cur_state|cur_token].no)if(cur_token{iftokenpointer|<'n')val[v_top].type=1,'a'+0.0'A'+0.0valv_top].i_val='a'+0.0'A'+0.0elseval[v_top].type=2,valv_top|.r_valtokenpointer}elseif(cur_token){iftokenpointer|<'N')val[v_top].type=1,valv_top].i_val=token[pointer'A'elseval[v_top].type=2,valv_top|.r_valtokenpointer}v_t+=2point++prin("s%d\n"act[cur_state][cur_token].no)}elseifact[cur_state][cur_token].rs==R{/*归约，检查类型并计算属性值*/jct[cur_state][cur_token|no=2*flen[j]while(i>0){jptop()}prin("r%d，act[cur_state][cur_token|noco<<fm[j]cur_sta=et.top()spushf_vnj|+Vt_numspushgto[cur_state][f_vnj]])if(j==1)//E->E+T{ifval[v_top2],type==valv_top6].type){ifval[v_top6],type==1)v_top6].i_val+=valv_top2].i_valelsev_top6].r_val+=valv_top2].r_valv_=o4}else{pri("TYPE_ERROR\n"break}}elseif(j==2)//E->E-T{ifval[v_top2],type==valv_top6].type){ifval[v_top6].type==1)v_top6].i_val=valv_top2].i_valelsev_top6].r_val=valv_top2].r_valv_=o4}else{pri:i"TYPE_ERROR\n"break}elseif(j==4)//T->T*F{ifval[v_top2],type==valv_top6].type){ifval[v_top6].type==1)v_top6].i_val*=valv_top2].i_valelsev_top6].r_val*=valv_top2].r_valv_=o4}else{pri:i"TYPE_ERROR\n"break}}elseif(j==5)//T->T/F{ifval[v_top2],type==valv_top6].type){ifval[v_top6].type==1)v_top6].i_val/=valv_top2].i_valelsev_top6].r_val/=valv_top2].r_valv_=o4}else{pri:i"TYPE_ERROR\n"break}}elseif(j==8)/