摘要：RG是形式語(yǔ)言中最典型的一類文法。主要討論和分析了RG的一種識(shí)別分析方法，給出了該方法的主要算法及實(shí)現(xiàn)的關(guān)鍵技術(shù)。對(duì)文法識(shí)別和自動(dòng)機(jī)生成有決定性的作用�？山o后續(xù)研究提供支持。

　　關(guān)鍵詞：RegularGrammar,識(shí)別,自動(dòng)機(jī)

　　1引言

　　喬姆斯基把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在于對(duì)產(chǎn)生式施加不同的限制。設(shè)G=(VN，VT，P，S)，若P中的每一個(gè)產(chǎn)生式的形式都是A→Ba或A→a，其中A和B都是非終結(jié)符，a是終結(jié)符，則G是3型文法或正規(guī)文法，即RG.RG又有左線性和右線性之分，即右部為“Ba”則為左線性，為“aB”則為右線性，本文僅以左線性情形，右線性情形就不贅述。

　　本文是在設(shè)計(jì)了一個(gè)識(shí)別輸入文法是否為RG的軟件的基礎(chǔ)上，著重對(duì)基本原理和關(guān)鍵技術(shù)做研究和分析，給出了一種識(shí)別方法的原理，在更好的加深鞏固形式語(yǔ)言這一重要理論的同時(shí)，使得該理論更緊密的與實(shí)踐相聯(lián)系。

　　2相關(guān)定義及理論

　　定義2.1文法與自動(dòng)機(jī)等價(jià)

　　根據(jù)形式語(yǔ)言理論，三型文法產(chǎn)生的語(yǔ)言是有窮自動(dòng)機(jī)(FA)所接受的串集合�？梢越o出3型文法和相應(yīng)識(shí)別系統(tǒng)FA間的轉(zhuǎn)換規(guī)則。

　　采用下面的規(guī)則可從正規(guī)文法G（假定G為右線性文法）直接構(gòu)造一個(gè)有窮自動(dòng)機(jī)NFAM；使得L(M)=L(G)：?

　�、僮帜副砼cG的終結(jié)符集相同；

　�、跒镚中的每個(gè)非終結(jié)符生成M的一個(gè)狀態(tài)，(不妨取成相同的名字)G的開始符號(hào)S是開始狀態(tài)S；

　�、墼黾右粋�(gè)新狀態(tài)Z，做為NFA的終態(tài)；

　�、軐�(duì)G中的形如A→tB其中t為終結(jié)符或ε，A和B為非終結(jié)符的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B；

　�、輰�(duì)G中形如A→t的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z。

　　定義2.2NFA的確定化

　　在有窮自動(dòng)機(jī)的理論里，有這樣的定理：設(shè)L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存在一個(gè)接受L的確定的有窮自動(dòng)機(jī)。將NFA轉(zhuǎn)換成接受同樣語(yǔ)言的DFA的算法稱為子集法。詳細(xì)證明可查閱參考文獻(xiàn)[1]。

　　3文法的識(shí)別主要算法分析

　　識(shí)別的關(guān)鍵是對(duì)所輸入的符號(hào)串的格式上的判斷，左部需要滿足為單個(gè)的大寫英文，而右部應(yīng)是單個(gè)小寫或是一個(gè)小寫和一個(gè)大寫的組合，只有這樣才滿足RG的要求，此處給出對(duì)右部的進(jìn)行識(shí)別的部分主要過程。

　　if(rlen==1)

　　{

　　charva=rs.GetAt(0);

　　findvalue(va,End,C);

　　rlen=-1;

　　}

　　以上算法是對(duì)文法右部的檢查,即判斷右部為單個(gè)小寫的情況.

　　if(rlen==2)

　　{

　　charVT1=rs.GetAt(0);

　　charVT2=rs.GetAt(1);

　　intfa=0;

　　while(fa<=maxlen)

　　{

　　if(fa==maxlen)

　　{D=0;fa++;}

　　else

　　{

　　if(VT1==Noend[fa].value)

　　{

　　intfb=0;

　　while(fb<=maxlen)

　　{

　　if(fb==maxlen){D=0;fb++;fa=maxlen+1;}

　　else

　　{

　　if(VT2==End[fb].value)//是終結(jié)符號(hào):

　　{fb=maxlen+1;fa=maxlen+1;}//檢查全部完畢:

　　else{fb++;}

　　}

　　}

　　}

　　else{fa++;}

　　}

　　以上是對(duì)小寫加大寫的情況的分析。對(duì)經(jīng)過判斷后的文法存儲(chǔ)，便可由接下的步驟完成文法到自動(dòng)機(jī)的轉(zhuǎn)換。這樣就完成了一個(gè)較為完整的RG識(shí)別過程。

　　4結(jié)論

　　本文主要根據(jù)RG的特點(diǎn)，在設(shè)計(jì)了一個(gè)識(shí)別過程的基礎(chǔ)上，完成文法判斷及到自動(dòng)機(jī)的轉(zhuǎn)換。希望能夠?qū)υ~法分析的初學(xué)者提供一些幫助。下步待繼續(xù)的工作是在自動(dòng)機(jī)的基礎(chǔ)上完成對(duì)輸入句子的運(yùn)行識(shí)別.

　　參考文獻(xiàn)：

　　[1]張幸兒.計(jì)算機(jī)編譯原理[M].2版.北京:科學(xué)出版社,2003:31-34.

　　[2]陳火旺,等.程序設(shè)計(jì)語(yǔ)言編譯原理[M].3版.北京:國(guó)防工業(yè)出版社,2000:34-35.

　　[3]王育堅(jiān).VC++面向?qū)ο缶幊探坛蘙M].北京:清華大學(xué)出版社,2003.

---

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiyingyonglw/23826.html