北郵大三上-編譯原理-語義分析實(shí)驗(yàn)報(bào)告

1、編譯原理第六章 語義分析班級：學(xué)號：姓名：schnee15 / 15文檔可自由編輯打印目 錄1.實(shí)驗(yàn)題目和要求32.實(shí)驗(yàn)分析和思考33.翻譯方案44.LR實(shí)現(xiàn) 自底向上分析（摘自語法分析實(shí)驗(yàn)）54.1.構(gòu)造識別所有活前綴的DFA54.2.構(gòu)造LR分析表65.S屬性定義的自底向上實(shí)現(xiàn)75.1.擴(kuò)充分析棧75.2.改造分析程序75.3.編程實(shí)現(xiàn)86.運(yùn)行結(jié)果截圖：141. 實(shí)驗(yàn)題目和要求題目：語義分析程序的設(shè)計(jì)與實(shí)現(xiàn)。實(shí)驗(yàn)內(nèi)容：編寫語義分析程序，實(shí)現(xiàn)對算術(shù)表達(dá)式的類型檢查和求值。要求所分析算術(shù)表達(dá)式由如下的文法產(chǎn)生。實(shí)驗(yàn)要求：用自底向上的語法制導(dǎo)翻譯技術(shù)實(shí)現(xiàn)對表達(dá)式的分析和翻譯。(1) 寫出滿足要

2、求的語法制導(dǎo)定義或翻譯方案。(2) 編寫分析程序，實(shí)現(xiàn)對表達(dá)式的類型進(jìn)行檢查和求值，并輸出： 分析過程中所有產(chǎn)生式。 識別出的表達(dá)式的類型。 識別出的表達(dá)式的值。(3) 實(shí)驗(yàn)方法：可以選用以下兩種方法之一。 自己編寫分析程序。 利用YACC自動(dòng)生成工具。2. 實(shí)驗(yàn)分析和思考由于要求進(jìn)行類型檢查和求值，所以可以定義兩個(gè)綜合屬性，一個(gè)記錄值一個(gè)記錄類型，存放在結(jié)構(gòu)中，一并傳入傳出。輸出的產(chǎn)生式可以作為虛擬綜合屬性，在產(chǎn)生式的最后打印出來。id認(rèn)為是定義的變量名，假設(shè)是26個(gè)小寫字母，它們的值存于一個(gè)數(shù)組里。將類型檢查和求值歸于一次掃描，當(dāng)檢查類型出錯(cuò)時(shí)則停止，否則繼續(xù)。哈希實(shí)現(xiàn)輸入的映射，模擬詞法

3、分析的記號流。輸入格式為每個(gè)num和id對應(yīng)兩個(gè)輸入字符，其他運(yùn)算符仍對應(yīng)一個(gè)字符。比如第4個(gè)num,輸入為num4。由于只具有綜合屬性，故可以用S屬性的自底向上翻譯實(shí)現(xiàn)，利用LR分析程序來實(shí)現(xiàn)，只需擴(kuò)充分析站和改造分析程序。PS:這次實(shí)驗(yàn)我只是簡單模擬了最簡單的顯式嚴(yán)格匹配，即沒有實(shí)現(xiàn)隱式類型轉(zhuǎn)換。3. 翻譯方案4. LR實(shí)現(xiàn) 自底向上分析（摘自語法分析實(shí)驗(yàn)）4.1. 構(gòu)造識別所有活前綴的DFA構(gòu)造擴(kuò)展文法FIRST和FOLLOW集如下ETFFIRSTid, (, numid, (, numid, (, numFOLLOW$, ), +, -$, ), +, -, *, /$, ), +,

4、-, *, /構(gòu)造識別所有活前綴的DFA如下4.2. 構(gòu)造LR分析表 (1) (4) (7) (2) (5) (8) (3) (6) (9) 狀態(tài)actiongoto+-*/idnum()$ETF0s4S6S51231s7s8acc2r3r3s9s10r3r33r6r6r6 r6r6r64r7r7r7r7r7r75s4s6s511236r9r9r9r9r9r97s4s6s51238s4s6s51339s4s6s51410s4s6s51511s7s8s161612r1r1s9s10r1r113r2r2s9s10r2r214r4r4r4r4r4r415r5r5r5r5r5r516r8r8r8r8r

