(整理完)編譯原理網(wǎng)上作業(yè)題20121101

./東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理網(wǎng)上作業(yè)題第一章編譯概述一、多項(xiàng)選擇題：1.編譯程序各階段的工作都涉及到〔。〔﹡﹡A.語法分析B.表格管理C.出錯(cuò)處理D.語義分析E.詞法分析2.編譯程序工作時(shí),通常有〔階段。

〔﹡A.詞法分析B.語法分析C.中間代碼生成D.語義檢查E.目標(biāo)代碼生成二、填空題：1．解釋程序和編譯程序的區(qū)別在于〔?！博~2．編譯過程通?？煞譃?個(gè)階段,分別是〔、〔、〔、〔和〔生成?！博~3．編譯程序工作過程中,第一段輸入是〔,最后階段的輸出為〔程序?！博~4．編譯程序是指將〔程序翻譯成〔程序的程序?！博~三、綜合題：1.畫出編譯程序的總體結(jié)構(gòu)圖,簡述各部分的主要功能?！博~﹡﹡第二章文法和語言的基本知識一、多項(xiàng)選擇題：1.下面哪些說法是錯(cuò)誤的〔?！博~﹡A.有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖

B.狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖

C.有向圖是一個(gè)DFA

D.DFA可以用狀態(tài)轉(zhuǎn)換圖表示

2.對無二義性文法來說,一棵語法樹往往代表了〔。〔﹡﹡A.多種推導(dǎo)過程

B.多種最左推導(dǎo)過程

C.一種最左推導(dǎo)過程D.僅一種推導(dǎo)過程

E.一種最左推導(dǎo)過程

3.如果文法G存在一個(gè)句子,滿足下列條件〔之一時(shí),則稱該文法是二義文法。〔﹡﹡A.該句子的最左推導(dǎo)與最右推導(dǎo)相同

B.該句子有兩個(gè)不同的最左推導(dǎo)

C.該句子有兩棵不同的最右推導(dǎo)

D.該句子有兩棵不同的語法樹

E.該句子的語法樹只有一個(gè)

4.有一文法G：S→ABA→aAb|εB→cBd|ε它不產(chǎn)生下面〔集合

〔﹡﹡A.{anbmcsup>ndm|n,m≥0}

B.{anbncsup>mdm|n,m>0}

C.{anbmcsup>mdn|n,m≥0}

D.{anbncsup>mdm|n,m≥0}

E.{anbncsup>ndm|n,n≥0}

5.自下而上的語法分析中,應(yīng)從〔開始分析。

〔﹡A.句型B.句子C.以單詞為單位的程序D.文法的開始符E.句柄

6.對正規(guī)文法描述的語言,以下〔有能力描述它。

〔﹡﹡A.0型文法B.1型文法C.上下文無關(guān)文法D.右線性文法E.左線性文法二、填空題：1．文法中的終結(jié)符和非終結(jié)符的交集是〔。詞法分析器交給語法分析器的文法符號一定是〔,它一定只出現(xiàn)在產(chǎn)生式的〔部?！博~2．最左推導(dǎo)是指每次都對句型中的〔非終結(jié)符進(jìn)行擴(kuò)展?！博~3．在語法分析中,最常見的兩種方法一定是〔分析法,另一是〔分析法?！博~4．采用〔語法分析時(shí),必須消除文法的左遞歸?！博~5．〔樹代表推導(dǎo)過程,〔樹代表歸約過程?！博~6．自下而上分析法采用〔、歸約、錯(cuò)誤處理、〔等四種操作?！博~﹡7．Chomsky把文法分為〔種類型,編譯器構(gòu)造中采用〔和〔文法,它們分別產(chǎn)生〔和〔語言,并分別用〔和〔自動機(jī)識別所產(chǎn)生的語言?！博~﹡三、判斷題：1．文法S→aS|bR|εR→cS。描述的語言是<a|bc>*〔﹡2．在自下而上的語法分析中,語法樹與分析樹一定相同?！博~3．二義文法不是上下文無關(guān)文法。〔﹡4．語法分析時(shí)必須先消除文法中的左遞歸?！博~5．規(guī)歸約和規(guī)推導(dǎo)是互逆的兩個(gè)過程。〔﹡6．一個(gè)文法所有句型的集合形成該文法所能接受的語言。〔﹡7．有窮自動機(jī)接受的語言是正則語言?！博~8．若r1和r2是Σ上的正規(guī)式,則r1|r2也是?！博~9．令Σ＝{a,b},則Σ上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*<a|b>*?！博~四、簡答題句柄：〔﹡2．素短語：〔﹡﹡3．語法樹：〔﹡﹡4．歸約：〔﹡﹡5．推導(dǎo)：〔﹡﹡五、問答題1．給出上下文無關(guān)文法的定義。〔﹡﹡2.文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc〔1它是Chomsky哪一型文法？〔2它生成的語言是什么？〔﹡﹡﹡3．按指定類型,給出語言的文法。L={aibj|j＞i≥1}的上下文無關(guān)文法?！博~﹡4．有文法G：S→aAcB|BdA→AaB|cB→bScA|b〔1試求句型aAaBcbbdcc和aAcbBdcc的句柄；〔2寫出句子acabcbbdcc的最左推導(dǎo)過程。〔﹡﹡﹡5．對于文法G[S]：S→〔L|aS|aL→L,S|S〔1畫出句型〔S,〔a的語法樹。〔2寫出上述句型的所有短語、直接短語、句柄和素短語。〔﹡﹡﹡6.考慮文法G[S],其產(chǎn)生式如下:S→<L>|aL→L,S|S<a>試指出此文法的終結(jié)符號、非終結(jié)符號。<b>給出句子<a,<a,a>>的分析樹。<c>構(gòu)造句子<a,<a,a>>的一個(gè)最左推導(dǎo)。<d>構(gòu)造句子<a,<a,a>>的一個(gè)最右推導(dǎo)。<e>這個(gè)文法生成的語言是什么？〔﹡﹡7．考慮文法G[T]：T→T*F|FF→F↑P|PP→〔T|i證明T*P↑〔T*F是該文法的一個(gè)句型,并指出直接短語和句柄?！博~﹡8．試描述下列文法產(chǎn)生的語言L〔G[S]〔﹡﹡S→10S0|aAA→bA|a9．已知語言L<G>={abnc|n≥1}試對該語言構(gòu)造相應(yīng)文法?！博~﹡10．證明下列文法的二義性〔﹡﹡﹡1．G[Z]2．G[S]Z→aZbZ|aZ|aS→ABA→bB|bC|baB→Sb|ba|aC→Bb|b11．有文法G[S]：S→iSeS|iS|i該文法是否是二義的。試證明之?！博~﹡12．文法G[T]：T→aR,R→Tb|d生成的語言是什么？G[T]是否為3型文法？〔﹡﹡13.試寫出能夠描述下列格式的文法?！博~﹡673917422試構(gòu)造生成語言的上下文無關(guān)文法?！博~﹡﹡<1>{anbnci|n≥1,i≥0}<2>{w|w∈{a,b}+,且w中a的個(gè)數(shù)恰好比b多1}下面的二義性文法描述命題演算公式,為它寫一個(gè)等價(jià)的非二義性文法。G[S]:S->SANDS|SORS|NOTS|p|q|<S>〔﹡﹡16.對于下列語言分別寫出它們的正規(guī)表達(dá)式?！博~﹡<1>

