編譯原理及實(shí)現(xiàn)(孫悅紅)期末復(fù)習(xí)

編譯原理期末復(fù)習(xí)注：下面出現(xiàn)的字母中，若無特別說明，小寫英文字母為終結(jié)符，大寫英文字母為非終結(jié)符，希臘字母為終結(jié)符與非終結(jié)符的任意組合。第一、二章（1）簡述編譯程序的概念及其構(gòu)成答：1）編譯程序：它特指把某種高級(jí)程序設(shè)計(jì)語言翻譯成等價(jià)的低級(jí)程序設(shè)計(jì)語言的翻譯程序。2)構(gòu)成：標(biāo)識(shí)符的各種屬性是在編譯的不同階段填入符號(hào)表的。詞法分析階段只能分析出標(biāo)識(shí)符名，語法分析階段只能判斷標(biāo)識(shí)符在語句中出現(xiàn)是否合法，只有到了語義分析階段，才能將標(biāo)識(shí)符的各種屬性填入符號(hào)表并使用這些屬性生成中間代碼。（2）簡述詞法分析階段的主要任務(wù)（也有可能問語法分析階段主要任務(wù)）答：詞法分析的任務(wù)是輸入源程序，對源程序進(jìn)行掃描，識(shí)別其中的單詞符號(hào)，把字符串形式的源程序轉(zhuǎn)換成單詞符號(hào)形式的源程序。語法分析的主要任務(wù)是對輸入的單詞符號(hào)進(jìn)行語法分析（根據(jù)語法規(guī)則進(jìn)行推導(dǎo)或者歸約），識(shí)別各類語法單位，判斷輸入是不是語法上正確的程序即：檢查這個(gè)符號(hào)串是否為該程序語言的句子。若是，輸出該句子的分析樹；若不是，則表示源程序存在語法錯(cuò)誤，需要報(bào)告錯(cuò)誤的性質(zhì)和位置。代碼進(jìn)行優(yōu)化的目的：提高目標(biāo)程序的執(zhí)行效率。代碼優(yōu)化首先在中間代碼上進(jìn)行。代碼優(yōu)化不是編譯程序的必要組成部分，不同的編譯程序所進(jìn)行的代碼優(yōu)化程度差別很大，能夠完成代碼優(yōu)化的編譯程序稱為“優(yōu)化編譯程序”。編譯的最后一步是將中間代碼生成特定機(jī)器上的低級(jí)語言代碼。這部分與機(jī)器類型有關(guān)，對程序中的每個(gè)變量指定存貯單元，把中間代碼的指令翻譯成等價(jià)的某種類型機(jī)器的機(jī)器指令代碼或匯編指令代碼。目標(biāo)代碼的形式可以使絕對指令代碼、可重定位的機(jī)器指令代碼或匯編指令代碼。(3)高級(jí)語言的特點(diǎn)：(4)說明解釋和編譯的區(qū)別：1)編譯要程序產(chǎn)生目標(biāo)程序，解釋程序是邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序；

2)編譯程序運(yùn)行效率高而解釋程序便于人機(jī)對話。解釋：以源程序作為輸入，輸入一句解釋執(zhí)行一句，不產(chǎn)生完整的目標(biāo)程序，相應(yīng)的翻譯程序稱為解釋程序(Interpreter)。編譯：將源程序全部譯為目標(biāo)程序，該目標(biāo)程序可在操作系統(tǒng)環(huán)境下直接執(zhí)行，相應(yīng)的翻譯程序稱為編譯程序(Compiler)（5）遍：所謂一“遍”是指編譯程序在編譯時(shí)把源程序或中間形式從頭到尾掃描一遍，并做相關(guān)的處理，生成新的中間形式或目標(biāo)代碼。 單遍程序：只對源程序進(jìn)行一遍掃描，就完成編譯的各項(xiàng)任務(wù)，產(chǎn)生目標(biāo)代碼。在單遍編譯程序中，不產(chǎn)生中間代碼，往往以語法分析程序?yàn)橹行模~法分析和語義分析作為語法分析的子程序。多遍程序：把編譯程序的五項(xiàng)任務(wù)分幾遍來進(jìn)行，每遍只完成部分任務(wù)。優(yōu)點(diǎn)是：可以減少內(nèi)存容量的需求。分遍后，以遍為單位分別調(diào)用編譯的各個(gè)程序，各遍程序可以相互覆蓋；可使各遍的編譯程序相互獨(dú)立，結(jié)構(gòu)清晰；能夠進(jìn)行充分的優(yōu)化，產(chǎn)生高質(zhì)量的目標(biāo)程序；可將編譯程序分為“前端”和“后端”，有利于編譯程序的移植。缺點(diǎn)：每遍都要讀符號(hào)、送符號(hào)，增加了許多重復(fù)性工作，降低編譯效率（6）前端主要與源語言有關(guān)，包括詞法分析、語法分析、語義分析和中間代碼生成、符號(hào)表的建立以及相應(yīng)的錯(cuò)誤處理和符號(hào)表操作。后端主要與目標(biāo)機(jī)器有關(guān)，包括代碼優(yōu)化、目標(biāo)代碼生成以及相應(yīng)的錯(cuò)誤處理和符號(hào)表操作。(7)補(bǔ)充第一章的概念：源程序：用程序設(shè)計(jì)語言書寫的程序，稱為源程序，該程序設(shè)計(jì)語言稱為源語言。目標(biāo)程序：經(jīng)翻譯程序加工后用目標(biāo)語言表示的程序。翻譯程序：將源程序譯成邏輯上等價(jià)的目標(biāo)程序的程序。匯編程序：將匯編語言程序翻譯成機(jī)器語言程序的程序。（8）第二章的概念：“字母表”：元素的非空有窮集合。典型的符號(hào)有字母、數(shù)字、各種標(biāo)點(diǎn)符號(hào)和各種運(yùn)算符。“符號(hào)串”：由字母表上0個(gè)或多個(gè)符號(hào)所組成的任何有窮序列。（注意：ε也是字母表上的符號(hào)串，它由0個(gè)符號(hào)組成。顯然，一個(gè)字母表上的全部符號(hào)串所組成的集合是無窮的。）符號(hào)串的長度：指符號(hào)串x中所含符號(hào)的個(gè)數(shù)，記為|x|。如|abc|=3，|abc+*abc|=8，而|ε|=0符號(hào)串相等：若x、y是字母表∑上的兩個(gè)符號(hào)串，那么當(dāng)且僅當(dāng)組成x的各符號(hào)與組成y的各符號(hào)依次相等時(shí)，則符號(hào)串x與符號(hào)串y相等，記作x=y。符號(hào)串的前(后)綴：指從符號(hào)串x的末尾(開頭)刪除0或多個(gè)符號(hào)后得到的符號(hào)串。如u、use都是use的前綴。如e、use都是use的后綴。符號(hào)串的子串：指從符號(hào)串x的開頭和末尾刪除0或多個(gè)符號(hào)后得到的符號(hào)串，如ver是university的子串,符號(hào)串的前綴、后綴都是它的子串。符號(hào)串的連接：若x、y是兩個(gè)符號(hào)串，則xy表示連接，是將符號(hào)串y連接在符號(hào)串x的后面。若x、y是字母表∑上的兩個(gè)符號(hào)串，則xy也是字母表∑上的符號(hào)串。（注意：連接沒有交換率，即xy≠yx而對于空串ε有εx=xε=x）集合的乘積運(yùn)算：令A(yù)、B為兩個(gè)符號(hào)串集合，A和B的乘積AB定義為：AB={xy|x∈A，y∈B}例如：A={a,b}B={c,d}，則AB={ac,ad,bc,bd}；對于空集合有{ε}有：{ε}A=A{ε}=A符號(hào)串的冪運(yùn)算：若x是符號(hào)串，則x的冪運(yùn)算定義為：n次冪個(gè)x相連接。例如：x=abc,x0=ε,x1=abc,x2=abcabc,…集合的冪運(yùn)算：設(shè)A為符號(hào)串集合，則A的冪運(yùn)算定義為：A0={ε}，A1=A，A2=AA……An=AA…A=AAn-1=An-1A，其中n>0 例如：A=={a，b}，則A0={ε}，A1={a,b}，A2={aa,ab,ba,bb}集合的正閉包和集合的閉包：設(shè)A為一個(gè)集合，則集合A的正閉包用A+表示， 定義為：A+=A1∪A2∪…∪An∪…集合A的閉包用A*表示，定義為：

