編譯原理陳意云-課后答案2

1、2021/3/111編譯原理習(xí)題課編譯原理習(xí)題課(2)欒 俊9/1/20212021/3/112 考慮文法S - (L)|aL - L,S|S(a) 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析樹(b) 為(a)的兩個句子構(gòu)造最左推導(dǎo)(c) 為(a)的兩個句子構(gòu)造最右推導(dǎo)(d) 這個文法產(chǎn)生的語言是什么2021/3/113S =(L)=(L,S) =(S,S)=(a,S)=(a,(L)=(a,(L,S)=(a,(S,S)=(a,(a,S)=(a,(a,a)S( L )L , SSa( L ) L , SSaaS =(L)=(L,S) =(L,(L)=(L,(L,S)=(L,(L

2、,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)2021/3/114S( L )L , SSaS =(L)=(L,S) =(S,S)=(a,S)=(a,(L)=(a,(L,S)=(a,(S,S)=(a,(L),S)=(a,(L,S),S) =(a,(S,S),S)=(a,(a,S),S)=(a,(a,a),S)=(a,(a,a),(L)=(a,(a,a),(L,S)=(a,(a,a),(S,S)=(a,(a,a),(a,S)=(a,(a,a),(a,a)( L )L , S( L )L , SSaa( L )L , SSaaSS =(L)=(L,S) =(L,(L

3、)=(L,(L,S)=(L,(L,(L)=(L,(L,(L,S)=(L,(L,(L,a)=(L,(L,(S,a)=(L,(L,(a,a)=(L,(S,(a,a)=(L,(L),(a,a)=(L,(L,S),(a,a)=(L,(L,a),(a,a)=(L,(S,a),(a,a)=(L,(a,a),(a,a)=(S,(a,a),(a,a)=(a,(a,a),(a,a)2021/3/115 描述的語言：括號匹配的串，串中的各項由”,”隔開，項可以是括號匹配的子串或a2021/3/116 考慮文法S - aSbS|bSaS|(a) 為句子abab構(gòu)造兩個不同的最左推導(dǎo)，以說明此文法二義(b) 為aba

4、b構(gòu)造對應(yīng)的最右推導(dǎo)(c) 為abab構(gòu)造對應(yīng)的分析樹(d) 這個文法產(chǎn)生的語言是什么2021/3/117 (1) S=aSbS=abS=abaSbS=ababS=abab(2) S=aSbS=abSaSbS=abaSbS=ababS=abab S=aSbS=aSb=abSaSb= abSab =abab (2)Sa S b Sa S b SSa S b Sb S a S(1)(2)描述的語言是a,b數(shù)目相等的串2021/3/118 文法R-R|R | RR | R* | (R) | a | b產(chǎn)生字母表(a, b)上所有不含的正規(guī)式該文法是二義的(a) 證明該文法產(chǎn)生字母表a,b上的所有正規(guī)

5、式(b) 為該文法寫一個等價的非二義文法。(c) 按照上面的兩個文法構(gòu)造ab|b*a的分析樹2021/3/119證明該文法產(chǎn)生字母表a,b上的所有正規(guī)式證明：1）該文法產(chǎn)生的串是字母表a,b上的正規(guī)式R-a和R-b產(chǎn)生a,b,而a,b是a,b上的符號，因此是正規(guī)式。若R1，R2產(chǎn)生正規(guī)式，則：R-R1R2產(chǎn)生正規(guī)式 R-R1|R2產(chǎn)生正規(guī)式| R-R1* 產(chǎn)生正規(guī)式* R-(R1)產(chǎn)生正規(guī)式 () 2)字母表a,b上的所有正規(guī)式都可由此文法產(chǎn)生字母表a,b上的任一正規(guī)式(其中,為正規(guī)式)必為以下形式之一：，可由R-RR產(chǎn)生|，可由R-R|R產(chǎn)生*，可由R-R*產(chǎn)生 ()，可由R-(R)產(chǎn)生 a

6、,可由R-a產(chǎn)生 b,可由R-b產(chǎn)生因而，該文法產(chǎn)生字母表a,b上的所有正規(guī)式2021/3/1110 該文法沒有體現(xiàn)運算符 |、*、() 、并置的優(yōu)先級，因而是二義的。R=R|R= a|R =a|R*=a|b*R=R*=R|R*=a|R*=a|b* E - E|T | TT - TF | FF - F* | (E) | a | bE=E|T=E|F=E|F*=E|b*=T|b*=F|b*=a|b*2021/3/1111 二義的 非二義的RR | RR RabR RaR *bRR RaR *R | RbR RbaEE | TT FTT FFabFF *ba2021/3/1112 下面的條件語句文

7、法stmt-if expr then stmt | matched_stmtmatched_stmt - if expr then matched_stmt else stmt | other試圖消除懸空else的二義性。請證明此文法仍是二義的。2021/3/1113 由于matched_stmt不能保證then和else的配對，因而存在二義性 句型if expr then if expr then matched_stmt else if expr then matched_stmt else stmt存在兩個不同的最左推導(dǎo) 期望的是： if expr then if expr then m

8、atched_stmt else if expr then matched_stmt else stmt2021/3/1114 一種推導(dǎo)，和期望的不一樣 stmt= matched_stmt= if expr then matched_stmt else stmt= if expr then if expr then matched_stmt else stmt else stmt= if expr then if expr then matched_stmt else if expr then stmt else stmt= if expr then if expr then matched

9、_stmt else if expr then matched_stmt else stmt if expr then if expr then matched_stmt else if expr then matched_stmt else stmt2021/3/1115 另一種推導(dǎo) stmt = if expr then stmt = if expr then matched_stmt = if expr then if expr then matched_stmt else stmt = if expr then if expr then matched_stmt else matche

10、d_stmt = if expr then if expr then matched_stmt else if expr then matched_stmt else stmt if expr then if expr then matched_stmt else if expr then matched_stmt else stmt2021/3/1116 消除3.1的左遞歸2021/3/1117 S - (L)|aL - L,S|S 只有直接左遞歸S - (L)|aL - SLL- ,SL|2021/3/1118 構(gòu)造下面文法的LL(1)分析表D - TLT - int|realL - id

11、RR - ,idR|2021/3/1119 先計算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $2021/3/1120intrealid,$DD - TLD - TLTT - intT - realLL - idRRR - ,idRR - 2021/3/1121 下面文法是否LL(1)文法？說明理由S - AB|PQxA - xyB - bcP - dP| Q - aQ|2021/3/1122 不是LL

12、(1)文法 LL(1)文法：對于產(chǎn)生式A-|*(1)( )( )(2)( )( )FIRSTFIRSTFIRSTFOLLOW 若，那么 本題中，F(xiàn)IRST(AB)=x, FIRST(PQx)=d,a,x不滿足條件(1)2021/3/1123 (a) 用3.1的文法構(gòu)造(a,(a,a)的最右推導(dǎo)，說出每個右句型的句柄 (b) 給出對應(yīng)(a)的最右推導(dǎo)的移進-歸約分析器的步驟 (c) 對照(b)的移進-歸約，給出自下而上構(gòu)造分析樹的步驟。2021/3/1124S =(L)=(L,S) =(L,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(

13、a,a)棧輸入動作$(a,(a,a)$移進$(a,(a,a)$移進$(a,(a,a)$歸約:S-a$(S(a,a)$歸約:L-S$(L,(a,a)$移進$(L,(a,a)$移進$(L,(a,a)$移進$(L,(a,a)$歸約:S-a2021/3/1125S =(L)=(L,S) =(L,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)棧輸入動作$(L,(S,a)$歸約:L-S$(L,(L,a)$移進$(L,(L,a)$移進$(L,(L,a)$歸約:S-a$(L,(L,S)$歸約:L-L,S$(L,(L)$移進$(L,(L)$歸約

14、:S-(L)$(L,S)$歸約:L-L,S2021/3/1126S =(L)=(L,S) =(L,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)棧輸入動作$(L)$移進$(L)$歸約:S-(L)$S$接受2021/3/1127棧輸入動作$(a,(a,a)$移進$(a,(a,a)$移進$(a,(a,a)$歸約:S-a$(S(a,a)$歸約:L-S$(L,(a,a)$移進$(L,(a,a)$移進$(L,(a,a)$移進$(L,(a,a)$歸約:S-a( a , ( a , a ) ) $SLS2021/3/1128棧輸入動作$(L,(S,a)$歸約:L-S$(L