正規(guī)文法到正規(guī)式轉(zhuǎn)換

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 消除文法的左遞歸 實(shí)驗(yàn)時(shí)間 2015年5月19日 院系 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級(jí) 學(xué)號(hào) 姓名 實(shí)驗(yàn)?zāi)康妮斎耄喝我獾恼?guī)文法。輸出：相應(yīng)的正規(guī)式。實(shí)驗(yàn)原理3型文法（正則文法，線性文法） 如果對(duì)于某文法G，P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = WT其中TVT；U,WVN，則稱該文法G為左線性文法。如果對(duì)于某文法G，P中的每個(gè)規(guī)則具有下列形式：U : = T 或 U : = TW其中TVT；U, WVN，則稱該文法G為右線性文

2、法。左線性文法和右線性文法通稱為3型文法或正則文法，有時(shí)又稱為有窮狀態(tài)文法，簡(jiǎn)寫為RG。按照定義，對(duì)于正則文法應(yīng)用規(guī)則時(shí)，單個(gè)非終結(jié)符號(hào)只能被替換為單個(gè)終結(jié)符號(hào)，或被替換為單個(gè)非終結(jié)符號(hào)加上單個(gè)終結(jié)符號(hào)，或者被替換為單個(gè)終結(jié)符號(hào)加上單個(gè)非終結(jié)符號(hào)。3型文法所確定的語言為3型語言L3，3型語言可由確定的有限狀態(tài)自動(dòng)機(jī)來識(shí)別。程序設(shè)計(jì)語言的單詞可由正則文法產(chǎn)生，例如，標(biāo)識(shí)符的定義可由正則文法描述如下：:=/顯然，該文法描述了以字母開頭的字母數(shù)字串的集合?，F(xiàn)在要引入另一種適合于描述單詞的表示法正則表達(dá)式。正則表達(dá)式又稱為正則式，每個(gè)正則表達(dá)式描述的集合稱為正則集。之所以采用正則表達(dá)式來描述，主要基于

3、以下幾點(diǎn)原因：詞法規(guī)則簡(jiǎn)單，無需上下文無關(guān)文法那樣嚴(yán)格的表示法，用正則式表示法來理解被定義的符號(hào)集合比理解由重寫規(guī)則集合定義的語言更為容易；從正則式構(gòu)造高效識(shí)別程序比上下文無關(guān)文法更容易；可以從某個(gè)正則式自動(dòng)地構(gòu)造識(shí)別程序，它可以識(shí)別用該正則式表示的字符串集合中的字符串，從而減輕后面要介紹的詞法分析時(shí)的工作量?？捎糜谄渌鞣N信息流的處理，例如，已經(jīng)應(yīng)用于某些模式識(shí)別問題、文獻(xiàn)目錄檢索系統(tǒng)以及正文編輯程序等。正則表達(dá)式和正則集設(shè)有字母表。上的正則表達(dá)式和它所表示的正則集遞歸地定義如下：和都是上的正則表達(dá)式，它們所表示的正則集分別為和，其中是空串，是空集；任意的a是正則表達(dá)式，它所表示的正則集是a

4、；如果e1和e2是上的任意的正則表達(dá)式，且分別表示的正則集為L(zhǎng)（e1）和L（e2），則：e1/e2也是正則表達(dá)式，表示的正則集為L(zhǎng)（e1 / e2）L（e1）L（e2）。e1 e2也是正則表達(dá)式，表示的正則集為L(zhǎng)（e1 e2）L（e1）L（e2）。（e1）*也是正則表達(dá)式，表示的正則集為L(zhǎng)（e1）*）L（e1）*。定義中（1）和（2）定義了原子正則表達(dá)式，而（3）則表明字母表上的正則表達(dá)式可由原子正則表達(dá)式或較簡(jiǎn)單的正則表達(dá)式通過聯(lián)合、連接與閉包運(yùn)算構(gòu)成一般的正則表達(dá)式。正則表達(dá)式的性質(zhì)如果兩個(gè)正則表達(dá)式e1和e2表示的正則集相同，即值相等，則稱它們是等價(jià)的。記為e1e2。正則表達(dá)式與正則文法

5、的關(guān)系一個(gè)正則表達(dá)式的值是正則集，它是正則語言的另一種表示法。不難看出，除了符號(hào)外，一個(gè)正則表達(dá)式的含義類似于正則文法的一個(gè)非終結(jié)符號(hào)規(guī)則右部的含義。例如，對(duì)于 := 0/1/2/9，由非終結(jié)符數(shù)字所產(chǎn)生的字符串集合與正則表達(dá)式0/1/2/9所定義的字符串集合是相同的。正則集，它對(duì)應(yīng)一個(gè)不包含任何句子的語言，引進(jìn)的目的主要是為了理論上的完備性。3.實(shí)驗(yàn)內(nèi)容由正規(guī)（則）文法構(gòu)造正規(guī)（則）式4.實(shí)驗(yàn)心得通過實(shí)驗(yàn)明確了正規(guī)文法構(gòu)造正規(guī)式的方法，對(duì)正規(guī)式及正規(guī)文法有了進(jìn)一步的認(rèn)識(shí)欲了解 5.實(shí)驗(yàn)代碼與結(jié)果#include#includeusing namespace std;struct WF/產(chǎn)生式

