遞歸下降分析程序

1、精選文檔一、實驗?zāi)康模?根據(jù)某一文法編制調(diào)試遞歸下降分析程序，以便對任意輸入的符號串進(jìn)行分析。本次實驗的目的主要是加深對遞歸下降分析法的理解。二、程序算法描述這次的實習(xí)主要是根據(jù)以下文法實現(xiàn)一個遞歸下降分析器，依據(jù)文法如下：（1）E->TG（2）G->+TG|TG|（3）T->FS（4）S->*FS|/FS|（5）F->(E)|i在這個遞歸下降分析器程序中每一個非終結(jié)符E、G、T、S和F構(gòu)造相應(yīng)的遞歸函數(shù)，函數(shù)的名字表示文法左部的非終結(jié)符，函數(shù)中就是按文法中每個非終結(jié)符右部的候選式依次進(jìn)行匹配，根據(jù)對輸入串的分析如果非終結(jié)符可以用其中的一個候選式替代就返回1，否則

2、返回0。因為該文法中有五個非終結(jié)符，所以定義了五個函數(shù)，分別為E（），G（），T()，S()和F（）。當(dāng)輸入一串字符串后，就對該字符串進(jìn)行分析，首先從開始符號分析，所以首先調(diào)用E()函數(shù)，在E（）函數(shù)中會調(diào)用T（）和G(),就是每個非終結(jié)符的候選式中出現(xiàn)了哪個非終結(jié)符就調(diào)用哪個函數(shù)。所以，將字符串的第一個字符和E中的每個候選式匹配，如果成功就匹配輸入字符串的下一個字符，當(dāng)最后剩下的字符為#時，匹配成功。其實這個工程就是構(gòu)造一個語法樹。 程序總流程圖如下：圖1 程序總流程圖三、關(guān)鍵性代碼這個工程的主要工作用五個非終結(jié)符生成的句子是否和輸入字符串匹配，所以主要的工作是函數(shù)E（），G（），T()，S

3、()和F（）的編寫。1. 對非終結(jié)符E處理的函數(shù)E()這個函數(shù)主要是根據(jù)文法中的E->TG，在E（）中調(diào)用了T（）和G（）來進(jìn)行遞歸分析，這個就是構(gòu)造生成樹的一個分支。 int E() int f,t;/變量printf("E->TGt");/輸出根據(jù)的文法 flag=1; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符f=T();if (f=0) return(0); /表示當(dāng)前分析字符可由非終結(jié)符T推導(dǎo)出t=G(); if (t=0) return(0); /表示當(dāng)前分析字符可由非終結(jié)符G推導(dǎo)出else return(

4、1);2. 對非終結(jié)符G處理的函數(shù)G()這個函數(shù)主要是根據(jù)文法中G->+TG|-TG|，在函數(shù)中調(diào)用了T()和G()函數(shù)。將當(dāng)前字符和候選式的第一個字符進(jìn)行匹配，如果匹配成功，就調(diào)用該候選式中涉及到得第一個非終結(jié)符對應(yīng)的函數(shù)，一次遞歸嵌套調(diào)用。如果不是由第一個候選式推出然后依次匹配剩下的候選式。int G() int f; if(ch='+') /當(dāng)前字符式+ bi1=ch; printf("G->+TGt");/說明用的是第一個候選式e0='G'e1='='e2='>'e3='+&#

5、39;e4='T'e5='G'e6='#' Compute ();/計算推導(dǎo)式 flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 ch=a+i1;/讀取當(dāng)前字符的下一個字符 if (f=0) return(0); /表示當(dāng)前分析字符可由非終結(jié)符T推導(dǎo)出 t=G(); if (t=0) return(0); /表示當(dāng)前分析字符可由非終結(jié)符G推導(dǎo)出 if(ch='-') /當(dāng)前字符是-bi1=ch;printf("G->+TGt");/說明用的是第二個候選式

6、e0='G'e1='='e2='>'e3='+'e4='T'e5='G'e6='#' Compute();/輸出推導(dǎo)式 flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/讀取當(dāng)前字符的下一個字符f=T();if (f=0) return(0); /表示當(dāng)前分析字符可由非終結(jié)符T推導(dǎo)出G();/判斷當(dāng)前分析字符是否是非終結(jié)符G的一個產(chǎn)生式return(1);printf("G->t");

