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

北邮 编译原理 语义分析实验报告编译原理 第六章 语义分析 目 录 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. 实验题目和要求 题目：语义分析程序的设计与实现。 实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。 E®E+T|E-T|TT®T*F|T/F|F F®id|(E)|num实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。 (1) 写出满足要求的语法制导定义或翻译方案。 (2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： 分析过程中所有产生式。 识别出的表达式的类型。 识别出的表达式的值。 (3) 实验方法：可以选用以下两种方法之一。 自己编写分析程序。 利用YACC自动生成工具。 2. 实验分析和思考 由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。 输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。 id认为是定义的变量名，假设是26个小写字母，它们的值存于一个数组里。 将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。 哈希实现输入的映射，模拟词法分析的记号流。 输入格式为每个num和id对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。 由于只具有综合属性，故可以用S属性的自底向上翻译实现，利用LR分析程序来实现，只需扩充分析站和改造分析程序。 PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。 3. 翻译方案 E®E1+TE.val=E1.val+T.val,print("E®E+T")if(E1.type=T.type)E.type=T.type;elseE.type=type_error;E®E1-TE.val=E1.val-T.val,print("E®E-T")if(E1.type=T.type)E.type=T.type;elseE.type=type_error;E®TE.val=T.val,print("E®T"),E.type=T.typeT®T1*FT.val=T1.val*F.val,print("T®T*F")if(T1.type=F.type)T.type=F.type;elseT.type=type_error;T®T1/FT.val=T1.val/F.val,print("T®T/F")if(T1.type=F.type)T.type=F.type;elseT.type=type_error;T®FT.val=F.val,print("T®F"),T.type=F.typeF®idF.val=id.val,print("F®id"),F.type=id.typeF®(E)F.val=E.val,print("F®(E)"),F.type=E.typeF®numF.val=num.val,print("F®num"),F.type=num.type4. LR实现 自底向上分析 4.1. 构造识别所有活前缀的DFA 构造扩展文法 E'®E E®E+T|E-T|TT®T*F|T/F|F F®id|(E)|numFIRST和FOLLOW集如下 E id, (, num $, ), +, - T id, (, num $, ), +, -, *, / F id, (, num $, ), +, -, *, / FIRST FOLLOW 构造识别所有活前缀的DFA如下 4.2. 构造LR分析表 E®E+T (1) T®T*F (4) F®id (7) E®E-T (2) T®T/F (5) F®(E) (8) E®T (3) T®F (6) F®num (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 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, 一个为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> using 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_input; /记号流 int len; /记号流长度 int pointer; /定义指向输入串的指针 string fmformula_num; /存放对应的产生式 int f_vnformula_num; /产生式对应的左部的非终结符 int flenformula_num; /产生式的长度 stack<int> st; /定义栈 struct action int rs; /初始化表项的动作为0即出错，R归约S移进ACC成功 int no; actState_numVt_num; /action表表项 int gtoState_numVn_num;/goto表表项 struct attri int type; /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 = 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 = 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 = 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; /产生式存入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; 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 /处理输入字符串将记号流存到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; void error puts("E R R O R !"); /错误处理程序 int main initial_table; initial_entry; lexi_input; tokenlen=Vt_num-1; len+; 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<='z') cur_token=5; else if(cur_token>='A' && cur_token<='Z') cur_token=4; if(actcur_statecur_token.rs = S) /*移进，只需让val也同步移进*/ st.push(cur_token); st.push(actcur_statecur_token.no); if(cur_token=5) if(tokenpointer<'n')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(tokenpointer<'N')valv_top.type=1, valv_top.i_val=tokenpointer-'A' else valv_top.type=2, valv_top.r_val=tokenpointer-'A'+0.0; v_top+=2; pointer+; printf("s%dn",actcur_statecur_token.no); else if(actcur_statecur_token.rs = R) /*归约，检查类型并计算属性值*/ j=actcur_statecur_token.no; i=2*flenj; while(i->0) st.pop; printf("r%d ", actcur_statecur_token.no); cout<<fmj; cur_state=st.top; st.push(f_vnj + Vt_num); st.push(gtocur_statef_vnj); if(j=1)/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_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_top-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_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 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;