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

1、編譯原理習題課(2, 23.02.2021,23.02.2021,2,3.1,考慮文法S - (L)|aL - L,S|S(a) 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析樹(b) 為(a)的兩個句子構(gòu)造最左推導(c) 為(a)的兩個句子構(gòu)造最右推導(d) 這個文法產(chǎn)生的語言是什么,23.02.2021,3,3.1 (續(xù)) - (a,(a,a,S =(L) =(L,S) =(S,S) =(a,S) =(a,(L) =(a,(L,S) =(a,(S,S)=(a,(a,S) =(a,(a,a,S =(L) =(L,S) =(L,(L) =(L,(L,S) =(L,(L,a) =(

2、L,(S,a) =(L,(a,a)=(S,(a,a) =(a,(a,a,23.02.2021,4,3.1 (續(xù)) - (a,(a,a),(a,a,S,L,L , S,S,a,S =(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,S,S =(L) =

3、(L,S) =(L,(L) =(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,23.02.2021,5,3.1 (續(xù),描述的語言：括號匹配的串，串中的各項由”,”隔開，項可以是括號匹配的子串或a,23.02.2021,6,3.2,考慮文法S - aSbS|bS

4、aS|(a) 為句子abab構(gòu)造兩個不同的最左推導，以說明此文法二義(b) 為abab構(gòu)造對應的最右推導(c) 為abab構(gòu)造對應的分析樹(d) 這個文法產(chǎn)生的語言是什么,23.02.2021,7,3.2 (續(xù),1) S=aSbS=abS=abaSbS=ababS=abab(2) S=aSbS=abSaSbS=abaSbS=ababS=abab S=aSbS=aSb=abSaSb= abSab =abab (2,S,a S b S,a S b S,S,a S b S,b S a S,1,2,描述的語言是a,b數(shù)目相等的串,23.02.2021,8,3.4,文法R-R|R | RR | R* |

5、 (R) | a | b產(chǎn)生字母表(a, b)上所有不含的正規(guī)式該文法是二義的(a) 證明該文法產(chǎn)生字母表a,b上的所有正規(guī)式(b) 為該文法寫一個等價的非二義文法。(c) 按照上面的兩個文法構(gòu)造ab|b*a的分析樹,23.02.2021,9,3.4 (續(xù),證明該文法產(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)生字母表

6、a,b上的任一正規(guī)式(其中,為正規(guī)式)必為以下形式之一：，可由R-RR產(chǎn)生|，可由R-R|R產(chǎn)生*，可由R-R*產(chǎn)生 ()，可由R-(R)產(chǎn)生 a,可由R-a產(chǎn)生 b,可由R-b產(chǎn)生因而，該文法產(chǎn)生字母表a,b上的所有正規(guī)式,23.02.2021,10,3.4 (續(xù),該文法沒有體現(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 | b E=E|T=E|F=E|F*=E|b*=T|b*=F|b*=a|b,23.02.2021,11,3

7、.4 (續(xù)) - ab|b*a,二義的 非二義的,R,R | R,R R,a,b,R R,a,R,b,R,R R,a,R,R | R,b,R R,b,a,E,E | T,T F,T,T F,F,a,b,F,F,b,a,23.02.2021,12,3.5,下面的條件語句文法 stmt-if expr then stmt | matched_stmt matched_stmt - if expr then matched_stmt else stmt | other試圖消除懸空else的二義性。請證明此文法仍是二義的,23.02.2021,13,3.5 (續(xù),由于matched_stmt不能保證t

8、hen和else的配對，因而存在二義性 句型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 stmt,23.02.2021,14,3.5 (續(xù),一種推導，和期望的不一樣 stmt = matched_stmt= if expr then matched_stmt else stmt= if expr t

9、hen 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_stmt else if expr then matched_stmt else stmt if expr then if expr then matched_stmt else if expr then matched_stmt else stmt,23.02.2021,15,3.

10、5 (續(xù),另一種推導 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 matched_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

11、if expr then matched_stmt else stmt,23.02.2021,16,3.8(a,消除3.1的左遞歸,23.02.2021,17,3.8(a) (續(xù),S - (L)|aL - L,S|S 只有直接左遞歸S - (L)|aL - SLL- ,SL,23.02.2021,18,3.10,構(gòu)造下面文法的LL(1)分析表D - TLT - int|realL - idRR - ,idR,23.02.2021,19,3.10 (續(xù),先計算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,F

12、OLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = ,23.02.2021,20,3.10 (續(xù),23.02.2021,21,3.11,下面文法是否LL(1)文法？說明理由S - AB|PQxA - xyB - bcP - dP| Q - aQ,23.02.2021,22,3.11 (續(xù),不是LL(1)文法 LL(1)文法：對于產(chǎn)生式A-,本題中，F(xiàn)IRST(AB)=x, FIRST(PQx)=d,a,x不滿足條件(1,23.02.2021,23,3.15,a) 用3.1的文法構(gòu)造(a,(a,a)的最右推導，說出每個右句型的句柄 (b) 給出對應

13、(a)的最右推導的移進-歸約分析器的步驟 (c) 對照(b)的移進-歸約，給出自下而上構(gòu)造分析樹的步驟,23.02.2021,24,3.15 (續(xù)) (a) (b,S =(L) =(L,S) =(L,(L) =(L,(L,S) =(L,(L,a) =(L,(S,a) =(L,(a,a)=(S,(a,a) =(a,(a,a,23.02.2021,25,3.15 (續(xù)) (a) (b)續(xù)上表,S =(L) =(L,S) =(L,(L) =(L,(L,S) =(L,(L,a) =(L,(S,a) =(L,(a,a)=(S,(a,a) =(a,(a,a,23.02.2021,26,3.15 (續(xù)) (a) (b)續(xù)上表,S =(L) =(L,S) =(L,(L) =(L,(L,S