A*=A0∪A+（一個(gè)集合的閉包比正閉包多個(gè)ε）（9）文法：描述語言語法結(jié)構(gòu)的形式規(guī)則，一般用一個(gè)四元式表示：G=（Vn，Vt，P，Z）其中Vn：非終結(jié)符集合(非空)，在產(chǎn)生式左部出現(xiàn)的Vt：終結(jié)符集合(非空)，只在產(chǎn)生式右部出現(xiàn)[Vn?Vt=?。Ｖ＝Vt∪Vn就是該文法的字匯表（即字匯表字母表）。]P：產(chǎn)生式或規(guī)則的集合(非空有窮集)α→β或α::=βZ：文法的識(shí)別符號(hào)或開始符號(hào)，至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次，Z?Vt（10）文法的EBNF表示：在書寫文法的規(guī)則時(shí)，可采用一些特殊的符號(hào)“或：|”、“重復(fù)連接：{}”、“組成：<>”、“優(yōu)先：（）”、“內(nèi)容可有可無：[]”來表示文法，這些符號(hào)叫做元符號(hào)（11）文法的形式（注：文法的形式一定要牢記，特別是2型和3型文法一定要牢記）1）0型文法(短語文法)：產(chǎn)生式形式為：α→β，其中α∈V+，β∈V*，V=Vn∪Vt2）1型(上下文有關(guān)文法)：產(chǎn)生式形式為:αUβ→αuβ，其中，U∈Vn，α、β∈V*，u∈V+，V=Vn∪Vt，U為非終結(jié)符號(hào)且只有在左右為α和β的環(huán)境下U可變?yōu)閡。因?yàn)橐?guī)則中的α和β不發(fā)生變化。例如：aUb→aABBaab3）2型文法（上下文無關(guān)文法)：產(chǎn)生式形式為：U→u，其中U∈Vn，u∈V*，V=V=Vn∪Vt4）3型文法(正規(guī)文法)：U→a或U∷=Wa（左線性）或U→aW（右線性）其中U，W∈Vn，a∈Vt從0型到3型文法對規(guī)則的限制逐漸增加，產(chǎn)生的語言類卻逐步縮小，即0型語言包含1型語言，1型語言包含2型語言，2型語言包含3型語言。因此，可以說3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0型文法的特例例題：設(shè)G=(VT，VN，S，P)是一個(gè)上下文無關(guān)文法，產(chǎn)生集合P中的任一個(gè)產(chǎn)生式應(yīng)具有什么樣的形式？若G是1型文法呢？若G是正則文法呢？上下文無關(guān)文法，產(chǎn)生式形式為：P?a，P?VN，a?(VTèVN)*。1型文法：產(chǎn)生式形式為:a?b其中：|a|￡|b|，僅S?e例外。正則文法：右線性文法：產(chǎn)生式形如：A?aB或A?a其中：a?VT*；A，B?VN左線性文法：產(chǎn)生式形如：A?Ba或A?a其中：a?VT*；A，B?VN（12）推導(dǎo)：所謂推導(dǎo)就是對于一個(gè)含非終結(jié)符A的符號(hào)串，利用規(guī)則A→α，把A替換成α得到新符號(hào)串的過程。若只需一步即可，則稱為直接推導(dǎo)。（可能考推導(dǎo)過程）最左推導(dǎo)：在推導(dǎo)的每一步，選擇符號(hào)串最左邊的非終結(jié)符進(jìn)行替換。最右推導(dǎo)：在推導(dǎo)的每一步，選擇符號(hào)串最右邊的非終結(jié)符進(jìn)行替換。（規(guī)范推導(dǎo)）(13)歸約：歸約是推導(dǎo)的逆過程，即用產(chǎn)生式的左部非終結(jié)符替換右部符號(hào)串。直接推導(dǎo)的逆：直接規(guī)約。(14)什么是句型？什么稱為句子？什么是語言？句型：從文法的起始符號(hào)出發(fā)，經(jīng)過0步或多步的推導(dǎo)能夠推導(dǎo)出來的符號(hào)（Vn，Vt）稱為句子。句子：只由終結(jié)符構(gòu)成的句型稱為句子，經(jīng)過多步推導(dǎo)，即推導(dǎo)長度>=1。(注意：每一個(gè)句子都有一個(gè)規(guī)范推導(dǎo),但并非每一個(gè)句型都有規(guī)范推導(dǎo)，只有那些能用規(guī)范推導(dǎo)產(chǎn)生的句型才是規(guī)范句型。)語言：所有句子的集合構(gòu)成該文法描述的語言。文法和語言有如下關(guān)系：1)給定一個(gè)文法,就能從結(jié)構(gòu)上唯一的確定其語言,即:G→L(G) 2)給定一種語言,能確定其文法,但不唯一,即:L→G1或G2或…。例2.4，已知文法G[Z]為：1)Z→aZb2)Z→ab或?qū)懗蒢→aZb|ab求該文法確定的語言。解：從識(shí)別符號(hào)開始推導(dǎo)，反復(fù)用規(guī)則1可得:Z=>aZb=>a2Zb2=>…=>an-1Zbn-1最后用規(guī)則2可得:Z=>aZb=>a2Zb2=>…=>an-11Zbn-1=>anbn所以該文法確定的語言為：L(G[Z])=(anbn|n≥1)例2.5，已知語言為:L(G)={abna|n≥1}，構(gòu)造產(chǎn)生該語言的文法。解：根據(jù)語言的形式，可構(gòu)造其文法G為:Z→aBaB→Bb|b還可以構(gòu)造文法G1為:Z→aBaB→bB|b從此可看出，G與G1是兩個(gè)不同的文法，但它們都可以描述語言{abna|n≥1}。稱G與G1為等價(jià)文法(15)遞歸規(guī)則：指那些在規(guī)則的右部含有與規(guī)則左部相同符號(hào)的規(guī)則。分左、右遞歸；直接、間接遞歸。例2.6判定如右文法所描述的語言是否是有窮的。Z→aBaB→bB|b解：因?yàn)槲姆ㄖ械牡诙l規(guī)則B→bB|b是遞歸規(guī)則，所以該文法描述的語言是無窮的。該文法描述的語言為{abna|n≥1}。(16)什么是短語？什么是直接短語（也稱為簡單短語）？什么是句柄？短語：如果存在某個(gè)文法非終結(jié)符P,滿足SβPγ,并且Pα則稱α為句型βαγ相對于非終結(jié)符P的短語。簡單短語：如果PTα,即從P出發(fā)一步推出α，則α稱為簡單短語。句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。(16)語法樹（推導(dǎo)過程）根節(jié)點(diǎn)代表文法的識(shí)別符號(hào)；內(nèi)部節(jié)點(diǎn)(非葉節(jié)點(diǎn))表示非終結(jié)符號(hào)每個(gè)末端節(jié)點(diǎn)(葉節(jié)點(diǎn))代表終結(jié)符或非終結(jié)符，它們從左向右排列起來，構(gòu)成句型。若葉節(jié)點(diǎn)都是終結(jié)符，則從左向右構(gòu)成句子。子樹與短語一一對應(yīng)：由末端節(jié)點(diǎn)組成的符號(hào)串，就是相對于子樹根的短語。任一根節(jié)點(diǎn)和葉結(jié)點(diǎn)是父子關(guān)系的短語皆為簡單短語。最左邊的簡單短語為句柄。推導(dǎo)過程不同，生成語法樹的過程也不同，但最終生成的語法樹是相同的，即無二義性?？碱}：文法G[S]為：S→SdT|TT→T<G|GG→(S)|a試給出句型(SdG)<a的推導(dǎo)過程及語法樹，并找出(SdG)<a的短語，直接（簡單）短語、句柄。分析：（1）推導(dǎo)（最好是規(guī)范推導(dǎo)）和畫語法樹。（2）根據(jù)所畫出的語法樹，可以很快的找出短語，直接短語，句柄等。答：（1）STTTT<GTG<GT(S)<GT(SdT)<GT(SdG)<GT(SdG)<a（2）短語：G，SdG,(SdG),a,(SdG)<a直接短語：G，a句柄：G語法樹：考題：2)文法G[E]的產(chǎn)生式為E→E+T|TT→T*F|FF→i|(E)①對于句型(i+i)*i，給出最左最右推導(dǎo)及相應(yīng)的推導(dǎo)樹②列出句型的所有短語、簡單短語。答：（1）最左推導(dǎo)：ETTTT*FTF*FT(E)*FT(E+T)*FT(T+T)*FT(F+T)*FT(i+T)*FT(i+F)*FT(i+i)*FT(i+i)*i最右推導(dǎo)ETTTT*FTT*iTF*iT(E)*iT(E+T)*iT(E+F)*iT(E+i)*iT(T+i)*iT(F+i)*iT(i+i)*i推導(dǎo)樹如下：（2）短語;i,i+i,(i+i),(i+i)*i直接短語：i句柄：i（17）二義性文法（簡答題）：一個(gè)文法中存某個(gè)句子，它有兩個(gè)不同的最左（或者最右推導(dǎo)）例如2.11，有文法G[E]：E∷=E+E|E*E|（E）|i，分析該文法是否為二義性文法。解：為了判斷該文法是否為二義性文法，我們找一個(gè)句子i+i*i，如果能夠構(gòu)造出兩個(gè)不同的語法樹，則說明該文法是二義性文法。下面兩個(gè)圖是為句子i+i*i構(gòu)造的兩棵語法樹，如圖2.2(a)、(b)所示。由于這兩棵語法樹不同，所以可以肯定文法G[E]是二義性文法。改寫文法G[E]：E∷=E+E|E*E|（E）|i，使其無二義性。解：新添非終結(jié)符號(hào)T和F，將文法寫成：E∷=T|E+T，T∷=F|T*F，F(xiàn)∷=(E)|i這樣，就避免了二義性。用改寫后的文法給出句i+i*i的語法樹如圖2.4所示。此時(shí)的語法樹是唯一的。（18）文法的實(shí)用限制限制條件：1)不能有U∷=U這樣的有害規(guī)則。2)不能有多余規(guī)則：一是推導(dǎo)中始終用不到的規(guī)則。二是一旦使用某規(guī)則后無法推出終結(jié)符號(hào)的規(guī)則。例2.14，有文法：Z∷=Aa，A∷=Ca|Bb，B∷=Ba|a，C∷=Cb，D∷=b，去掉有害規(guī)則和多余規(guī)則。解：該文法中，由于非終結(jié)符號(hào)D不出現(xiàn)任何規(guī)則的右部且D不是開始符號(hào)，所以在句子的推導(dǎo)中不可能用到規(guī)則D∷=b，因此是多余規(guī)則，應(yīng)該去掉。規(guī)則C∷=Cb也是一條多余規(guī)則，因?yàn)橐坏┦褂昧诉@條規(guī)則以后，將使推導(dǎo)無窮地進(jìn)行下去，即C=>Cb=>Cbb=>Cbbb…,無法推出終結(jié)符號(hào)串。而規(guī)則A∷=Ca因?yàn)闀?huì)產(chǎn)生C，所以也要去掉。最后得到的文法為：Z∷=AaA∷=BbB∷=Ba|a（19）根據(jù)語言推文法這類題目首先要看清題目，指定的是什么文法，一般都是2型（上下無關(guān)文法）或者3型（正規(guī)文法），這兩類文法形式一定要記住。掌握幾個(gè)基本形式{an|n>0}對應(yīng)文法S→aS|a {an|n>=0}對應(yīng)文法S→aS|ε(ε是空字) {anbn|n>0}對應(yīng)文法S→aSb|ab1、按指定類型給出下列語言的文法,并指出語言的類型。（10分）(1)L1={anbmcn|n≥0,m>0}二型文法：S→aSc|BB→bB|b(2)L2={0na1nbmcm|n>0，m≥0}二型文法：S→ABA→0A1|0a1B→bBc|ε2、按指定類型給出下列語言的文法。（10分）(1)L1={candbm|n≥0,m>0}用正規(guī)文法。S→cAA→aA|BB→dCC→bC|b(2)L2={0na1nbmcm|n>0,m≥0}用二型文法。S→ABA→0A1|0a1B→bBc|ε3、按指定的類型給出下列語言的文法（10分）(1)L1={canbm|n≥0,m>0}用正規(guī)文法。S→cAA→aA|BB→bB|b(2)L2={0na1nbm|n>0，m≥0}用二型文法。S→ABA→0A1|0a1B→bB|ε4、按指定的類型給出下列語言的文法（10分）L1={anbmc|n>=0,m>0}用正規(guī)文法S→aS|AA→bA|bBB→cL2={a0n1nbdm|n>0,m>0}用二型文法S→ABA→aTT→0T1|01B→bDD→dD|d第三章詞法分析(1)正則文法：程序設(shè)計(jì)語言的單詞符號(hào)可用3型文法來描述，3型文法也稱為正則文法。(2）狀態(tài)圖：有窮的有向圖。結(jié)點(diǎn)代表狀態(tài)(非終結(jié)符)，用圓圈表示；狀態(tài)間用有向弧線連接，連接弧上標(biāo)記有符號(hào)（終結(jié)符），表示在弧線射出端的狀態(tài)下，讀入弧線上標(biāo)記的符號(hào)可轉(zhuǎn)換到弧線指向的狀態(tài)。狀態(tài)圖只有有窮個(gè)狀態(tài)，其中有一個(gè)是開始狀態(tài)（新增設(shè)的），旁邊加“”，至少有一個(gè)狀態(tài)是結(jié)束狀態(tài)（開始符號(hào)），結(jié)束狀態(tài)常用雙圈表示。如U→a的規(guī)則，畫一條從開始狀態(tài)S指向結(jié)點(diǎn)U的弧線，并在弧上標(biāo)記a。如U∷=Wa的規(guī)則，畫一條從結(jié)點(diǎn)W指向結(jié)點(diǎn)U的弧線，并在弧上標(biāo)記a。例3.1，設(shè)有正則文法G[Z]：Z→U0|V1U→Z1|1V→Z0|0畫出該文法對應(yīng)的狀態(tài)圖。解：根據(jù)狀態(tài)圖的畫法，首先確定狀態(tài)圖的結(jié)點(diǎn)。文法中有三個(gè)非終結(jié)符號(hào)Z、U、V，加上代表開始狀態(tài)S的結(jié)點(diǎn)，因此共有四個(gè)結(jié)點(diǎn)，其中S結(jié)點(diǎn)為開始狀態(tài)，Z結(jié)點(diǎn)為終結(jié)狀態(tài)。對于規(guī)則Z→U0|V1，則分別從結(jié)點(diǎn)U和結(jié)點(diǎn)V畫指向結(jié)點(diǎn)Z的弧線，并分別在弧線上標(biāo)記0和1；對于規(guī)則U→Z1|1，從Z畫指向U的弧線，從S畫指向U的弧線，并分別在弧線上標(biāo)記為1；對于規(guī)則V→Z0|0，分別從Z和S畫指向V畫弧線，并分別在弧線上標(biāo)記0。如圖3.4所示。 例3.2，對句子0110進(jìn)行的分析。解：根據(jù)上面介紹的狀態(tài)圖使用方法，我們在圖3.5（a）列出分析的每一步。首先，在開始狀態(tài)S下掃描的第一個(gè)符號(hào)是0，轉(zhuǎn)到狀態(tài)V，表示0是句柄，歸約到V。接下來，在狀態(tài)V掃描1，轉(zhuǎn)到狀態(tài)Z，此時(shí)句柄為V1，歸約成Z。再往下掃描1，由狀態(tài)Z轉(zhuǎn)到狀態(tài)U，表示句柄為Z1歸約為U。最后，掃描0，轉(zhuǎn)到狀態(tài)Z，此時(shí)句柄為U0，歸約為Z，從而形成圖3.5（b）所示的語法樹。（利用狀態(tài)圖識(shí)別句子的方法是一種自底向上的分析方法。句柄是當(dāng)前狀態(tài)的名字和隨后掃描的字符，而句柄所要?dú)w約的符號(hào)就是下一個(gè)狀態(tài)的名字。）(3)正則表達(dá)式設(shè)有兩個(gè)正則表達(dá)式R1和R2，它們分別產(chǎn)生語言L1和L2，則正則表達(dá)式運(yùn)算符的操作定義如下：

