語義分析程序的設(shè)計與實現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上語義分析程序的設(shè)計與實現(xiàn)班號： 姓名：張榮 學(xué)號： 序號：26實驗日期：2010-11-23 一：實驗內(nèi)容：編寫語法分析程序，實現(xiàn)對算術(shù)表達(dá)式的語法分析，要求所分析的算術(shù)表達(dá)式由如下的文法產(chǎn)生。E-E+T|E-T|TT-T*F|T/F|FF-id|(E)|num二：實驗要求：在對表達(dá)式進行分析的同時，輸出所采用的產(chǎn)生式?？梢圆捎枚喾N方法編寫遞歸調(diào)用程序，實現(xiàn)自頂向下的分析。編寫LL(1)語法分析程序，要求：編程實現(xiàn)算法4.2，為給定的文法自動構(gòu)造預(yù)測分析表編程實現(xiàn)算法4.1，構(gòu)造LL(1)預(yù)測分析程序，編寫語法分析程序，實現(xiàn)自底向上的分析，要求：構(gòu)造識別所有活前綴的D

2、FA構(gòu)造LR分析表編程實現(xiàn)算法4.3，構(gòu)造LR分析程序利用yacc自動生成語法分析程序，調(diào)用LEX自動生成的詞法分析器程序三：實驗方法：由LEX建立YACC的詞法分析程序由LEX產(chǎn)生的詞法分析程序可用于YACC，LEX編譯程序根據(jù)LEX源程序產(chǎn)生詞法分析程序yylex(),這個名字就是YACC所需要的詞法分析程序的名字。如果YACC要調(diào)用LEX產(chǎn)生的詞法分析程序，則在YACC源程序的第三部分用語句#include“l(fā)ex.yy.c”代替函數(shù)yylex()的定義，這一yylex()就可以訪問YACC中記號的名字，因為LEX的輸出時候YACC輸出文件的一部分，所有，每個LEX的動作都返回YACC知

3、道的終結(jié)符。在UNIX的環(huán)境下，如果LEX源程序在first.l中，YACC的源程序在second.y中，可以使用以下命令得到所需要的分析程序。Lex first.lYacc second.ycc-o yaccdemo y.tab.c lex.yy.cyacc原理介紹Yacc 是用可移植的 C 語言寫成的。接受的規(guī)定類別是非常一般性的: 帶有去歧義規(guī)則的 LALR(1) 文法。Yacc 提供了一個通用工具來在計算機程序的輸入上施加結(jié)構(gòu)。Yacc 用戶準(zhǔn)備輸入處理的規(guī)定；它包括描述輸入結(jié)構(gòu)的規(guī)則，在識別了這些規(guī)則的時候調(diào)用的代碼，和做基本輸入的一個低層例程。Yacc 接著生成一個函數(shù)來控制輸入處

