編譯原理習題課(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