遞歸下降語(yǔ)法分析程序設(shè)計(jì)

1、精選文檔編譯方法 實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱：簡(jiǎn)單的語(yǔ)法分析程序設(shè)計(jì)實(shí)驗(yàn)要求1. 功能：對(duì)簡(jiǎn)單的賦值語(yǔ)句進(jìn)行語(yǔ)法分析隨機(jī)輸入賦值語(yǔ)句，輸出所輸入的賦值語(yǔ)句與相應(yīng)的四元式2. 采用遞歸下降分析程序完成（自上而下的分析）3. 確定各個(gè)子程序的功能并畫出流程圖4. 文法如下：5. 編碼、調(diào)試通過(guò)采用標(biāo)準(zhǔn)輸入輸出方式。輸入輸出的樣例如下：【樣例輸入】x:=a+b*c/d-(e+f)【樣例輸出】(說(shuō)明，語(yǔ)句和四元式之間用5個(gè)空格隔開)T1:=b*c     (*,b,c,T1)T2:=T1/d     (/,T1,d,T2)T3:=a+T2    

2、  (+,a,T2,T3)T4:=e+f     (+,e,f,T4)T5:=T3-T4     (-,T3,T4,T5)x:=T5     (:=,T5,-,x)  【樣例說(shuō)明】程序除能夠正確輸出四元式外，當(dāng)輸入的表達(dá)式錯(cuò)誤時(shí)，還應(yīng)能檢測(cè)出語(yǔ)法錯(cuò)誤，給出相應(yīng)錯(cuò)誤提示。6. 設(shè)計(jì)3-5個(gè)賦值語(yǔ)句測(cè)試實(shí)例，檢驗(yàn)程序能否輸出正確的四元式；當(dāng)輸入錯(cuò)誤的句子時(shí)，檢驗(yàn)程序能夠給出語(yǔ)法錯(cuò)誤的相應(yīng)提示信息。7. 報(bào)告內(nèi)容包括：遞歸程序的調(diào)用過(guò)程，各子程序的流程圖和總控流程圖，詳細(xì)設(shè)計(jì)，3-5個(gè)測(cè)試用例的程序運(yùn)行截圖及相

3、關(guān)說(shuō)明，有詳細(xì)注釋的程序代碼清單等。目錄1.語(yǔ)法分析遞歸下降分析算法51.1背景知識(shí)51.2消除左遞歸62.詳細(xì)設(shè)計(jì)及流程圖62.1 函數(shù)void V( ) / V -> a|b|c|d|e.|z62.2 函數(shù)void A( ) / A -> V:=E72.3 函數(shù)void E() /E -> TE'72.4函數(shù)void T( ) / T -> FT'82.5函數(shù)void E1( ) /E'-> +TE'|-TE'|null82.6函數(shù)void T1() / T'-> *FT'|/FT'|nul

4、l93.測(cè)試用例及截圖93.1測(cè)試用例1及截圖93.2測(cè)試用例2及截圖103.3測(cè)試用例3及截圖11代碼清單111.語(yǔ)法分析遞歸下降分析算法1.1背景知識(shí)無(wú)回溯的自上向下分析技術(shù)可用的先決條件是：無(wú)左遞歸和無(wú)回溯。 無(wú)左遞歸：既沒(méi)有直接左遞歸，也沒(méi)有間接左遞歸。無(wú)回溯：對(duì)于任一非終結(jié)符號(hào)U的產(chǎn)生式右部x1|x2|xn，其對(duì)應(yīng)的字的首終結(jié)符號(hào)兩兩不相交。如果一個(gè)文法不含回路，也不含以為右部的產(chǎn)生式，那么可以通過(guò)執(zhí)行消除文法左遞歸的算法消除文法的一切左遞歸（改寫后的文法可能含有以為右部的產(chǎn)生式）。文法的左遞歸消除算法： 1、將文法G的所有非終結(jié)符排序?yàn)閁1 ,U2 , ,Un; 2、For(i=1

5、；i+；in) for j1 to i-1 把產(chǎn)生式UiUj替換成Ui1| 2|m； 其中：Uj 1| 2 | |m 消除Ui產(chǎn)生式中的直接左遞歸； 3.化簡(jiǎn)改寫之后的文法，刪除多余產(chǎn)生式。文法的直接左遞歸消除公式： 直接左遞歸形式：UUx|y； 其中：x，y（VNVT）* ，y不以U打頭。 直接左遞歸的消除： UyU UxU| 直接左遞歸的一般形式：UUx1|Ux2|Uxm|y1|y2|yn； 其中：xi ,yi都不以U打頭。 一般形式直接左遞歸的消除: Uy1U| y2U | ynUUx1U| x2U| | xmU| 回溯的消除的前提是文法不得含有左遞歸，可提左因子來(lái)消除回溯。1.2消除左