英文字母組成的所有符號串,要求符號串中順序包含五個(gè)元音。<2>

英文字母組成的所有符號串,要求符號串中的字母依照詞典順序排列。第三章詞法分析與有窮自動機(jī)一、多項(xiàng)選擇題：1.在詞法分析中,能識別出〔?！博~﹡A.基本字

B.四元式

C.運(yùn)算符

D.逆波蘭式

E.常數(shù)2.令∑={a,b},則∑上所有以b開頭,后跟若干個(gè)ab的字的全體對應(yīng)的正規(guī)式為〔。〔﹡﹡

A.b<ab>*

B.b<ab>+

C.<ba>*b

D.<ba>+b

E.b<a|b>二、填空題：1．確定有限自動機(jī)DFA是〔的一個(gè)特例。〔﹡2．若二個(gè)正規(guī)式所表示的〔相同,則認(rèn)為二者是等價(jià)的?！博~3．一個(gè)字集是正規(guī)的,當(dāng)且僅當(dāng)它可由〔所〔?！博~三、判斷題：1．一個(gè)有限狀態(tài)自動機(jī)中,有且僅有一個(gè)惟一終態(tài)?！?．設(shè)r和s分別是正規(guī)式,則有L〔r|s=L<r>|L<s>?！?．自動機(jī)M和M′的狀態(tài)數(shù)不同,則二者必不等價(jià)?！?．確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集?！?．對任意一個(gè)右線性文法G,都存在一個(gè)NFAM,滿足L<G>=L<M>?！?．對任意一個(gè)右線性文法G,都存在一個(gè)DFAM,滿足L<G>=L<M>?！?．對任何正規(guī)表達(dá)式e,都存在一個(gè)NFAM,滿足L<G>=L<e>?！?．對任何正規(guī)表達(dá)式e,都存在一個(gè)DFAM,滿足L<G>=L<e>?！?．設(shè)M是一個(gè)NFA,并且L<M>＝{x,y,z},則M的狀態(tài)數(shù)至少為4個(gè)?！?0．對任何一個(gè)NFAM,都存在一個(gè)DFAM',使得L<M'>=L<M>?！菜?、綜合題：1．設(shè)M＝〔{x,y},{a,b},f,x,{y}為一非確定的有限自動機(jī),其中f定義如下：f〔x,a＝{x,y}f〔a,b＝{y}f〔y,a＝φf〔y,b＝{x,y}試構(gòu)造相應(yīng)的確定有限自動機(jī)M′。〔﹡﹡2．對給定正規(guī)式b*〔d|ad〔b|ab+,構(gòu)造其NFAM?！博~﹡3．字母表{a,b}上的正規(guī)式R=〔ba|a*,構(gòu)造R的相應(yīng)DFA?！博~﹡4．請寫出在∑=〔a,b上,不是a開頭的,但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式,并構(gòu)造與之等價(jià)狀態(tài)最少的DFA?！博~﹡﹡人運(yùn)狼、羊、菜過河,一次運(yùn)一件,不讓羊吃掉菜,也不讓狼吃掉羊,畫出渡河的狀態(tài)轉(zhuǎn)換圖?？煞駥⑵涑橄鬄橐粋€(gè)有限自動機(jī)。〔﹡﹡﹡6．對于正規(guī)表達(dá)式<a|b>*a<a|b>構(gòu)造最小狀態(tài)的DFA?！博~﹡第四章語法分析一、多項(xiàng)選擇題：1.一個(gè)LR分析器包括〔。〔﹡﹡A.一個(gè)總控程序B.一個(gè)項(xiàng)目集C.一個(gè)活前綴D.一分析表E.一個(gè)分析棧2.LR分析器核心部分是一分析表,該表包括〔等子表?！博~﹡A.LL<1>分析B.優(yōu)先關(guān)系C.GOTOD.LRE.ACTION3.每一項(xiàng)ACTION[S,a]所規(guī)定的動作包括〔?！博~﹡A.移進(jìn)B.比較C.接受

D.歸約

E.報(bào)錯(cuò)4.對LR分析表的構(gòu)造,有可能存在〔動作沖突?！博~﹡

A.移進(jìn)B.歸約

C.移進(jìn)/歸約

D.移進(jìn)/移進(jìn)

E.歸約/歸約5.對LR分析器來說,存在〔等分析表的構(gòu)造方法?！博~﹡

A.LALR

B.LR〔0

C.SLR〔1

D.SLR〔0

E.LR〔16.自上而下的語法分析方法有〔?！博~﹡

A.算符優(yōu)先分析法

B.LL〔1分析法

C.SLR〔1分析法

D.LR〔0分析法

E.LALR〔1分析法二、填空題：1．對于一個(gè)文法,如果能夠構(gòu)造〔。使得它的〔均是唯一確定的,則稱該文法為LR文法。〔﹡2．字的前綴是指該字的〔。〔﹡3．活前綴是指〔的一個(gè)前綴,這種前綴不含〔之后的任何符號。〔﹡4．在LR分析過程中,只要〔的已掃描部分保持可歸約成一個(gè)〔,則掃描過的部分正確。5．將識別〔的NFA確定化,使其成為以〔為狀態(tài)的DFA,這個(gè)DFA就是建立〔的基礎(chǔ)?！博~﹡6．A→α·稱為〔項(xiàng)目；對文法開始符S′→α·為〔項(xiàng)目；若a為終結(jié)符,則稱A→α·aβ為〔項(xiàng)目；若B為非終結(jié)符,則稱A→α·aβ為〔項(xiàng)目。〔﹡﹡7．LR〔0分析法的名字中"L"表示〔,"R"表示〔,"0”表示〔。三、判斷題：1．對一個(gè)右線性文法G,必存在一個(gè)左線性文法G',使得L<G>=L<G'>,反之亦然。〔﹡四、綜合題：1．構(gòu)造下面文法的LL〔1分析表?！博~﹡﹡D→TLT→int|realL→idRR→,idR|ε2．下面文法G[S]是否為LL〔1文法？說明理由?！博~﹡S→AB|PQxA→xyB→bcP→dP|εQ→aQ|ε3．設(shè)有以下文法：〔﹡﹡﹡G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε〔1求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集?！?該文法是LL〔1文法嗎？〔3構(gòu)造C[S]的LL〔1分析表。4．將文法G[V]改造成為LL<1>的?！博~﹡﹡G[V]：V→N|N[E]E→V|V+EN→i5．已知文法：〔﹡﹡﹡G[A]：A→aAa|ε〔1該文法是LL〔1文法嗎？為什么？〔2若采用LL〔1方法進(jìn)行語法分析,如何得到該文法的LL〔1分析表？〔3若輸入符號串"aaaa",請給出語法分析過程。6．設(shè)有文法G[S]為：〔﹡﹡﹡S→a|b|<A>A→SdA|S〔1完成下列算符優(yōu)先關(guān)系表,見下表,并判斷G[S]是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表〔2給出句型〔SdSdS的短語、簡單短語、句柄、素短語和最左素短語?！?給出輸入串〔adb#的分析過程。7．設(shè)有文法G[S]為：〔﹡﹡﹡S→a|b|<A>A→SdA|S〔1完成下列算符優(yōu)先關(guān)系表,見下表,并判斷G[S]是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表〔2給出句型〔SdSdS的短語、簡單短語、句柄、素短語和最左素短語?！?給出輸入串〔adb#的分析過程。8．對于文法G[S]：S→AS|bA→SA|a〔1列出所有LR〔0項(xiàng)目；〔2列出構(gòu)成文法LR〔0項(xiàng)目集規(guī)族。〔﹡﹡﹡9．有文法G[S]S→a|∧|〔TT→T,S|S該文法是否是LL〔1文法,若不是,請進(jìn)行改寫。并給出它的分析表?！博~﹡﹡10．有文法G[S]〔1S→A〔2S→B〔3A→aAb〔4A→c〔5B→aBb〔6B→d試構(gòu)造相應(yīng)的LR〔0項(xiàng)目集規(guī)族及相應(yīng)的分析表。〔﹡﹡﹡11.已知文法G[S],其產(chǎn)生式如下：

