《编译原理陈意云课后答案ppt课件.ppt》由会员分享，可在线阅读，更多相关《编译原理陈意云课后答案ppt课件.ppt（30页珍藏版）》请在三一办公上搜索。
1、编译原理习题课(2),栾 俊12/11/2022,2022/12/11,2,3.1,考虑文法S - (L)|aL - L,S|S(a) 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b) 为(a)的两个句子构造最左推导(c) 为(a)的两个句子构造最右推导(d) 这个文法产生的语言是什么,2022/12/11,3,3.1 (续) - (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)=(L,(S,
2、a)=(L,(a,a)=(S,(a,a)=(a,(a,a),2022/12/11,4,3.1 (续) - (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)=(L,S) =(L,
3、(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),2022/12/11,5,3.1 (续),描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a,2022/12/11,6,3.2,考虑文法S - aSbS|bSaS|(a) 为句子abab构造两个不同的最
4、左推导，以说明此文法二义(b) 为abab构造对应的最右推导(c) 为abab构造对应的分析树(d) 这个文法产生的语言是什么,2022/12/11,7,3.2 (续),(1) S=aSbS=abS=abaSbS=ababS=abab(2) S=aSbS=abSaSbS=abaSbS=ababS=ababS=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数目相等的串,2022/12/11,8,3.4,文法R-R|R | RR | R* | (R) | a | b产生字母
5、表(a, b)上所有不含的正规式该文法是二义的(a) 证明该文法产生字母表a,b上的所有正规式(b) 为该文法写一个等价的非二义文法。(c) 按照上面的两个文法构造ab|b*a的分析树,2022/12/11,9,3.4 (续),证明该文法产生字母表a,b上的所有正规式证明：1）该文法产生的串是字母表a,b上的正规式R-a和R-b产生a,b,而a,b是a,b上的符号，因此是正规式。若R1，R2产生正规式，则：R-R1R2产生正规式 R-R1|R2产生正规式| R-R1* 产生正规式* R-(R1)产生正规式 () 2)字母表a,b上的所有正规式都可由此文法产生字母表a,b上的任一正规式(其中,为
6、正规式)必为以下形式之一：，可由R-RR产生|，可由R-R|R产生*，可由R-R*产生 ()，可由R-(R)产生 a,可由R-a产生 b,可由R-b产生因而，该文法产生字母表a,b上的所有正规式,2022/12/11,10,3.4 (续),该文法没有体现运算符 |、*、() 、并置的优先级，因而是二义的。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*,2022/12/11,11,3.4 (续) - ab|b*a,
7、二义的 非二义的,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,2022/12/11,12,3.5,下面的条件语句文法stmt-if expr then stmt | matched_stmtmatched_stmt - if expr then matched_stmt else stmt | other试图消除悬空else的二义性。请证明此文法仍是二义的。,2022/12/11,13,3.5 (续),由于matched_stmt不能保证then和else的配
8、对，因而存在二义性句型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,2022/12/11,14,3.5 (续),一种推导，和期望的不一样stmt= matched_stmt= if expr then matched_stmt else stmt= if expr then if expr t
9、hen 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 stmtif expr then if expr then matched_stmt else if expr then matched_stmt else stmt,2022/12/11,15,3.5 (续),另一种推导stm
10、t = 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 stmtif expr then if expr then matched_stmt else if expr then ma
11、tched_stmt else stmt,2022/12/11,16,3.8(a),消除3.1的左递归,2022/12/11,17,3.8(a) (续),S - (L)|aL - L,S|S只有直接左递归S - (L)|aL - SLL- ,SL|,2022/12/11,18,3.10,构造下面文法的LL(1)分析表D - TLT - int|realL - idRR - ,idR|,2022/12/11,19,3.10 (续),先计算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,FOLLOW(D) =
12、FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $,2022/12/11,20,3.10 (续),2022/12/11,21,3.11,下面文法是否LL(1)文法？说明理由S - AB|PQxA - xyB - bcP - dP| Q - aQ|,2022/12/11,22,3.11 (续),不是LL(1)文法LL(1)文法：对于产生式A-|,本题中，FIRST(AB)=x, FIRST(PQx)=d,a,x不满足条件(1),2022/12/11,23,3.15,(a) 用3.1的文法构造(a,(a,a)的最右推导，说出每个右句型的句柄(b) 给出对应(a)的最右
13、推导的移进-归约分析器的步骤(c) 对照(b)的移进-归约，给出自下而上构造分析树的步骤。,2022/12/11,24,3.15 (续) (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),2022/12/11,25,3.15 (续) (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),2022/12/11,26,3.15 (续) (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),2022/12/11,27,3.15 (续) (c),( a , ( a , a ) ) $,S,L,S,2022/12/11,28,3.15 (续) (c),( a , ( a , a ) ) $,S,L,S,L,S,2022/12/11,29,3.15 (续) (c),( a , ( a , a ) ) $,S,L,S,L,S,谢谢！,