6、 string left; /左 string right; /右;/正規(guī)文法轉(zhuǎn)換為正規(guī)式/轉(zhuǎn)換規(guī)則1(A-xB,B-y-A-xy)/轉(zhuǎn)換規(guī)則2 (A-x,A|y-A-x*(y)/轉(zhuǎn)換規(guī)則3(A-x,A-y,-A-x|y)void transform(WF *p,int n) int i,j,m,flag; /合并產(chǎn)生式 for (i=0; in; i+)for(j=i+1; jaA,A(S)-bA-A(S)-aA|bA的形式 if(pi.left=pj.left)&(pi.right1=pj.right1) pi.right=pi.right+|+pj.right; pj.left=; pj

7、.right=; /合并:轉(zhuǎn)換規(guī)則3(合并如S-a,S-b，S-c-S-a|b|c的形式) if(pi.right.length()=1&pj.right.length()=1&pi.left=pj.left) pi.right=pi.right+|+pj.right; pj.left=; pj.right=; /提取公因式:如S-aA|bA-S-(a|b)A的形式 for(i=0; i2&A=pi.right1&pi.right1=Z&pi.right2=|) for(j=1; ja |b ; if(j=flag-1) pi.right=(+pi.right.substr(0,pi.righ

8、t.length()-1)+)+pi.right.substr(pi.right.length()-1);/S-(a|b)A; /轉(zhuǎn)換規(guī)則2.1 (A-xA|y-A-x*(y) for(i=0; i(a|d)A(a|d) if(pi.left0=pi.rightpi.right.length()-1&pi.right.length()1) for(j=0; ja|d for(m=0; mpj.right.length(); m+) if(A=pj.rightm&pj.rightm(a|d)*(a|d) pj.right=; pj.left=; /轉(zhuǎn)換規(guī)則2.2(S-(xx)A A-aA 轉(zhuǎn)化為

9、S-(xx)a*A) for(i=0; i1 & pi.left0!=pi.rightpi.right.length()-1)/左部的非終結(jié)符不等于右部的最后一個(gè) for(j=0; j1 & pi.rightpi.right.length()-1=pj.left0 & pj.left0=pj.rightpj.right.length()-1) pi.right=pi.right.substr(0,pi.right.length()-1)+pj.right.substr(0,pj.right.length()-1)+*+pj.rightpj.right.length()-1; pj.right=

10、; pj.left=; /將表達(dá)式右部所有非終結(jié)符替換 flag=n; while(flag=0)/當(dāng)所有產(chǎn)生式的右部均為終結(jié)符構(gòu)成時(shí)停止轉(zhuǎn)換 for(i=0,flag=flag-1; in; i+) for(j=0; jpi.right.length(); j+) if(A=pi.rightj&pi.rightj=Z) for(m=0; mn; m+) if(pm.left0=pi.rightj&m!=i) pi.right=pi.right.substr(0,j)+pm.right+pi.right.substr(j+1); pm.left=; pm.right=; break; /再次合

11、并左部相等的產(chǎn)生式 for(i=0; in; i+) for(j=0; j1) pi.right=pi.right+|+(+pj.right+); pj.left=; pj.right=; else pi.right=pi.right+|+pj.right; pj.left=; pj.right=; /判斷文法類型bool IsZero(WF *p,int n) /判斷0型文法(左部不含非終結(jié)符則不是0型文法) int i,j; for(i=0; in; i+) /遍歷所有產(chǎn)生式 for(j=0; j=A&pi.leftj=Z) break; if(j=pi.left.length() cou

12、t該文法不是0型文法endl; return false; if(i=n) return true;/如果每個(gè)產(chǎn)生式都能找到非終結(jié)符bool IsFirst(WF *p,int n) /判斷1型文法(右邊長(zhǎng)度大于等于左邊長(zhǎng)度) if(IsZero(p,n) /先判斷是否是0型文法 int i; for(i=0; ipi.right.length()&pi.right.length()!=0) /判斷產(chǎn)生式左部長(zhǎng)度是否大于右部 break; if(i=n) return true; cout該文法是一個(gè)0型文法endl; return false;bool IsSecond(WF *p,int

13、n) /判斷2型文法(左部是一個(gè)非終結(jié)符) int i; if(IsFirst(p,n) /是否是1型文法 for(i=0; i=A&pi.left0=Z) /判斷產(chǎn)生式左部長(zhǎng)度是否為一，左部第一個(gè)是否是非終結(jié)符 break; if(i=n) return true; cout該文法是1型文法endl; return false;bool IsThird(WF *p,int n) /判斷3型文法(形如Aa,AaB的形式) int i; if(IsSecond(p,n) /是否是2型文法 for(i=0; i=3)|(pi.right0=A&pi.right0=Z) /判斷產(chǎn)生式右部字符個(gè)數(shù)是否

14、是1或者2，判斷右部第一個(gè)字符是否是非終結(jié)符 break; if(i=n) for(i=0; i=A&pi.right1=Z) break; if(i=n) cout該文法屬于3型文法endl; return true; cout該文法屬于2型文法endl; return false;int main( ) int i,j,n; string input;/*fstream myFile;myFile.open(1.txt);string q10;int j=0;int i=0;if(myFile.is_open()while(!myFile.eof()getline(myFile,qj);/coutqj+endl;ssi=qj;ss1i=qj;i+;j+;*/ while(true) cout請(qǐng)輸入文法產(chǎn)生式個(gè)數(shù)Nendln; WF *p=new WFn; / 初始化產(chǎn)生式數(shù)組 for(i=0; iinput; /輸入 for(j=0; jinput.length(); j+) /改變輸入數(shù)據(jù)的形式 if(inputj=-) pi.left=input.substr(0,j); pi.right=input.substr(j+2,input.length(); if(IsThir