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

1、語義分析程序的設(shè)計(jì)與實(shí)現(xiàn)（共17頁）-本頁僅作為文檔封面，使用時請直接刪除即可-內(nèi)頁可以根據(jù)需求調(diào)整合適字體及大小-17語義分析程序的設(shè)計(jì)與實(shí)現(xiàn)學(xué)號:學(xué)211627序號：26班號：16姓名：m實(shí)驗(yàn)日期：2010-11-23一：實(shí)驗(yàn)內(nèi)容：錯誤!未定義書簽二：實(shí)驗(yàn)要求：錯誤!未定義書簽三：實(shí)驗(yàn)方法：錯誤!未定義書簽由LEX建立YACC的詞法分析程序錯誤！未定義書簽yacc原理介紹錯誤！未定義書簽詞法分析錯誤！未定義書簽解析器如何工作錯誤!未定義書簽Yacc環(huán)境錯誤！未定義書簽常用代碼錯誤！未定義書簽第四：YAC加部名稱：錯誤!未定義書簽第五：運(yùn)行結(jié)果（源代碼見附錄）錯誤!未定義書簽第六：實(shí)驗(yàn)總結(jié)錯

2、誤!未定義書簽第七：附錄錯誤!未定義書簽附錄一：yacc程序，加注釋錯誤！未定義書簽附錄二：詞法分析器的工作原理錯誤！未定義書簽一：實(shí)驗(yàn)內(nèi)容：編寫語法分析程序，實(shí)現(xiàn)對算術(shù)表達(dá)式的語法分析，要求所分析的算術(shù)表達(dá)式由如下的文法產(chǎn)生。 E->E+T|E-T|T T->T*F|T/F|F F->id|(E)|num二：實(shí)驗(yàn)要求：在對表達(dá)式進(jìn)行分析的同時，輸出所采用的產(chǎn)生式?？梢圆捎枚喾N方法 編寫遞歸調(diào)用程序，實(shí)現(xiàn)自頂向下的分析。 編寫LL(1)語法分析程序，要求： 編程實(shí)現(xiàn)算法，為給定的文法自動構(gòu)造預(yù)測分析表 編程實(shí)現(xiàn)算法，構(gòu)造LL(1)預(yù)測分析程序， 編寫語法分析程序，實(shí)現(xiàn)自底向上

3、的分析，要求：構(gòu)造識別所有活前綴的DFA構(gòu)造LR分析表編程實(shí)現(xiàn)算法，構(gòu)造LR分析程序利用yacc自動生成語法分析程序，調(diào)用LEX自動生成的詞法分析器程序三：實(shí)驗(yàn)方法：由LEX建立YACC勺詞法分析程序由LEX產(chǎn)生的詞法分析程序可用于YACCLEX編譯程序根據(jù)LEX源程序產(chǎn)生詞法分析程序yylex(),這個名字就是YACCf需要的詞法分析程序的名字。如果YAC圖調(diào)用LEX產(chǎn)生的詞法分析程序，則在YACCM程序的第三部分用語句#include"代替函數(shù)yylex()的定義，這一yylex()就可以訪問YACCW己號的名字，因?yàn)長EX的輸出時候YAC獺出文件的一部分，所有，每個LEX的動作

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