S→<L>|a

L→L,S|S從G[S]中消除左遞歸,并為之構(gòu)造一個(gè)非遞歸預(yù)測分析器LL<1>分析表。請說明在句子<a,<a,a>>上的分析器的動作。〔﹡﹡﹡12.證明下面文法是SLR<1>文法,并構(gòu)造其SLR分析表。E→E+T|TT→TF|FF→F*|a|b〔﹡﹡﹡第五章語法制導(dǎo)翻譯技術(shù)和中間代碼生成一、多項(xiàng)選擇題： 1.中間代碼主要有〔?！博~﹡

A.四元式B.二元式C.三元式 D.后綴式E.間接三元式2.在下面的〔語法制導(dǎo)翻譯中,采用拉鏈-回填技術(shù)?！博~﹡

A.賦值語句B.goto語句

C.條件語句 D.循環(huán)語句3.下列〔中間代碼形式有益于優(yōu)化處理?！博~﹡

A.三元式 B.四元式 C.間接三元式 D.逆波蘭表示法 E.樹形表示法4.在編譯程序中安排中間代碼生成的目的是〔。〔﹡﹡

A.便于進(jìn)行存儲空間的組織 B.利于目標(biāo)代碼的優(yōu)化

C.利于編譯程序的移植D.利于目標(biāo)代碼的移植 E.利于提高目標(biāo)代碼的質(zhì)量5.三地址代碼語句具體實(shí)現(xiàn)通常有〔表示方法。〔﹡﹡

