編譯原理及技術(shù)期末考試復(fù)習(xí)試題整理

./2.1考慮文法G[S],其產(chǎn)生式如下:S→<L>|aL→L,S|S試指出此文法的終結(jié)符號、非終結(jié)符號。終結(jié)符號為：{<,>,a,,,}非終結(jié)符號為：{S,L}開始符號為：S<2>給出下列各句子的分析樹：①<a,a>

②<a,<a,a>>③<a,<<a,a>,<a,a>>>

<3>構(gòu)造下列各句子的一個(gè)最左推導(dǎo)：①<a,a>S<L><L,S><S,S><a,S><a,a>②<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>>③<a,<<a,a>,<a,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>>><4>構(gòu)造下列各句子的一個(gè)最右推導(dǎo)：=1\*GB3①<a,a>S<L><L,S><L,a><S,a><a,a>②<a,<a,a>>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>>S<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>>><5>這個(gè)文法生成的語言是什么？L<G[S]>=<α1,α2,...,αn>或a其中αi<1≤i≤n>,即L<G[S]>是一個(gè)以a為原子的純表,但不包括空表。2.2考慮文法G[S]S→aSbS|bSaS|ε<1>試說明此文法是二義性的?？梢詮膶τ诰渥觓bab有兩個(gè)不同的最左推導(dǎo)來說明。SaSbSabSabaSbSababSabab

SaSbSabSaSbSabaSbSababSabab

所以此文法是二義性的。<2>對于句子abab構(gòu)造兩個(gè)不同的最右推導(dǎo)。SaSbSaSbaSbSaSbaSbaSbababab

SaSbSaSbabSaSbabSababab<3>對于句子abab構(gòu)造兩棵不同的分析樹。

<一>

<二>

<4>此文法所產(chǎn)生的語言是什么？此文法產(chǎn)生的語言是：所有a的個(gè)數(shù)與b的個(gè)數(shù)相等的由a和b組成的字符串。2.4已知文法G[S]的產(chǎn)生式如下：S→<L>|aL→L,S|S

屬于L<G[S]>的句子是A,<a,a>是L<G[S]>的句子,這個(gè)句子的最左推導(dǎo)是B,最右推導(dǎo)是C,分析樹是D,句柄是E。

A：①a

②a,a

③<L>

④<L,a>B,C：①S<L><L,S><L,a><S,a><a,a>

②S<L><L,S><S,S><S,a><a,a>

③S<L><L,S><S,S><a,S><a,a>

D：

E：①<a,a>

②a,a

③<a>④a解答：A：①B：③C：①D：②E：④3.1

有限狀態(tài)自動(dòng)機(jī)可用五元組〔VT,Q,δ,q0,Qf來描述,設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：

VT={0,1},Q={q0,q1,q2},Qf={q2},δ的定義為：

δ〔q0,0=q1

δ〔q1,0=q2

δ〔q2,1=q2

δ〔q2,0=q2

M是一個(gè)A有限狀態(tài)自動(dòng)機(jī),它所對應(yīng)的狀態(tài)轉(zhuǎn)換圖為B,它所能接受的語言可以用正則表達(dá)式表示為C。其含義為D。A:

①歧義的

②非歧義的

③確定的

④非確定的

B:

C：①<0|1>*

②00<0|1>*

③<0|1>*00

④0<0|1>*0

D：①由0和1所組成的符號串的集合；

②以0為頭符號和尾符號、由0和1所組成的符號串的集合；

③以兩個(gè)0結(jié)束的,由0和1所組成的符號串的集合；

④以兩個(gè)0開始的,由0和1所組成的符號串的集合。答案A:③

B:②

C:②

D:④3.2

<1>有窮自動(dòng)機(jī)接受的語言是正則語言?！?/p>

<2>若r1和r2是Σ上的正規(guī)式,則r1|r2也是。〔

<3>設(shè)M是一個(gè)NFA,并且L<M>＝{x,y,z},則M的狀態(tài)數(shù)至少為4個(gè)。

<4>令Σ＝{a,b},則Σ上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*<a|b>*。

<5>對任何一個(gè)NFAM,都存在一個(gè)DFAM',使得L<M'>=L<M>?！?/p>

<6>對一個(gè)右線性文法G,必存在一個(gè)左線性文法G',使得L<G>=L<G'>,反之亦然?！泊鸢?lt;1>

T

<2>

T

<3>

F

<4>

F

<5>

T3.3

描述下列各正規(guī)表達(dá)式所表示的語言。

<1>

0<0|1>*0

<2>

<<ε|0>1*>*

<3>

<0|1>*0<0|1><0|1>

<4>

0*10*10*10*

<5>

<00|11>*<<01|10><00|11>*<01|10><00|11>*>*答案<1>

以0開頭并且以0結(jié)尾的,由0和1組成的所有符號串<2>

{α|α∈{0,1}*}即由0和1組成的所有符號串。<3>

由0和1組成的符號串,且從右邊開始數(shù)第3位為0。<4>

含3個(gè)1的由0和1組成的所有符號串。

{α|α∈{0,1}+,且α中含有3個(gè)1}<5>

{α|α∈{0,1}*,α中含0和1的數(shù)目為偶數(shù)。}4.10已知文法G[S],其產(chǎn)生式如下：S→<L>|a

L→L,S|S

文法G[S]的算符優(yōu)先關(guān)系由下表給出。建立與下表相應(yīng)的算符優(yōu)先函數(shù)并用算符優(yōu)先分析法分析句子<a,<a,a>>。文法G[S]的算符優(yōu)先關(guān)系表：解：對每個(gè)終結(jié)符或＄建立符號f與g,把f<和g>分成一組。

根據(jù)G[S]的算符優(yōu)先關(guān)系表,畫出如下的有向圖:優(yōu)先函數(shù)如下：用算符優(yōu)先分析法分析句子<a,<a,a>>

4.19<1>存在有左遞歸規(guī)則的文法是LL<1>的。

<2>任何算符優(yōu)先文法的句型中不會有兩個(gè)相鄰的非終結(jié)符號。

<3>算符優(yōu)先文法中任何兩個(gè)相鄰的終結(jié)符號之間至少滿足三種

關(guān)系<＜·,·＞,>之一。

<4>任何LL<1>文法都是無二義性的。

<5>每一個(gè)SLR<1>文法也都是LR<1>文法。

<6>存在一種算法,能判定任何上下文無關(guān)文法是否是LL<1>的。

<7>任何一個(gè)LL<1>文法都是一個(gè)LR<1>文法,反之亦然。

<8>'LR<1>'括號中的1是指,在選用產(chǎn)生式A→α進(jìn)行分析,看當(dāng)前讀入符號是否在FIRST<α>中。答案：<1>×<2>√<3>×<4>√<5>√<6>√<7>×<8>×4.20在編譯程序中,語法分析分為自頂向下分析和自底向上分析兩類。__A__和LL<1>分析法屬于自頂向下分析；__B__和LR分析法屬于自底向上分析。自頂向下分析試圖為輸入符號串構(gòu)造一個(gè)__C__；自底向上分析試圖為輸入符號串構(gòu)造一個(gè)__D__。采用自頂向下分析方法時(shí),要求文法中不含有__E__。A、B：①深度分析法②寬度優(yōu)先分析法③算符優(yōu)先分析法④預(yù)測遞歸分析法C、D：①語法樹②有向無環(huán)圖③最左推導(dǎo)④最右推導(dǎo)E：①右遞歸②左遞歸③直接右遞歸④直接左遞歸A：④B：③C：③D：④E：②4.21自底向上語法分析采用__A__分析法,常用的是自底向上語法分析有算符優(yōu)先分析法和LR分析法。LR分析是尋找右句型的__B__；而算符優(yōu)先分析是尋找右句型的__C__。LR分析法中分析能力最強(qiáng)的是__D__；分析能力最弱的是__E__。A：①遞歸②回溯③枚舉④移進(jìn)－規(guī)約B、C：①短語②素短語③最左素短語④句柄D、E：①SLR<1>②LR<0>③LR<1>④LALR<1>A：④B：④C：③D：③E：②5.5用S的綜合屬性val給出在下面的文法中的S產(chǎn)生的二進(jìn)制數(shù)的值〔例如,對于輸入

101.101,S.val=5.625：

S→L.L|L

L→LB|BB→0|1〔1試用各有關(guān)綜合屬性決定S.val?！?試用一個(gè)語法制導(dǎo)定義來決定S.val,在這個(gè)定義中僅有B的綜合屬性,設(shè)為c,它給出由B生成的位對于最后的數(shù)值的貢獻(xiàn)。例如,在101.101中的第一位和最后一位對于值5.625的貢獻(xiàn)分別為4和0.125。解答：<1>用綜合屬性決定s.val的語法制導(dǎo)定義：產(chǎn)生式語義規(guī)則

S->LS.val:=L.val;

S->L1.L2S.val:=L1.val+L2.val*L2.p;

L->BL.val:=B.val;

L.p:=2-1;

L->L1BL.val:=L1.val*2+B.val;L.p:=L.p*2-1;

B->0B.val:=0;

B->1B.val:=1;注：L.p表示恢復(fù)L.val的因子。<2>分析：設(shè)B.c是B的綜合屬性,是B產(chǎn)生的位對最終值的貢獻(xiàn)。要求出B.c,必須求出B產(chǎn)生位的權(quán),設(shè)B.i。B.i的求法請參看下面的圖示：另外,設(shè)L.fi為繼承因子,L.fs為綜合因子,語法制導(dǎo)定義如下：產(chǎn)生式語義規(guī)則

S->LL.i:=1;L.fi:=2;L.fs:=1;S.val:=L.val;

S->L1.L2L1.i=1;L1.fi=2;L1.fs:=1;L2.i=2-1;L2.fi=1;L2.fs:=2-1;S.val:=L1.val+L2.val;

L->BL.s:=L.i;B.i:=L.s;L.val:=B.c;

L->L1BL1.i:=L.i*L1.fi;L.s:=L1.s*L1.fs;B.i:=L.s;L.val:=L1.val+B.c;

B->0B.c:=0;

B->1B.c:=B.i;5.15描述文法符號語義的屬性有兩種,一種稱為<A>,另一種稱為<B>。<A>值的計(jì)算依賴于分析樹中它的<C>的屬性值；<B>的值的計(jì)算依賴于分析樹中它的<D>的屬性值。A,B:①L-屬性②R-屬性③綜合屬性④繼承屬性C,D:①父結(jié)點(diǎn)②子結(jié)點(diǎn)③兄弟結(jié)點(diǎn)④父結(jié)點(diǎn)與子結(jié)點(diǎn)⑤父結(jié)點(diǎn)與兄弟結(jié)點(diǎn)解答:A③

B④

C②

D⑤5.16<1>語法制導(dǎo)定義中某文法符號的一個(gè)屬性,既可以是綜合屬性,又可以是繼承屬性。<2>只使用綜合屬性的語法制導(dǎo)定義稱為S-屬性定義。<3>把L-屬性定義變換成翻譯模式,在構(gòu)造翻譯程序的過程中前進(jìn)了一大步。<4>一個(gè)特定的翻譯模式既適于自頂向下分析,又適于自底向上分析。<5>用于自頂向下分析的翻譯模式,其基礎(chǔ)文法中不能含有左遞歸。<6>在基礎(chǔ)文法中增加標(biāo)記非終結(jié)符不會導(dǎo)致新的語法分析沖突。解答:<1>FALSE

<2>TRUE

<3>TRUE

<4>FALSE

<5>TRUE

<6>FALSE6.7

<1>對于允許遞歸調(diào)用的程序語言,程序運(yùn)行時(shí)的存儲分配策略不能采用靜態(tài)的存儲分配策略?！?/p>

<2>若一個(gè)程序語言的任何變量的存儲空間大小和相互位置都能在編譯時(shí)確定,則可采用靜態(tài)分配策略?！?/p>

<3>在不含嵌套過程的詞法作用域中,若一個(gè)過程中有對名字a的非局部引用,則a必須在任何過程〔或函數(shù)外被說明?！?lt;4>在允許嵌套的詞法作用域的語言中,過程不能作為參數(shù),原因時(shí)不能建立其運(yùn)行環(huán)境的存取鏈?！?lt;5>在堆式存儲分配中,一個(gè)堆中存活的活動(dòng)記錄不一定是鄰接的?！?lt;6>如果源程序正文中過程p直接嵌入在過程q中,那么,p的一個(gè)活動(dòng)記錄中的存取鏈接指向q的最近的活動(dòng)記錄。〔解答：<1><TRUE><2><FALSE><3><TRUE><4><FALSE>

<5><TRUE><6><TRUE>6.8運(yùn)行時(shí)的存儲分配策略分<

A

>和<

B

>兩類。<

B

>又分<

C

>和<

D

>。一個(gè)語言中不同種類的變量根據(jù)定義域和生存期的不同往往采用不同的存儲分配策略,C語言中的靜態(tài)變量往往采用<

A

>,而自動(dòng)<out>類變量往往采用<

C

>。使用mallac中申請的內(nèi)存單元采用<

D

>。

A,B,C,D:①棧式分配②最佳分配

③堆式分配④靜態(tài)分配

⑤隨機(jī)分配

⑥動(dòng)態(tài)分配解答：A:④

B:⑥

C:①

D:③7.2翻譯算術(shù)表達(dá)式一〔a＋b*〔c＋d＋〔a＋b＋c為

<1>四元式,

<2>三元式

<3>間接三元式解答：<1>四元式序列為：

oparg1arg2result<1>+abt1<2>+cd

t2<3>*t1t2t3<4>uminust3t4<5>+abt5<6>+t5ct6<7>+t4t6t7<2>三元式序列為：

oparg1arg2<1>+ab<2>+cd<3>*<1><2><4>uminus<3><5>+ab<6>+<5>c<7>+<4><6><3>間接三元式表示：

statement

oparg1arg2<1><11><11>+ab<2><12><12>+cd<3><13><13>*<11><12><4><14><14>uminus<13><5><11><15>+<11>c<6><15><16>+<14><15><7><16>

9.1試構(gòu)造下面的程序的流圖,并找出其中所有回邊及循環(huán)。

readP

x:=1

c:=P*P

ifc<100gotoL1

B:=P*P

x:=x+1

B:=B+x

writex

halt

L1:B:=10

x:=x+2

B:=B+x

writeB

ifB<100gotoL2

halt

L2:x:=