5、來從輸入流中選取基本項(xiàng)目(叫做記號(token)。依據(jù)叫做文法規(guī)則的輸入結(jié)構(gòu)規(guī)則來組織這些記號；在識別了這些規(guī)則中的某一個的時候，接著調(diào)用為這個規(guī)則提供的叫做動作的用戶代碼；動作有能力返回值并使用其他動作的值。為了便利在動作和解析器之間的通信，對動作語句要做稍微的改動。在這個上下文中使用美元符號“$”作為給Yacc的一個信號。詞法分析用戶必須提供一個詞法分析器來讀取輸入流并把記號（帶有值，如果需要的話）傳達(dá)到解析器。詞法分析器使叫做yylex的整數(shù)值的函數(shù)。這個函數(shù)返回一個整數(shù)的記號編號，它表示讀取的記號的種類。如果這個記號關(guān)聯(lián)著一個值，應(yīng)當(dāng)把它賦予外部變量yylval。為使通信得以發(fā)生，解析

6、器和詞法分析器必須在記號編號上達(dá)成一致。編號可以由Yacc或用戶來選擇。在這兩種情況下，使用C語言的“#define”機(jī)制允許詞法分析器使用符號來返回這些編號。例如，假定在Yacc規(guī)定文件的聲明段中已經(jīng)定義記號名字DIGIT。它的意圖是返回一個DIGIT記號編號，和等于這個數(shù)字的數(shù)值的一個值。倘若詞法分析器代碼位于規(guī)定文件的程序段，標(biāo)識符DIGIT將被定義為與記號DIGIT關(guān)聯(lián)的記號編號。這種機(jī)制導(dǎo)致清晰的、易于修改的詞法分析器；唯一的缺點(diǎn)是在文法中需要避免使用任何在C語言或解析器中保留的或有意義的記號名字；例如，使用記號名字if或while就一定會導(dǎo)致編譯詞法分析器時出現(xiàn)嚴(yán)峻的困難。記號名字

7、error保留給錯誤處理，不應(yīng)該隨便使用。同上所述，記號編號可以由Yacc或用戶來選擇。在缺省的條件下，編號由Yacc選擇。文字字符的缺省記號編號是它在本地字符集中的字符數(shù)值。其他名字賦予從257開始的記號編號。要把一個記號編號賦予一個記號（包括文字），可以在聲明段中記號或文字的第一次出現(xiàn)時直接跟隨著一個非負(fù)整數(shù)。這個整數(shù)被接受為這個名字或文字的記號編號。不通過這種機(jī)制定義的名字和文字保持它們的缺省定義。所有記號編號都是不同的是很重要的。構(gòu)造詞法分析器的一個有用的工具是MikeLesk8開發(fā)的Lex程序。這些詞法分析器設(shè)計(jì)用來與Yacc解析器緊密協(xié)調(diào)工作。這些詞法分析器的規(guī)定使用正則表達(dá)式而不

8、是文法規(guī)則?？梢暂p易的用Lex生成非常復(fù)雜的詞法分析器，但是仍有一些語言（比如FORTRAN）適應(yīng)任何理論框架，它的詞法分析器必須手工制作。解析器如何工作Yacc把規(guī)定文件轉(zhuǎn)換成C程序，它依據(jù)給出的規(guī)定解析輸入。做從規(guī)定到解析器轉(zhuǎn)換的算法是復(fù)雜的，就不在這里討論了（更多信息參見引用）。但是，解析器自身就相對簡單了，理解它是如何工作的，盡管不是嚴(yán)格必須的，但會使錯誤修復(fù)和歧義處置更加易于理解。Yacc提供的解析器是由帶有一個棧的有窮狀態(tài)自動機(jī)組成。解析器自身還有能力讀取和記?。ń凶龀埃╨ookahead）記號）下一個輸入記號。當(dāng)前狀態(tài)總是在棧頂。有窮狀態(tài)自動機(jī)的狀態(tài)是一個給定的小整數(shù)標(biāo)簽(la

9、bel)；最初時，機(jī)器是在狀態(tài)0下，棧只包含狀態(tài)0，沒有讀取超前記號。機(jī)器對它只能獲得四個動作，叫做移進(jìn)(shift)、歸約(reduce)、接受和錯誤。Yacc環(huán)境在用戶向Yacc輸入規(guī)定的時候，在多數(shù)系統(tǒng)上輸出文件是叫做的一個C程序文件(因?yàn)楸镜匚募到y(tǒng)慣例，它的名字在不同安裝中可能是不同的)。Yacc生成的函數(shù)叫yyparse；它是整數(shù)值的函數(shù)。在調(diào)用的時候，它依次重復(fù)的調(diào)用用戶提供的詞法分析器yylex來獲得輸入記號。最終，要么是檢測到一個錯誤，在這種情況下(如果沒有錯誤修復(fù)是可能的)yyparse返回值1，要么詞法分析器返回結(jié)束標(biāo)記記號并且解析器接受。在這種情況下，yyparse返回

