编译原理陈意云-课后答案2

编译原理习题课(2)栾俊luanj@2/1/20232/1/20231luanj@3.1考虑文法

S->(L)|a

L->L,S|S

(a)建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树

(b)为(a)的两个句子构造最左推导

(c)为(a)的两个句子构造最右推导

(d)这个文法产生的语言是什么2/1/20232luanj@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,SSa(L)L,SSaaS =>(L) =>(L,S) =>(L,(L)) =>(L,(L,S)) =>(L,(L,a)) =>(L,(S,a)) =>(L,(a,a))

=>(S,(a,a)) =>(a,(a,a))2/1/20233luanj@3.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)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)))2/1/20234luanj@3.1(续)描述的语言：

括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a2/1/20235luanj@3.2考虑文法

S->aSbS|bSaS|ε

(a)为句子abab构造两个不同的最左推导，以说明此文法二义

(b)为abab构造对应的最右推导

(c)为abab构造对应的分析树

(d)这个文法产生的语言是什么2/1/20236luanj@3.2(续)(1)S=>aSbS=>abS=>abaSbS=>ababS=>abab

(2)S=>aSbS=>abSaSbS=>abaSbS=>ababS=>ababS=>aSbS=>aSb=>abSaSb=>abSab=>abab(2)SaSbSεaSbSεεSaSbSbSaSεεε(1)(2)描述的语言是a,b数目相等的串2/1/20237luanj@3.4文法

R->R’|’R|RR|R*|(R)|a|b

产生字母表(a,b)上所有不含ε的正规式

该文法是二义的

(a)证明该文法产生字母表{a,b}上的所有正规式

(b)为该文法写一个等价的非二义文法。

(c)按照上面的两个文法构造ab|b*a的分析树2/1/20238luanj@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}上的任一正规式(其中α,β为正规式)必为以下形式之一：

αβ，可由R->RR产生

α|β，可由R->R|R产生

α*，可由R->R*产生

(α)，可由R->(R)产生

a,可由R->a产生

b,可由R->b产生

因而，该文法产生字母表{a,b}上的所有正规式2/1/20239luanj@3.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|bE=>E|T=>E|F=>E|F*=>E|b*

=>T|b*=>F|b*=>a|b*2/1/202310luanj@3.4(续)-ab|b*a二义的非二义的RR|RRRabRRaR*bRRRaR*R|RbRRba…EE|TTFTTFFabFF*ba2/1/202311luanj@3.5下面的条件语句文法stmt->if

expr

thenstmt|matched_stmtmatched_stmt->

if

expr

then

matched_stmt

elsestmt|other

试图消除悬空else的二义性。请证明此文法仍是二义的。2/1/202312luanj@3.5(续)由于matched_stmt不能保证then和else的配对，因而存在二义性句型if

expr

then

if

expr

then

matched_stmt

else

if

expr

then

matched_stmt

elsestmt存在两个不同的最左推导期望的是：

if

expr

then

if

expr

then

matched_stmt

else

if

expr

then

matched_stmt

else

stmt2/1/202313luanj@3.5(续)一种推导，和期望的不一样stmt =>matched_stmt

=>if

expr

then

matched_stmt

elsestmt

=>if

expr

then

if

expr

then

matched_stmt

elsestmtelsestmt

=>if

expr

then

if

expr

then

matched_stmt

else

if

expr

thenstmtelsestmt

=>if

expr

then

if

expr

then

matched_stmt

else

if

expr

then

matched_stmt

elsestmtif

expr

then

if

expr

then

matched_stmt

else

if

expr

then

matched_stmt

else

stmt2/1/202314luanj@3.5(续)另一种推导stmt

=>if

expr

thenstmt

=>if

expr

then

matched_stmt

=>if

expr

then

if

expr

then

matched_stmt

elsestmt

=>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

elsestmtif

expr

then

if

expr

then

matched_stmt

else

if

expr

then

matched_stmt

else

stmt2/1/202315luanj@3.8(a)消除3.1的左递归2/1/202316luanj@3.8(a)(续)S->(L)|a

L->L,S|S只有直接左递归

S->(L)|a

L->SL’

L’->,SL’|ε2/1/202317luanj@3.10构造下面文法的LL(1)分析表

D->TL

T->int|real

L->idR

R->,idR|ε2/1/202318luanj@3.10(续)先计算FIRST和FOLLOW

FIRST(D)=FIRST(T)={int,real}

FIRST(L)={id}

FIRST(R)={,,ε}

FOLLOW(D)=FOLLOW(L)={$}

FOLLOW(T)={id}

FOLLOW(R)={$}2/1/202319luanj@3.10(续)intrealid,$DD->TLD->TLTT->intT->realLL->idRRR->,idRR->ε2/1/202320luanj@3.11下面文法是否LL(1)文法？说明理由

S->AB|PQx

A->xy

B->bc

P->dP|ε

Q->aQ|ε2/1/202321luanj@3.11(续)不是LL(1)文法LL(1)文法：对于产生式A->α|β

本题中，FIRST(AB)={x},FIRST(PQx)={d,a,x}

不满足条件(1)

2/1/202322luanj@3.15(a)用3.1的文法构造(a,(a,a))的最右推导，说出每个右句型的句柄(b)给出对应(a)的最右推导的移进-归约分析器的步骤(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤。

2/1/202323luanj@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))栈输入动作$(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->a2/1/202324luanj@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))栈输入动作$(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,S2/1/202325luanj@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))栈输入动作$(L)$移进$(L)$归约:S->(L