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

《北邮 编译原理 语义分析实验报告.docx》由会员分享，可在线阅读，更多相关《北邮 编译原理 语义分析实验报告.docx（16页珍藏版）》请在三一办公上搜索。

1、北邮 编译原理 语义分析实验报告编译原理 第六章 语义分析 目 录 1. 2. 3. 4. 实验题目和要求 . 2 实验分析和思考 . 3 翻译方案 . 4 LR实现 自底向上分析 . 5 4.1. 构造识别所有活前缀的DFA . 5 4.2. 构造LR分析表 . 6 5. S属性定义的自底向上实现 . 7 5.1. 扩充分析栈 . 7 5.2. 改造分析程序 . 7 5.3. 编程实现 . 7 6. 运行结果截图： . 13 1. 实验题目和要求 题目：语义分析程序的设计与实现。 实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。 EE+T|

2、E-T|TTT*F|T/F|F Fid|(E)|num实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。 (1) 写出满足要求的语法制导定义或翻译方案。 (2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： 分析过程中所有产生式。 识别出的表达式的类型。 识别出的表达式的值。 (3) 实验方法：可以选用以下两种方法之一。 自己编写分析程序。 利用YACC自动生成工具。 2. 实验分析和思考 由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。 输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。 id认为是定

3、义的变量名，假设是26个小写字母，它们的值存于一个数组里。 将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。 哈希实现输入的映射，模拟词法分析的记号流。 输入格式为每个num和id对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。 由于只具有综合属性，故可以用S属性的自底向上翻译实现，利用LR分析程序来实现，只需扩充分析站和改造分析程序。 PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。 3. 翻译方案 EE1+TE.val=E1.val+T.val,print(EE+T)if(E1.type=T.type)E.type=

4、T.type;elseE.type=type_error;EE1-TE.val=E1.val-T.val,print(EE-T)if(E1.type=T.type)E.type=T.type;elseE.type=type_error;ETE.val=T.val,print(ET),E.type=T.typeTT1*FT.val=T1.val*F.val,print(TT*F)if(T1.type=F.type)T.type=F.type;elseT.type=type_error;TT1/FT.val=T1.val/F.val,print(TT/F)if(T1.type=F.type)T.t

5、ype=F.type;elseT.type=type_error;TFT.val=F.val,print(TF),T.type=F.typeFidF.val=id.val,print(Fid),F.type=id.typeF(E)F.val=E.val,print(F(E),F.type=E.typeFnumF.val=num.val,print(Fnum),F.type=num.type4. LR实现 自底向上分析 4.1. 构造识别所有活前缀的DFA 构造扩展文法 EE EE+T|E-T|TTT*F|T/F|F Fid|(E)|numFIRST和FOLLOW集如下 E id, (, num

6、 $, ), +, - T id, (, num $, ), +, -, *, / F id, (, num $, ), +, -, *, / FIRST FOLLOW 构造识别所有活前缀的DFA如下 4.2. 构造LR分析表 EE+T (1) TT*F (4) Fid (7) EE-T (2) TT/F (5) F(E) (8) ET (3) TF (6) Fnum (9) 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 action + s7 r3 r6 r7 r9 s7 r1 r2 r4 r5 r8 goto num S6 s6 s6 s6 s6

7、s6 - s8 r3 r6 r7 r9 s8 r1 r2 r4 r5 r8 * s9 r6 r7 r9 s9 s9 r4 r5 r8 / s10 r6 r7 r9 s10 s10 r4 r5 r8 id s4 s4 s4 s4 s4 s4 ( S5 s5 s5 s5 s5 s5 ) r3 r6 r7 r9 s16 r1 r2 r4 r5 r8 $ acc r3 r6 r7 r9 r1 r2 r4 r5 r8 E 1 11 T 2 2 12 13 F 3 3 3 3 14 15 16 5. S属性定义的自底向上实现 5.1. 扩充分析栈 多定义一个结构栈数组，结构里有两个变量，一个为val, 一

8、个为type。实现时，val其实是定义了两个变量，一个表示int时的值，一个表示real时的值，因为无法公用一个类型的变量。 定义type只有三种，一种为int, 一种为real, 一种为type_error。 val由外部提供。可通过数组搜索。 5.2. 改造分析程序 在归约时完成类型检查和求值。 之所以与归约联系，是因为每一次归约决定着所用的是哪一个产生式。 acc时打印最终求值结果和表达式类型。 5.3. 编程实现 #include #include #include #include #include #include #include #include #include using

9、namespace std; const int S = 1; /移进 const int R = 2; /归约 const int ACC = 3; /分析成功 const int Vt_num = 9; /终结符和$数 const int Vn_num = 3; /非终结符数 const int State_num = 17; /状态数 const int formula_num = 10; /扩展文法产生式数目 const int Max_input = 1024; /输入记号流长度 const int max_stack = 2500; /栈的最大高度 int tokenMax_inp

10、ut; /记号流 int len; /记号流长度 int pointer; /定义指向输入串的指针 string fmformula_num; /存放对应的产生式 int f_vnformula_num; /产生式对应的左部的非终结符 int flenformula_num; /产生式的长度 stack st; /定义栈 struct action int rs; /初始化表项的动作为0即出错，R归约S移进ACC成功 int no; actState_numVt_num; /action表表项 int gtoState_numVn_num;/goto表表项 struct attri int t

11、ype; /int-1, real-2, type_error-0 int i_val; double r_val; valmax_stack; int v_top; void initial_table /初始化分析表 memset(act, 0, sizeof(act); memset(gto, -1, sizeof(gto); /动作表action act04 = S, 4; act05 = S, 6; act06 = S, 5; act10 = S, 7; act11 = S, 8; act18.rs = ACC; act54 = S, 4; act55 = S, 6; act56 =

12、 S, 5; act74 = S, 4; act75 = S, 6; act76 = S, 5; act84 = S, 4; act85 = S, 6; act86 = S, 5; act94 = S, 4; act95 = S, 6; act96 = S, 5; act104= S, 4; act105= S, 6; act106= S, 5; act110= S, 7; act111= S, 8; act117= S,16; act30 = act31 = act32 = act33 = act37 = act38 = R, 6; act40 = act41 = act42 = act43

13、 = act47 = act48 = R, 7; act60 = act61 = act62 = act63 = act67 = act68 = R, 9; act140= act141= act142= act143= act147= act148= R, 4; act150= act151= act152= act153= act157= act158= R, 5; act160= act161= act162= act163= act167= act168= R, 8; act22 = S, 9; act23 = S, 10;act20 = act21 = act27 = act28 =

14、 R, 3; act122= S, 9; act123= S,10; act120= act121= act127= act128= R, 1; act132= S, 9; act133= S,10; act130= act131= act137= act138= R, 2; /转移表goto gto92 = 14; gto102= 15; gto112= 16; gto71 = 12; gto72 = 3; gto81 = 13; gto82 = 3; gto50 = 11; gto51 = 2; gto52 = 3; gto00 = 1; gto01 = 2; gto02 = 3; /产生

15、式存入fm数组 /记录产生式对应的左部的非终结符f_vn /记录产生式右部的长度flen fm1 = E - E+T n; f_vn1 = 0; flen1 = 3; fm2 = E - E-T n; f_vn2 = 0; flen2 = 3; fm3 = E - T n; f_vn3 = 0; flen3 = 1; fm4 = T - T*F n; f_vn4 = 1; flen4 = 3; fm5 = T - T/F n; f_vn5 = 1; flen5 = 3; fm6 = T - F n; f_vn6 = 1; flen6 = 1; fm7 = F - id n; f_vn7 = 2

16、; flen7 = 1; fm8 = F - (E) n; f_vn8 = 2; flen8 = 3; fm9 = F - num n; f_vn9 = 2; flen9 = 1; /*初始化num和id表项的值*/ void initial_entry /id: A-M为int,N-Z为real /num:a-m为int,n-z为real /值为A/a:0, N/n:0.00 void lexi_input /调用词法分析程序 /+ - * / id num ( ) $分别对应从0到8的整数 /A-Z为id(4), a-z为num(5) /a-97, A-65 /处理输入字符串将记号流存到t

17、oken数组里 /并将记号流长度赋给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; void error puts(E R R O R !); /错误处理程序 int main initial_table; initial_entry; lexi_input; tokenlen=Vt_num-1; len

18、+; while(!st.empty) st.pop; /清空栈 st.push(0); /0状态入栈 pointer=0; /指针指向输入记号流的第一个记号 v_top=1; /属性值指针 int cur_state, cur_token; int i, j; do cur_state = st.top; /栈顶状态 cur_token = tokenpointer;/当前指针指向的输入符号 if(cur_token=a & cur_token=A & cur_token=Z) cur_token=4; if(actcur_statecur_token.rs = S) /*移进，只需让val

19、也同步移进*/ st.push(cur_token); st.push(actcur_statecur_token.no); if(cur_token=5) if(tokenpointern)valv_top.type=1, valv_top.i_val=tokenpointer-a; else valv_top.type=2, valv_top.r_val=tokenpointer-a+0.0; else if(cur_token=4) if(tokenpointer0) st.pop; printf(r%d , actcur_statecur_token.no); coutE+T if(v

20、alv_top-2.type=valv_top-6.type) if(valv_top-6.type=1) valv_top-6.i_val+=valv_top-2.i_val; else valv_top-6.r_val+=valv_top-2.r_val; v_top-=4; else printf(TYPE_ERROR !n); break; else if(j=2)/E-E-T if(valv_top-2.type=valv_top-6.type) if(valv_top-6.type=1) valv_top-6.i_val-=valv_top-2.i_val; else valv_t

21、op-6.r_val-=valv_top-2.r_val; v_top-=4; else printf(TYPE_ERROR !n); break; else if(j=4)/T-T*F if(valv_top-2.type=valv_top-6.type) if(valv_top-6.type=1) valv_top-6.i_val*=valv_top-2.i_val; else valv_top-6.r_val*=valv_top-2.r_val; v_top-=4; else printf(TYPE_ERROR !n); break; else if(j=5)/T-T/F if(valv

22、_top-2.type=valv_top-6.type) if(valv_top-6.type=1) valv_top-6.i_val/=valv_top-2.i_val; else valv_top-6.r_val/=valv_top-2.r_val; v_top-=4; else printf(TYPE_ERROR !n); break; else if(j=8)/F-(E) valv_top-6=valv_top-4; v_top-=4; else if(actcur_statecur_token.rs = ACC) /*表达式类型检查无误，输出类型及值*/ puts(S U C C E

23、 S S !); printf(The expression type is ); if(valv_top-2.type=1)printf(integer); else printf(real); printf(, the value is ); if(valv_top-2.type=1)printf(%dnn, valv_top-2.i_val); else printf(%lfnn, valv_top-2.r_val); break ; else error; break; while(1); return 0; 6. 运行结果截图： 输入符号串为 O-N+n 即token=79, 1, 78, 0, 110; len=5; 输入符号串为 (a+b)*c/(L-E) 即token=6, 97, 0, 98, 7, 2, 99, 3, 6, 76, 1, 69, 7; len=13; 输入符号串O-M+m 即token=79, 1, 77, 0, 109; len=5;