A.逆波蘭表示 B.三元式 C.間接三元式 D.樹形表示 E.四元式二、填空題：1．中間代碼有〔、〔、〔、〔等形式,生成中間代碼主要是為了使〔。2．語法制導(dǎo)翻譯既可以用來產(chǎn)生〔代碼,也可以用來產(chǎn)生〔指令,甚至可用來對輸入串進(jìn)行〔。〔﹡3．當(dāng)源程序中的標(biāo)號出現(xiàn)"先引用后定義"時(shí),中間代碼的轉(zhuǎn)移地址須持〔時(shí)才能確定,因而要進(jìn)行〔?！博~4．文法符號的屬性有兩種,一種稱為〔,另一種稱為〔?！博~﹡5．后綴式abc-/所代表的表達(dá)式是〔,表達(dá)式<a-b>*c可用后綴式〔表示?！博~﹡6．用一〔輔以〔的辦法來表示中間代碼,這種表示法稱為間接三元式?！博~﹡三、問答題：1．給出下列表達(dá)式的逆波蘭表示〔后綴式：〔﹡﹡①a*<-b+c>②<A∨B>∧<C∨┑D∧E>2．寫出算術(shù)表達(dá)式：A+B*<C-D>+E/<C-D>↑N的：〔﹡﹡﹡①四元式序列；②三元式序列；③間接三元式序列3．寫出下面算術(shù)表達(dá)式E值的語義描述：〔﹡﹡〔1E→E1+E2〔2E→0〔3E→14．給出下列表達(dá)式的逆波蘭表式?！博~﹡〔1a≤b+c∧a＞d∨a+b≠e〔2a=c∧b=d〔3〔a*b-c**n+b*〔a+d/e5.分別寫出語句a:=b*-c+b*-c的四元式、三元式和間接三元式的表示。〔﹡﹡﹡6.文法及其翻譯方案為：P:=bQb{print:"1”}Q:=cR{print:"2Q:=a{print:"3”}R:=Qad{print:"4當(dāng)輸入串為bccaadadb時(shí),該翻譯方案的輸出是什么？〔﹡﹡7.給定文法G[E]:E:=T+E|TT:=F*T|FF:=i|<E>則求i+i+<i*i>*i的逆波蘭表示?！博~﹡第六章符號表的組織和管理一、多項(xiàng)選擇題：1.符號表的每一項(xiàng)均包含〔?！博~﹡A.名字欄 B.類型欄 C.信息欄D.值欄 E.a～d均包含2.對編譯程序所用到的符號表,涉及的操作有〔?！博~﹡A.填寫或更新信息欄容 B.填入新名 C.給定名字,訪問它的有關(guān)信息D.雜湊技術(shù) E.線性表和排序二叉樹3.源程序中的錯(cuò)誤一般有〔?！博~﹡A.詞法錯(cuò)誤 B.語法錯(cuò)誤 C.語義錯(cuò)誤 D.編譯錯(cuò)誤

E.違反環(huán)境限制的錯(cuò)誤二、填空題：1．符號表中名字欄容有兩種填寫方式,它們是〔填寫和〔填寫?！博~﹡2．詞法分析階段的錯(cuò)誤主要是〔,可通過〔的辦法糾正錯(cuò)誤?！博~﹡3．符號表中名字的有關(guān)信息在〔和〔過程中陸續(xù)填入。〔﹡4．在目標(biāo)代碼生成階段,符號表是〔的依據(jù)。〔﹡三、簡答題：1．在編譯過程中為什么要建立符號表？〔﹡﹡2.一個(gè)過程的活動記錄中一般包含那些數(shù)據(jù)。〔﹡﹡第七章運(yùn)行時(shí)的存儲組織與管理一、多項(xiàng)選擇題：1.下面〔需要在運(yùn)行階段分配存儲空間。〔﹡﹡

A.數(shù)組B.指針變量

C.動態(tài)數(shù)組

D.靜態(tài)變量

E.動態(tài)變量2.棧式動態(tài)分配允許〔?！博~﹡

A.遞歸過程

B.分程序結(jié)構(gòu)

C.動態(tài)變量

D.動態(tài)數(shù)組

E.靜態(tài)數(shù)組3.動態(tài)存儲分配可采用的分配方案有〔?！博~﹡

A.隊(duì)式存儲分配

B.棧式存儲分配

C.鏈?zhǔn)酱鎯Ψ峙?/p>

D.堆式存儲分配

E.線性存儲分配4.棧式動態(tài)分配與管理因調(diào)用而進(jìn)入過程之后,要做的工作是〔?！博~﹡

A.定義新的活動記錄的SP

B.保護(hù)返回地址

C.傳遞參數(shù)值

D.建立DISPLAY表

E.定義新的活動記錄的TOP5.靜態(tài)分配不允許程序出現(xiàn)〔?！博~﹡

A.遞歸過程

B.靜態(tài)數(shù)組

C.可變體積的數(shù)據(jù)項(xiàng)目

D.待定性質(zhì)的名字

E.靜態(tài)變量6.活動記錄包括〔?！博~﹡

A.局部變量

B.連接數(shù)據(jù)

C.形式單元

D.局部數(shù)組的情變量

E.臨時(shí)工作單元第八章目標(biāo)代碼生成一、多項(xiàng)選擇題：1.根據(jù)優(yōu)化所涉及的圍,可將優(yōu)化分為〔?！博~﹡

A.局部優(yōu)化

B.過程優(yōu)化

C.全局優(yōu)化

D.循環(huán)優(yōu)化

E.四元式優(yōu)化2.下列優(yōu)化中,屬于循環(huán)優(yōu)化的有〔。〔﹡﹡

A.強(qiáng)度削弱

B.合并已知量

C.刪除無用賦值

D.刪除歸納變量

E.代碼外提3.如果a→b是程序流圖中的一條邊,則由這條回邊構(gòu)成的循環(huán)由〔結(jié)點(diǎn)組成。〔﹡﹡

A.a

B.b

C.有通路到達(dá)b的結(jié)點(diǎn)

D.有通路到達(dá)a且該通路上不經(jīng)過b的結(jié)點(diǎn)

E.有通路到達(dá)b且該通路上不經(jīng)過a的結(jié)點(diǎn)

4.采用無環(huán)有向圖〔DAG,可以實(shí)現(xiàn)的優(yōu)化有〔?！博~﹡

A.合并已知量

B.刪除公共子表達(dá)式

C.強(qiáng)度削弱

D.刪除無用賦值

E.刪除歸納變量5.編譯程序的輸出結(jié)果可以是〔?！博~﹡

A.目標(biāo)代碼

B.匯編語言代碼

C.中間代碼

D.優(yōu)化后的中間代碼

E.可重定位代碼二、填空題：1．局部優(yōu)化是〔圍進(jìn)行的一種優(yōu)化。〔﹡2．在一個(gè)基本塊,可實(shí)行3種優(yōu)化方法,即合并已知量、〔、〔?！博~﹡3．優(yōu)化就是對程序進(jìn)行各種〔變換,使之能生成更有效的〔?！博~4．在優(yōu)化中,可把循環(huán)中的〔提到循環(huán)外面去,這種方法稱為〔?！博~﹡東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理作業(yè)題參考答案第一章編譯概述多項(xiàng)選擇題：1.編譯程序各階段的工作都涉及到〔BC。〔﹡﹡A.語法分析B.表格管理C.出錯(cuò)處理D.語義分析E.詞法分析2.編譯程序工作時(shí),通常有〔ABCE階段。

〔﹡A.詞法分析B.語法分析C.中間代碼生成D.語義檢查E.目標(biāo)代碼生成填空題：1．解釋程序和編譯程序的區(qū)別在于〔是否生成目標(biāo)程序?！博~2．編譯過程通常可分為5個(gè)階段,分別是〔詞法分析、〔語法分析、〔中間代碼生成、〔代碼優(yōu)化和〔目標(biāo)代碼生成。〔﹡3．編譯程序工作過程中,第一段輸入是〔源程序,最后階段的輸出為〔目標(biāo)代碼生成程序。〔﹡4．編譯程序是指將〔高級語言編寫的程序翻譯成〔目標(biāo)語言程序的程序?！博~綜合題：1.畫出編譯程序的總體結(jié)構(gòu)圖,簡述各部分的主要功能?！博~﹡﹡解答：編譯程序的總體結(jié)構(gòu)如下圖所示：詞法分析程序：輸入源程序,進(jìn)行詞法分析,輸出單詞符號。語法分析程序：在詞法分析的基礎(chǔ)上,根據(jù)語言的語法規(guī)則〔方法規(guī)則把單詞符號串分解成各類語法單位,并判斷輸入串是否構(gòu)成語法上正確的"程序"。中間代碼生成程序：按照語義規(guī)則把語法分析程序歸約〔或推導(dǎo)出的語法單位翻譯成一定形式的中間代碼,比如說四元式。優(yōu)化程序：對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成程序：把中間代碼翻譯成目標(biāo)語言程序。表格管理模塊保存一系列的表格,登記源程序的各類信息和編譯各階段的進(jìn)展情況。編譯程序各階段所產(chǎn)生的中間結(jié)果都記錄在表格中,所需信息多數(shù)都需從表格中獲取,整個(gè)編譯過程中都在不斷地和表格打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。此外,編譯的各個(gè)階段都可能出現(xiàn)錯(cuò)誤。出錯(cuò)處理程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理。第二章文法和語言的基本知識多項(xiàng)選擇題：1.ABC2.ACE3.BCD4.AC5.BC填空題：1．文法中的終結(jié)符和非終結(jié)符的交集是〔空集。詞法分析器交給語法分析器的文法符號一定是〔終結(jié)符,它一定只出現(xiàn)在產(chǎn)生式的〔右部?！博~2．最左推導(dǎo)是指每次都對句型中的〔最左非終結(jié)符進(jìn)行擴(kuò)展?！博~3．在語法分析中,最常見的兩種方法一定是〔自上而上分析法,另一是〔自下而上分析法?！博~4．采用〔自上而下語法分析時(shí),必須消除文法的左遞歸?！博~5．〔語法樹代表推導(dǎo)過程,〔分析樹代表歸約過程?！博~6．自下而上分析法采用〔移進(jìn)、歸約、錯(cuò)誤處理、〔接受等四種操作?！博~﹡7．Chomsky把文法分為〔4種類型,編譯器構(gòu)造中采用〔2型和〔3型文法,它們分別產(chǎn)生〔上下文無關(guān)語言和〔正規(guī)語言語言,并分別用〔下推自動機(jī)和〔有限自動機(jī)識別所產(chǎn)生的語言?！博~﹡判斷題：1．正確2．錯(cuò)誤3．錯(cuò)誤4．錯(cuò)誤5．錯(cuò)誤6．錯(cuò)誤7．正確8．正確9．錯(cuò)誤簡答題1句柄：〔﹡解答：一個(gè)句型的最左直接短語稱為該句型的句柄。2．素短語：〔﹡﹡解答：至少含有一個(gè)終結(jié)符的素短語,并且除它自身之外不再含任何更小的素短語。3．語法樹：〔﹡﹡解答：滿足下面4個(gè)條件的樹稱之為文法G[S]的一棵語法樹。①每一終結(jié)均有一標(biāo)記,此標(biāo)記為VN∪VT中的一個(gè)符號；②樹的根結(jié)點(diǎn)以文法G[S]的開始符S標(biāo)記；③若一結(jié)點(diǎn)至少有一個(gè)直接后繼,則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號；④若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼,且按從左至右的順序,這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,…,Xk,則A→X1,X2,…,Xk,必然是G的一個(gè)產(chǎn)生式。4．歸約：〔﹡﹡解答：我們稱αγβ直接歸約出αAβ,僅當(dāng)A→γ是一個(gè)產(chǎn)生式,且α、β∈<VN∪VT>*。歸約過程就是從輸入串開始,反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號,直至文法開始符。5．推導(dǎo)：〔﹡﹡解答：我們稱αAβ直接推出αγβ,即αAβTαγβ,僅當(dāng)A→γ是一個(gè)產(chǎn)生式,且α、β∈<VN∪VT>*。如果α1α2…αn,則我們稱這個(gè)序列是從α1至α2的一個(gè)推導(dǎo)。若存在一個(gè)從α1αn的推導(dǎo),則稱α1可推導(dǎo)出αn。推導(dǎo)是歸約的逆過程。問答題1．給出上下文無關(guān)文法的定義?！博~﹡解答：一個(gè)上下文無關(guān)文法G是一個(gè)四元式〔VT,VN,S,P,其中：●VT是一個(gè)非空有限集,它的每個(gè)元素稱為終結(jié)符號；●VN是一個(gè)非空有限集,它的每個(gè)元素稱為非終結(jié)符號,VT∩VN=Φ；●S是一個(gè)非終結(jié)符號,稱為開始符號；●P是一個(gè)產(chǎn)生式集合〔有限,每個(gè)產(chǎn)生式的形式是P→α,其中,P∈VN,α∈<VT∪VN>*。開始符號S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2.文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc〔1它是Chomsky哪一型文法？〔2它生成的語言是什么？〔﹡﹡﹡解答：〔1由于產(chǎn)生式左部存在終結(jié)符號,且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符號長度,所以文法G[S]是Chomsky1型文法,即上下文有關(guān)文法?！?按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低〔否則無法推出句子,我們可以得到：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQaabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc……于是得到文法G[S]生成的語言L={anbncn|n≥1}3．按指定類型,給出語言的文法。L={aibj|j＞i≥1}的上下文無關(guān)文法?！博~﹡解答：由L={aibj|j＞i≥1}知,所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有S→aSb型產(chǎn)生式,以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次,還需有S→Sb或S→bS型的產(chǎn)生式,用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無關(guān)文法G[S]為：G[S]：S→aSb|Sb|b4．有文法G：S→aAcB|BdA→AaB|cB→bScA|b〔1試求句型aAaBcbbdcc和aAcbBdcc的句柄；〔2寫出句子acabcbbdcc的最左推導(dǎo)過程?！博~﹡﹡解答：〔1分別畫出對應(yīng)兩句型的語法樹,如下圖所示句柄:AaBBd圖語法樹〔2句子acabcbbdcc的最左推導(dǎo)如下：STaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5．對于文法G[S]：S→〔L|aS|aL→L,S|S〔1畫出句型〔S,〔a的語法樹?！?寫出上述句型的所有短語、直接短語、句柄和素短語。〔﹡﹡﹡解答：〔1句型〔S,〔a的語法樹如下圖所示。圖句型〔S,〔a的語法樹〔2由上圖可知：①短語：S、a、<a>、S,<a>、<S,<a>>；②直接短語：a、S；③句柄：S；④素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得,即；因此素短語為a。6.考慮文法G[S],其產(chǎn)生式如下:S→<L>|aL→L,S|S<a>試指出此文法的終結(jié)符號、非終結(jié)符號。<b>給出句子<a,<a,a>>的分析樹。<c>構(gòu)造句子<a,<a,a>>的一個(gè)最左推導(dǎo)。<d>構(gòu)造句子<a,<a,a>>的一個(gè)最右推導(dǎo)。<e>這個(gè)文法生成的語言是什么？〔﹡﹡解答：<a>終結(jié)符號為：{<,>,a,,,}

非終結(jié)符號為：{S,L}

開始符號為：S<b>分析樹〔c

S<L><L,S><S,S><a,S><a,<L><a,<L,S>>

<a,<S,S>><a,<a,S>><a,<a,a>><d>S<L><L,S><L,<L>><L,<L,S>><L,<L,a>>

<L,<S,a>><L,<a,a>><S,<a,a>><a,<a,a>><e>L<G[S]>=<α1,α2,...,αn>或a

其中αi<1≤i≤n>是L<G[S]>。即L<G[S]>產(chǎn)生一個(gè)以a為原子的純表,但不包括空表。7．考慮文法G[T]：T→T*F|FF→F↑P|PP→〔T|i證明T*P↑〔T*F是該文法的一個(gè)句型,并指出直接短語和句柄。〔﹡﹡解答：首先構(gòu)造T*P↑〔T*F的語法樹如下圖所示。圖句型T*P↑〔T*F的語法樹由上圖可知,T*P↑〔T*F是文法G[T]的一個(gè)句型。直接短語有兩個(gè),即P和T*F；句柄為P。8．試描述下列文法產(chǎn)生的語言L〔G[S]〔﹡﹡S→10S0|aAA→bA|a解答：L<G>={<10>iabna0in≥0i≥0}9．已知語言L<G>={abnc|n≥1}試對該語言構(gòu)造相應(yīng)文法。〔﹡﹡解答：G[Z]:Z→aBCB→Bb|b10．證明下列文法的二義性〔﹡﹡﹡1．G[Z]2．G[S]Z→aZbZ|aZ|aS→ABA→bB|bC|baB→Sb|ba|aC→Bb|b解答：〔1對于句子aaaba,畫出二棵不同的語法樹,因而是二義的?！?G[S]對于句子baba,畫出二棵不同的語法樹,因而是二義的。11．有文法G[S]：S→iSeS|iS|i該文法是否是二義的。試證明之?！博~﹡解答：對于句子iiiei,有兩棵不同的語法樹,故文法是二義的。12．文法G[T]：T→aR,R→Tb|d生成的語言是什么？G[T]是否為3型文法？〔﹡﹡解答：不是3型文法。13.試寫出能夠描述下列格式的文法。〔﹡﹡673917422解答：文法產(chǎn)生式規(guī)則如下：<>→<局代碼><本機(jī)碼><>→<區(qū)前綴><局代碼><本機(jī)碼><區(qū)前綴>→<地區(qū)碼>‘-’<區(qū)前綴>→‘<’<地區(qū)碼>‘>’<地區(qū)碼>→DIGDIG<地區(qū)碼>→DIGDIGDIG<局代碼>→DIGDIGDIGDIG<本機(jī)碼>→DIGDIGDIGDIG試構(gòu)造生成語言的上下文無關(guān)文法。〔﹡﹡﹡<1>{anbnci|n≥1,i≥0}<2>{w|w∈{a,b}+,且w中a的個(gè)數(shù)恰好比b多1}解答：<1>把a(bǔ)nbnci分成anbn和ci兩部分,分別由兩個(gè)非終結(jié)符號生成,因此,生成此文法的產(chǎn)生式為：S→ABA→aAb|abB→cB|ε<2>令S為開始符號,產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè),令E為一個(gè)非終結(jié)符號,產(chǎn)生含相同個(gè)數(shù)的a和b的所有串,則產(chǎn)生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|ε下面的二義性文法描述命題演算公式,為它寫一個(gè)等價(jià)的非二義性文法。G[S]:S->SANDS|SORS|NOTS|p|q|<S>〔﹡﹡解答：G[S]:S->SANDA|AA->AORB|BB->NOTB|p|q|<S>16.對于下列語言分別寫出它們的正規(guī)表達(dá)式?！博~﹡<1>

