北邮大三上-编译原理-语义分析实验报告.doc

编译原理第六章 语义分析班级：09211311学号：姓名：schnee目 录1.实验题目和要求32.实验分析和思考33.翻译方案44.LR实现 自底向上分析（摘自语法分析实验）54.1.构造识别所有活前缀的DFA54.2.构造LR分析表65.S属性定义的自底向上实现75.1.扩充分析栈75.2.改造分析程序75.3.编程实现86.运行结果截图：141. 实验题目和要求题目：语义分析程序的设计与实现。实验内容：编写语义分析程序，实现对算术表达式的类型检查和求值。要求所分析算术表达式由如下的文法产生。实验要求：用自底向上的语法制导翻译技术实现对表达式的分析和翻译。(1) 写出满足要求的语法制导定义或翻译方案。(2) 编写分析程序，实现对表达式的类型进行检查和求值，并输出： 分析过程中所有产生式。 识别出的表达式的类型。 识别出的表达式的值。(3) 实验方法：可以选用以下两种方法之一。 自己编写分析程序。 利用YACC自动生成工具。2. 实验分析和思考由于要求进行类型检查和求值，所以可以定义两个综合属性，一个记录值一个记录类型，存放在结构中，一并传入传出。输出的产生式可以作为虚拟综合属性，在产生式的最后打印出来。id认为是定义的变量名，假设是26个小写字母，它们的值存于一个数组里。将类型检查和求值归于一次扫描，当检查类型出错时则停止，否则继续。哈希实现输入的映射，模拟词法分析的记号流。输入格式为每个num和id对应两个输入字符，其他运算符仍对应一个字符。比如第4个num,输入为num4。由于只具有综合属性，故可以用S属性的自底向上翻译实现，利用LR分析程序来实现，只需扩充分析站和改造分析程序。PS:这次实验我只是简单模拟了最简单的显式严格匹配，即没有实现隐式类型转换。3. 翻译方案4. LR实现 自底向上分析（摘自语法分析实验）4.1. 构造识别所有活前缀的DFA构造扩展文法FIRST和FOLLOW集如下ETFFIRSTid, (, numid, (, numid, (, numFOLLOW$, ), +, -$, ), +, -, *, /$, ), +, -, *, /构造识别所有活前缀的DFA如下4.2. 构造LR分析表 (1) (4) (7) (2) (5) (8) (3) (6) (9) 状态actiongoto+-*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6 r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r8r85. S属性定义的自底向上实现5.1. 扩充分析栈多定义一个结构栈数组，结构里有两个变量，一个为val, 一个为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 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 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.00void 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=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(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(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