連接：R1.R2={xy|x∈L1，y∈L2}

選擇：R1|R2={x|x∈L1或x∈L2}

重復(fù)：{R1}={x|x∈L1*，L1*=L10∪L11∪L12∪…}設(shè)∑是有窮字母表，在∑上的正則表達(dá)式及所描述的語言可遞歸定義如下：1.Φ是一個(gè)表示空集的正則表達(dá)式。2.ε是一個(gè)正則表達(dá)式，它所表示的語言僅含一個(gè)空符號(hào)串，即{ε}3.a是一個(gè)正則表達(dá)式，a∈∑，它所表示的語言由符號(hào)a所組成{a}4.如果R1和R2是正則表達(dá)式，其表示的語言分別為L1和L2，則1)R1|R2或R1+R2是一個(gè)表示語言L1∪L2的正則表達(dá)式2)R1.R2或R1R2是一個(gè)表示語言L1L2的正則表達(dá)式3){R1}或R1*是一個(gè)表示語言L1*的正則表達(dá)式4)(R)表示的語言仍是L1的正則表達(dá)式，但調(diào)整優(yōu)先權(quán)，使括號(hào)內(nèi)的運(yùn)算符優(yōu)先權(quán)高于括號(hào)外的。5.所有∑上的正則表達(dá)式可由上述4條規(guī)則構(gòu)造出來。注意：不要混淆Φ和ε，正則表達(dá)式ε描述的語言只含一個(gè)空字符串ε，而Φ表示不含有任何字符串。 優(yōu)先級(jí)：重復(fù)>連接>選擇(遞減順序)，故表達(dá)式(p|q).r中的括號(hào)則不能去掉。不同的正則表達(dá)式可描述相同的語言。如果兩個(gè)正則表達(dá)式表示相同的語言，則稱這兩個(gè)表達(dá)式等價(jià)或相等。正則表達(dá)式的部分操作符滿足結(jié)合律、交換律和分配律:即(ab)c=a(bc)(a|b)|c=a|(b|c)a|b=b|aa(b|c)=ab|ac注意：連接不滿足交換律，即ab≠ba例3.5，設(shè)字母表∑={a,b}，則a,b,Φ和ε都是∑上的正則表達(dá)式，所描述的語言為{a}、、{}、{ε}，求表達(dá)式{a}、{a|b}和{aa|ab|ba|bb}定義的語言。解：根據(jù)正則表達(dá)式的形式定義，可得如下結(jié)果：表達(dá)式{a}定義的語言為：{ambn|m≥0,n≥0}，表達(dá)式{a|b}定義的語言為：{x|x∈{a,b}*}，即字母a或b組成的任意長度字符串。？而表達(dá)式{aa|ab|ba|bb}表示的語言由字母a或b組成的所有偶長度字符串。？（4）正則文法到正則表達(dá)式的轉(zhuǎn)換正則表達(dá)式在描述語言時(shí)比正則文法更為簡潔。轉(zhuǎn)換規(guī)則：1.A→xB，B→y正規(guī)式為：A=xy2.A→xA|y正規(guī)式為：A={x}y3.A→x，A→y正規(guī)式為：A=x|y例3.7，有正則文法如下，將其換成等價(jià)的正則表達(dá)式。S→aSS→aBB→bCC→aCC→a解：第一步，利用3條規(guī)則：S={a}aB——第二條；B=bC——第三條；C={a}a——第二條然后按解方程組的方法可得：C={a}a；B=b{a}a；S={a}ab{a}a最終轉(zhuǎn)成正則表達(dá)式：S={a}ab{a}a(5)DFA（確定的有窮狀態(tài)自動(dòng)機(jī)）：后續(xù)狀態(tài)唯一，不存在ε一個(gè)確定的有窮自動(dòng)機(jī)M（記作DFAM）是一個(gè)五元組：M=（Q，Σ，q0，F(xiàn)，δ）其中：Σ：是一個(gè)字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)Q：是一個(gè)有窮的狀態(tài)集合。q0：q0∈Q，是唯一的初始狀態(tài)。F：F∈Q，稱為終結(jié)狀態(tài)集合。δ：狀態(tài)轉(zhuǎn)換函數(shù)，是一個(gè)Q×∑→Q的單值映射。在確定的有窮自動(dòng)機(jī)中，狀態(tài)轉(zhuǎn)換函數(shù)的具體形式如下：δ（q，a）=q’，其中q∈Q，q’∈Q，a∈∑q’是一個(gè)單值函數(shù)，表示在當(dāng)前狀態(tài)為q下，輸入符號(hào)為a時(shí)，自動(dòng)機(jī)將從狀態(tài)q轉(zhuǎn)換到下一個(gè)狀態(tài)q’，q’稱為q的后繼狀態(tài)。狀態(tài)矩陣中的第一列元素與自動(dòng)機(jī)M中的狀態(tài)集合Q一一對應(yīng)，初始狀態(tài)q0是第一列的第一個(gè)元素，右上角標(biāo)記*的元素對應(yīng)終結(jié)狀態(tài)；第一行元素與子目標(biāo)中的每個(gè)符號(hào)相對應(yīng)。例3.9，設(shè)計(jì)能接受偶數(shù)個(gè)0和偶數(shù)個(gè)1組成的串的有窮自動(dòng)機(jī)，畫出其狀態(tài)圖及狀態(tài)轉(zhuǎn)換矩陣并判別110101、11101能否被該自動(dòng)機(jī)接受。解：首先設(shè)計(jì)能接受偶數(shù)個(gè)0和偶數(shù)個(gè)1組成的數(shù)字串的有窮自動(dòng)機(jī)如下：（首先想到一些例子00、11、1010、0101、0110、1001）M1=（{S,A,B,C}，{0,1}，S，{S}，δ）δ（S，0）=Bδ（S，1）=Aδ（A，0）=Cδ（A，1）=Sδ（B，0）=Sδ（B，1）=Cδ（C，0）=Aδ（C，1）=B判別110101、11101能否被該自動(dòng)機(jī)接受：δ(S，110101)=δ(A，10101)=δ(S，101)=δ(B，101)=δ(C，01)=δ(A，1)=S(接受)δ(S，11101)=δ(A，1101)=δ(S，101)=δ(A，01)=δ(C，1)=B(拒絕)(5)NFA（不確定的有窮狀態(tài)自動(dòng)機(jī)）：后續(xù)狀態(tài)唯一，不存在ε一個(gè)不確定的有窮自動(dòng)機(jī)NFAM’是一個(gè)五元式M’=（Q，∑∪{ε}，q0，F(xiàn)，δ）其中：Q：有窮狀態(tài)集(同DFA)∑∪{ε}：輸入字母表與空串組成的集合q0：開始狀態(tài)q0∈Q(同DFA)F：終止?fàn)顟B(tài)集F∈Q(同DFA)δ：狀態(tài)轉(zhuǎn)換函數(shù)，為Q*∑∪{ε}到Q的子集的映射。不確定的有窮自動(dòng)機(jī)同樣可以用狀態(tài)圖和狀態(tài)轉(zhuǎn)換矩陣來表示，表示方法與確定的相同。為了判別一個(gè)字符串x能否被NFA接受，還需要對狀態(tài)轉(zhuǎn)換函數(shù)做補(bǔ)充定義：設(shè)δ(q,a)={p1,p2,…,pn}，其中a∈∑∪{ε}，q,p1,p2,…,pn∈Q1)δ(q,ε)=ε-closure(q)，其中ε-closure(q)表示從狀態(tài)q出發(fā)，沿著ε弧到達(dá)的后繼狀態(tài)集合以及再從這些后繼狀態(tài)沿著ε弧所能到達(dá)的所有狀態(tài)集合。（并且包括自身）2)δ(q,at)=δ(p1,t)∪δ(p2,t)∪…∪δ(pn,t),其中a∈∑∪{ε},t∈∑*3)δ({q1,q2,…,qn},x)=δ(q1,x)∪δ(q2,x)∪…∪δ(qi,x)其中x∈∑*，表示從不確定自動(dòng)機(jī)的狀態(tài)集出發(fā)，掃描字符串x后，所到達(dá)的狀態(tài)集等于從當(dāng)前狀態(tài)集的每一個(gè)狀態(tài)集出發(fā)，掃描字符串x后所到達(dá)的狀態(tài)集之和。M’所接受的語言為L（M’）={x|x∈∑*，δ(q0,x)=Q’，Q’∩F≠Φ}例3.10，有NFAM’=（{0,1，2}，{a,b}∪{ε},0,{2},δ）其中：δ（0，a）={2},δ（0，ε）={1},δ（1，b）={1,2},δ（2，a）={2},δ（2，b）={2}畫出其狀態(tài)圖及狀態(tài)轉(zhuǎn)換矩陣，確定該自動(dòng)機(jī)接收的語言。解：不確定的有窮自動(dòng)機(jī)用狀態(tài)圖和狀態(tài)轉(zhuǎn)換矩陣來表示，如圖3.12(a)和3.12(b)所示。該自動(dòng)機(jī)接受的語言為L(M’)={(a|bm)(a|b)n|m≥1,n≥0}（6）NFA和DFA之間的轉(zhuǎn)化（綜合題，15分）1、狀態(tài)集P的ε閉包2、狀態(tài)集P的a弧轉(zhuǎn)換集設(shè)P仍是一自動(dòng)機(jī)M’的狀態(tài)集的子集，P={P1,P2,…,Pn},a∈∑，即a是字母表∑的一個(gè)輸入符號(hào)，則Pa弧轉(zhuǎn)換集為：Pa=ε-closure(J)，其中J=δ(P1,a)∪δ(P2,a)∪…∪δ(Pn,a)沿著標(biāo)記為a的弧所到達(dá)的后繼狀態(tài)集合，再加上這些后繼狀態(tài)集合中的每個(gè)狀態(tài)的ε閉包，3、根據(jù)NFAM’構(gòu)造DFAM例題：構(gòu)造確定的有窮自動(dòng)機(jī)過程如下：1）首先根據(jù)ε閉包的計(jì)算方法求NFAM的開始狀態(tài)q0’的ε閉包，從而確定DNFAM的開始狀態(tài)q0。q0=ε-closure({q0’})=ε-closure({1})={1，4}2）根據(jù)弧轉(zhuǎn)換集的計(jì)算方法求開始狀態(tài)q0對每個(gè)輸入符號(hào)的弧轉(zhuǎn)換集q0a、q0b和q0c從而確定與開始狀態(tài)q0有關(guān)的狀態(tài)轉(zhuǎn)換函數(shù)。δ(q0,a)=q0a=ε-closure(δ(1,a)∪δ(4,a))=ε-closure({2,3}∪Φ)={2,3}將{2,3}作為新狀態(tài),并令q1={2,3}，即得到δ(q0,a)=q1δ(q0,b)=q0b=ε-closure(δ(1,b)∪δ(4,b))=ε-closure(Φ)=Φδ(q0,c)=q0c=ε-closure(δ(1,c)∪δ(4,c))=ε-closure(Φ)=Φ由于δ(q0,b)=Φ，δ(q0,c)=Φ，說明沒有新狀態(tài)產(chǎn)生。至此，我們得到有關(guān)開始狀態(tài)q0的全部狀態(tài)轉(zhuǎn)換函數(shù)只有一個(gè)，即δ(q0,a)=q1。3）按步驟2的方法，對每個(gè)新狀態(tài)計(jì)算相關(guān)的狀態(tài)轉(zhuǎn)換函數(shù)。計(jì)算狀態(tài)q1的狀態(tài)轉(zhuǎn)換函數(shù)：δ(q1,a)=q1a=ε-closure(δ(2,a)∪δ(3,a))=ε-closure({2}∪Φ)={2}，將{2}作為新狀態(tài),并令q2={2}δ(q1,b)=q1b=ε-closure(δ(2,b)∪δ(3,b))=ε-closure({4}∪Φ)={4}，將{4}作為新狀態(tài),并令q3={4}δ(q1,c)=q1c=ε-closure(δ(2,c)∪δ(3,c))=ε-closure(Φ∪{3,4})={3,4}，將{3，4}作為新狀態(tài),并令q4={3，4}至此，得到有關(guān)開始狀態(tài)q1的全部狀態(tài)轉(zhuǎn)換函數(shù)。4）接下來，計(jì)算新狀態(tài)q2、q3、q4的有關(guān)狀態(tài)轉(zhuǎn)換函數(shù)如下：δ(q2,a)={2}=q2,δ(q2,b)={4}=q3,δ(q2,c)=Φδ(q3,a)=Φ,δ(q3,b)=Φ,δ(q3,c)=Φδ(q4,a)=Φ，δ(q4,b)=Φ，δ(q4,c)={3,4}=q4計(jì)算到此，不再有新狀態(tài)出現(xiàn)。5）根據(jù)上面求出的各個(gè)狀態(tài)確定終結(jié)狀態(tài)集 F={p|p∩F’≠Φ}，其中p為M的每個(gè)狀態(tài)子集：因?yàn)閝0={1,4}、q1={2,3}、q2={2}、q3={4}、q4={3,4}，而F’={4}，q0、q3、q4與F’相交不為空，所以確定終結(jié)狀態(tài)集F={q0,q3,q4}最后,我們得到確定的有窮自動(dòng)機(jī)如下：DFAM=({q0,q1,q2,q3,q4},{a,b,c},δ,q0,{q0,q3,q4})其中狀態(tài)轉(zhuǎn)換函數(shù)為：δ(q0,a)=q1δ(q1,a)=q2，δ(q1,b)=q3，δ(q1,c)=q4δ(q2,a)=q2，δ(q2,b)=q3δ(q4,c)=q4該轉(zhuǎn)換后的狀態(tài)圖及狀態(tài)轉(zhuǎn)換矩陣如圖所示：（驗(yàn)證正確性：NFA、DFA描述語言一致）(7)根據(jù)正則表達(dá)式構(gòu)造有窮自動(dòng)機(jī)1)基本正則表達(dá)式Φ、ε和基本正則表達(dá)式Φ、ε和a（a∈∑）：Φ描述的語言為空集，ε和a所定義的語言分別為{ε}和{a}，可構(gòu)造的NFA分別是，見右圖；2)連接：設(shè)R1和R2都是基本正則表達(dá)式，則構(gòu)造與正則表達(dá)式R1.R2等價(jià)的NFA3)選擇：設(shè)R1和R2都是正則表達(dá)式，則構(gòu)造與正則表達(dá)式R1|R2等價(jià)的NFAR4)重復(fù)：設(shè)R是正則表達(dá)式，則構(gòu)造與正則表達(dá)式{R}等價(jià)的NFARNFA-〉DFA過程類似上題（8）確定的有窮自動(dòng)機(jī)的化簡（會(huì)考）對于任何給定的DFA，都有一個(gè)含有最少狀態(tài)的等價(jià)的DFA，而且這個(gè)最少狀態(tài)的DFA是唯一的。從任何DFA中都可以得到這個(gè)最少狀態(tài)的DFA。1、等價(jià)狀態(tài)與不等價(jià)狀態(tài)：在一個(gè)確定的有窮自動(dòng)機(jī)里，如果從S1狀態(tài)出發(fā)接受的所有符號(hào)串集合與從S2狀態(tài)出發(fā)接受的所有符號(hào)串集合一樣，那么稱狀態(tài)S1和S2是等價(jià)的；否則是不等價(jià)的。例：有δ(1,a)=3，δ(2,a)=3，因此，狀態(tài)1和狀態(tài)2是等價(jià)的。2.多余狀態(tài)（應(yīng)該刪除）：有兩種：一是指從初始狀態(tài)到該狀態(tài)之間沒有通路。二是指從該狀態(tài)到終止?fàn)顟B(tài)之間沒有通路。對S3={0，2}化分:因?yàn)棣?0,a)=1，δ(2,a)=1；δ(0,b)=2，δ(2,b)=42、4不屬于同一狀態(tài)集，所以將S3分成S5={0}，S6={2}至此，不再能繼續(xù)劃分，最終得到不能劃分的狀態(tài)集有S2={3，4}，S4={1}，S5={0}，S6={2}每個(gè)狀態(tài)集留一個(gè)狀態(tài)得：S2={3}，S4={1}，S5={0}，S6={2}將原來的轉(zhuǎn)換函數(shù)中的狀態(tài)4改成狀態(tài)3，得到δ(0,a)=1，δ(1,a)=3，δ(2,a)=1，δ(3,a)=3，δ(3,a)=3δ(0,b)=2，δ(1,b)=2，δ(2,b)=3，δ(3,b)=3，δ(3,b)=3去掉重復(fù)的，最終得到化簡后的狀態(tài)函數(shù)如下，對應(yīng)的狀態(tài)圖如圖2所示。δ(0,a)=1，δ(1,a)=3，δ(2,a)=1，δ(3,a)=3δ(0,b)=2，δ(1,b)=2，δ(2,b)=3，δ(3,b)=3（9）LEX（lexicalAnanlyzerGenerator）是一個(gè)詞法分析程序的自動(dòng)生成器。LEX是1972年貝爾實(shí)驗(yàn)室首先在UNIX上實(shí)現(xiàn)的。FLEX（FastlexicalAnanlyzerGenerator）是對LEX的擴(kuò)充，它可在MS-DOS下運(yùn)行。本書中實(shí)際使用的是FLEX，我們?nèi)苑Q呼LEX。LEX能根據(jù)給定的正則表達(dá)式自動(dòng)生成相應(yīng)的詞法分析程序。LEX的輸入是用LEX語言寫的源程序，生成一個(gè)用C語言描述的詞法分析器，所以LEX本身就相當(dāng)于LEX語言的編譯程序。LEX生成的目標(biāo)程序包含一個(gè)狀態(tài)轉(zhuǎn)換矩陣和一個(gè)控制執(zhí)行程序?？碱}：構(gòu)造奇數(shù)個(gè)0和奇數(shù)個(gè)1組成的自動(dòng)機(jī)。（10分）1狀態(tài)1：偶數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)2：奇數(shù)個(gè)0偶數(shù)個(gè)1狀態(tài)3：奇數(shù)個(gè)0奇數(shù)個(gè)1狀態(tài)4：偶數(shù)個(gè)0奇數(shù)個(gè)（如果題目改成偶數(shù)個(gè)0，奇數(shù)個(gè)1，只要將狀態(tài)4轉(zhuǎn)換成終態(tài)即可，其他類似。）第四章、語法分析——自頂向下分析（LL（1）分析法和遞歸向下分析法）實(shí)際上，F(xiàn)IRST(α)就是從α可能推導(dǎo)出的所有開頭終結(jié)符號(hào)和可能的ε。FOLLOW(A)就是在所有句型中出現(xiàn)在緊接A之后的終結(jié)符號(hào)或#。（在FOLLOW集合中無ε）例題：S→aBc|bc|c，則FIRST(S)={a，b，c}例4.4有文法E→TE’，E’→+TE’,E’→ε,T→FT’,T’→*FT’,T’→ε，F(xiàn)→(E)|i，求各Vn的FOLLOW集。解：首先，我們需要求出某些符號(hào)的FIRST集：FIRST(E)=FIRST(T)=FIRST(F)={(，i}FIRST(E’)={+，ε}，F(xiàn)IRST(T’)={*，ε}接下來，按FOLLOW集定義求各非終結(jié)符號(hào)的FOLLOW集：FOLLOW(E)={)，#}(因?yàn)镋出現(xiàn)在產(chǎn)生式的右邊的情況只有F→(E)|i，所以根據(jù)定義和規(guī)則1)FOLLOW(E’)=FOLLOW(E)={)，#}(因?yàn)镋→TE’，應(yīng)用規(guī)則3。此外，沒有其他產(chǎn)生式能提供了)FOLLOW(T)=FIRST(E’)∪FOLLOW(E)∪FOLLOW(E’)={+，)，#}[因?yàn)镋’→+TE’，E’≠ε，應(yīng)用規(guī)則2，F(xiàn)IRST(E’)加進(jìn)FOLLOW(T)；因?yàn)镋→TE’，E’→ε，應(yīng)用規(guī)則3，F(xiàn)OLLOW(E)加進(jìn)FOLLOW(T)因?yàn)镋’→+TE’，E’→ε，應(yīng)用規(guī)則3，F(xiàn)OLLOW(E’)加進(jìn)FOLLOW(T)]FOLLOW(T’)=FOLLOW(T)={+，)，#}FOLLOW(F)=FIRST(T’)∪FOLLOW(T)∪FOLLOW(T’)={+，*，)，#}2、遞歸下降分析法(1)思路：將文法中的每一個(gè)非終結(jié)符U的文法規(guī)則看作是識(shí)別U的一個(gè)過程定義，為每個(gè)非終結(jié)符號(hào)構(gòu)造一個(gè)子程序，以完成該非終結(jié)符號(hào)所對應(yīng)的語法成分的分析和識(shí)別任務(wù)。(2)存在問題：1)、左遞歸問題消除直接左遞歸的方法：將不含左遞歸的各選式用圓括號(hào)括起來，放置在規(guī)則右部的最左端，然后將含有遞歸的侯選式中的左遞歸符號(hào)去掉，剩余部分用花括號(hào)括起來放置在規(guī)則右部的最右端，這樣，就可將直接左遞歸規(guī)則轉(zhuǎn)變成用擴(kuò)充BNF表示的等價(jià)文法。消除一般的間接左遞歸：先變成直接左遞歸，再消除直接左遞歸。例4.4有文法：E::=E+T|E-T|T，T::=T*F|T/F|F，為其設(shè)計(jì)遞歸分析程序。解：先按上面介紹的方法消除左遞歸：[注意“{”和“}”括起來的內(nèi)容采用循環(huán)設(shè)計(jì)。]E::=E+T|E-T|T可改成E::=T{+T|-T}T::=T*F|T/F|F可改成T::=F{*F|/F}例4.5有文法G[S]：S::=Qc|c，Q::=Rb|b，R::=Sa|a，消除左遞歸。解：該文法表面上看，沒有直接左遞歸，但因?yàn)镾=>Qc=>Rbc=>Sabc，說明存在間接左遞歸。首先把R::=Sa|a代入Q::=Rb|b中得：Q::=Sab|ab|b再把Q::=Sab|ab|b代入S::=Qc|c中得直接左遞歸規(guī)則：S::=Sabc|abc|bc|c按消除直接左遞歸方法，最后得到的S規(guī)則為：S::=(abc|bc|c){abc}S規(guī)則中不再含有符號(hào)Q和R，所以，Q和R規(guī)則為多余規(guī)則，應(yīng)刪除。注意：對非終結(jié)符號(hào)的排序不同，最后得到的文法在形式上可能不同，但它們都是等價(jià)文法。消去左遞歸過程中，要注意保證文法的識(shí)別符號(hào)不變。2)、局部二義性問題(右部多個(gè)侯選式的第一個(gè)符號(hào)相同問題)假設(shè)文法中有規(guī)則為：U::=xV|xW，解決辦法如下：①