6、遞歸根據(jù)實(shí)驗(yàn)中給出的文法，進(jìn)行消除左遞歸及回溯，得到下列的式子A -> V:=EE -> TE'E'-> +TE'|-TE'|nullT -> FT'T'-> *FT'|/FT'|nullF -> V|(E)V -> a|b|c|d|e.|z2.詳細(xì)設(shè)計(jì)及流程圖根據(jù)消除左遞歸后的文法，可以編寫相應(yīng)的函數(shù)。2.1 函數(shù)void V( ) / V -> a|b|c|d|e.|zvoid V() / V -> a|b|c|d|e.|z函數(shù)設(shè)計(jì)主要用來(lái)識(shí)別小寫字母的，如果是小寫字母的話

7、，放入字符表，不是的話，輸出語(yǔ)法錯(cuò)誤。函數(shù)比較簡(jiǎn)單，代碼如下：if(islower(ssym)Tablelist_n0 = ssym; /把讀取的小寫字母存入符號(hào)表，便于分析是生成中間代碼Tablelist_n1 = '0'list_n+;sym+;elseprintf("Operand Errors!n"); /運(yùn)算對(duì)象錯(cuò)誤SIGN=1;exit(0);2.2 函數(shù)void A( ) / A -> V:=Evoid A() / A -> V:=E 函數(shù)主要用來(lái)實(shí)現(xiàn)賦值的操作，流程圖如圖1所示。 圖1 A( ) 函數(shù)流程圖2.3 函數(shù)void E

8、() /E -> TE'函數(shù)E（）里面主要遞歸調(diào)用函數(shù)T( )和E'( )。當(dāng)沒(méi)有出現(xiàn)語(yǔ)法錯(cuò)誤時(shí)就可正常的運(yùn)行。函數(shù)比較簡(jiǎn)單，代碼如下：if(SIGN=0)T();E1();2.4函數(shù)void T( ) / T -> FT'函數(shù)T( )里面主要遞歸調(diào)用函數(shù)F ( )和T''( )。當(dāng)沒(méi)有出現(xiàn)語(yǔ)法錯(cuò)誤時(shí)就可正常的運(yùn)行。函數(shù)比較簡(jiǎn)單，代碼如下：if(SIGN=0)F();T1();2.5函數(shù)void E1( ) /E'-> +TE'|-TE'|null函數(shù)void E1() /E'-> +TE'

9、|-TE'|null，主要用來(lái)實(shí)現(xiàn)加減法的語(yǔ)義分析。流程圖如圖2所示。 圖2 E1 ( ) 函數(shù)流程圖2.6函數(shù)void T1() / T'-> *FT'|/FT'|null函數(shù)void T1() / T'-> *FT'|/FT'|null，主要用來(lái)實(shí)現(xiàn)乘除法的語(yǔ)義分析。流程圖如圖3所示。 圖3 T1 ( ) 函數(shù)流程圖3.測(cè)試用例及截圖3.1測(cè)試用例1及截圖 用例1為實(shí)驗(yàn)要求上的的用例。測(cè)試結(jié)果圖4所示。 圖4 測(cè)試用例1及結(jié)果截圖3.2測(cè)試用例2及截圖 用例2為出現(xiàn)大寫字母，出現(xiàn)報(bào)錯(cuò)。測(cè)試結(jié)果圖5所示。 圖5 測(cè)試用例2及

10、結(jié)果截圖3.3測(cè)試用例3及截圖 用例3為隨意編寫用例。測(cè)試結(jié)果圖6所示。 圖6 測(cè)試用例3及結(jié)果截圖代碼清單#include<stdio.h>#include<stdlib.h>#include<string.h>#include <ctype.h>void A(); / A -> V:=Evoid E(); / E -> TE'void T(); / T -> FT'void E1(); / E'-> +TE'|-TE'|nullvoid T1(); / T'-> *

11、FT'|/FT'|nullvoid F(); / F -> V|(E)void V(); / V -> a|b|c|d|e.|zchar s50,n='1' /s50用于存放輸入的賦值表達(dá)式char Table503; /產(chǎn)生中間代碼所需的符號(hào)表int SIGN,sym; /sym為s50中當(dāng)前讀入符號(hào)的下標(biāo)int list_n=0; /符號(hào)表的下標(biāo)/*消除左遞歸及回溯A -> V:=EE -> TE'E'-> +TE'|-TE'|nullT -> FT'T'-> *FT&

12、#39;|/FT'|nullF -> V|(E)V -> a|b|c|d|e.|z*/int main()SIGN = 0; /SIGN用于指示賦值表達(dá)式是否出現(xiàn)錯(cuò)誤sym=0;scanf("%s",&s);if( s0 = '0') /沒(méi)有輸入的情況直接退出return 0;A();if(ssym!='0'&&SIGN=0)printf("ERROR!n");exit(0);return 0;void A() / A -> V:=EV();if(ssym=':&#

13、39;&&ssym+1='=') /判斷賦值號(hào)是否有拼寫錯(cuò)誤sym+=2;E();printf("%s:=%s",Tablelist_n-2,Tablelist_n-1);printf(" (:=,%s,-,%s)n",Tablelist_n-1,Tablelist_n-2);elseprintf("The assignment Symbol spelling mistakes!n"); /賦值號(hào)拼寫錯(cuò)誤SIGN=1;exit(0);void V() / V -> a|b|c|d|e.|zif(i

14、slower(ssym)Tablelist_n0 = ssym; /把讀取的小寫字母存入符號(hào)表，便于分析是生成中間代碼Tablelist_n1 = '0'list_n+;sym+;elseprintf("Operand Errors!n"); /運(yùn)算對(duì)象錯(cuò)誤SIGN=1;exit(0);void E() /E -> TE'if(SIGN=0)T();E1();void T() / T -> FT'if(SIGN=0)F();T1();void E1() /E'-> +TE'|-TE'|nullint

15、p;if(SIGN=0)if(ssym = '+'|ssym='-')p=sym; /用p記錄出現(xiàn)'+'或'-'時(shí)sym的值sym+;T();char ch3;ch0 = 'T'ch1 = n; ch2 = '0' if(sp = '+') printf("%s:=%s+%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (+,%s,%s,%s)n", Tablelist_n-2,Tabl

16、elist_n-1,ch); /輸出四元式elseprintf("%s:=%s-%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (-,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch); /輸出四元式strcpy(Tablelist_n-2,ch); /將當(dāng)前結(jié)果歸結(jié)式放在符號(hào)表中l(wèi)ist_n-;n+;E1(); void T1() / T'-> *FT'|/FT'|null int p;if(SIGN=0)if(ssym =

17、'*'|ssym='/')p=sym; sym+;F();char ch3;ch0 = 'T' ch1 = n;ch2 = '0'if(sp = '*') printf("%s:=%s*%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (*,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch);/輸出四元式elseprintf("%s:=%s/%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (/,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch);/輸出四元式 strcpy(Tabl