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

2、FA構(gòu)造LR分析表編程實(shí)現(xiàn)算法4.3，構(gòu)造LR分析程序利用yacc自動(dòng)生成語(yǔ)法分析程序，調(diào)用LEX自動(dòng)生成的詞法分析器程序三：實(shí)驗(yàn)方法：由LEX建立YACC的詞法分析程序由LEX產(chǎn)生的詞法分析程序可用于YACC，LEX編譯程序根據(jù)LEX源程序產(chǎn)生詞法分析程序yylex(),這個(gè)名字就是YACC所需要的詞法分析程序的名字。如果YACC要調(diào)用LEX產(chǎn)生的詞法分析程序，則在YACC源程序的第三部分用語(yǔ)句#include“l(fā)ex.yy.c”代替函數(shù)yylex()的定義，這一yylex()就可以訪問(wèn)YACC中記號(hào)的名字，因?yàn)長(zhǎng)EX的輸出時(shí)候YACC輸出文件的一部分，所有，每個(gè)LEX的動(dòng)作都返回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 語(yǔ)言寫(xiě)成的。接受的規(guī)定類別是非常一般性的: 帶有去歧義規(guī)則的 LALR(1) 文法。Yacc 提供了一個(gè)通用工具來(lái)在計(jì)算機(jī)程序的輸入上施加結(jié)構(gòu)。Yacc 用戶準(zhǔn)備輸入處理的規(guī)定；它包括描述輸入結(jié)構(gòu)的規(guī)則，在識(shí)別了這些規(guī)則的時(shí)候調(diào)用的代碼，和做基本輸入的一個(gè)低層例程。Yacc 接著生成一個(gè)函數(shù)來(lái)控制輸入處

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

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

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

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

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

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

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

11、已經(jīng)讀入哪個(gè)輸入符號(hào)和解析器動(dòng)作是什么的討論。依賴于操作系統(tǒng)，可以通過(guò)使用調(diào)試系統(tǒng)來(lái)設(shè)置這個(gè)變量。 常用代碼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)部名稱說(shuō)明y.tab.cy.tab.hyyparseyylval yyerrorerroryyerrok、yycharYYSTYPEyydebugYACC輸出文件名YACC生成的

12、頭文件，包含有記號(hào)定義YACC分析程序棧中的當(dāng)前記號(hào)的值由YACC使用的用戶定義的錯(cuò)誤信息打印程序YACC錯(cuò)誤違記號(hào)在錯(cuò)誤處理之后，回到正常操作方式變了，記錄導(dǎo)致錯(cuò)誤的先行記號(hào)定義分析棧值類型的預(yù)處理器符號(hào)變量，用戶置1生成有關(guān)分析動(dòng)作的運(yùn)行信息第五：運(yùn)行結(jié)果（源代碼見(jiàn)附錄）在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 運(yùn)行可執(zhí)

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

14、或者，遞歸的讀取字符，分別判斷，此時(shí)，我選擇了循環(huán)判斷來(lái)解決這個(gè)問(wè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)境下打開(kāi)，但是，下載了Parser Generator后，就可以直接讀取.y文件，但此時(shí)不能運(yùn)行yacc，還需要進(jìn)行環(huán)境變量（例如PASH）的配置，才能在windows環(huán)境下使用yacc編譯器。這個(gè)對(duì)于未安裝虛擬機(jī)，初識(shí)li

15、nix的人使用yacc提供了很大的方便。4.通過(guò)lex yacc的編程練習(xí)，明白了詞法分析和語(yǔ)法分析的基本操作，弄清了原理，為下一步進(jìn)行語(yǔ)義分析打下了良好的基礎(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語(yǔ)言聲明*/#include#include%token ID/*說(shuō)明記號(hào)，在這里說(shuō)明的記號(hào)可以用于隨后的翻譯規(guī)則部分和輔助過(guò)程中*/%token NUM% /*文法記號(hào)聲明，默認(rèn)第一個(gè)產(chǎn)生式的左部非終結(jié)符號(hào)時(shí)候文法的開(kāi)始符號(hào)*/ /*文法產(chǎn)生式和相關(guān)語(yǔ)義動(dòng)作*/line: exprn printf(%dn,$1); ;/*表示輸入是表達(dá)式后面跟一個(gè)換行符*/expr: expr + term $=$1+$3;/*帶單引號(hào)的是終結(jié)符*/ |expr - term $=$1-$3;/*$表示和規(guī)則左部非終結(jié)屬性，$i表示右部第i個(gè)文法的相關(guān)屬性*/ |term $=$1; ;term: term * factor $=$1*$3;/*非終結(jié)符的名字要對(duì)應(yīng)*/ |term / factor $=$1/$3; |factor $=$1; ;factor: ID $=$1; |( expr ) $=$2; |NUM $=$1; ;%/*輔助過(guò)程*/main()return yyparse();/*