提取公因子，將規(guī)則變成：U::=x(V|W)②加入一個(gè)新的非終結(jié)符號(hào)A，令A(yù)=V|W，則將規(guī)則改為：U::=xA，A::=V|W3)、右部侯選式的第一個(gè)符號(hào)是非終結(jié)符號(hào)首先求出每個(gè)侯選式的首符號(hào)集，然后根據(jù)各侯選式的首符號(hào)集內(nèi)容來選擇侯選式。設(shè)文法G沒有左遞歸，規(guī)則形式為：U∷=α|β，先求出每個(gè)侯選式的FIRST(α)和FIRST(β)，為保證在設(shè)計(jì)子程序時(shí)能明確選擇某個(gè)侯選式，需要滿足以下兩點(diǎn)：①FIRST(α)∩FIRST(β)=φ即各侯選式的首符號(hào)集互不相交。②若ε∈FIRST(β)，那么，F(xiàn)IRST(α)∩FOLLOW(U)=φ。(例如：A→bAS|ε,ε∈FIRST(ε),FIRST(bAS)∩FOLLOW(A)≠φ)設(shè)當(dāng)前的輸入符號(hào)是a，a∈Vt①若a∈FIRST(α)或ε∈FIRST(α)且a∈FOLLOW(U)，則用α侯選式。若a∈FIRST(β)或ε∈FIRST(β)且a∈FOLLOW(U)，則用β侯選式。若a!∈FIRST(α)且a!∈FIRST(β)，則語法錯(cuò)，轉(zhuǎn)出錯(cuò)處理。例4.11，有文法G[Z]：Z::=AcB|Bd，A::=AaBb，B::=aA|a設(shè)計(jì)遞歸下降分析程序。解:首先將左遞歸去掉，將規(guī)則A::=AaB|b改成A::=b{aB}提取公因子，將規(guī)則B::=aA|a改成B::=a(A|ε)改后的文法為：Z::=AcB|Bd,A::=b{aB},B::=a(A|ε)對于規(guī)則Z::=AcB|Bd，為了設(shè)計(jì)分析程序，要求出每個(gè)選項(xiàng)的頭符號(hào)集，即FIRST(AcB)={c}，F(xiàn)IRST(Bd)={a}，分析程序如下圖(a)所示。對于規(guī)則A::=c{aB},分析程序如圖(b)所示。對于規(guī)則B::=a(A|ε),FIRST(A)={c}，分析程序如圖(c)所示。3、LL(1)分析方法（1）LL(1)分析使用一個(gè)下堆棧而不是遞歸調(diào)用來完成分析。名稱中第一個(gè)L表示自左向右順序掃描輸入符號(hào)串，第二個(gè)L表示分析過程產(chǎn)生一個(gè)句子的最左推導(dǎo)。括號(hào)中的1表示每進(jìn)行一步推導(dǎo)，只需要向前查看一個(gè)輸入符號(hào)，便能確定當(dāng)前所應(yīng)選用的規(guī)則。(2)LL(1)分析器由一個(gè)總控程序、一張分析表和一個(gè)分析棧組成，如圖4.4所示。輸入符號(hào)串：指要分析的輸入符號(hào)串。為了分析算法的統(tǒng)一，在輸入串的末尾放置一個(gè)特殊符號(hào)#。分析表M：是一個(gè)二維表，可用一個(gè)二維數(shù)組M[A，a]來表示，它概括了文法的全部信息。數(shù)組的行A是文法中的一個(gè)非終結(jié)符號(hào)、終結(jié)符號(hào)和#；而列a是文法的一個(gè)終結(jié)符號(hào)和#。M指出了分析器應(yīng)做的動(dòng)作。分析棧：用來存放一系列文法符號(hào)。分析開始時(shí)，先將#入棧，然后再將文法的開始符號(hào)入棧。輸出流：分析過程中使用的產(chǎn)生式序列?？偪爻绦颍悍治銎鲗斎氪姆治隹靠偪爻绦蛲瓿伞８鶕?jù)分析棧的棧頂符號(hào)X和當(dāng)前的輸入符號(hào)，總控程序按照分析表的指示來決定分析器的動(dòng)作。(3)分析表的構(gòu)建，按下列規(guī)則確定分析表中的元素M（產(chǎn)生式A→α）：對FIRST(α)中的每個(gè)終結(jié)符a，置M[A，a]=“POP，PUSH(α’)”，其中α’為α的倒置。若ε∈FIRST(α)，則對屬于FOLLOW(A)的每個(gè)符號(hào)b(b為終結(jié)符或#)，置M[A，b]=“POP”。把M中的所有M[a，a]置為“POP，NEXTSYM”。把M中所有不按規(guī)則1、2定義的元素均置為空或“ERROR”。例4.7，有文法E→TE’，E’→+TE’，E’→ε，T→FT’，T’→*FT’，T’→ε，F(xiàn)→(E)|i。（1）構(gòu)造分析表。（2）對符號(hào)串i+i*i進(jìn)行分析，并寫出分析過程。解：（1）分析表如下：對規(guī)則E→TE’：FIRST(TE’)={(，i)}，那么在分析表的符號(hào)E所在的行、符號(hào)(和i所在的列對應(yīng)的位置分別填入“POP,PUSH(E’T)”,見表中E行。對規(guī)則E’→+TE’：FIRST(+TE’)={+}，在符號(hào)E行符號(hào)+列對應(yīng)的位置填入“POP,PUSH(E’T’+)”對規(guī)則E’→ε：ε∈FIRST(α)，F(xiàn)OLLOW(E’)=FOLLOW(E){)，#}，所以在符號(hào)E行符號(hào))和#列對應(yīng)的位置填入“POP”，見表中的E’行。（其余類似）（2）對符號(hào)串i+i*i的分析過程在下表列出：表4.2中輸出的產(chǎn)生式序列構(gòu)成對輸入符號(hào)串的最左推導(dǎo)。按此產(chǎn)生式序列構(gòu)造輸入符號(hào)串i+i*i的最左推導(dǎo)過程如下：E=>TE’=>FT’E’=>iT’E’=>iE’=>i+TE’=>i+FT’E’=>i+iT’E’=>i+i*FT’E’=>i+i*iT’E’=>i+i*iE’=>i+i*i（4）LL(1)分析的主要問題及解決方法（選擇、填空）左遞轉(zhuǎn)成右遞歸(步驟如下)1）

