2022年北邮计算机科学与技术编译原理语义分析 .pdf

《2022年北邮计算机科学与技术编译原理语义分析 .pdf》由会员分享，可在线阅读，更多相关《2022年北邮计算机科学与技术编译原理语义分析 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 语义分析程序实验报告 班级： 2010211302 学号： 10211180 姓名：魏乐业 班内序号： 21 一、实验原理与算法分析： (1). 词法分析过程： 将字符流转换为记号流。有效字符为： digit : 0-9 ID symbol : _, a-z, A-Z operator : +, - , *, / , ( , ) 正则表达式： 数字： digit* 标识符： letter(letter|digit)* (2). 语法分析过程： 1. 将文法改写为拓广文法： 1. E - E 2. E - E + T 3. E - E - T 4. E - T 5. T - T * F 6.

2、T - T / F 7. T - F 8. F - id 9. F - ( E ) 10. F - num 在该文法中 , 非终结符号有： E,E,T,F 终结符号有： id,num,+,-,*,/,(,) 2. 求该文法非终结符的FIRST集与 FOLLOW 集： FIRST set: FIRST (E): id num ( FIRST (E): id num ( FIRST (T): id num ( FIRST (F): id num ( FOLLOW set: FOLLOW (E): $ FOLLOW (E): + - ) $ FOLLOW (T): + - * / ) $ FOLLO

3、W (F): + - * / ) $ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 3. 求该文法的LR(0)项目集规范族： CLOUSURE I0 E - .E E - .E+T E - .E-T E - .T T - .T*F T - .T/F T - .F F - .id F - .(E) F - .num CLOUSURE I1 E - E. E - E.+T E - E.-T CLOUSURE I2 E - T.

4、T - T.*F T - T./F CLOUSURE I3 T - F. CLOUSURE I4 F - id. CLOUSURE I5 F - num. CLOUSURE I6 F - (.E) E - .E+T E - .E-T E - .T T - .T*F T - .T/F T - .F F - .id F - .(E) F - .num CLOUSURE I7 E - E+.T T - .T*F T - .T/F T - .F F - .id F - .(E) F - .num CLOUSURE I8 E - E-.T T - .T*F T - .T/F T - .F F - .id

5、 F - .(E) F - .num CLOUSURE I9 T - T*.F F - .id F - .(E) F - .num CLOUSURE I10 T - T/.F F - .id F - .(E) F - .num CLOUSURE I11 F - (E.) E - E.+T E - E.-T CLOUSURE I12 E - E+T. T - T.*F T - T./F CLOUSURE I13 E - E-T. T - T.*F T - T./F CLOUSURE I14 T - T*F. CLOUSURE I15 T - T/F. CLOUSURE I16 F - (E).

6、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 4. 利用识别该文法的所有活前缀的DFA ，构造 ACTION表与 GOTO 表： ACTOIN表: id num + - * / ( ) $ 0 s4 s5 s6 1 s7 s8 acc 2 r3 r3 s9 s10 r3 r3 3 r6 r6 r6 r6 r6 r6 4 r7 r7 r7 r7 r7 r7 5 r9 r9 r9 r9 r9 r9 6 s4 s5 s6 7 s4

7、 s5 s6 8 s4 s5 s6 9 s4 s5 s6 10 s4 s5 s6 11 s7 s8 s16 12 r1 r1 s9 s10 r1 r1 13 r2 r2 s9 s10 r2 r2 14 r4 r4 r4 r4 r4 r4 15 r5 r5 r5 r5 r5 r5 16 r8 r8 r8 r8 r8 r8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - GOTO 表: E T F 0 1 2 3 1 2 3 4

8、5 6 11 2 3 7 12 3 8 13 3 9 14 10 15 11 12 13 14 15 16 (3). 语义分析过程： 算数表达式求值的语法制导定义： 产生式 语义规则 代码段 E - E return E.val answer=valtop; E - E + T E.val=E.val+T.val valntop=valtop-2+valtop; E - E - T E.val=E.val-T.val valntop=valtop-2-valtop; E - T E.val=T.val T - T * F T.val=T.val*F.val valntop=valtop-2*v

9、altop; T - T / F T.val=T.val/F.val valntop=valtop-2/valtop; T - F T.val=F.val F - id F.val=id.val F - ( E ) F.val=E.val valntop=valtop-1; F - digit F.val=digit.lexval 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 二、程序运行效果： (1) 测试 1: 名师资料

10、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - (2) 测试 2: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

11、- 第 7 页，共 14 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 三、实验程序源代码： #include #include #include #include #define NN 20 #define MAXN 1000 #define INF 9999999 #define ERROR -1 using namespace std; char *token_str=,ID,d

12、igit,+,-,*,/,(,),$; const char *ori_grammer=E - E, E - E + T, E - E - T, E - T, T - T * F, T - T / F, T - F, F - id, F - ( E ), F - digit; enumE_=MAXN+1,E,T,F; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - enumNUL=0,ID,NUM,ADD,SUB,MUL,DI

13、V,OPL,OPR,END; const int GRAMMERNNNN=E_,E, E,E,ADD,T, E,E,SUB,T, E,T, T,T,MUL,F, T,T,DIV,F, T,F, F,ID, F,OPL,E,OPR, F,NUM; const int GrammerL=1,3,3,1,3,3,1,1,3,1; const int ACTIONNNNN=INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,INF,INF,7,8,INF,INF,INF,INF,0, INF,INF,INF,-3,-3,9,10,INF,-3,-3, INF,INF,INF,

14、-6,-6,-6,-6,INF,-6,-6, INF,INF,INF,-7,-7,-7,-7,INF,-7,-7, INF,INF,INF,-9,-9,-9,-9,INF,-9,-9, INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,4,5,INF,INF,INF,INF,6,INF,INF, INF,INF,INF,7,8,INF,INF,INF,16,I

15、NF, INF,INF,INF,-1,-1,9,10,INF,-1,-1, INF,INF,INF,-2,-2,9,10,INF,-2,-2, INF,INF,INF,-4,-4,-4,-4,INF,-4,-4, INF,INF,INF,-5,-5,-5,-5,INF,-5,-5, INF,INF,INF,-8,-8,-8,-8,INF,-8,-8; const int GOTONNNN=INF,INF,1,2,3, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF, INF,I

16、NF,INF,INF,INF, INF,INF,11,2,3, INF,INF,INF,12,3, INF,INF,INF,13,3, INF,INF,INF,INF,14, INF,INF,INF,INF,15, 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - INF,INF,INF,INF,INF, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF

17、, INF,INF,INF,INF,INF, INF,INF,INF,INF,INF; int isIDsym(char ch) return (ch=_|ch=a&ch=A&ch=0&ch=9); int isBlank(char ch) return (ch= |ch=t|ch=n); int SLRcalculate(vector &token,vector &token_val,int &answer) char tmp_strMAXN; vector S,val; int I,a,pos=0,top; S.push_back(0); val.push_back(INF); token

18、.push_back(END); while(1) I=S.back(); a=tokenpos; top=val.size()-1; printf(INUPT : ); for(int i=pos;itoken.size();i+) if(tokeni=NUM) printf(%d,token_vali); else printf(%s,token_strtokeni); printf(n); printf(state :t); for(int i=0;iS.size();i+) printf(%-5d,Si); printf(n); 名师资料总结 - - -精品资料欢迎下载 - - - -

19、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - printf(val :t); for(int i=0;i0) sprintf(tmp_str,Shift %d,ACTIONIa); S.push_back(ACTIONIa); val.push_back(token_valpos); pos+; else if(ACTIONIa0) int n=-ACTIONIa; int ntop=top-GrammerLn+1; sprintf(tmp_str,reduce by %s,o

20、ri_grammern); switch(n) case 1: valntop=valtop-2+valtop;break; case 2: valntop=valtop-2-valtop;break; case 4: valntop=valtop-2*valtop;break; case 5: valntop=valtop-2/valtop;break; case 8: valntop=valtop-1;break; for(int i=0;itop-ntop;i+) val.pop_back(); for(int i=0;i=token.size() return ERROR; print

21、f(%snn,tmp_str); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - int LexicalAnalyse(char *str,vector &token,vector &token_val) int state=0; char *ptr=str,ch; int value=0; while(ptr) ch=*ptr; switch(state) case 0: if(isDigit(ch) state=1; e

22、lse if(isIDsym(ch) state=2; else state=3; break; case 1: if(isDigit(ch) value=value*10+ch-0; ptr+; else token.push_back(NUM); token_val.push_back(value); value=0; state=0; break; case 2: if(isIDsym(ch)|isDigit(ch) ptr+; else token.push_back(ID); token_val.push_back(INF); state=0; break; case 3: swit

23、ch(ch) case +: token.push_back(ADD);break; case -: token.push_back(SUB);break; case *: token.push_back(MUL);break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - case /: token.push_back(DIV);break; case (: token.push_back(OPL);break; cas

24、e ): token.push_back(OPR);break; default:if(!isBlank(ch)return ERROR; ptr+; state=0; if(!isBlank(ch) token_val.push_back(INF); break; int main() char strMAXN; int answer,flag; vector token,token_val; printf(Please input the expression: ); gets(str); LexicalAnalyse(str,token,token_val); printf(Lexica

25、l Analyse :n); for(int i=0;itoken.size();i+) printf(%s ,token_strtokeni); printf(nn); printf(Syntax Analyse by SLR :n); flag=SLRcalculate(token,token_val,answer); if(flag=0) printf(Accept.n); printf(The final result is %d.n,answer); else printf(Error input!n); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -