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