4、理。這個函數(shù)叫做解析器(parser)，它調(diào)用用戶提供的低層輸入例程(詞法分析器(analyzer)來從輸入流中選取基本項目(叫做記號(token)。依據(jù)叫做文法規(guī)則的輸入結(jié)構(gòu)規(guī)則來組織這些記號；在識別了這些規(guī)則中的某一個的時候，接著調(diào)用為這個規(guī)則提供的叫做動作的用戶代碼；動作有能力返回值并使用其他動作的值。 為了便利在動作和解析器之間的通信，對動作語句要做稍微的改動。在這個上下文中使用美元符號“$”作為給 Yacc 的一個信號。詞法分析用戶必須提供一個詞法分析器來讀取輸入流并把記號(帶有值，如果需要的話)傳達(dá)到解析器。詞法分析器使叫做 yylex 的整數(shù)值的函數(shù)。這個函數(shù)返回一個整數(shù)的記號編

5、號，它表示讀取的記號的種類。如果這個記號關(guān)聯(lián)著一個值，應(yīng)當(dāng)把它賦予外部變量 yylval。 為使通信得以發(fā)生，解析器和詞法分析器必須在記號編號上達(dá)成一致。編號可以由 Yacc 或用戶來選擇。在這兩種情況下，使用 C 語言的“# define”機制允許詞法分析器使用符號來返回這些編號。例如，假定在 Yacc 規(guī)定文件的聲明段中已經(jīng)定義記號名字 DIGIT。它的意圖是返回一個 DIGIT 記號編號，和等于這個數(shù)字的數(shù)值的一個值。倘若詞法分析器代碼位于規(guī)定文件的程序段，標(biāo)識符 DIGIT 將被定義為與記號 DIGIT 關(guān)聯(lián)的記號編號。 這種機制導(dǎo)致清晰的、易于修改的詞法分析器；唯一的缺點是在文法中需

6、要避免使用任何在 C 語言或解析器中保留的或有意義的記號名字；例如，使用記號名字 if 或 while 就一定會導(dǎo)致編譯詞法分析器時出現(xiàn)嚴(yán)峻的困難。記號名字 error 保留給錯誤處理，不應(yīng)該隨便使用。 同上所述，記號編號可以由 Yacc 或用戶來選擇。在缺省的條件下，編號由 Yacc 選擇。文字字符的缺省記號編號是它在本地字符集中的字符數(shù)值。其他名字賦予從 257 開始的記號編號。 要把一個記號編號賦予一個記號(包括文字)，可以在聲明段中記號或文字的第一次出現(xiàn)時直接跟隨著一個非負(fù)整數(shù)。這個整數(shù)被接受為這個名字或文字的記號編號。不通過這種機制定義的名字和文字保持它們的缺省定義。所有記號編號都是

7、不同的是很重要的。 構(gòu)造詞法分析器的一個有用的工具是 Mike Lesk8開發(fā)的 Lex 程序。這些詞法分析器設(shè)計用來與 Yacc 解析器緊密協(xié)調(diào)工作。這些詞法分析器的規(guī)定使用正則表達(dá)式而不是文法規(guī)則。可以輕易的用 Lex 生成非常復(fù)雜的詞法分析器，但是仍有一些語言(比如 FORTRAN)不適應(yīng)任何理論框架，它的詞法分析器必須手工制作。解析器如何工作Yacc 把規(guī)定文件轉(zhuǎn)換成 C 程序，它依據(jù)給出的規(guī)定解析輸入。做從規(guī)定到解析器轉(zhuǎn)換的算法是復(fù)雜的，就不在這里討論了(更多信息參見引用)。但是，解析器自身就相對簡單了，理解它是如何工作的，盡管不是嚴(yán)格必須的，但會使錯誤修復(fù)和歧義處置更加易于理解。

8、Yacc 提供的解析器是由帶有一個棧的有窮狀態(tài)自動機組成。解析器自身還有能力讀取和記住(叫做超前(lookahead)記號)下一個輸入記號。當(dāng)前狀態(tài)總是在棧頂。有窮狀態(tài)自動機的狀態(tài)是一個給定的小整數(shù)標(biāo)簽(label)；最初時，機器是在狀態(tài) 0 下，棧只包含狀態(tài) 0，沒有讀取超前記號。 機器對它只能獲得四個動作，叫做移進(shift)、歸約(reduce)、接受和錯誤。 Yacc環(huán)境在用戶向 Yacc 輸入規(guī)定的時候，在多數(shù)系統(tǒng)上輸出文件是叫做 y.tab.c 的一個 C 程序文件(因為本地文件系統(tǒng)慣例，它的名字在不同安裝中可能是不同的)。Yacc 生成的函數(shù)叫 yyparse；它是整數(shù)值的函數(shù)

9、。在調(diào)用的時候，它依次重復(fù)的調(diào)用用戶提供的詞法分析器 yylex來獲得輸入記號。最終，要么是檢測到一個錯誤，在這種情況下(如果沒有錯誤修復(fù)是可能的) yyparse 返回值 1，要么詞法分析器返回結(jié)束標(biāo)記記號并且解析器接受。在這種情況下，yyparse 返回值 0。 用戶必須為解析器提供特定數(shù)量的環(huán)境來獲得一個工作的程序。例如，同每個 C 程序一樣，必須被定義程序調(diào)用的 main()，它最終調(diào)用 yyparse。此外，叫做 yyerror 的一個例程在檢測到語法錯誤的時候打印一個消息。 用戶必須以某種形式提供這兩個例程。為了減輕使用 Yacc 的起初努力，提供了帶有缺省版本的 main 和 y

10、yerror 的一個庫。這個庫的名字是依賴系統(tǒng)的；在很多系統(tǒng)上使用到裝載器的 -ly 參數(shù)來訪問這個庫。到 yyerror 的參數(shù)是包含錯誤信息的字符串，通常是字符串“syntax error”。 一般的應(yīng)用可能需要更好的消息。通常，程序跟蹤輸入行數(shù)，并與檢測到的語法錯誤一起打印。外部整數(shù)變量 yychar 在檢測到錯誤的時候包含超前記號的編號；這對給出更好的診斷有好處。因為 main 程序(需要讀參數(shù)等等)大多數(shù)時候是用戶提供的。Yacc 庫只在小項目或大點的項目的早期階段有用。 外部整數(shù)變量 yydebug 通常設(shè)置為 0。如果設(shè)置為非零的值，解析器會輸出對它的動作的一個冗余的描述，包括對

11、已經(jīng)讀入哪個輸入符號和解析器動作是什么的討論。依賴于操作系統(tǒng)，可以通過使用調(diào)試系統(tǒng)來設(shè)置這個變量。 常用代碼if( islower( c ) ) yylval = c - a; return ( LETTER ); if( isdigit( c ) ) yylval = c - 0; return( DIGIT ); if(c=a|c=A) yylval=c; return(ID); 第四：YACC內(nèi)部名稱：YACC內(nèi)部名稱說明y.tab.cy.tab.hyyparseyylval yyerrorerroryyerrok、yycharYYSTYPEyydebugYACC輸出文件名YACC生成的

12、頭文件，包含有記號定義YACC分析程序棧中的當(dāng)前記號的值由YACC使用的用戶定義的錯誤信息打印程序YACC錯誤違記號在錯誤處理之后，回到正常操作方式變了，記錄導(dǎo)致錯誤的先行記號定義分析棧值類型的預(yù)處理器符號變量，用戶置1生成有關(guān)分析動作的運行信息第五：運行結(jié)果（源代碼見附錄）在linix下輸入的命令行依次是：Cd 桌面Yacc translate.yGcc y.tab.c o rong./rong注：Cd 桌面 到桌面目錄下Yacc translate.y 用yacc編譯器編譯translate.y程序到C文件Gcc y.tab.c o rong 用C編譯器生成可執(zhí)行文件./rong 運行可執(zhí)

13、行文件輸入表達(dá)式，打印正確計算結(jié)果，否則，輸出syntax error第六：實驗總結(jié)1.用C語言實現(xiàn)詞法分析的效率較高，但用LEX可以機械的執(zhí)行程序，不用思考，雖然效率不是很高，但比較方便。Lex可以智能的讀單詞，并且按照最長匹配原則和優(yōu)先匹配原則識別單詞。Yacc則很簡單的文法式進行分析，不需要定義遞歸的詳細(xì)飛計算法則，直接修改生成式和標(biāo)記符就可以應(yīng)用于語法分析，簡單方便，可移植性高。2.%token ID %token NUM 必須預(yù)先定義，否則會顯示沒有事先定義，此外對于C語言來說，isdigit(c)能判斷一個字符是否是數(shù)字，但是，本題中要識別的是整數(shù)和記號，那么或者選用lex調(diào)用表，

14、或者，遞歸的讀取字符，分別判斷，此時，我選擇了循環(huán)判斷來解決這個問題。而這段代碼是屬于基礎(chǔ)代碼模式。if(isdigit(c)yylval=c-0;return(NUM);else if(c=a|c=A)yylval=c;return(ID);else if(c=n)done = 1;3.yacc程序，是在linix環(huán)境下，用命令行執(zhí)行的，.y文件不能直接在windows環(huán)境下打開，但是，下載了Parser Generator后，就可以直接讀取.y文件，但此時不能運行yacc，還需要進行環(huán)境變量（例如PASH）的配置，才能在windows環(huán)境下使用yacc編譯器。這個對于未安裝虛擬機，初識li

15、nix的人使用yacc提供了很大的方便。4.通過lex yacc的編程練習(xí)，明白了詞法分析和語法分析的基本操作，弄清了原理，為下一步進行語義分析打下了良好的基礎(chǔ)。第七：附錄附錄一：yacc程序，加注釋%#include#include#includetypedef struct xint i;int c; type;%union int num; char *id; type c;%token NUM%token ID%type expr,term,factor%line: exprn if($1.i=0) printf(%d numn,$1.i); else printf(idn); ;ex

16、pr: expr + term if($1.c=0&($3.c=0) $.i=$1.i+$3.i; $.c=0; printf(E-E+T E.type:numn); else $.c=1; $.i=-1; printf(E-E+T E.type:idn); |expr - term if($1.c=0&($3.c=0) $.i=$1.i-$3.i; $.c=0; printf(E-E-T E.type:numn); else $.c=1; $.i=-1; printf(E-E-T E.type:idn); |term $.i=$1.i; $.c=$1.c; if($.c=0 ) printf

17、(E-T E.type:numn); else printf(E-T E.type:idn); ;term: term * factor if($1.c=0&($3.c=0) $.i=$1.i*$3.i; $.c=0; printf(T-T*F T.type:numn); else $.c=1; $.i=-1; printf(T-T*F T.type:idn); |term / factor if($1.c=0&($3.c=0) $.i=$1.i/$3.i; $.c=0; printf(T-T/F T.type:numn); else $.c=1; $.i=-1; printf(T-T/F T

18、.type:idn); |factor $.c=$1.c; $.i=$1.i; if($.c=0) printf(T-F T.type:numn); else printf(T-F T.type:idn); ;factor: ID $.c=1;$.i=-1; |( expr ) $.c=$2.c; $.i=$2.i; if($.c=0) printf(F-(E) F.type:numn); else printf(F-(E) F.type:idn); |NUM $.i=$1;$.c=0; ; %main()return yyparse();int yylex(void)static int d

19、one =0;int c;if(done) return 0;while(c=getchar()= );if(isdigit(c) ungetc(c,stdin); yylval.num=c-0; scanf(%d,&yylval); printf(nnumn); printf(F-num F.type:numn); return(NUM);else if(c=a|c=A) yylval.id=ID; printf(nidn); printf(F-id F.type:idn); return(ID);else if(c=n) done = 1;return c;void yyerror(cha

20、r *s)printf(%sn,s);%/*第一節(jié)，普通的C語言聲明*/#include#include%token ID/*說明記號，在這里說明的記號可以用于隨后的翻譯規(guī)則部分和輔助過程中*/%token NUM% /*文法記號聲明，默認(rèn)第一個產(chǎn)生式的左部非終結(jié)符號時候文法的開始符號*/ /*文法產(chǎn)生式和相關(guān)語義動作*/line: exprn printf(%dn,$1); ;/*表示輸入是表達(dá)式后面跟一個換行符*/expr: expr + term $=$1+$3;/*帶單引號的是終結(jié)符*/ |expr - term $=$1-$3;/*$表示和規(guī)則左部非終結(jié)屬性，$i表示右部第i個文法的相關(guān)屬性*/ |term $=$1; ;term: term * factor $=$1*$3;/*非終結(jié)符的名字要對應(yīng)*/ |term / factor $=$1/$3; |factor $=$1; ;factor: ID $=$1; |( expr ) $=$2; |NUM $=$1; ;%/*輔助過程*/main()return yyparse();/*