7、e0='G'e1='='e2='>'e3=''e4='#'Compute ();/推導(dǎo)式計算flag=1;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(1);3.對非終結(jié)符T處理的函數(shù)T()函數(shù)主要是根據(jù)文法中的T->FS,在函數(shù)中調(diào)用F()和S()，進(jìn)行遞歸分析，也是構(gòu)造語法樹的一個分支。int T() int f,t;printf("T->FSt");/說明所用的推導(dǎo)式是T->FSe0='T'e1

8、='='e2='>'e3='F'e4='S'e5='#' Compute ();/推導(dǎo)式計算flag=1;outDeduce ();/輸出字符串outputRemain ();/輸出剩余字符f=F();if (f=0) return(0);/表示當(dāng)前分析字符可由非終結(jié)符F推導(dǎo)出t=S();/表示當(dāng)前分析字符可由非終結(jié)符S推導(dǎo)出if (t=0) return(0);else return(1);4. 對非終結(jié)符S處理的函數(shù)S()函數(shù)的主要是文法要求S->*FS|/FS|，在函數(shù)中調(diào)用F()和S()函數(shù)。其

9、實這個過程和對非終結(jié)符G的處理很類似，將當(dāng)然字符與該非終結(jié)符的每個候選式的第一個字符進(jìn)行匹配。比如當(dāng)然字符為*，說明使用第一個候選式，然后調(diào)用F()和S()函數(shù)進(jìn)行遞歸分析。如果當(dāng)前字符為/，就使用第二個候選式，然后也調(diào)用F()和S()函數(shù)進(jìn)行遞歸分析。如果當(dāng)前字符是在和G中的任何一個候選式的第一個字符都不匹配，就返回1,說明當(dāng)然字符不能由非終結(jié)符G推出。int S()int f,t;if(ch='*') /當(dāng)前字符是*bi1=ch;printf("S->*FSt");/說明使用的是第一個候選式e0='S'e1='='e

10、2='>'e3='*'e4='F'e5='S'e6='#'Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/取出當(dāng)前字符的下一個字符f=F();if (f=0) return(0); /如果當(dāng)然分析字符可由非終結(jié)符F推出t=S();if (t=0) return(0); /如果當(dāng)然分析字符可由非終結(jié)符S推出 else return(1);if(ch='/') /當(dāng)前字符是/bi1=ch;pri

11、ntf("S->*FSt");/說明使用的是第二個候選式e0='S'e1='='e2='>'e3='*'e4='F'e5='S'e6='#'Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1; /取出當(dāng)前字符的下一個字符f=F();/如果當(dāng)然分析字符可由非終結(jié)符F推出if (f=0) return(0);t=S();/如果當(dāng)然分析字符可由非終結(jié)符S推出if

12、 (t=0) return(0);else return(1); printf("S->t"); e0='S'e1='='e2='>'e3=''e4='#' Compute ();/推導(dǎo)式計算 flag=1; ai1=ch; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(1); printf("S->t"); e0='S'e1='='e2='>'e3

13、=''e4='#' output();/推導(dǎo)式計算 flag=1; ai1=ch; outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符 return(1);5.對非終結(jié)符F處理的函數(shù)F()函數(shù)主要是根據(jù)文法中給出的F->(E)|i ，在函數(shù)中調(diào)用E()。這個過程和前面對其他非終結(jié)符的處理差不多，都是根據(jù)候選式中涉及的非終結(jié)符調(diào)用相應(yīng)的函數(shù)。將當(dāng)前字符和每一個候選式的第一個字符進(jìn)行匹配，比如如果當(dāng)然字符是（，就使用第一個候選式，然后調(diào)用E()進(jìn)行遞歸向下分析。如果當(dāng)前字符是i,就使用第二個候選式。int F() int f

14、; if(ch='(') /當(dāng)前字符是（bi1=ch;printf("F->(E)t");/說明使用的是第一個候選式 e0='F'e1='='e2='>'e3='('e4='E'e5=')'e6='#'Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1;/讀取下一個字符f=E();if (f=0) return(0); /如果當(dāng)然分析字符可

15、由非終結(jié)符E推出if(ch=')') /當(dāng)前字符是)bi1=ch;printf("F->(E)t");/說明使用的是第一個候選式 flag=0;outDeduce ();/輸出字符串 input1();/輸出剩余字符ch=a+i1;else printf("errorn");return(0); else if(ch='i') /當(dāng)前字符是ibi1=ch;printf("F->it");/說明使用的是第二個候選式e0='F'e1='='e2='>