英文字母組成的所有符號串,要求符號串中順序包含五個(gè)元音。<2>

英文字母組成的所有符號串,要求符號串中的字母依照詞典順序排列。解答：<1>令Letter表示除這五個(gè)元音外的其它字母。<<letter>*A<letter>*E<letter>*I<letter>*O<letter>*U<letter>>*<2>A*B*Z*第三章詞法分析與有窮自動機(jī)多項(xiàng)選擇題：1.ACE2.ABD填空題：1．確定有限自動機(jī)DFA是〔NFA的一個(gè)特例?！博~2．若二個(gè)正規(guī)式所表示的〔正規(guī)集相同,則認(rèn)為二者是等價(jià)的?！博~3．一個(gè)字集是正規(guī)的,當(dāng)且僅當(dāng)它可由〔DFA/NFA所〔識別?！博~判斷題：1．錯(cuò)誤2．錯(cuò)誤3．錯(cuò)誤4．正確5．正確6．正確7．正確8．正確9．錯(cuò)誤10．正確綜合題：1．設(shè)M＝〔{x,y},{a,b},f,x,{y}為一非確定的有限自動機(jī),其中f定義如下：f〔x,a＝{x,y}f〔a,b＝{y}f〔y,a＝φf〔y,b＝{x,y}試構(gòu)造相應(yīng)的確定有限自動機(jī)M′?！博~﹡解答：對照自動機(jī)的定義M=<S,Σ,f,S0,Z>,由f的定義可知f<x,a>、f<y,b>均為多值函數(shù),所以是一非確定有限自動機(jī),先畫出NFAM相應(yīng)的狀態(tài)圖,如圖下所示。圖NFAM用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣下表所示。將轉(zhuǎn)換矩陣中的所有子集重新命名而形成下表所示的狀態(tài)轉(zhuǎn)換矩陣。表狀態(tài)轉(zhuǎn)換矩陣即得到M′＝〔{0,1,2},{a,b},f,0,{1,2},其狀態(tài)轉(zhuǎn)換圖如下圖所示。將上圖的DFAM′最小化。首先,將M′的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}；其次,考察{1,2}。由于{1,2}a={1,2}b={2}{1,2},所以不再將其劃分了,也即整個(gè)劃分只有兩組{0},{1,2}：令狀態(tài)1代表{1,2},即把原來到達(dá)2的弧都導(dǎo)向1,并刪除狀態(tài)2。最后,得到如下圖所示化簡DFAM′。圖化簡后的DFAM′2．對給定正規(guī)式b*〔d|ad〔b|ab+,構(gòu)造其NFAM?！博~﹡解答：首先用A+=AA*改造正規(guī)式得：b*<d|ad><b|ab><b|ab>*；其次,構(gòu)造該正規(guī)式的NFAM,如下圖所示。圖NFAM3．字母表{a,b}上的正規(guī)式R=〔ba|a*,構(gòu)造R的相應(yīng)DFA?！博~﹡解答：IIaIbx1y1y21y1y221y