5、8r85. S屬性定義的自底向上實(shí)現(xiàn)5.1. 擴(kuò)充分析棧多定義一個(gè)結(jié)構(gòu)棧數(shù)組，結(jié)構(gòu)里有兩個(gè)變量，一個(gè)為val, 一個(gè)為type。實(shí)現(xiàn)時(shí)，val其實(shí)是定義了兩個(gè)變量，一個(gè)表示int時(shí)的值，一個(gè)表示real時(shí)的值，因?yàn)闊o法公用一個(gè)類型的變量。定義type只有三種，一種為int, 一種為real, 一種為type_error。val由外部提供?？赏ㄟ^數(shù)組搜索。5.2. 改造分析程序在歸約時(shí)完成類型檢查和求值。之所以與歸約聯(lián)系，是因?yàn)槊恳淮螝w約決定著所用的是哪一個(gè)產(chǎn)生式。acc時(shí)打印最終求值結(jié)果和表達(dá)式類型。5.3. 編程實(shí)現(xiàn)#include <cmath>#include <sta

6、ck>#include <vector>#include <string>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int S = 1; /移進(jìn)const int R = 2; /歸約const int ACC = 3; /分析成功const int Vt_num = 9; /終結(jié)符和$數(shù)const int Vn_

7、num = 3; /非終結(jié)符數(shù)const int State_num = 17; /狀態(tài)數(shù)const int formula_num = 10; /擴(kuò)展文法產(chǎn)生式數(shù)目const int Max_input = 1024; /輸入記號流長度const int max_stack = 2500; /棧的最大高度int tokenMax_input; /記號流int len; /記號流長度int pointer; /定義指向輸入串的指針string fmformula_num; /存放對應(yīng)的產(chǎn)生式int f_vnformula_num; /產(chǎn)生式對應(yīng)的左部的非終結(jié)符int flenformula_n

8、um; /產(chǎn)生式的長度stack<int> st; /定義棧struct action int rs; /初始化表項(xiàng)的動(dòng)作為0即出錯(cuò)，R歸約S移進(jìn)ACC成功 int no;actState_numVt_num; /action表表項(xiàng)int gtoState_numVn_num;/goto表表項(xiàng)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, size

9、of(act); memset(gto, -1, sizeof(gto); /動(dòng)作表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,

10、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,

11、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= act13

12、8= R, 2; /轉(zhuǎn)移表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; /產(chǎn)生式存入fm數(shù)組 /記錄產(chǎn)生式對應(yīng)的左部的非終結(jié)符f_vn/記錄產(chǎn)生式右部的長度flen fm1 = "E -> E+T n" f_vn1 = 0; flen1 = 3; fm2 = "E -> E-T n"

13、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

14、 -> (E) n" f_vn8 = 2; flen8 = 3; fm9 = "F -> num n" f_vn9 = 2; flen9 = 1;/*初始化num和id表項(xiàng)的值*/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()/調(diào)用詞法分析程序 /+ - * / id num ( ) $分別對應(yīng)從0到8的整數(shù) /A-Z為id(4), a-z為num(5) /'a'-97, 'A

15、'-65 /處理輸入字符串將記號流存到token數(shù)組里 /并將記號流長度賦給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 !");/錯(cuò)誤處理程序int main() initial_table(); initial_en

16、try(); lexi_input(); tokenlen=Vt_num-1; len+; while(!st.empty() st.pop(); /清空棧 st.push(0); /0狀態(tài)入棧 pointer=0; /指針指向輸入記號流的第一個(gè)記號 v_top=1; /屬性值指針 int cur_state, cur_token; int i, j; do cur_state = st.top(); /棧頂狀態(tài) cur_token = tokenpointer;/當(dāng)前指針指向的輸入符號 if(cur_token>='a' && cur_token<

17、='z') cur_token=5; else if(cur_token>='A' && cur_token<='Z') cur_token=4; if(actcur_statecur_token.rs = S) /*移進(jìn)，只需讓val也同步移進(jìn)*/ 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=to

18、kenpointer-'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

19、%dn",actcur_statecur_token.no); else if(actcur_statecur_token.rs = R) /*歸約，檢查類型并計(jì)算屬性值*/ 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); i

20、f(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

21、.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_to