16、'e3='i'e4='#'Compute ();/推導(dǎo)式計算flag=0;outDeduce ();/輸出字符串 outputRemain ();/輸出剩余字符ch=a+i1; else printf("errorn");return(0); return(1);四、測試結(jié)果這個程序測試時是往命令行中輸入一串字符串，來判斷該字符串是否是給出文法的一個句型，測試過程窗口中都詳細(xì)給了出來。這次我測試的字符串是“i+i*i#”。截圖如下：如果輸入的字符串不是文法的一個句型，窗口中會顯示error，說明輸入的字符串不正確。這里我測試的字符串是

17、“i+E”，截圖如下：五、實習(xí)總結(jié)這是編譯原理的第二次實習(xí)，這次的實習(xí)主要是實現(xiàn)一個遞歸下降分析器，主要就是根據(jù)一個文法，判斷用戶輸入的字符串是否是該文法的一個句型。這個實現(xiàn)的過程形象點(diǎn)就是構(gòu)造一個語法樹，從開始字符開始，將輸入字符串的第一個字符與文法中的非終結(jié)符的每個候選式的第一個字符進(jìn)行匹配，成功后匹配下一個字符，直到字符串的所有字符都能匹配上。這次的實習(xí)的過程讓我想起了數(shù)據(jù)結(jié)構(gòu)上學(xué)到的樹的構(gòu)建，實現(xiàn)的代碼有的地方也參照了網(wǎng)上的程序，實現(xiàn)的過程中出現(xiàn)了很多錯誤，總之，最后還是實現(xiàn)了。實習(xí)中出現(xiàn)的錯誤有的是將過程沒有分析完整，也有的語法出現(xiàn)了錯誤，自己也請教了同學(xué)。通過這次的實習(xí)，自己對遞歸

18、下降分析有了深入的認(rèn)識，其實課本上的知識自己看的很簡單，但是實現(xiàn)的過程是很麻煩的，自己以后也會多多練習(xí)。附錄：總程序：#include <stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>char a50 ,b50,d200,e10;/a存放輸入的字符串char ch;int n1,i1=0,flag=1,n=5;int E();int T();int G();int S();int F();void outDeduce();void outputRemain();void Co

19、mpute();void main()/*遞歸分析*/ int f,p,j=0; char x; d0='E' d1='=' d2='>' d3='T' d4='G' d5='#' printf("*遞歸下降分析器*n"); printf("請輸入字符串(以#號結(jié)束)n"); do scanf("%c",&ch); aj=ch; j+; while(ch!='#'); n1=j; ch=b0=a0; print

20、f("文法t分析串tt分析字符t剩余串n"); f=E(); if (f=0) return; if (ch='#') printf("輸入字符串正確n"); p=0; x=dp; else printf("errorn"); getchar(); getchar(); return; printf("n"); getchar(); getchar();int E() int f,t; printf("E-TGt"); flag=1; outDeduce();/輸出分析串 out

21、putRemain();/輸出剩余字符 f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int T() int f,t; printf("T-FSt"); e0='T' e1='=' e2='>' e3='F' e4='S' e5='#' Compute(); flag=1; outDeduce(); outputRemain(); f=F(); if (f=0) return(0);

22、 t=S(); if (t=0) return(0); else return(1);int G() int f; if(ch='+') bi1=ch; printf("G-+TGt"); e0='G' e1='=' e2='>' e3='+' e4='T' e5='G' e6='#' Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=T(); if (f=0) return

23、(0); G(); return(1); printf("G-t"); e0='G' e1='=' e2='>' e3='' e4='#' Compute(); flag=1; outDeduce(); outputRemain(); return(1);int S() int f,t; if(ch='*') bi1=ch; printf("S-*FSt"); e0='S' e1='=' e2='>'

24、 e3='*' e4='F' e5='S' e6='#' Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); printf("S-t"); e0='S' e1='=' e2='>' e3='' e4='#' Compute();

25、 flag=1; ai1=ch; outDeduce(); outputRemain(); return(1);int F() int f; if(ch='(') bi1=ch; printf("F-(E)t"); e0='F' e1='=' e2='>' e3='(' e4='E' e5=')' e6='#' Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=E(); if (f=0) return(0); if(ch=')') bi1=ch; printf("F-(E)t"); flag=0; outDeduce(); outputRemain(); ch=a+i1; else printf("errorn"); return(0); else if(ch='i') bi1=ch; printf("F-it"); e0='F' e1='