IIaIb12322332

4．請寫出在∑=〔a,b上,不是a開頭的,但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式,并構(gòu)造與之等價(jià)狀態(tài)最少的DFA。〔﹡﹡﹡解答：根據(jù)題意,不以a開頭就意味著以b開頭,且以aa結(jié)尾的正規(guī)式為：b<a|b>*aa根將圖1所示的NFA確定化,如圖2所示。NFA將圖1所示的NFA確定化,如圖從圖2可知已為最簡狀態(tài),由于開始狀態(tài)0只能輸入字符b而不能與狀態(tài)1合并,而狀態(tài)2和狀態(tài)3面對輸入符號的下一狀態(tài)相同,但兩者一為非終態(tài)、一為終態(tài),故也不有合并,故圖2所示的狀態(tài)轉(zhuǎn)換矩陣已是最簡的DFA,如圖3所示據(jù)正規(guī)式畫出NFA,如圖1所示。圖2狀態(tài)轉(zhuǎn)換矩陣圖3最簡DFA人運(yùn)狼、羊、菜過河,一次運(yùn)一件,不讓羊吃掉菜,也不讓狼吃掉羊,畫出渡河的狀態(tài)轉(zhuǎn)換圖?？煞駥⑵涑橄鬄橐粋€(gè)有限自動機(jī)?！博~﹡﹡解答：先寫出渡河的方法,串中對象順序?yàn)槿藖砘囟珊訒r(shí)所運(yùn)的貨物的順序：①羊空菜羊狼空羊②羊空狼羊菜空羊現(xiàn)給出一個(gè)NFA:M=<Σ,Q,0,{9},δ>其中Σ={羊,空,菜,狼}Q={0,1,2,3,4,5,6,7,8,9}轉(zhuǎn)形函數(shù)δ<0,羊>=1,

δ<1,空>=2,

δ<2,菜>=3,

δ<2,狼>=5δ<3,羊>=4,

δ<5,羊>=6,

δ<4,狼>=7,

δ<6,菜>=7δ<7,空>=8,

δ<8,羊>=96．對于正規(guī)表達(dá)式<a|b>*a<a|b>構(gòu)造最小狀態(tài)的DFA?！博~﹡解答：①NFAM:②DFAM:③化簡:

②中的DFAM中沒有等價(jià)狀態(tài),因此為最小化的DFAM。第四章語法分析多項(xiàng)選擇題：1.AD2.CE3.ACDE4.CE5.ABCE6.ACDE填空題：1．對于一個(gè)文法,如果能夠構(gòu)造〔LR<0>文法。使得它的〔每個(gè)入口均是唯一確定的,則稱該文法為LR文法?！博~2．字的前綴是指該字的〔任意首部?！博~3．活前綴是指〔規(guī)句型的一個(gè)前綴,這種前綴不含〔句柄之后的任何符號?！博~4．在LR分析過程中,只要〔輸入串的已掃描部分保持可歸約成一個(gè)〔活前綴,則掃描過的部分正確。〔﹡5．將識別〔活前綴的NFA確定化,使其成為以〔項(xiàng)目集合為狀態(tài)的DFA,這個(gè)DFA就是建立〔LR分析算法的基礎(chǔ)。〔﹡﹡6．A→α·稱為〔歸約項(xiàng)目；對文法開始符S′→α·為〔接受項(xiàng)目；若a為終結(jié)符,則稱A→α·aβ為〔移進(jìn)項(xiàng)目；若B為非終結(jié)符,則稱A→α·aβ為〔待約項(xiàng)目?！博~﹡7．LR〔0分析法的名字中"L"表示〔自左至右分析,"R"表示〔采用最右推導(dǎo)的逆過程即最左歸約,"0”表示〔向右查看0個(gè)字符。〔﹡﹡判斷題：1．正確簡答題：綜合題：1．構(gòu)造下面文法的LL〔1分析表?！博~﹡﹡D→TLT→int|realL→idRR→,idR|ε解答：LL〔1分析表見下表。分析雖然這個(gè)文法很簡單,我們還是從求開始符號集合和后繼符號集合開始。FIRST〔D=FIRST〔T={int,real}FOLLOW〔D=FOLLOW〔L={#}FIRST〔L={id}FOLLOW〔T={id}FIRST〔R={,,ε}FOLLOW〔R={#}有了上面每個(gè)非終結(jié)符的FIRST集合,填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部α的FIRST〔α就不是件難事了。填表時(shí)唯一要小心的時(shí),ε是產(chǎn)生式R→ε右部的一個(gè)開始符號,而#在FOLLOW〔R中,所以R→ε填在輸入符號#的欄目中。表LL〔1分析表2．下面文法G[S]是否為LL〔1文法？說明理由?！博~﹡S→AB|PQxA→xyB→bcP→dP|εQ→aQ|ε解答：該文法不是LL〔1文法,見下面分析中的說明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。〔1P的兩個(gè)右部dP和ε的開始符號肯定不相交?！?Q的兩個(gè)右部aQ和ε的開始符號肯定不相交?！?對S來說,由于x∈FIRST<AB>,同時(shí)也有x∈FIRST<PQx>〔因?yàn)镻和Q都可能為空。所以該文法不是LL〔1文法。3．設(shè)有以下文法：〔﹡﹡﹡G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε〔1求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集?！?該文法是LL〔1文法嗎？〔3構(gòu)造C[S]的LL〔1分析表。解答：〔1求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋孩賁是識別符號,且有A→BSD、B→SAc、D→Se,所以FOLLOW〔S應(yīng)包含F(xiàn)IRST<D>∪FIRST<Ac>∪FIRST<e>∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}②又因?yàn)锳→BSD和D→ε,所以FOLLOW中還包含F(xiàn)OLLOW<A>。因?yàn)镾→aAbDe和B→SAc,所以FOLLOW〔A=FIRST〔bDe∪FIRST〔c={b,c}綜合①、②得FOLLOW〔S={a,d,c,e,#}∪{a,b,c,d,e,#}因?yàn)锳→BSD,所以FOLLOW〔B=FIRST〔SD={a,d}因?yàn)镾→aAbDe|d、A→BSD|e和B→SAc|cD,所以FOLLOW〔D=FIRST〔e∪FOLLOW〔A∪FOLLOW〔B={e}∪{b,c}∪{a,d}={a,b,c,d,e}〔2G[S]不是LL〔1文法。因?yàn)楫a(chǎn)生式B→SAc|cD|ε中FIRST〔SAc∩FOLLOW〔B={a,d}≠〔3構(gòu)造G[S]的LL〔1分析表。按照LL〔1分析表的構(gòu)造算法構(gòu)造方法G[S]的LL〔1分析表如下表所示。表G[S]的LL〔1分析表4．將文法G[V]改造成為LL<1>的?！博~﹡﹡G[V]：V→N|N[E]E→V|V+EN→i解答：對文法G[V]提取公共左因子后得到文法：G′[V]：V→NAA→ε|[E]E→VBB→ε|+EN→i求出文法G′[V]中每一個(gè)非終結(jié)符號的FIRST集：FIRST<V>={i}FIRST<A>={[,ε}FIRST<E>={i}FIRST<B>={+,ε}FIRST<N>={i}求出文法G′[V]中每一個(gè)非終結(jié)符號的FOLLOW集：FOLLOW<V>={#}∪FIRST<B>\{ε}∪FOLLOW<E>={#,+,]}FOLLOW<A>=FOLLOW<V>={+,,#}FOLLOW<E>=FIRST<]>\{ε}∪FOLLOW<B>=FIRST<]>\{ε}∪FOLLOW<E>={]}FOLLOW<B>=FOLLOW<E>={]}FOLLOW<N>=FIRST<A>\{ε}∪FOLLOW<V>={[,],+,#}可以看到,對文法G′[V]的產(chǎn)生式A→ε|[E],有FIRST<[E]>∩FOLLOW<A>={[}∩{+,],#}=對產(chǎn)生式B→ε|+E,有FIRST<+E>∩FOLLOW<B>={+}∩{]}=而文法的其他產(chǎn)生式都只有一個(gè)不為ε的右部,所以文法G′[V]是LL<1>文法。5．已知文法：〔﹡﹡﹡G[A]：A→aAa|ε〔1該文法是LL〔1文法嗎？為什么？〔2若采用LL〔1方法進(jìn)行語法分析,如何得到該文法的LL〔1分析表？〔3若輸入符號串"aaaa",請給出語法分析過程。解答：〔1因?yàn)楫a(chǎn)生式A→aAa|ε有空產(chǎn)生式右部,而FOLLOW<A>={#}∪FIRST<a>={a,#}造成FIRST<A>∩FOLLOW<A>={A,ε}∩{a,#}≠所以該文法不是LL〔1文法。〔2若采用LL〔1方法進(jìn)行語法分析,必須修改該文法。因該文法產(chǎn)生偶數(shù)〔可以為0個(gè)a,所以得到文法G′[A]：A→aaA|ε此時(shí)對產(chǎn)生式A→aaA|ε,有FOLLOW<A>={#}∪FOLLOW<A>={#},因而FIRST<A>∩FOLLOW<A>={a,ε}∩{#}=所以文法G′[A]是LL〔1文法,按LL〔1分析表構(gòu)造算法構(gòu)造該文法的LL〔1分析表如下表所示。表文法G′[A]的LL<1>分析表〔3若采用LL<1>方法進(jìn)行語法分析,對符號串"aaaa"的分析過程如下表所示。表對符號串"aaaa"的分析過程6．設(shè)有文法G[S]為：〔﹡﹡﹡S→a|b|<A>A→SdA|S〔1完成下列算符優(yōu)先關(guān)系表,見下表,并判斷G[S]是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表〔2給出句型〔SdSdS的短語、簡單短語、句柄、素短語和最左素短語。〔3給出輸入串〔adb#的分析過程。解答：〔1先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|<A>得：FIRSTVT<S>={a,b,<>；由A→Sd…得：FIRSTVT<A>=hdd9n7r；又由A→S…得：FIRSTVT<S>FIRSTVT<A>,即FIRSTVT<A>={d,a,b,<}；由S→a|b|<A>得；LASTVT<S>={a,b,}}；由A→…dA得：LASTVT<A>=v3hhrhr,又由A→S得：LASTVT<S>LASTVT<A>,即LASTVT<A>={d,a,b,>}。構(gòu)造優(yōu)先關(guān)系表方法如下：①對P→…ab…,或P→…aQb…,有ab；②對P→…aR…,而b∈FIRSTVT<R>,有ab；③對P→…Rb…,而a∈FIRSTVT<R>,有ab。由此得到：①由S→<A>得：<>；②由S→<A…得：<FIRSTVT<A>,即：<d,<a,<b,<<；由A→…dA得：dFIRSTVT<A>,即：dd,da,db,d<；③由S→A>得,LASTVT<A>>,即：d>,a>,b>,>>；由A→Sd…得：LASTVT<S>d,即：ad,bd,>d；此外,由#S#得：##；由#FIRSTVT<S>得：#a,#b,#<；由LASTVT<S>#得：d#,a#,b#,>#。最后得到算符優(yōu)先關(guān)系表,見下表。表算符優(yōu)先關(guān)系表由上表可以看出,任何兩個(gè)終結(jié)符之間至少只滿足、、三種優(yōu)先關(guān)系之一,故G[S]為算符優(yōu)先文法?！?為求出句型〔SdSdS的短語、簡單短語、句柄,我們先畫出該句型對應(yīng)的語法樹,如下圖所示。由圖得到：短語：S,SdS,SdSdS,〔SdSdS簡單短語〔即直接短語：S句柄〔即最左直接短語：S素短語：SdS,它同時(shí)也是該句型的最左素短語。圖句型〔SdSdS的語法樹〔3輸入串〔adb#的分析過程見下表。表輸入串〔adb#的分析過程7．設(shè)有文法G[S]為：〔﹡﹡﹡S→a|b|<A>A→SdA|S〔1完成下列算符優(yōu)先關(guān)系表,見下表,并判斷G[S]是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表〔2給出句型〔SdSdS的短語、簡單短語、句柄、素短語和最左素短語?！?給出輸入串〔adb#的分析過程。解答：〔1先求文法G[S]的FIRSTVT集和LASTVT集：由S→a|b|<A>得：FIRSTVT<S>={a,b,<>；由A→Sd…得：FIRSTVT<A>=lb9vptd；又由A→S…得：FIRSTVT<S>FIRSTVT<A>,即FIRSTVT<A>={d,a,b,<}；由S→a|b|<A>得；LASTVT<S>={a,b,}}；由A→…dA得：LASTVT<A>=ljbjv5j,又由A→S得：LASTVT<S>LASTVT<A>,即LASTVT<A>={d,a,b,>}。構(gòu)造優(yōu)先關(guān)系表方法如下：①對P→…ab…,或P→…aQb…,有ab；②對P→…aR…,而b∈FIRSTVT<R>,有ab；③對P→…Rb…,而a∈FIRSTVT<R>,有ab。由此得到：①由S→<A>得：<>；②由S→<A…得：<FIRSTVT<A>,即：<d,<a,<b,<<；由A→…dA得：dFIRSTVT<A>,即：dd,da,db,d<；③由S→A>得,LASTVT<A>>,即：d>,a>,b>,>>；由A→Sd…得：LASTVT<S>d,即：ad,bd,>d；此外,由#S#得：##；由#FIRSTVT<S>得：#a,#b,#<；由LASTVT<S>#得：d#,a#,b#,>#。最后得到算符優(yōu)先關(guān)系表,見下表。表算符優(yōu)先關(guān)系表由上表可以看出,任何兩個(gè)終結(jié)符之間至少只滿足、、三種優(yōu)先關(guān)系之一,故G[S]為算符優(yōu)先文法?！?為求出句型〔SdSdS的短語、簡單短語、句柄,我們先畫出該句型對應(yīng)的語法樹,如下圖所示。由圖得到：短語：S,SdS,SdSdS,〔SdSdS簡單短語〔即直接短語：S句柄〔即最左直接短語：S素短語：SdS,它同時(shí)也是該句型的最左素短語。圖句型〔SdSdS的語法樹〔3輸入串〔adb#的分析過程見下表。表輸入串〔adb#的分析過程8．對于文法G[S]：S→AS|bA→SA|a〔1列出所有LR〔0項(xiàng)目；〔2列出構(gòu)成文法LR〔0項(xiàng)目集規(guī)族?！博~﹡﹡解答：首先將文法G拓廣為G[S′]：S′→SS→AS|bA→SA|a〔1文法G[S′]的LR〔0項(xiàng)目是：1．S′→·S5．S→AS·9．A→S·A2．S′→S·6．S→·b10．A→SA·3．S→·AS7．S→b·11．A→·a4．S→A·S8．A→·SA12．A→a·〔2用ε-CLOSURE〔閉包辦法構(gòu)造文法G′的LR〔0項(xiàng)目集規(guī)族如下：I0：1．S′→·SI3：9．A→S·AI6：12．A→a·3．S→·AS8．A→·SAI7：7．S→b·8．A→·SA3．S→·AS11．A→·a6．S→·b6．S→·b11．A→·aI1：2．S′→S·I4：10.A→SA·9．A→S·A4.S→A·S8．A→·SA3.S→·AS11．A→·a6.S→·b3.S→·AS8.A→·SA6.S→·b11.A→·aI2：4．S→A·SI5：5．S→AS·3．S→·AS9．A→S·A6．S→·b8．A→·SA8．A→·SA11．A→·a11．A→·a3．S→·AS6．S→·b注意：I1中的S′→S·和A→·SA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；,而I4中的A→SA和A→A·S則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；I5中的S→AS·和A→S·A則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法G′的LR〔0規(guī)族。9．有文法G[S]S→a|∧|〔TT→T,S|S該文法是否是LL〔1文法,若不是,請進(jìn)行改寫。并給出它的分析表?！博~﹡﹡解答：不是。T→ST'T'→T,S|SFIRST<S>=FIRST<T>={a,∧,〔}FIRST<T'>={,,ε}FOLLOW<S>={#,,,>}FOLLOW<T'>=FOLLOW<T>={}分析表如下：10．有文法G[S]〔1S→A〔2S→B〔3A→aAb〔4A→c〔5B→aBb〔6B→d試構(gòu)造相應(yīng)的LR〔0項(xiàng)目集規(guī)族及相應(yīng)的分析表。〔﹡﹡﹡解答：11.已知文法G[S],其產(chǎn)生式如下：

