【正文】 的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2…AR，那么A174。A1A2…AR一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)生的句子。4．LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。5．語(yǔ)言和文法文法就是語(yǔ)言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN 是非空有窮集合，稱為非終結(jié)符號(hào)集合；VT 是非空有窮集合，稱為終結(jié)符號(hào)集合；P是產(chǎn)生式的集合(非空)；S是開始符號(hào)(或識(shí)別符號(hào))。這里，VN∩VT=198。，SVN。V=VN∪VT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)={x| S222。*x，其中S為文法開始符號(hào)，且 }簡(jiǎn)單的說，文法描述的語(yǔ)言是該文法一切句子的集合。四、簡(jiǎn)答題(共4小題，每小題5分，共20分)1．編譯程序和高級(jí)語(yǔ)言有什么區(qū)別? 用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序（這個(gè)過程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語(yǔ)言編寫的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語(yǔ)句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的對(duì)話，隨時(shí)可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過程進(jìn)行很快，在過程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRAN語(yǔ)言就是編譯型高級(jí)語(yǔ)言。2．編譯程序的工作分為那幾個(gè)階段? 詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。3．簡(jiǎn)述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。4．簡(jiǎn)述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對(duì)程序代碼進(jìn)行一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。五、綜合應(yīng)用題(共3小題，每小題10分，共30分)1．證明下述文法G：S174。aSbS|aS|d是二義性文法。解：一個(gè)文法，如果存在某個(gè)句子有不只一棵語(yǔ)法分析樹與之對(duì)應(yīng)，那么稱這個(gè)文法是二義性文法。句子aadbd有兩棵語(yǔ)法樹。如下圖：dSSabSSadSaSSabSdd(1) (2)由此可知，S174。aSbS|aS|d定義的文法是二義性文法。ASBbBSab2．對(duì)于文法G[S]：S174。AB，A174。Aa|bB，B174。a|Sb求句型baSb的全部短語(yǔ)、直接短語(yǔ)和句柄？句型baSb的語(yǔ)法樹如圖五(2)所示。解：baSb為句型baSb的相對(duì)于S的短語(yǔ)，ba為句型baSb的相對(duì)于A的短語(yǔ)，Sb為句型baSb的相對(duì)于B的短語(yǔ)，且為直接短語(yǔ)，a為句型baSb的相對(duì)于B的短語(yǔ)，且為直接短語(yǔ)和句柄。3．設(shè)有非確定的有自限動(dòng)機(jī)NFA M=({A，B，C}，{0，1}，d，{A}，{C})，其中：d (A，0)={C} d (A，1)={A，B} d (B，1)={C} d (C，1)={C}。請(qǐng)畫出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。解：狀態(tài)轉(zhuǎn)換距陣為：d01ACA，BB198。CC198。C狀態(tài)轉(zhuǎn)換圖為11011《編譯原理》期末試題（六）編譯原理 樣題【 】1．____型文法也稱為正規(guī)文法?！　　A] 0 [B] 1 [C] 2 [D] 3【 】2．____文法不是LL(1)的?！　? [A] 遞歸 [B] 右遞歸 [C] 2型 [D] 含有公共左因子的【 】3． 文法E→E+E|E*E|i的句子i*i+i*i的不同語(yǔ)法分析樹的總數(shù)為______?！　　A]1 [B]3 [C]5 [D]7【 】4．四元式之間的聯(lián)系是通過 實(shí)現(xiàn)。 [A]臨時(shí)變量 [B]指示器 [C]符號(hào)表 [D]程序變量【 】5．同心集合并可能會(huì)產(chǎn)生的新沖突為 。 [A]二義 [B]移進(jìn)/移進(jìn) [C]移進(jìn)/歸約 [D]歸約/歸約【 】6．代碼優(yōu)化時(shí)所依據(jù)的是 。[A]語(yǔ)法規(guī)則 [B]詞法規(guī)則 [C]等價(jià)變換規(guī)則 [D]語(yǔ)義規(guī)則【 】7．表達(dá)式a(b)*c的逆波蘭表示為 。[A]ab@c* [B]ab@c* [C]ab@ [D]ab@c* （注：@為單目減運(yùn)算符）【 】8．過程的DISPLAY表記錄了 。[A]過程的連接數(shù)據(jù) [B]過程的嵌套層次[C]過程的返回地址 [D]過程的入口地址二 填空題3．對(duì)于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語(yǔ)言相同），則稱文法G1和G2是等價(jià)的。4．對(duì)于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是T ，最左素短語(yǔ)是 T*F。 5．最右推導(dǎo)的逆過程稱為規(guī)范歸約 ，也稱為 最左歸約。6．規(guī)范規(guī)約中的可規(guī)約串是句柄 ，算符優(yōu)先分析中的可規(guī)約串是 最左素短語(yǔ)7．（A∨ B）∧（C∨ 172。D∧ E） 的逆波蘭式是ＡＢ∨ＣＤ172。Ｅ∧∨∧。8．在屬性文法中文法符號(hào)的兩種屬性分別稱為繼承屬性 和綜合屬性（次序可換）。9．符號(hào)表的每一項(xiàng)是由名字欄和 地址分配 兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是 地址分配 的依據(jù)。 10．一個(gè)過程的DISPLAY表的內(nèi)容是它的　直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址三 有窮自動(dòng)機(jī)M接受字母表S＝{0,1}上所有滿足下述條件的串：每個(gè)1都有0直接跟在右邊。構(gòu)造一個(gè)最小的DFA M及和M等價(jià)的正規(guī)式?！尽俊尽克?證明正規(guī)式(ab)*a 與正規(guī)式a(ba)*等價(jià) （用構(gòu)造他們的最小的DFA方法）?！敬鸢福骸?五 寫一個(gè)文法，使其語(yǔ)言是：L ＝ { 1n0m1m0n | m,n≥0 }【】【】五 文法G：S → 1S0 | AA → 0A1 | ε六 對(duì)文法G[S] 　 S → aSb | PP → bPc | bQcQ → Qa | a(1) 它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表(2) 文法G[S]消除左遞歸、提取左公因子后是否是LL（1）文法？請(qǐng)證實(shí)?！尽俊尽縖S]的FIRSTVT集和LASTVT集：FIERSTVT（S）={a,b} LASTBVT（S）={b,c} FIERSTVT(P)= LASTBVT（P）={c} FIERSTVT(Q)={a} LASTBVT（Q）={a}構(gòu)造優(yōu)先關(guān)系表為： a b c a b c 由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了aa 和aa以及bb和bb，所以該文法不是算符優(yōu)先文法。2. 消除左遞歸和提取左公因子后的文法為：S → aSb | PP → bP’P’→ Pc |QcQ → aQ’Q’→ aQ’|ε求具有相同左部的兩個(gè)產(chǎn)生式的Select集的交集：Select(S→aSb)∩Select(S→P) = {a}∩First(P) = {a}∩ = ФSelect(P’→Pc)∩Select(P’→Qc) = First(P)∩First(Q)=∩{a}= ФSelect(Q’→aQ’)∩Select(Q’→ε) = {a}∩Follow(Q) = {a}∩{c} = Ф所以修改后的文法是LL（1）文法。七 已知文法G為:（0） S′→ S（1） S → aAd（2） S → bAc（3） S → aec（4） S → bed（5） A → e 試構(gòu)造它的LR（1）項(xiàng)目集、可歸前綴圖和LR（1）分析表。【】【答案：】ecAdI0:S′→ S , S→ aAd , S→ bAc , S→ aec , S→ bed , I2： S→a Ad , S→a ec , A→ e , d aI1：S′→S , SI3: S→b Ac , S→b ed , A→ e , cbI6: S→bAc, AI7：S→be d , A→e , cI11：S→bed , dI10：S→bAc , I4：S→aA d , I5：S→ae c , 　 A→e , deI8：S→aAd , I9：S→aec , c構(gòu)造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1AS3bedc1S gotoaS2 action 0狀態(tài)八 已知源程序如下： prod:=0。 i:=1。 while i≤20 do beginprod:=prod+a[i]*b[i]。i:=i+1 end。試按語(yǔ)法制導(dǎo)翻譯法將源程序翻譯成四元式序列（設(shè)A是數(shù)組a的起始地址，B是數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié)）?！敬鸢福骸烤?設(shè)有以下程序段 procedure P(x,y,z) begin Y:=y*3。 Z:=X+z。 end。 begin a:=5。 b:=2。 p(a*b,a,a)。 print(a)。 end若參數(shù)傳遞的方法分別為（1）傳值、（2）傳地址、（3）傳名，試問結(jié)果分別什么？【】【】十 （1）傳值 5； （2）傳地址 25； （3）傳名 45十 對(duì)以下文法，請(qǐng)寫出關(guān)于括號(hào)嵌套層數(shù)的屬性文法。(為S,L引入屬性h,用來記錄輸出配對(duì)的括號(hào)個(gè)數(shù))文法規(guī)則語(yǔ) 義 規(guī) 則S→(T)S→iT→T,ST→S答案： 十一 對(duì)PL/0語(yǔ)言的while語(yǔ)句 while 條件B DO 語(yǔ)句S 的編譯程序，請(qǐng)?jiān)诳杖碧幪羁?，完成該語(yǔ)句的編譯算法：switch (SYM) { ……case WHILESYM: CX1=CX 。GetSym()。 CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX)。 CX2=CX 。GEN(JPC,0,0)。 if (SYM==DOSYM) GetSym() 。