10、值0。用戶必須為解析器提供特定數(shù)量的環(huán)境來獲得一個工作的程序。例如，同每個C程序一樣，必須被定義程序調(diào)用的main()，它最終調(diào)用yyparse。此外，叫做yyerror的一個例程在檢測到語法錯誤的時候打印一個消息。用戶必須以某種形式提供這兩個例程。為了減輕使用Yacc的起初努力，提供了帶有缺省版本的main和yyerror的一個庫。這個庫的名字是依賴系統(tǒng)的；在很多系統(tǒng)上使用到裝載器的-ly參數(shù)來訪問這個庫。到y(tǒng)yerror的參數(shù)是包含錯誤信息的字符串，通常是字符串“syntaxerror”。一般的應(yīng)用可能需要更好的消息。通常，程序跟蹤輸入行數(shù)，并與檢測到的語法錯誤一起打印。外部整數(shù)變量yyc

11、har在檢測到錯誤的時候包含超前記號的編號；這對給出更好的診斷有好處。因?yàn)閙ain程序(需要讀參數(shù)等等)大多數(shù)時候是用戶提供的。Yacc庫只在小項(xiàng)目或大點(diǎn)的項(xiàng)目的早期階段有用。外部整數(shù)變量yydebug通常設(shè)置為0。如果設(shè)置為非零的值，解析器會輸出對它的動作的一個冗余的描述，包括對已經(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<=&#

12、39;z'&&c>='a'|c<='Z'&&c>='A')yylval=c;return(ID);第四：YAC咕部名稱:YACC部名稱說明yyerrorerroryyerrok、yycharYYSTYPEyydebugYACCt出文件名YACCfe成的頭文件，包含有記號定義YAC8析程序棧中的當(dāng)前記號的值由YAC餓用的用戶定義的錯誤信息打印程序YACCt誤違記號在錯誤處理之后，回到正常操作方式變了，記錄導(dǎo)致錯誤的先行記號定義分析棧值類型的預(yù)處理器符號變量，用戶置1生成有關(guān)分析動作的運(yùn)行信息

13、第五:運(yùn)行結(jié)果（源代碼見附錄）在linix下輸入的命令行依次是:Cd桌面YaccGcc-orong./rongzhmng:hdng-lmptop：桌面$yacctranslatehui.yzhang7hng-laptop：-/桌面$gccy.tab.c-ooktranslatehui.y：45：warning：conflictingtypesfar'yyerror1y,tab.c：1423：note：previous工mplititdeclarationof*yyerror,here油/ngzhang-l用to口：/桌面$Jok1+2-4+6)*2-17zhangzhang-lapto

14、p$./ok2>+syntaxerror注：Cd桌面到桌面目錄下Yacc用yacc編譯器編譯程序到C文件Gcc-orong用C編譯器生成可執(zhí)行文件./rong運(yùn)行可執(zhí)行文件輸入表達(dá)式，打印正確計(jì)算結(jié)果，否則，輸出syntaxerror第六：實(shí)驗(yàn)總結(jié)1 .用C語言實(shí)現(xiàn)詞法分析的效率較高，但用LEX可以機(jī)械的執(zhí)行程序，不用思考，雖然效率不是很高，但比較方便。Lex可以智能的讀單詞，并且按照最長匹配原則和優(yōu)先匹配原則識別單詞。Yacc則很簡單的文法式進(jìn)行分析，不需要定義遞歸的詳細(xì)飛計(jì)算法則，直接修改生成式和標(biāo)記符就可以應(yīng)用于語法分析，簡單方便，可移植性高。2 .%tokenID%tokenNU

15、M必須預(yù)先定義，否則會顯示沒有事先定義，此外對于C語言來說，isdigit(c)能判斷一個字符是否是數(shù)字，但是，本題中要識別的是整數(shù)和記號，那么或者選用lex調(diào)用表，或者，遞歸的讀取字符，分別判斷，此時，我選擇了循環(huán)判斷來解決這個問題。而這段代碼是屬于基礎(chǔ)代碼模式。if(isdigit(c)yylval=c-'0'return(NUM);elseif(c<='z'&&c>='a'|c<='Z'&&c>='A')yylval=c;return(ID);elsei

16、f(c='n')done=1;程序，是在linix環(huán)境下，用命令行執(zhí)行的，.y文件不能直接在windows環(huán)境下打開，但是，下載了ParserGenerator后，就可以直接讀取.y文件，但此時不能運(yùn)行yacc，還需要進(jìn)行環(huán)境變量(例如PASH的配置，才能在windows環(huán)境下使用yacc編譯器。這個對于未安裝虛擬機(jī)，初識linix的人使用yacc提供了很大的方便。4 .通過lexyacc的編程練習(xí)，明白了詞法分析和語法分析的基本操作，弄清了原理，為下一步進(jìn)行語義分析打下了良好的基礎(chǔ)。第七：附錄附錄一：yacc程序，加注釋%#include<>#include<

17、;>#include<>typedefstructxinti;intc;type;%unionintnum;char*id;typec;%token<num>NUM%token<id>ID%type<c>expr,term,factor%line:expr'n'if($>=0)printf("%dnumn",$;elseprintf("idn");)；expr:expr'+'termif($=0&&($=0)($.i=$+$;$.c=0;print

18、f("E->E+T:numn");)else$.c=1;$.i=-1;printf("E->E+T:idn");)|expr'-'termif($=0&&($=0)$.i=$;$.c=0;printf("E->E-T:numn");)else$.c=1;$.i=-1;printf("E->E-T:idn");)|term$.i=$;$.c=$;if($.c=0)printf("E->T:numn");elseprintf("

19、E->T:idn"););term:term'*'factorif($=0&&($=0)$,i=$*$;$.c=0;printf("T->T*F:numn");)else($.c=1;$.i=-1;printf("T->T*F:idn");)|term7'factorif($=0&&($=0)($.i=$；$.c=0;printf("T->T/F:numn");)else($.c=1;$.i=-1;printf("T->T/F:i

20、dn");)|factor$.c=$;if($.c=0)printf("T->F:numn");elseprintf("T->F:idn");)Jfactor:ID$.c=1;$,i=-1;|'fexpr')'$.c=$;$.i=$;if($.c=0)printf("F->(E):numn");elseprintf("F->(E):idn");|NUM$,i=$1;$,c=0;%main()returnyyparse();intyylex(void)stat

21、icintdone=0;intc;if(done)return0;while(c=getchar()='');if(isdigit(c)ungetc(c,stdin);=c-'0'scanf("%d",&yylval);printf("nnumn");printf("F->num:numn");return(NUM);elseif(c<='z'&&c>='a'|c<='Z'&&c>=&#

22、39;A')=ID;printf("nidn");printf("F->id:idn");return(ID);elseif(c='n')done=1;returnc;voidyyerror(char*s)printf("%sn",s);%/*第一節(jié)，普通的C語言聲明*/#include<>#include<>%tokenID/*說明記號，在這里說明的記號可以用于隨后的翻譯規(guī)則部分和輔助過程中*/%tokenNUM%/*文法記號聲明，默認(rèn)第一個產(chǎn)生式的左部非終結(jié)符號時候文法的開始符

23、號*/*文法產(chǎn)生式和相關(guān)語義動作*/line:expr'n'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()returnyyparse();/*分析成功返回0，失敗返回1*/intyyl