S→<L>|a

L→L,S|S從G[S]中消除左遞歸,并為之構(gòu)造一個(gè)非遞歸預(yù)測分析器LL<1>分析表。請說明在句子<a,<a,a>>上的分析器的動作?！博~﹡﹡答：將所給文法消除左遞歸得G'：S→<L>|aL→SL'L'→,SL'|ε實(shí)現(xiàn)預(yù)測分析器的不含遞歸調(diào)用的一種有效方法是使用一分析表和一個(gè)棧進(jìn)行聯(lián)合控制,下面構(gòu)造預(yù)測分析表：根據(jù)文法G'有FIRST<s>={<,a>FOLLOW<S>={>,',',$}FIRST<L>={<,a>FOLLOW<L>={>}FIRST<L’>={','}FOLLOW<L’>={>}按以上結(jié)果,構(gòu)造預(yù)測分析表M如下：文法G’是LL<1>的,因?yàn)樗腖L<1>分析表不含多重定義入口。預(yù)測分析器對輸入符號串<a,<a,a>>做出的分析動作如下：12.證明下面文法是SLR<1>文法,并構(gòu)造其SLR分析表。E→E+T|TT→TF|FF→F*|a|b〔﹡﹡﹡答：該文法的拓廣文法G'為<0>E'→E<1>E→E+T<2>E→T<3>T→TF<4>T→F<5>F→F*<6>F→a<7>F→b其LR<0>項(xiàng)目集規(guī)族和goto函數(shù)<識別活前綴的DFA>如下:I0={E'→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·F*,F→·a,F→·b}I1