1、1 / 10編編 譯譯 原原 理理課程學習研討題課程學習研討題上海大學計算機學院編譯原理課程組2016 年 3 月2 / 10第一次研討、第一批（第第一次研討、第一批（第 3 周）周）1討論： （1）編譯方法與解釋方法的主要區別（2）編譯程序組合中分端(前端/后端)和分遍(單遍/多遍)的作用（3）編譯程序生成方法中自編譯與自展的含義2編寫 PL/0 程序,功能：輸入正整數 n，求 sum = 1! + 2 ! + . + n!3擴充 PL/0 語言文法的定義，增加實數類型和數組類型。例：Var i:integer; r:real; A:array1.10of real; Ai:=r;4設有下列

2、文法 G1S和 G2S：1)指出文法的類型 2）證明兩者等價 G1S：SaAb | bBa AaA | a BBb | b G2S：SaA | bB AaA | aC BbB | bD Cb Da5. 構造一個文法，使其語言是奇數集，且每個奇數不以 0 開頭。6.文法 GS 的一個句子 abbba 的語法樹如下圖: S A B a A b b B a b 1) GS可能包含哪些產生式? 2) 給出句子 abbba 的規范推導。3) 求出句子 abbba 的句柄。7設有上下文無關文法 GS：SaAb AaB Aa BbA Bb試構造與 GS等價的正規文法。8 實驗一 識別標識符(A)3 / 10

3、第一次研討、第二批（第第一次研討、第二批（第 4 周）周）1編寫 PL/0 程序，輸入正整數 n、x1、x2、xn，計算：S= xi/i! i=1n。2構造下列語言的文法，并分析比較（1）L1(G)=anbn|n1（2）L2(G)=(ab) n|n1（3）L3(G)=anbm|n,m0（4）L4(G)=anbm|n,m13.定義一個文法，產生表達式 E： 1）含有雙目運算符 +，* 2）+ 的優先級高于* 3）+ 右結合，* 左結合 4）運算對象為標識符 i 5）可用括號改變算符的優先級4擴充 PL/0 語言文法的定義, 增加 for 語句的功能。for 語句的示例如下：for i:= 1 t

4、o 100 do s:=s+i; 5.定義一個文法，產生下列語言： 該語言由 a、b 符號串組成，串中 a 和 b 的個數相同6證明下列文法為二義文法(能否轉換為等價的非二義文法?) G1S：SA AAA AaAb Aab G2S：SaSb SSb Sb 7試寫出 VT0,1，分別滿足下述要求的正則表達式： 所有以 1 開始和 0 結束的符號串。 恰含有 3 個 1 的所有符號所組成的集合。 集合01，1。 所有以 111 結束的符號串。8實驗一 識別標識符(B)4 / 10第二次研討、第一批（第第二次研討、第一批（第 5 周）周）1構造一個 DFA，接受=a，b上由正規式 aa*(a|ba)

5、*b 定義的字符串并給出相應的正規文法。2. 寫出的文法.例如: 有 2 個關系 R ( a,b,c)，S (c,d,e)。以下是簡單查詢語句的樣例： 語句 1: SELECT a, b FROM R WHERE a=15 OR b18;語句 2: SELECT R.a, S.c FROM R , S WHERE R.c=S.c AND R.b=3 分時，機器會給顧客一塊硬糖（只給糖不找錢） 。 1）寫出售后機售糖的正規表達式； 2）構造識別上述正規表達式的最簡 DFA。8. 實驗二 詞法分析(A)5 / 10第二次研討、第二批（第第二次研討、第二批（第 6 周）周）1.給出的文法。例如：有

6、2 個關系 R ( a,b,c)，S (c,d,e)。以下是嵌套查詢語句的樣例：語句：SELECT a,b FROM R WHERE R.c in (SELECT S.c FROM S WHERE d=15);2.構造一個最簡 DFA M，接受=d，.，e， 上的正規式 dd.dd(edd)表示的無符號數的集合。其中d 為 09 的數字。3正規文法（又稱為右線性文法）：文法中每一條產生式 的形式都為 ： AaB 或 Aa。 左線性文法：每一條產生式 的形式都為：ABa 或 Aa。設計一個算法，把給定的左線性文法轉換為等價的右線性文法。4. 構造一個 DFA M,接受 =a,b上滿足下列條件的符

7、號串： 1）以 a 開頭，以 b 結尾； 2）不包含“aba”。5.對一個文法若消除了左遞歸，提取了左公共因子后是否一定為 LL(1)文法？試舉例說明。6已知文法 GE的定義如下：E E + T | TT T * F | FF (E) | i 試構造一組遞歸下降分析子程序，使之識別 GE所產生的語言。7.語言可接受的合法文件名為：device:name.extension，其中device、name、extension 是長度至少為 1 的字符串，而且第一部分（device:）和第三部分（.extension）可缺省。試畫出識別這種文件名的最簡 DFA。8實驗二 詞法分析(B)6 / 10第三

