《编译原理陈意云_课后答案2[1]》由会员分享，可在线阅读，更多相关《编译原理陈意云_课后答案2[1]（30页珍藏版）》请在金锄头文库上搜索。
1、编译原理习题课(2)栾 俊 *3.1 考虑文法 S - (L)|a L - L,S|S (a) 建立句子(a,(a,a)和(a,(a,a),(a,a)的分 析树 (b) 为(a)的两个句子构造最左推导 (c) 为(a)的两个句子构造最右推导 (d) 这个文法产生的语言是什么D3.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 , SSa( L )L , SSaaS =(L) =(L,S) =(L,(L) =(L,(L,S) =(L,(L,a)
2、=(L,(S,a) =(L,(a,a) =(S,(a,a) =(a,(a,a)D3.1 (续) - (a,(a,a),(a,a)S( 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
3、)L , SSaaSS =(L) =(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)D3.1 (续) 描述的语言： 括号匹配的串，串中的各项由”,”隔开， 项可以是括号匹配的子串或aD3.2 考虑文法 S - aSbS|bSaS|
4、 (a) 为句子abab构造两个不同的最左推导， 以说明此文法二义 (b) 为abab构造对应 的最右推导 (c) 为abab构造对应 的分析树 (d) 这个文法产生的语言是什么D3.2 (续) (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数目相等的串D3.4 文法 R-R|R | RR | R* | (R) | a | b 产生字母表(a,
5、 b)上所有不含的正规式 该文法是二义的 (a) 证明该文法产生字母表a,b上的所有正 规式 (b) 为该文法写一个等价的非二义文法。 (c) 按照上面的两个文法构造ab|b*a的分析 树D3.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上的所有正规式D3.4 (续) 该文法没有体现运算符 |、*、() 、并置的优 先级，因而是二义的。 R=R|R= a|R =a|R*=a|b* R=R*=R|R*=a|R*=a|b* E - E|T | T T - TF | F F - F* | (E) | a | b E=E|T=E|F=E|F*=E|b* =T|b*=F|b*=a|b*D3.4 (续) - ab|b*a 二义的 非二义的RR | RR RabR RaR *
7、bRR RaR *R | RbR RbaEE | TT FTT FFabFF *baD3.5 下面的条件语句文法 stmt-if expr then stmt | matched_stmt matched_stmt - if expr then matched_stmt else stmt | other 试图消除悬空else的二义性。请证明此文法仍 是二义的。D3.5 (续) 由于matched_stmt不能保证then和else的配对，因而存在 二义性 句型if expr then if expr then matched_stmt else if expr then matched_st
8、mt else stmt存在两个不同的最左推导 期望的是：if expr thenif expr thenmatched_stmtelseif expr then matched_stmt else stmtD3.5 (续) 一种推导，和期望的不一样 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 t
9、hen stmt else stmt = if expr then if expr then matched_stmt else if expr then matched_stmt else stmt if expr thenif expr thenmatched_stmtelseif expr then matched_stmt else stmtD3.5 (续) 另一种推导 stmt = if expr then stmt = if expr then matched_stmt = if expr then if expr then matched_stmt else stmt = if
10、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 thenif expr thenmatched_stmtelseif expr then matched_stmt else stmtD3.8(a) 消除3.1的左递归D3.8(a) (续) S - (L)|a L - L,S|S 只有直接左递归 S - (L)|a L - SL L- ,SL|D3.10 构造
11、下面文法的LL(1)分析表 D - TL T - int|real L - idR R - ,idR|D3.10 (续) 先计算FIRST和FOLLOW FIRST(D) = FIRST(T) = int,real FIRST(L) = id FIRST(R) = , FOLLOW(D) = FOLLOW(L) = $ FOLLOW(T) = id FOLLOW(R) = $D3.10 (续)intrealid,$DD - TLD - TLTT - intT - realLL - idRRR - ,idRR - D3.11 下面文法是否LL(1)文法？说明理由 S - AB|PQx A - x
12、y B - bc P - dP| Q - aQ|D3.11 (续) 不是LL(1)文法 LL(1)文法：对于产生式A-| 本题中，FIRST(AB)=x, FIRST(PQx)=d,a,x 不满足条件(1)D3.15 (a) 用3.1的文法构造(a,(a,a)的最右推导， 说出每个右句型的句柄 (b) 给出对应(a)的最右推导的移进-归约分 析器的步骤 (c) 对照(b)的移进-归约，给出自下而上构 造分析树的步骤。D3.15 (续) (a) (b) S =(L) =(L,S) =(L,(L) =(L,(L,S) =(L,(L,a) =(L,(S,a) =(L,(a,a) =(S,(a,a)
13、=(a,(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- aD3.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)栈输入动作$(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)$归约 :S-(L)$(L,S)$归约 :L-L,SD
