【正文】 (B)={ )， ( } LASTVT(S)={ i， +， *， ( } LASTVT(A)={ +， *， ( } LASTVT(B)={ *， ( } 優(yōu)先關(guān)系表 : (3 分 ) i + ( ) * i + ( ) * 優(yōu)先函數(shù) : (3 分 ) i + ( ) * f 2 6 6 1 6 g 1 4 6 6 1 六、設(shè)某語(yǔ)言的 dowhile 語(yǔ)句的語(yǔ)法形式為 (9 分 ) S ? do S(1) While E 其語(yǔ)義解釋為： 真 假 S(1)的代碼 E 的代碼 E T F ( E ) E + T F i T T * F 針對(duì)自下而上的語(yǔ)法分析器，按如下要求構(gòu)造該語(yǔ)句的翻譯模式： (1) 寫(xiě)出適合語(yǔ)法制導(dǎo)翻譯的產(chǎn)生式； (2) 寫(xiě)出每個(gè)產(chǎn)生式對(duì)應(yīng)的語(yǔ)義動(dòng) 作。 4． (6 分 )運(yùn)行時(shí)的 DISPLAY 表的內(nèi)容是什么？它的作用是什么？ 答： DISPLAY 表是 嵌套層次顯示表 。 正確 每個(gè)文法都能改寫(xiě)為 LL(1)文法。最左素短語(yǔ)則指處于句型最左邊的那個(gè)素短語(yǔ)。 （ 13） A、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度慢 B、解釋器參與運(yùn)行控制，程序執(zhí)行的速度慢 C、解釋器參與運(yùn)行控制，程序執(zhí)行的速度快 D、解釋器不參與運(yùn)行控制，程序執(zhí)行的速度快 （ 14） A、詞法分析 B、語(yǔ)法分析 C、中間代碼生成 D、語(yǔ)義分析 (15) A、字符串 B、單詞 C、標(biāo)識(shí)符 D、語(yǔ)句 (16) A、自左至右 B、自頂向下 C、自底向上 D、自右至左 (17) A、詞法分析 B、語(yǔ)法分析 C、語(yǔ)義分析 D、目標(biāo)代碼生成 例題 5： 假設(shè)某程序語(yǔ)言的文法如下： S→ a | b | (T) T→ TdS | S 其中， VT={a,b,d,(,)}， VN={S,T}， S是開(kāi)始符號(hào)。FC} E→i {ETC)} EA→E(1) {BACKPATCH(E(1) (6 分 ) 解： (1) E0→E(1) E→E0E(2) EA→E(1) E→EAE(2) E→i (3 分 ) (2) E→E(1) {BACKPATCH(E(1) 應(yīng)著重考慮的問(wèn)題： (1)如何使生成的目標(biāo)代碼較短； (2)如何充分利用寄存器，以減少訪(fǎng)問(wèn)內(nèi)存次數(shù)； (3)如何充分利用指僅系統(tǒng)的的特點(diǎn)。 4．短語(yǔ)－－令 G是一個(gè)文法。 j: ?0?j{n0 +=1。 S ? D C D ? a D b | a b C ? C c | c 解：語(yǔ)法制導(dǎo)的定義如下： S ? D C if ? then print (“error”) D ? a b := 1 D ? a D1 b := + 1 C ? c := 1 C ? C1 c := + 1 2. 給出文法 G（ L）的翻 譯模式，它 分別 計(jì)算字符串 中 0 與 1 的 個(gè)數(shù) 。 2) 構(gòu)造識(shí)別該語(yǔ)言的 DFA。 12. 一個(gè)過(guò)程相應(yīng)的 DISPLAY 表的內(nèi)容為 （ 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址。 4．語(yǔ)法分析最常用的兩類(lèi)方法是（ 自 頂向 下 ） 和 （ 自 底向 上 ）分析法。 5．一個(gè)上下文無(wú)關(guān)文法所含的四個(gè)組成部分是（ 一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)、一個(gè)開(kāi)始符號(hào)、一組產(chǎn)生式 ）。 ） 13. 符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如 （ 類(lèi)型、種屬、所占單元大小、地址 ）等等。 2． 生成語(yǔ)言 L（ G）＝ {apbmcpanbn | p=0, m=1, n=2}的文法 G 是什么？它是 chomsky 的哪型文法。 （要求 ANTLR 代碼） S→ | L L→ BL L→ε B→ 0|1 Grammer L01 members {int n0。} |?1? j{n1 +=1。 S劃文法的開(kāi)始符號(hào)，假定αβδ是文法 G的一個(gè)句型，如果有 Sα Aδ且 AB，則稱(chēng)β是句型αβ相對(duì)非終結(jié)符 A的短語(yǔ)。 計(jì)算題： 寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以 0 開(kāi)頭。FC， NXQ)； E0TC， NXQ)； E0TC：＝ NXQ； E 考查該文法，稱(chēng)句型 (Sd(T)db)是 S的一個(gè) A 。 最左推導(dǎo)是指任何一步推導(dǎo)過(guò)程σ→β，都是對(duì)σ中的最左非終結(jié)符進(jìn)行替換。 不 正確 對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動(dòng)態(tài)貯存分配策略。 每當(dāng)進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表 i，則它的 diaplay表含有 i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層 、直接外層、 …、直至最外層 (主程序， 0 層 )等每層過(guò)程的最新活動(dòng)記錄的起始地址。 答： (1). 適合語(yǔ)法制導(dǎo)翻譯的文法 (3分 ) G(S): R? do U?R S(1) While S?U E (2). (6分 ) R? do { :=NXQ } U?R S(1) While { :=。 解： 先計(jì)算各個(gè)產(chǎn)生式的 Predict 集： Predict (A iB*e)={ i }。 H a(T + S) T + S (S) H a 簡(jiǎn)單短語(yǔ)４個(gè)： a , T + S , H , (S) 句柄： a。 解答： 1）句型（ bcScT）的推導(dǎo)樹(shù)如圖 ： 圖 句型（ bcScT）的推導(dǎo)樹(shù) 短語(yǔ)： b。 e） S是開(kāi)始符號(hào)， ∴ 句柄不存在 。 2022 年編譯原理試題 1．（ 10 分）處于 /* 和 */之間的串構(gòu)成注解，注解中間沒(méi)有 */。 如句子 (a, (a, a) )，第一小題的輸出是 2，第二小題的輸出是 1 2 2。而第二個(gè)表達(dá)式執(zhí)行的是 (?yz.(x + y) + z) 3 5，不會(huì)出現(xiàn)參數(shù)個(gè)數(shù)不足的情況。 offset := offset + } T ? integer { := integer。 := + } T ? integer { := integer。 S ? D C D ? a D b | a b C ? C c | c (b) 語(yǔ)句的文法如下： S ? id := E | if E then S | while E do S | begin S 。 { := }S2 end S ? break{if not then print(“error”) } （ 15 分） (a) 用正規(guī)式表示字母 表 {a, b}上， a 不會(huì)相鄰的所有串。（在這兩個(gè)文件中，第 1 行都是函數(shù) func 的原型，第 2 行都是函數(shù) func 的定義，函數(shù)體為空。 E ? while E1 do E2 := max(, ) +1。它的類(lèi)型和函數(shù)原型中聲明的類(lèi)型不相同，所以編譯器會(huì)報(bào)告錯(cuò)誤。 s ) 。 2022 年編譯原理試題參考答案 1．語(yǔ)言 L 的正規(guī)式是： (a|b)*(aa|bb) 接受該語(yǔ)言的最簡(jiǎn) DFA 是： 2． S? ? S S ? M a | b M c | d c | b d a M ? d 因?yàn)?a 是 M 的后繼符號(hào)之一，因此在上面最右邊一個(gè)項(xiàng)目集中有移進(jìn) ?歸約沖突。 0*10*10*10* ⑶ 集合 {01， 1}。 (0|1)*111 ⑴ 試寫(xiě)出非負(fù)整數(shù)集的正則表達(dá)式。 S S ? s | ( SL ) 6．（ 1） （ 2） b := 1 b := 2 if w = x goto L2 （ 1） e := b goto L2 （ 2） L1: goto L3 （ 3） L2: c := 3 b := 4 c := 6 （ 4） L3: if y = z goto L4 （ 5） goto L5 （ 6） L4: g := g + 1 h := 8 goto L1 （ 7） L5: h := 9 （ 8） （ 3）結(jié)點(diǎn) 7 和 3 構(gòu)成一個(gè)循環(huán)，其中 5 是入口結(jié)點(diǎn)。 ( s 。 2022 年編譯原理試題 1．（ 20 分）寫(xiě)出字母表 ? = {a, b}上語(yǔ)言 L = {w | w 的最后兩個(gè)字母是 aa 或 bb}的正規(guī)式，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn) DFA。 E ? E1 + E2 := max(, )。 int func(double)。 （ 10 分）構(gòu)造下面文法的 LL(1)分析表。 2022 年編譯原理和技術(shù)試題參考答案 1． (a) 語(yǔ)言 { ( ), (( ) ( )), ((( ))), ( ) ( ) ( ) ( ) ( )}是正規(guī)語(yǔ)言，因?yàn)樵撜Z(yǔ)言只包括有限個(gè)句子，它可以用正規(guī)式定義如下： ( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( ) (b) 我們分析 正規(guī)式 ( (? | 0) 1* )*表示的語(yǔ)言。 := 8 } 1．（ 15 分） (a) 字母表 ? = { ( , ) }上的語(yǔ)言 { ( ), (( )( )), ((( ))), ( )( )( )( )( )}是不是正規(guī)語(yǔ)言？為什么？ (b) 正規(guī)式 (0 | 1)* 和 ( (? | 0) 1* )*是否等價(jià)，說(shuō)明理由。 := 8 } 使用了變量 offset。 2022 年編譯原理試題 1 2 4 start 5 2 others others / * * * / 1．（ 20 分）寫(xiě)出字母表 ? = {a, b}上語(yǔ)言 L = {w | w 中 a 的個(gè)數(shù)是偶數(shù) }的正規(guī)式，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn) DFA。如何利用它通過(guò)盡量少的工作來(lái)得到 B 機(jī)器的 C 語(yǔ)言編譯器 CCB。 2．（ 10 分）為語(yǔ)言 L ＝ {ambn | 0 ? m ? 2n}（即 a 的個(gè)數(shù)不超過(guò) b 的個(gè)數(shù)的兩倍） 寫(xiě)一個(gè) LR（