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