8、次研討、第一批（第第三次研討、第一批（第 7 周）周）1設有文法 GS：SSaF | F FFbP | P Pc | d(1) 構造 GS的算符優先關系表(2) 分別給出 cadbdac# 和 dbcabc# 的分析過程2已知文法 GP的定義如下：P begin D S endD D; d | dS S; s | s試構造一組遞歸下降分析程序，使之識別 GP所產生的語言。3設有文法 GS：Sa B c | b A B Aa A b | b Bb | (1) 證明 GS是一個 LL(1)文法。 (2) 構造 GS的預測分析表。 (3) 給出 baabbb 的分析過程。4設有文法 GS: (0)

9、SS (1) SSaA (2) Sa (3) AAbS (4) Ab(1) 構造 GS的 LR(0)項目規范族 C=I0,I1,In。(2) 構造 SLR(1)分析表，判斷 GS的文法類型。(3) 寫出句子 aabba 的分析過程。5設采用自底向上的移進-歸約語法分析，屬性文法 GA如下： A a B print “0”A c print “1”B A b print “2”(1) 輸入為 aacbb 時，打印的符號串是什么？(2) 寫出 aacbb 的語法制導分析過程。6設有文法 GE：EE+T | ET | TTT*F | TF | FFnum | bool |（E）設計 GE的語義子程序

10、，對表達式進行類型檢查并翻譯為逆波蘭式。7設有文法 Gnumber：number numnum numdigit num | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7| 8 | 9設計 Gnumber的語義子程序，計算實數 number 的值。8實驗三 語法分析(A)7 / 10第三次研討、第二批（第第三次研討、第二批（第 8 周）周） 1設有文法 GS：SA AA m D n | B Ba | m S n DS | DbS (1) 構造 GS的算符優先關系表。(2) 給出 aman# 和 maban# 的分析過程。(3) 由(2)說明算符優先分析算法的

11、局限性。 2設有文法 GE：EETE |（E）| i T + | * (1) 證明 GE是一個非 LL(1)文法。 (2) 把 GE等價改寫為 LL(1)文法 G1E，并構造其預測分析表。 (3) 給出句子（i+i）* (i+i) 的分析過程。3 設有文法 GS: S Ab | Ba A aA | a B a 將其改造成 LL(1)文法，并編寫遞歸下降分析程序，使之識別 GS所產生的語言。4設有文法 GS: (0) SS (1) SaS (2) SbA (3) AdA (4) Ad(1) 構造 GS的 LR(0)項目規范族 C=I0,I1,In,(2) 說明 GS屬于哪一種 LR 文法，構造相

12、應的 LR 分析表(3) 寫出句子 aabbd 的分析過程。5寫出表達式(ab*c)/(ab)d 的四元式，逆波蘭式及三元式序列。6條件語句的語法簡寫為：S iSeS | iS | S ; S | a其中: i 代表 if，e 代表 else，a 代表賦值語句。如果規定：(1) else 與其左邊最近的 if 結合；(2) ；服從左結合。請給出文法中 i、e 和；的優先關系，然后構造出無二義的 LR 分析表，并對輸入串 iiaea 寫出分析過程。7設采用自底向上的移進-歸約語法分析，屬性文法 GE如下：E E + T print “0”E T print “1”T T * F print “2

13、”T F print “3”F (E) print “4”F i print “5”寫出 i*(i+i*i)的語法制導分析過程，打印的符號串是什么？8實驗三 語法分析(B)8 / 10第四次研討、第一批（第第四次研討、第一批（第 9 周）周）1以下是簡單表達式（只含有加、減運算）計算的一個屬性文法 G（E）:E TR R.in := T.val ; E.val := R.val R +TR1 R1.in := R.in + T.val ; R.val := R1.val R -TR1 R1.in := R.in - T.val ; R.val := R1.val R R.val := R.in

14、 T num T.val := lexval(num) 其中：lexval(num)表示從詞法分析程序得到的常數的值。試給出表達式 8-3+6 的語法樹和相應的帶標注語法分析樹。2教材 P224 第 4 題。3寫出下列語句的三位置中間代碼（四元式序列）： while (AC or B=1) then C:=C+1 else while (AC goto L2（6） B=B+19 / 10（7） Goto L4（8） L2: write ( B )2）找出題 1）流圖中的回邊與循環7把下列中間代碼序列劃分為基本塊并作出其流圖1）(1) read(x)(2) read(y)(3) A := 10(

15、4) if x0 or s s) then s:=s+i; i:=i-1; end; 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 1 1 0 0 3 0 0 1 0 0 0 4 0 0 0 0 1 1 5 0 1 0 0 0 1 6 0 0 0 1 0 010 / 105設有基本塊D:=A-C E:=A*C F:=D*E S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q K:=G*5 L:=K+J M:=L 假設基本塊出口時只有 M 還被引用，寫出 DAG 優化后的四元序列。6寫出對下列四元式進行優化后的結果。for (k=1 ; k=100; k+) m=i+10*k; n=j+10*k；(1) (=,1,-,k