對形如U::=x|y|…|z|Uv的直接左遞歸文法規(guī)則，增加一個(gè)新的非終結(jié)符號(hào)U’，令U為左遞歸規(guī)則中的不含左遞歸符號(hào)的部分加上新的非終結(jié)符號(hào)U’，即U::=(x|y|….|z)U’。2）

新的非終結(jié)符號(hào)U’有兩個(gè)侯選式，一為含左遞歸符號(hào)的部分去掉含左遞歸符號(hào)，再加上新的非終結(jié)符號(hào)U’，即U’::=vU’；另一個(gè)為ε，即U’::=ε，即U’::=vU’|ε例：對左遞歸規(guī)則E→E+T|T，其等價(jià)的右遞歸規(guī)則為：E→TE’，E’→+TE’|ε解決分析表多重定義問題若一個(gè)LL(1)文法的分析表無多重定義，當(dāng)且僅當(dāng)對于文法G的每個(gè)非終結(jié)符A的任何兩條不同規(guī)則A→α|β，下面條件成立：?FIRST(α)∩FIRST(β)=φ即頭符號(hào)集不相交。 ?假若β==*>ε，那么，F(xiàn)IRST(α)∩FOLLOW(A)=φ，即α所能推出的符號(hào)串的頭符號(hào)集中的元素不能出現(xiàn)在FOLLOW(A)中。例如，規(guī)則：T→(E)|a(E)|a可改成：T→(E)|aT’，T’→(E)|ε（和遞歸下降的解決二義性類似）但并非所有的文法都可用此法解決分析表的多重定義?？紤]有文法G[S]：S→AU|BR,A→aAU|b,B→aBR|b,U→c,R→d對于規(guī)則S→AU|BR，因?yàn)镕IRST(AU)∩FIRST(BR)≠φ，故該文法不是LL(1)文法。為了能夠提取公因子，必須將非終結(jié)符號(hào)A、B的產(chǎn)生式帶入S的產(chǎn)生式中，得到：S→aAUU|bU|aBRR|bR經(jīng)提取公因子后，得到S→a(AUU|BRR)|b(U|R),令S’、S”分別代替括號(hào)中的左右部分，得如下等價(jià)文法：S→aS’|bS”,S’→AUU|BRR,S”→U|R,A→aAU|b,B→aBR|b,U→c,R→d顯然，對于規(guī)則S’→AUU|BRR，因?yàn)镕IRST(AUU)∩FIRST(BRR)≠φ，故它仍然不是LL(1)文法。且無論重復(fù)多少次提取公因子，都不能把它變成LL(1)文法。由于遞歸下降分析法也存在這類問題，所以，自頂向下分析方法無法對這類文法進(jìn)行語法分析。（5）LL(1)文法具有下列性質(zhì)：任何LL(1)文法都是無二義的。若文法中有左遞歸，肯定不是LL(1)文法。但有些左遞歸文法可轉(zhuǎn)換成右遞歸文法，從而滿足LL(1)文法的要求。存在一種算法，能判定文法是否為LL(1)文法。存在一種算法，能判定任意兩個(gè)LL(1)文法是否產(chǎn)生相同的語言。不存在這樣的算法，判定任意上下文無關(guān)語言能否由LL(1)文法產(chǎn)生。非LL(1)語言是存在的。（6）判斷一個(gè)文法是否是LL(1)文法的充要條件：文法不含左遞歸，對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若A→a1|a2|…|an則FIRST(ai)∩FIRST(aj)＝f(i1j)對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含e，則FIRST(ai)∩FOLLOW(A)=fi=1,2,...,n如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法?？碱}1：將文法G[S]S→[AA→B]|ASB→aB|a改寫為等價(jià)的G’[S],使得G’[S]不含左遞歸和左公因子。答：消除左遞歸和左公因子后的文法為：S→[AA→B]A’A’→SA’|eB→aB’B’→B|e考題2：寫出文法G[A]:A→Ba|Cb|cB→dA|Ae|fC→Bg|h消除左遞歸后的文法。答：(1)經(jīng)分析發(fā)現(xiàn)文法G[A]并無直接左遞歸；(2)消除間接左遞歸：將A,B,C按照B,C,A排序（建議將A放在最后）由于出現(xiàn)C→Bg形式，將B代入C得：C→dAg|Aeg|fg|h又由于A出現(xiàn)A→BaA→Cb將B,C帶入A得到：A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|c等價(jià)于A→Aea|Aegb|dAa|fa|dAgb|fgb|hb|c將A消除直接左遞歸A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’A’→eaA’|egbA’|e此時(shí)，對于B→dA|Ae|f，C→dAg|Aeg|fg|h由于未在任何產(chǎn)生式的右部出現(xiàn)，所以是多余的。綜上所述:消除遞歸后的文法為：A→dAaA’|faA’|dAgbA’|fgbA’|hbA’|cA’；A’→eaA’|egbA’|e考題1：判斷下面文法是否為LL(1)文法，若是，請構(gòu)造相應(yīng)的LL(1)分析表并分析句子aabe的分析過程。S→aDD→STe|εT→bMM→bHH→M|ε分析：判斷一個(gè)文法是否為LL(1)文法是否為LL(1)文法，主要就是判斷是否滿足LL(1)文法的充要條件，有一個(gè)不滿足就不是LL(1)文法。對于aabe根據(jù)文法STaDTaSTeTaaDTeTaaTeTaabMe由于M不能為空字ε，所以最后肯定推不出來，也就是該句子不能由該文法推出，出錯(cuò)。答：(1)經(jīng)分析該文法無左遞歸；(2)①非終結(jié)符的First和Follow集合如下表所示非終結(jié)符XFirst(X)Follow(X)Sa#bDεa#bTbeMbeHεbe②將文法分解為：S→aDD→SteD→εT→bMM→bHH→MH→ε依次計(jì)算：First(aD)={a}First(Ste)={a}Follow(D)={#b}First(bM)=First(bH)=First(M)=Follow(H)={e}∵First(Ste)∩Follow(D)=ФFirst(M)∩Follow(H)=Ф∴該文法是LL(1)文法LL(1)分析表如下：abe#SS→aDDD→STeD→εD→εTT→bMMM→bHHH→MH→ε(3)aabe的分析過程如下：步驟符號(hào)棧輸入串所用產(chǎn)生式0#Saabe#1#Daaabe#S→aD2#Dabe#3#eTSabe#D→STe4#eTDaabe#5#eTDbe#6#eTbe#D→ε7#eMbbe#T→bM8#eMe#出錯(cuò)考題2：判斷下面文法是不是LL(1)文法，若是請構(gòu)造相應(yīng)的LL(1)分析表，寫出aaabd的分析過程。S→aHH→aMd|dM→Ab|eA→aM|e答：（1）可以判斷該文法無左遞歸。（2）將文法分解為分解：S→aHH→aMdH→dM→AbM→eA→aMA→e求First和Follow集合非終結(jié)符XFirst(X)Follow(X)Sa#Ha,d#Me,a,ed,bAa,eb求Select集合（實(shí)質(zhì)就是計(jì)算First集）Select(S→aH)=First(aH)={a}Select(H→aMd)=First(aMd)={a}Select(H→d)=nbvnxnvSelect(M→Ab)=First(Ab)={a,e}Select(M→e)=First(e)UFollow(M)=Follow(M)={d,b}Select(A→aM)=First{aM}={a}Select(A→e)=First(e)={e}∵Select(H→aMd)∩Select(H→d)=ФSelect(M→Ab)∩Select(M→e)=ФSelect(A→aM)∩Select(A→e)=Ф∴該文法是LL(1)文法。（3）LL(1)分析表如下：adbeSS→aHHH→aMdH→dMM→AbM→eM→eM→AbAA→aMA→eaaabd#的分析過程如下：步驟符號(hào)棧輸入串所用產(chǎn)生式0#Saaabd#1#Haaaabd#S→aH2#Haabd#3#dMaaabd#H→aMd4#dMabd#5#dbAabd#M→Ab6#dbMaabd#A→aM7#dbMbd#8#dbbd#M→e9#dd#10##第五章、自底向上分析法（LR（0）分析法）（1）自底向上分析法（又稱：移進(jìn)歸約法）思路：分析過程從輸入符號(hào)串開始，通過反復(fù)查找當(dāng)前句型的句柄（最左的簡單短語），并使用規(guī)則，將找到的句柄歸約（最左歸約）成相應(yīng)的非終結(jié)符號(hào)，直到歸約到開始符號(hào)。過程：設(shè)置一個(gè)寄存符號(hào)的先進(jìn)后出棧，稱為符號(hào)棧。在分析進(jìn)行時(shí)，把輸入符號(hào)逐個(gè)按掃描順序移進(jìn)棧里，當(dāng)棧頂符號(hào)串形成句柄(即為某條規(guī)則的右部)時(shí)，就歸約，把棧頂構(gòu)成句柄的那個(gè)符號(hào)串用相應(yīng)規(guī)則左部的非終結(jié)符號(hào)來代替。再檢查棧頂是否又出現(xiàn)了新的句柄，若有，繼續(xù)歸約；若沒有形成新的句柄，則再從輸入符號(hào)串移進(jìn)新的符號(hào)，如此繼續(xù)直到整個(gè)輸入符號(hào)串處理完畢。最終如果棧里只有識(shí)別符號(hào)，則所分析的輸入符號(hào)串為合法的句子，報(bào)告成功；否則，輸入串是不合法的符號(hào)串，報(bào)告錯(cuò)誤。（2）LR(K)分析方法：L表示從左到右掃描所給定的輸入串，R表示以相反的方向構(gòu)造該輸入串的最右推導(dǎo)(即規(guī)范推導(dǎo))。K表示為了做出分析決定需要向前看的輸入符號(hào)的個(gè)數(shù)。LR分析方法對文法適應(yīng)性強(qiáng)，分析能力強(qiáng)，對源程序中錯(cuò)誤的診斷靈敏，但結(jié)構(gòu)比前面介紹的自頂向下的分析方法復(fù)雜，向前查看的符號(hào)愈多，相應(yīng)的分析方法愈復(fù)雜。（3）LR分析器（3）LR分析器有一個(gè)給定的輸入符號(hào)串，一個(gè)分析棧和一個(gè)有窮的控制系統(tǒng)。如圖5.2所示。輸入符號(hào)串：等待分析的符號(hào)串。分析棧有兩部分：一個(gè)是符號(hào)棧，另一個(gè)是狀態(tài)棧，它們都是先進(jìn)后出棧?？刂葡到y(tǒng)：包括一個(gè)分析表和一個(gè)總控程序。對于不同的文法來說，分析表各有不同，但總控程序都是一樣。LR分析器的工作過程就是在總控程序的控制下，從左到右掃描輸入符號(hào)串，根據(jù)分析棧中的符號(hào)和狀態(tài)以及當(dāng)前的輸入符號(hào)，查閱分析表并按分析表的指示完成相應(yīng)的分析動(dòng)作，直到符號(hào)棧中出現(xiàn)開始符號(hào)。分析表：分析器的核心，由動(dòng)作部分ACTION表（應(yīng)采取什么動(dòng)作）和狀態(tài)轉(zhuǎn)換部分GOTO表（下個(gè)狀態(tài)是什么）組成。表中S1、S2、…、Sn為分析器的各個(gè)狀態(tài)；a1、a2、…、am為文法的全部終結(jié)符號(hào)及右界符#；X1、X2、…、Xk為文法的非終結(jié)符號(hào)。分析表的動(dòng)作有下列四種：移進(jìn)(Sn)：將輸入符號(hào)aj移進(jìn)符號(hào)棧，將狀態(tài)n移進(jìn)狀態(tài)棧，輸入指針指向下一個(gè)輸入符號(hào)。歸約(R)：當(dāng)棧頂形成句柄時(shí)，按照相應(yīng)的產(chǎn)生式U→W進(jìn)行歸約。若產(chǎn)生式右部W的長度為n，則將符號(hào)棧棧頂n個(gè)符號(hào)和狀態(tài)棧棧頂n個(gè)狀態(tài)出棧，然后將歸約后的文法符號(hào)U移入符號(hào)棧，并根據(jù)此時(shí)狀態(tài)棧頂?shù)臓顟B(tài)Si及符號(hào)棧頂?shù)姆?hào)U，查GOTO標(biāo)，將GOTO[Si，U]移入狀態(tài)棧。接受(A)：當(dāng)輸入符號(hào)串到達(dá)右界符#時(shí)，且符號(hào)棧只有文法的開始符號(hào)時(shí)，則分析成功結(jié)束，接受輸入符號(hào)串并結(jié)束分析。報(bào)錯(cuò)(E)：在狀態(tài)棧的棧頂狀態(tài)為Si時(shí)，如果輸入符號(hào)為不應(yīng)該遇到的符號(hào)時(shí)，即ACTION[Si，aj]=空白，則報(bào)錯(cuò)，說明輸入符號(hào)串有語法錯(cuò)誤。(4)拓廣文法：使文法只有一個(gè)以識(shí)別符號(hào)作為左部的產(chǎn)生式，從而使構(gòu)造出來的分析器有唯一的接受狀態(tài)例5.3,對文法G∶E→T|E+T|E－T；T→i|(E)進(jìn)行拓廣。解：引入一個(gè)新的開始符號(hào)S，使得文法的開始符號(hào)所在的規(guī)則唯一，這樣得到拓廣文法如下：S→E；E→T|E+T|E－T；T→i|(E)(5)活前綴與可歸前綴：設(shè)λβt是一個(gè)規(guī)范句型，即λβt是能用最右推導(dǎo)得到的句型，其中β表示句柄，t∈Vt*，如果λβ=u1u2…ur，那么稱符號(hào)串u1u2…ui(其中1≤i≤r)是句型λβt的活前綴。從活前綴的定義可知，一個(gè)規(guī)范句型的活前綴可以有多個(gè)，但觀察這些活前綴，會(huì)發(fā)現(xiàn)其中活前綴u1、u1u2、…、u1u2…ur-1不含有完整句柄β，只有活前綴u1u2…ur含有完整句柄β，那么這個(gè)含有句柄的活前綴u1u2…ur稱為可歸前綴。活前綴不含句柄右邊的任意符號(hào)，而可歸前綴是含有句柄的活前綴。對一個(gè)規(guī)范句型來說，活前綴可有多個(gè)，可歸前綴只有一個(gè)。例5.4，有文法G∶E→T|E+T|E-T，T→i|(E)，找規(guī)范句型E+(i-i)的活前綴和可歸前綴。解：首先畫出E+(i-i)的語法樹，可找出第一個(gè)i是句柄，那么λβt=E+(i-i)此時(shí)，t=-1)因此活前綴為：E，E+，E+(，E+(i，其中E+(i是可歸前綴?？偨Y(jié)活前綴求法：先畫出句型的語法樹，找出句柄，然后，從句型的左邊第一個(gè)符號(hào)開始，取長度分別為1、2、…的符號(hào)串，直到包含句柄在內(nèi)的長度符號(hào)串就是該句型所有的活前綴。而可歸前綴就是最長的活前綴。注意：所有活前綴都不包括句柄右邊的任何符號(hào)(即t中的任何符號(hào))。LR分析過程中，如果輸入符號(hào)串沒有語法錯(cuò)誤，則在分析的每一步，若將符號(hào)棧中的全部文法符號(hào)與剩余的輸入符號(hào)串連接起來，得到的一定是所給文法的一個(gè)規(guī)范句型。也就是說，壓入符號(hào)棧中的符號(hào)串一定是某一規(guī)范句型的前綴，而且這種前綴不會(huì)含有任何句柄右邊的符號(hào)，所以都是活前綴。當(dāng)符號(hào)棧形成句柄，即符號(hào)棧的內(nèi)容為可歸前綴時(shí)，就會(huì)立即被歸約。所以說，LR分析就是逐步在符號(hào)棧中產(chǎn)生可歸前綴，再進(jìn)行歸約的過程。識(shí)別活前綴的主要目的是要輸出為給定的輸入串構(gòu)造逆向最右推導(dǎo)(即最左歸約)時(shí)使用的產(chǎn)生式序列(6)LR(0)項(xiàng)目項(xiàng)目的定義：對某個(gè)文法G來說，如果A→α1α2為G的一條規(guī)則，那么，對規(guī)則的右部加上一個(gè)圓點(diǎn)，就成為一個(gè)項(xiàng)目。其形式為：A→α1·α2圓點(diǎn)是表示項(xiàng)目的一種標(biāo)記，即，一條規(guī)則的右部標(biāo)有圓點(diǎn)，那么它就是項(xiàng)目。一般情況下，因?yàn)閳A點(diǎn)的位置不同。一條規(guī)則可以有幾個(gè)項(xiàng)目。項(xiàng)目中點(diǎn)后面的符號(hào)稱為該項(xiàng)目的后繼符號(hào)（可能是非終結(jié)符、終結(jié)符、空）項(xiàng)目的分類：移進(jìn)項(xiàng)目：后繼符號(hào)為終結(jié)符號(hào)，如E→E．－T。待約項(xiàng)目：后繼符號(hào)為非終結(jié)符號(hào)，如E→E－．T和S→.E歸約項(xiàng)目：后繼符號(hào)為空，即點(diǎn)在最后。如E→E－T．和S→E.接受項(xiàng)目：文法的開始符號(hào)S的歸約項(xiàng)目。接受項(xiàng)目是一個(gè)特殊的歸約項(xiàng)目，它表示該產(chǎn)生式歸約后分析將結(jié)束。項(xiàng)目S→E.就是接受項(xiàng)目（S是開始符號(hào)）。項(xiàng)目有效性一個(gè)項(xiàng)目A→α1·α2對于某個(gè)活前綴λα1是有效的，當(dāng)且僅當(dāng)存在某個(gè)最右推導(dǎo)。S=|*=>λAt=|=>λα1·α2t，其中t是終結(jié)符號(hào)串。活前綴和句柄的關(guān)系有三種：如果活前綴包含句柄，表示符號(hào)棧頂形成句柄，則就可以歸約。當(dāng)一個(gè)點(diǎn)在最后的項(xiàng)目對活前綴有效時(shí)，則可以進(jìn)行歸約，所以把點(diǎn)在最后的項(xiàng)目稱為歸約項(xiàng)目。如果活前綴只包含句柄的部分符號(hào)，正期待著從余流的輸入符號(hào)中看到句柄的其余符號(hào)。假設(shè)活前綴含有α1，有產(chǎn)生式A→α1α2，由于活前綴中有產(chǎn)生式右部α1α2的α1部分，所以說A→α1.α2對活前綴有效。同樣，如果有另一個(gè)產(chǎn)生式B→α1α3，那么B→α1.α3對活前綴也有效。如果活前綴不含句柄的任何符號(hào)，則需將余流的輸入符號(hào)移進(jìn)。假設(shè)下一步移進(jìn)的符號(hào)可能是α的前綴，那么，對于任一產(chǎn)生式A→α來說，由于活前綴中不含α的任何符號(hào)，所以說A→.α對活前綴有效。一個(gè)項(xiàng)目指明了在分析過程的某一時(shí)刻，已經(jīng)看到的一個(gè)產(chǎn)生式右部的多少。一般來說，活前綴與有效項(xiàng)目是多對多關(guān)系。例5.5，有文法S→E，E→T|E+T|E-T，T→i|(E)，列出該文法的所有項(xiàng)目，并找出對活前綴E－有效的項(xiàng)目。解：首先列出每條規(guī)則對應(yīng)的多個(gè)項(xiàng)目：S→E，有項(xiàng)目S→.E，S→E.E→T，有項(xiàng)目E→.T，E→T.E→E+T，有項(xiàng)目E→.E+T，E→E.+T，E→E+.T，E→E+T.E→E-T，有項(xiàng)目E→.E-T，E→E.-T，E→E-.T，E→E-T.T→i，有項(xiàng)目E→.i，E→i.T→(E)，有項(xiàng)目T→.(E)T→(.E)T→(E.)T→(E).只有項(xiàng)目E→E－．T，T→．i和T→．(E)對活前綴E－是有效的，這是因?yàn)閺腟到含有活前綴E－的規(guī)范句型的規(guī)范推導(dǎo)中，能夠使用這些項(xiàng)目：①先看推導(dǎo)過程S=>E=>E－T，最后一步推導(dǎo)使用的規(guī)則是E→E－T，句柄為E－T，該過程推導(dǎo)出的句型E－T含有活前綴E－，而E－是句柄E－T的一部分，所以說規(guī)則E→E－T的項(xiàng)目E→E－．T對E－是有效的。②接下來看推導(dǎo)過程S=>E=>E－T=>E－i，最后一步推導(dǎo)使用的規(guī)則是T→i，句柄為i，該過程推導(dǎo)出的句型E－i也含有活前綴E－，但由于活前綴E-不含句柄i的任何符號(hào)，所以說項(xiàng)目T→．i對E－也是有效的。③同理，對于推導(dǎo)過程S=>E=>E－T==>E－(E)，可證明項(xiàng)目T→．(E)對E－也是有效的。④因此，E→E－．T，T→．i和T→．(E)是活前綴E-的有效項(xiàng)目集。（7）構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)1）、項(xiàng)目集的閉包運(yùn)算（設(shè)I為一項(xiàng)目集）I中的每一個(gè)項(xiàng)目都屬于CLOSURE(I)。如項(xiàng)目A→α1·Xα2屬于CLOSURE(I)，且X為非終結(jié)符號(hào)，則將形式為X→.λ的項(xiàng)目添加到LOSURE(I)重復(fù)(1)和(2)，直到CLOSURE(I)封閉為止。例5.6（可能考，約4-5分）有文法：E’::=E，E::=E+T，E::=T，T::=T*F，T::=F，F(xiàn)::=(E)，F(xiàn)::=i，設(shè)項(xiàng)目集I={E’→.E}，求CLOSURE(I)。解：根據(jù)閉包運(yùn)算的第1條，CLOSURE(I)={E’→.E}根據(jù)第2條，因?yàn)镋是非終結(jié)符號(hào)，所以將規(guī)則E::=E+T和E::=T在其右部最前面加點(diǎn)形成E→.E+T和E→.T，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→.E，E→.E+T，E→.T}根據(jù)第3條，重復(fù)計(jì)算，直到CLOSURE(I)封閉為止。因?yàn)門是非終結(jié)符號(hào)，所以將規(guī)則T::=T*F和T::=F在其右部最前面加點(diǎn)形成T→.T*F和T→.F，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→.E，E→.E+T，E→.T，T→.T*F，T→.F}因?yàn)镕是非終結(jié)符號(hào)，所以將F→.(E)和F→.i，加進(jìn)CLOSURE(I)中：CLOSURE(I)={E’→.E，E→.E+T，E→.T，T→.T*F，T→.F，F(xiàn)→.(E)，F(xiàn)→.i}至此，CLOSURE(I)封閉。2）、項(xiàng)目集之間的轉(zhuǎn)換函數(shù)GO假設(shè)有一項(xiàng)目為A→α.Xβ，令X是一個(gè)字匯表中的符號(hào)，則對項(xiàng)目A→α.Xβ進(jìn)行讀X操作，結(jié)果為項(xiàng)目A→αX.β。設(shè)I是一個(gè)項(xiàng)目集,X是任一文法符號(hào)，則項(xiàng)目集之間的轉(zhuǎn)換用GO[I,X]函數(shù)表示，定義為：GO[I,X]=CLOSURE(J)。其中J={任何具有[A→αX.β]的項(xiàng)目|[A→α.Xβ]∈I}，即對項(xiàng)目集I中所有的項(xiàng)目進(jìn)行讀X操作的結(jié)果。CLOSURE(J)為對J進(jìn)行了閉包運(yùn)算得到的項(xiàng)目集，稱為I的后繼項(xiàng)目集。令狀態(tài)I代表項(xiàng)目集I，狀態(tài)J代表后繼項(xiàng)目集CLOSURE(J)，用狀態(tài)圖表示則為：例5.7，有文法：E’::=E，E::=E+T，E::=T，T::=T*F，T::=F，F(xiàn)::=(E)，F(xiàn)::=i有項(xiàng)目集I={E’→E.,E→E.+T},求GO[I,+]解：在I中挑出點(diǎn)后是+的項(xiàng)目有：E→E.+T,將點(diǎn)移到+后面得J={E→E+.T}對J進(jìn)行閉包運(yùn)算得CLOSURE(J)={E→E+.T，T→.F，T→.T*F,F→.(E),F→.i}GO(I,+)={E→E+.T，T→.F，T→.T*F,F→.(E),F→.i}用狀態(tài)圖表示為：2）、舉例說識(shí)別活前綴的有窮自動(dòng)機(jī)的構(gòu)造方法假設(shè)有拓廣文法為：①S→A，②A→(A)，③A→a從文法的開始符號(hào)所在的規(guī)則S→A開始，項(xiàng)目S→.A將作為有窮自動(dòng)機(jī)的開始狀態(tài)。項(xiàng)目S→.A反映了此時(shí)分析器還沒有識(shí)別任何(非空)活前綴。對例中的文法，開始符號(hào)所在的規(guī)則為S→A，所以開始狀態(tài)0的項(xiàng)目集有C0={S→.A}，且項(xiàng)目S→.A稱為基本項(xiàng)目(只有一條；若多條，則先將它轉(zhuǎn)為拓廣文法)。然后，需要對項(xiàng)目集中的各成員進(jìn)行閉包(closure)運(yùn)算，也就是看項(xiàng)目中的點(diǎn)后面的符號(hào)是否是非終結(jié)符號(hào)。如果是非終結(jié)符號(hào)，則將該非終結(jié)符號(hào)為左部的規(guī)則，在其右部最前面加點(diǎn)構(gòu)成項(xiàng)目，并填加到該項(xiàng)目集中。接下來構(gòu)造C0的后繼項(xiàng)目集。觀察狀態(tài)0的項(xiàng)目集C0的每個(gè)項(xiàng)目，點(diǎn)后的符號(hào)即后繼符號(hào)。下面介紹此題中項(xiàng)目集C1、C2、C3的構(gòu)造：首先將C0中后繼符號(hào)為A的項(xiàng)目挑選出來，可得項(xiàng)目集{S→.A}，將點(diǎn)移到A的后面，得到C1的基本項(xiàng)目集為{S→A.}，然后對此項(xiàng)目集進(jìn)行閉包運(yùn)算。由于在該項(xiàng)目集只有一個(gè)項(xiàng)目中，且點(diǎn)位于最右，所以閉包運(yùn)算沒有添加任何項(xiàng)目，最終C1={S→A.}，即GO[0，A]=1。看C0中的項(xiàng)目{A→.(A)}，后繼符號(hào)是(，將點(diǎn)移到(的后面，得到C2的基本項(xiàng)目集為{A→(.A)}。由于點(diǎn)后面是非終結(jié)符號(hào)A，所以將{A→.(A)，A→.a}加入項(xiàng)目集，最終C2={A→(.A)，A→.(A)，A→.a}，即GO[0，(]=2。看C0中的項(xiàng)目{A→.a}，最終得C3={A→a