01-普通作業一（第一章）

一、選擇題（從備選項中選出一個或多個正確答案）。

1.編譯程序的源程序是高級語言編寫的程序，目標程序是編寫的程序。

A.高級語言B.匯編語言C.機器語言D,匯編語言或機器語言

2.編譯程序是對進行翻譯。

A.高級語言B.匯編語言C.機器語言D.自然語言

3.如果編譯程序生成的目標程序是機器代碼程序，則源程序的執行分為兩個階段。

A.編譯B.匯編C.運行D.預處理

4.編譯的工作過程一般劃分為詞法分析、、語義分析、中間代碼生成、代碼優化

和目標代碼生成若干階段。

A.表格管理B.出錯處理C.語法分析D.預處理

5.詞法分析階段的主要任務是識別。

A.表達式B.單詞C.語句D,詞組

二、判斷題（對于下列陳述中正確的說法選擇回答“對”，否則選擇回答“錯”）。

1.編譯程序是一種常見的應用軟件。

2.C語言的編譯程序可以用C語言編寫。

3.編譯方式與解釋方式的區別之一在于是否生成目標程序。

4.中間代碼生成是編譯程序不可或缺的部分。

5.含有優化的編譯程序執行效率高。

三、解釋下列術語：

（1）編譯程序

（2）源程序

（3）目標程序

（4）編譯程序的前端

（5）后端

（6）遍

四、一個典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？并畫出編譯程

序的總體結構圖。

五、何謂翻譯程序、編譯程序和解釋程序？它們三者之間有何種關系？

參考答案：

一、選擇題

1.D2.A3.AC4.C5.B

二、判斷題

1.錯2.對3.對4.錯5.錯

三、

⑴把用高級程序設計語言書寫的源程序，翻譯成等價的計算機匯編語言或機器語言書寫的

目標程序的翻譯程序。

(2)源程序，是指未經編譯的，按照一定的程序設計語言規范書寫的，人類可讀的文本文件。

⑶為源程序經編譯可直接被計算機運行的機器碼集合，在計算機文件上以.obj作擴展名。

⑷編譯程序的前端通常指：詞法分析、語法分析、語義分析等生成最終代碼以前的一系列

步驟。

⑸后端包含代碼優化和目標代碼生成部分。

⑹對源程序或其等價的中間語言程序從頭到尾掃視并完成規定任務的過程。

四、數據結構、分析部分、綜合部分、結構。

五、

第二章高級語言及其語法描述

本章要點

1.程序語言的定義；

2.高級程序語言一般結構和主要共同特征；

3.正確理解上下文無關文法基本概念，包括：

文法的定義、推導、句型、句子、語言、語法樹、二義性等；

4.Chomsky文法分類；

本章目標

掌握和理解程序語言的定義、高級語言的一般特征及程序語言的語法描述.

本章重點

1.語法，詞法規則與語法規則；

2.語義和語義規則；

3.數據類型與操作；

4.推導，最左推導和最右推導；

5.語法分析樹和二義性；

本章難點

1.二義性文法;

2.Chomsky各個文法類；

作業題

一、單項選擇題：

(按照組卷方案，至少15道小題)

1.Chomsky把文法分成四種類型，。型、1型、2型和3型。3型文法也稱為,2

型文法也稱為。

a.上下文無關文法b.上下文相關文法c.正則文法d.短語文法

2.許多廣為使用的語言，如Fortran、C、Pascal等，屬于?

a.強制式語言b.應用式語言c.基于規則的語言d.面向對象的語言

設是一個文法，是開始符號。若則稱是一個。

3.GSSn'a,ae(VTUVN),,a

a.句子b.句型c.推導d.語言

4.一個數據類型通常包括的三種要素中，沒有下面的。

a.用于區別這種類型的數據對象的屬性；b.這種類型的數據對象可以具有的值；

c.對這種類型的數據對象的內存分配；d.可以作用于這種類型的數據對象的操作；

5.Chomsky把文法分成四種類型，其中，也稱正規文法

a.O型b.1型c.2型d.3型

6.語言的詞法規則一般用Chomsky的____型文法來描述：

a.0b.1c.2d.3

7.文法

Sf(L)|a

LfL,S|S

中，下面—是該文法中的終結符號。

a.Sb.,c.Ld.|

8.文法G所描述的語言是的集合。

a.文法G的字母表Z中的所有符號組成的符號串；

b.文法G的字母表E的閉包￡*中的所有符號串；

c.文法G的識別符號推出的所有符號串；

d.文法G的識別符號推出的所有終結符號串；

9.語言L={aca|ae（a|b廣},該語言是語言?

a.3型語言，b.2型語言，c.l型語言，d.O型語言

10.設有文法G：

1-11|10|la|1c|a|b|c|

下面符號串中不是該文法的句子是：

a.abO,b.aOcOl,c.aaa,d.bclO

11.給定文法A-bA|cc,下面的符號串中，是該文法句子的是o

a.bcbc,b.bbbcc,c.bcbcc,d.bccbcc；

12.Chomsky定義的四種形式語言文法中，2型文法可由（G）識別。

a.圖靈機；b.確定性有限自動機；c.下推自動機；d.非確定性有限自動機;

13.若文法G定義的語言是無限集，則文法必然是。

a.上下文無關的b.遞歸的c.二義性的d.無二義性的

14.文法S-aaS|abc定義的語言是。

a.{a2kbc|k>0}b.{akbc|k>0}

c.{a2klbc|k>0}d.{akakbc|k>0}

15.文法：G：S-xSx|y所識別的語言是（）。

a.xyxb.（xyx）*c.x*yx*d.xnyxn（n20）

—.答案:l.c.；2.a.；3.b；4.c；5.d；6.d；7.b；8,d；9.d；10.a；11.b；12.c；13.b；

14.c；15.d；

二、填空題：

（按照組卷方案，至少15道小題）

1.假設G是一個文法,a是由終結符和非終結符組成的串，s是文法的開始符號，如果s=>*a,

則稱a是。

2.在賦值語句中，賦值號'：=’左右兩邊的變量名扮演著兩種不同的角色，為了區分一個名

字的這兩種特征，我們把一個名字所代表的稱為該名的左值，把一個名字的稱

為該名字的右值。

3.對于文法G,僅含終結符號的句型稱為。

4.設有文法G⑸，其部分產生式：

E-E+T|T

T-T*F|F

F~(E)|a

貝

UVN={},VT={}?

5.由文法產生的集合是文法產生的語言。

6.Chomsky語法定義的3型文法又可以分為。

7.一個上下文文法G的四個組成部分分別是：。

8.已知語言：{aEWln,m20},其語法定義為：G=({a,b},{S,A,B},S,P),其中P

為：。

9.已知某語言的語法定義為：G=({a},{S}S,P),且P:S-aS|￡,則該語言

為?

10.已知某語言為{wcwR|3e{a,b}*},其語法定義為G=({a,b,c},{S},S,P),其中P

為：。

11.所謂最右推導是指。

12.己知文法G(Z):

E-ET+|T

TfF*|F

F—FPt|P

PfE|i

試寫出其識別的一個句子：。

13.文法G⑸：S-aA|a,A-aS為_____型文法，其確定的語言的為：。

14.在一棵語法樹生長過程中的任何時刻，就是

一個句型。

15.我們說G=(VT,VN，S,P)是一個0型文法，如果它的每一個產生式a-p是這樣一種結

構：。

二.答案：1.句型；2.單元的地址(或者：單元、存儲單元的地址)，值(或者：單元的內

容)3.句子；4.VN={E,T,F},“={+,*,(,),a}；5.句子；6.右線性文法和左線性文法;

7.開始符號，產生式集合，終結符集合，非終結符集合；8.S玲AB；A^aAb|￡；B-^aBb|￡；

9.{an|n20}；10.S玲aSa|bSb|￡；11.任何一步a=B都是對a中的最右非終結符進行替換。12.

個*2n+1所有那些沒有后代的末端結點從左到右排列起來；

iii+；13.{a|n>0};14.15.

VT)'且至少含有一個非終結符，而(VN

ae(vNuBeUvT)\

三、判斷題：

(按照組卷方案，至少15道小題)

1.一棵語法樹表示了一個句型所有的不同推導過程，包括最右推導和最左推導。（）

2.可能有兩個不同的文法G和G,期中一個是二義的而另一個是無二義的，但是卻有L（G）

L（GZ）o（）

3.變量既持有左值又持有右值，而常數和帶有算符的表達式一般認為只持有右值。（）

4.文法G:

SfbA

A-*aA|a

定義的語言是所有以b開頭的后跟至少一個a的字符串的集合。（）

5.設有文法G：

S-S*S|S+S|（S）|a

該文法是二義的。（）

6.正則文法一定不是二義的。（）

7.上下文無關文法可以產生語言L={|i>=l,n>=l}?（）

8.不存在任何正規文法能產生語言L={anbn|n>=l}?（）

9.對于每一個左線性文法Gi，都存在一個右線性文法G2，使得L（GI）=L（G2）。（）

10.正規文法產生的語言都可以用上下文無關文法來描述。（）

11.上下文無關文法比正規文法有更強的描述能力。（）

12.文法的二義性和語言的二義性在概念上是相同的，也就是說，對于某個語言，不可能存

在兩個以上的文法來描述它。（）

13.二義性是可以判定的，也就是說，可以編這么一個程序，輸入該文法后，該程序能確切

地給出該文法是否二義的答案。（）

14.說明語句旨在定義名字的性質。編譯程序把這些性質登記在符號表中，并檢查程序中名

字的引用和說明是否一致。實際上，許多說明語句并不能翻譯成相應的目標代碼。（）

15.C語言是一個允許子程序嵌套定義的語言。（）

三.答案：1.V；2.V；3.V；4.V；5.V；6.X；7.V；8.V；9.V；10.V；11.V；12.X；13.X；

14.V；15.X；

四、名詞解釋：

（按照組卷方案，至少3道小題）

1.二義性文法；2.推導和直接推導；3.句型，句子和語言；4.上下文無關文法;

5.語法；6.正規文法（左線性文法和右線性文法）；

四.答案：

1.如果一個文法存在某個句子對應兩棵以上不同的語法樹，則稱這個文法是是二義性文法。

2.設A-y是一個產生式，且a、pe（VTuVN）*,若aAB=>ayP，則稱aA|3直接推出ayP；或者

說，a鄧是aAp的一個直接推導。

如果ai=>a2=>......=>an,則稱這個序列是從a1到an的一個推導。

3.設G是一個文法，s是它的開始符號。如果s=>*a,則稱a是一個句型。

僅含終結符的句型叫句子。

文法G所產生的句子的全體叫文法G的語言，記為L（G）,L（G）={a|S=>*a,aev/lo

4.上下文無關文法G是一個四元式（VT，VN，S,P）,其中：

VT是一個非空有限集合，其中的每一個元素稱為終結符；

VN是一個非空有限集合，其中的每一個元素稱為非終結符，VNnvT=0；

S是一個非終結符，稱為開始符號：

P是一個產生式有限集合，每個產生式的形式是Pfa,其中PCVN，aG（V2VN）*。開始符號

S至少必須在某個產生式的左部出現一次。

5.若文法G=（V「VN，S,P）的任何產生式為A~aB或A-a,其中，aeVT*.A,B￡VN,則

稱G是右線性文法；

若文法G=（V「VN，S,P）的任何產生式為A-Ba或A-a,其中，aeV；,A,BSVN,則稱G

是左線性文法；

左線性文法和右線性文法均為正規文法。

五、簡答題：

（按照組卷方案，至少3道小題）

1.作為描述程序語言的上下文無關文法，對它有哪些限制？

答：

第一點：文法中不含任何下面形式的產生式：P-P;

第二點：每個非終結符P都必須有用處。也就是說，必須存在含P的句型；或者說，對P

不存在永不終結的回路。

2.什么是二義性文法？從輸入串abab來說明下面文法二義嗎？

S->aSbS|bSaS|e

該文法產生的語言是什么？

答:

如果一個文法存在某個句子對應兩棵以上不同的語法樹，則稱這個文法是二義的。

例如輸入串abab,它有兩棵語法樹如下：

所以，該文法是二義的。

此文法產生的語言是：所有a的個數與b的個數相等的由a和b組成的字符串。

3.文法G⑸為：

S-Ac|aB

A-ab

B-be

該文法是否為二義的？為什么？

答：

對于串abe

⑴S二〉Ac二〉abc⑵S二〉aB二〉abc

即存在兩不同的最右推導。所以，該文法是二義的。

或者：

對輸入字符串abc,能構造兩棵不同的語法樹，所以它是二義的。

4已知文法G=({A,B,C},{a,b,c},P,A),P由以下產生式組成:

Afabc

A->aBbc

Bb->bB

Bc->Cbcc

bCfCb

aC->aaB

aC-*aa

此文法所表示的語言是什么？

答：

分析文法的規則：

每使用一次BcfCbcc,b、c的個數各增加一個；

每使用一次aCfaaB或aC-aa,a的個數就增加一個；

產生式BbfbB、bC-Cb起連接轉換作用。

由于A是開始符號，由產生式A-abc推導得到終結符號串abc；由產生式A-aBbc推導得

到B后，每當使用產生式Bb-bB、Bc—Cbcc、bC—Cb、aCfaaB就會遞歸調用B一次，所

產生的a、b、c的個數分別增加一個，因此推導所得的終結符號串為abc、aabbcc、aaabbbccc、…

所以文法描述的語言為{aW|n>0}.

5已知文法G[Z]:

Z-OU|1V

U-1Z|1

V—0Z|0

(1)請寫出此文法描述的只含有4個符號的全部句子。

(2)G[Z]產生的語言是什么？

(3)該文法在Chomsky文法分類中屬于幾型文法？

答：

(1)0101,0110,1010,1001

(2)分析G⑵所推導出的句子的特點：由Z開始的推導不外乎圖1所示的四種情形。

圖1文法G[Z]可能的幾種推導

由Z推導出10或01后就終止或進入遞歸，而Z的每次遞歸將推導出相同的符號串：10或

Olo所以G⑵產生的語言L(G[Z])={x|x6(10|01)+}

(3)該文法屬于3型文法。

七、應用題:

1.試分析下面給出的if-then-else語句的文法，它的提出原本是為了矯正dangling-else（else

懸掛）文法的二義性：

stmt玲ifexprthenstmt\matched-stmt

matched-stmt^ifexprthenmatched-stmtelsestmt\other

expr->e

考慮句子ifethenifethenotherelseifethenotherelseother,試說明此文法仍然是二義性

的。

答：

1.考慮句子ifethenifethenotherelseifethenotherelseother

它具有如下所示的兩種分析樹

stmt

ifexprthenstmt

matched-stmt

ifexprthenmatched-stmteslestmt

othermatched-stmt

ifexprthenmatched-stmteslestmt

othermatched-stml

other

stmt

matched-stmt

other

則上面給出的if-then-else文法仍是二義性的。

2.考慮文法G[bexpr]：

bexpr^>bexprorbterm\bterm

bterm^>btermandbfactor|bfactor

bfactor^>r\otbfactor\(bexpr)|true|false

(a)請指出此文法的終結符號、非終結符號和開始符號。

(b)試對于句子1101：(什110032歸6)構造-一棵分析樹。

(C)試說明此文法所產生的語言是全體布爾表達式。

答：

(a)終結符號為:{or,and,not,(,),true,false}

非終結符號為：{bexpr,bterm,bfactor)

開始符號為：bexpr

(b)句子not(trueorfalse)的分析樹為：

(c)用歸納法說明如下：

⑴不含運算的布爾表達式，常數true和false由此文法產

生：

bexpr=>bterm=>bfactor=>true

bexpr=>bterm=>bfactor=>false

(2)設結論對于少于n(n”)個運算的布爾表達式成立，即

若be1和be?是含有少于n個運算的布爾表達式，則有：

++

bexpr=>bei；bexpr=>be2o

⑶對于含有n個運算的布爾表達式，可表示成下面三種

形式：

(a)(be。or(be2)

(b)(be。and(be2)

(c)not(bej

對于(a)：bexpr=>bexprorbterm

=>btermorbterm=>bfactororbterm

=>(bexpr)orbterm=>+(beJorbterm

=>(bei)orbfactor=>(bejor(bexpr)

+

=>(bei)or(be2)

同理，有：

+

Bexpr=>(bejand(be2)

Bexpr=>+not(bej

綜上所述，此文法所產生的語言是全體布爾表達式。

3.已知文法G[S],其產生式為:S->(S)|E

(a)L(G)是什么？

(b)對于⑶的結果，請給出證明。

答：

(a)解：L(G)={(n)n|n>0}

(b)證明：

首先證明L(G)q{(n)n|n20}

對推導次數進行歸納

1)：當推導次數為1時，使用產生式Sf￡,此時左括號與右括號個數為0

2):假設推導次數為n時(a)成立，即：

S4(((...S...)))^(((……)))

n-1n-in-1n-1

則推導次數為n+1次時，多使用一次產生式S-⑸即：

S4(((...S...)))=>(((...S...)))=>(((……)))

n-1n-1nnnn

推導次數為n+1次時(a)成立。

根據⑴(2)可得：L(G)c{(n)n|n>0}

其次證明{(n)n|n?O}=L(G)

對n進行歸納

1):當n=0時，使用產生式S-*E即可；

2):假設當n=k時，結論成立，即「)keL(G),下面證n=k+l時結論成立。

由(k)keL(G),其推導過程如下：

S4(((...S...)))=>(((……)))

kkkk

當n=k+l時，推導過程如下：

S4(((...S...)))=>(((...S...)))=>(((……)))

kkk+1k+lk+1k+1

故(k+i)k+ieL(G)

nn

根據⑴⑵可得：{()|n>O}￡L(G)

根據1,2可知：L(G)={(n)n|>0}

4.試構造生成下列語言的上下文無關文法：

(lXaVd|n>l,i>0}

(2){w|wW{a,b}+,且w中a的個數恰好比b多1}

(3){w|wG{a,b}*,且|a141b|421a|}

答：

(1)把a%"分成a%"和d兩部分，分別由兩個非終結符號生成，因此，生成此文法的產

生式為：

S玲AB

A玲aAb|ab

BBcB|e

(2)令S為開始符號，產生的w中a的個數恰好比b多一個，令E為一個非終結符號，產

生含相同個數的a和b的所有串，則產生式如下：

S->aE|Ea|bSS|SbS|SSb

E-?aEbE|bEaE|e

(3)設文法開始符號為S,產生的w中滿足|a|S|b|S2|a|。因此,可想到S有如下的產生式(其

中B產生1到2個b)：

SfaSBS|BSaS|e

B-b|bb

5.已知文法G⑸：

S玲AB

A->aA|a

B玲bB|b

求該文法所定義的語言。

答：

從規則2可推出：a,aa,aaa,.......

從規則3可推出：b,bb,bbb,.......

再從規則1可推出句子：

ab,aab,aabb,aaab,abbb,......

即，從S出發可推出多個a后跟多個b的字符串，且a的個數與b的個數不盡相同。

故：L(G)={ambn|m,nel}

6.考慮下面上下文無關文法G[S]：

S—SS*|SS+|a

⑴對于符號串aa+a*分別給出最左推導和最右推導過程，并為該串構造語法樹。

(2)G⑶的語言是什么？

答：

⑴此文法生成串aa+a*的最右推導：

S=>ss*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

此文法生成串aa+a*的最左推導：

S=>SS*=>SS+S*=>*=>aS+S*=>aa+S*=>aa+a*

s

aa

(2)該文法生成的語言是：*和+的后綴表達式，即逆波蘭式。

7令文法G為

N-D|ND

D-0|1|2|3|4|5|6|7|8|9

⑴G的語言L(G)是什么？

(2)給出句子0127、34和568的最左推導和最右推導。

答：

(1)

NnNDnNDDnNDDDnNDDDD......nDD......D

:.L(G)={d(n+1)|nNO,de{0,1,9}}

允許以0開頭的自然數(十進制無符號整數)；

(2)

0127最左推導：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=^0127

0127最右推導：N=ND=N7=ND7nN27=ND27nN127=Dl27noi27

8寫一個文法，使其語言是奇數集，且每個奇數不以0開頭。

答：(首先分析題意，本題是希望構造一個文法，由它產生的句子是奇數，并且不以0開頭,

也就是說它的每個句子都是以1、3、5、7、9中的某個數結尾。如果數字只有一位，則1、

3、5、7、9就滿足要求，如果有多位，則要求第1位不能是0,而中間有多少位，每位是什

么數字(必須是數字)則沒什么要求，因此，我們可以把這個文法分3部分來完成。分別用

3個非終結符來產生句子的第1位、中間部分和最后一位。

引入幾個非終結符，其中，一個用作產生句子的開頭，可以是1一9之間的數，不包括

0；一個用來產生句子的結尾，為奇數：另一個則用來產生以非0整數開頭后面跟任意多個

數字的數字串，進行分解之后，這個文法就很好寫了。)

令S表示不以0開始的奇數集合。

S好〈奇數頭〉〈整數〉〈奇數尾〉I〈奇數頭〉〈奇數尾〉|〈奇數尾〉

〈奇數尾〉1|3|5|7|9

〈奇數頭〉->2|4|6|8|〈奇數尾〉

〈整數〉->〈整數〉〈數字〉|〈數字〉

〈數字〉玲0|〈奇數頭〉

9寫一個上下文無關文法CFG,使其語言是能被5整除且不以0開頭的無符號整數的集合。

（如｛5,10,15,…

答：

能被5整除的數從形式上看，是以。和5結尾的數字串。題目要求的不以0開頭，并要

注意0不是該語言的句子。所求文法為：

G（S）：S—MFI5

Ff5I0

M-MDIN

DfNI0

N-*l|2l3l4l5l6l7l8l9

10證明下面的文法是二義的：

S->iSeSIiSIi

答：（根據文法的二義性的定義，如果要證明該文法是二義的，必須找到一個句子，使得該

句子具有兩個不同的最右推導或兩個不同的語法樹。我們首先分析這個文法，根據我們對程

序語言的了解，不難發現，這個文法應該是用來表示if….else….結構的（用“i”代表“if”

或語句集，“e”代表“else”）.因此我們就要到if….else…結構中去找二義性。我們知道，

程序語言一般都規定else部分是和它前面離它最近的沒有被匹配的的if語句進行匹配。而

上面的這個文法體現不出這種限制，因此我們可以找這樣一個句子，在else前面有兩個if

（如句子iiiei）,else和不同的if進行匹配時就會產生不同的語義。）

解答：

考慮句子iiiei,存在如下兩個最右推導：

S=>iSeS=>iSei=>iiSei=>iiiei

S=>iS=>iiSeS=>iiSei=>iiiei

11某程序設計語言的表達式由運算符61、02s03.標識符、（、）組成，其中和82的優

先級相同，。3的優先級低于91、。2的優先級，優先級相同的運算符從右往左計算，可以用

括號改變運算的順序，則下述四種文法中哪一個可以描述上述的表達式文法？

設E為識別符號，終結符號集=｛也、①、仇、（、）、I｝，非終結符號集=｛E、T、F｝。

a.E玲T|E6iT|Ee2T

T-?F|T03F

F-?(E)|I

b.E^T|T01E|T02E

T^F|F03T

F玲(E)|l

c.E^T|E03T

T^F|TeiF|T62F

F玲(E)|l

d.E->T|T03E

T^F|F0IT|F02T

—(E)11

答：

(對于一個包含運算符的語言，運算符的結合順序、運算符的優先級在文法中反映為遞

歸的方向和推導(或規約)的先后，左遞歸表明左邊的運算先處理，對應的運算符左結合;

右遞歸表明右邊的運算先處理，對應的運算符右結合。兩個運算符連續出現，后推導出(或

先被規約)的，表明其運算先被處理，因此優先級高；反之，先推導出(或后被規約)的,

表明其運算后被處理，因此優先級低。)

題意要求：&和g的優先級相同，1的優先級低于也、外的優先級，因此力比仇、g先推

導出來，即應為圖3所示的四種情形。

圖3可能的文法推導順序

因此a和b不成立。

又因為優先級相同的運算符從右往左計算，應采用右遞歸，即應為圖4所示的情形。

⑴(2(3)

圖4可能的文法遞歸結構

故c不成立，應為do

第三章詞法分析

本章要點

1.詞法分析器設計，

2.正規表達式與有限自動機，

3.詞法分析器自動生成。

本章目標：

1.理解對詞法分析器的任務，掌握詞法分析器的設計；

2.掌握正規表達式與有限自動機；

3.掌握詞法分析器的自動產生。

本章重占.

1.詞法分析器的作用和接口，用高級語言編寫詞法分析器等內容，它們與詞法分析器的實

現有關。應重點掌握詞法分析器的任務與設計，狀態轉換圖等內容。

2.掌握下面涉及的一些概念，它們之間轉換的技巧、方法或算法。

（1）非形式描述的語言0正規式

（2）正規式fNFA（非確定的有限自動機）

（3）NFA—DFA（確定的有限自動機）

（4）DFA-?最簡DFA

本章難點

（1）非形式描述的語言-正規式

（2）正規式-NFA（非確定的有限自動機）

（3）NFA—DFA（確定的有限自動機）

（4）DFA.最簡DFA

作業題

一、單項選擇題

(按照組卷方案，至少15道)

1.程序語言下面的單詞符號中，一般不需要超前搜索

a.關鍵字b.標識符c.常數d.算符和界符

2.在狀態轉換圖的實現中，—一般對應一個循環語句

a.不含回路的分叉結點b,含回路的狀態結點c.終態結點d.都不是

3.用了表示字母，d表示數字，Z={l,d},則定義標識符的正則表達式可以是：。

(a)ld*(b)ll'(c)l(l|d)*(d)H*|d*

4.正規表達式⑻a|W表示的集合是

(a){e,ab.ba,aa,bb}(b){ab,ba,aa>bb}

(c){a,b,ab,aa>ba,bb}(d){e,a,b,aa,bb,ab,ba}

有限狀態自動機可用五元組T來描述，設有一有限狀態自動機的

5.(V，Q,6,q0,Qf)M

定義如下：

T的定義為：

V={0,1},Q={q°，qi，q2}.Qf={q2}-6

6(qo，0)=qi6(q】，0)=q?

6(q2,1)=q26(q2,0)=q2

M所對應的狀態轉換圖為—o

臺旗+-谷利辯琴睡第

6.有限狀態自動機可用五元組(g，Q,8,q0,Qf)來描述，設有一有限狀態自動機M的

定義如下：

VT={0,1},Q={q°，q”q2}.Qf={q2}-6的定義為：

6(q(),0)=qi6(q00)=q2

6(q2,1)=q26(q2,0)=q2

M所能接受的語言可以用正則表達式表示為一。

①(0|1)*(2)00(011)*(3)(011)*00@0(011)*0

7.有限狀態自動機可用五元組Q，8,q0,Qf)來描述，設有一有限狀態自動機M的

定義如下：

VT={0,1},Q={q0，qi，q?}>Qf={q2}>6的定義為：

6(q0,0)=qi6(qi，0)=q2

6(q2，1)=q26(q2,0)=q2

M所能接受的語言為—o

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

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

③以兩個0結束的，由0和1所組成的符號串的集合

④以兩個0開始的，由0和I所組成的符號串的集合

8.從接受語言的能力上來說，非確定型有窮自動機和是等價的。

a.i.正規式；ii.上下文無關文法；iii.確定性有窮自動機；

b.i.左線性正規文法；ii.右線性正規文法；iii.確定性有窮自動機；

c.i.正規式；ii.上下文無關文法；iii.正規文法；

d.i.正規式；ii.確定性有窮自動機；iii.下推自動機；

9.下面四個選項中，關于編譯過程中掃描器的任務的敘述，是較為完整且正確的。

①組織源程序的輸入；按詞法規則分割出單詞，識別其屬性，并轉換成屬性字的形式輸

出；刪除注釋；刪除空格和無用字符；行計數、列計數；發現并定位詞法錯誤；建立符號表。

②按詞法規則分割出單詞，識別其屬性，并轉換成屬性字的形式輸出：發現并定位詞法

錯誤：建立符號表：輸出狀態轉換圖；把狀態轉換圖自動轉換成詞法掃描程序。

③組織源程序的輸入；按詞法規則分割出單詞，識別其屬性，并轉換成屬性字的形式輸

出。

④組織源程序的輸入；按詞法規則分割出單詞，識別其屬性，并轉換成屬性字的形式輸

出；行計數、列計數；發現并定位詞法錯誤；建立符號表；輸出狀態轉換圖；把狀態轉換圖

自動轉換成詞法掃描程序。

10.關于NFA的敘述中，下面是不正確的。

A,有一個有窮字母表B.有多個初始狀態

C.有多個終止狀態D.有多個有限狀態

11.詞法分析的理論基礎是。

A.有窮自動機理論B.圖靈機理論C.圖論D.無窮自動機理論

12.設有兩個狀態S和T,如果從S出發能讀出某個字w而停于終態，那么從T出發也能讀

出同樣的字而停于終態；反之，果從T出發能讀出某個字w而停于終態，那么從S出發也

能讀出同樣的字而停于終態。則我們稱狀態S和狀態T是。

A.可區分的；B.等價的；C.多余的；D.無用的。

13.詞法分析器的輸出結果是。

A、單詞自身值B、單詞在符號表中的位置

C、單詞的種別編碼D、單詞的種別編碼和自身值

14.編譯過程中掃描器的任務包括。

①組織源程序的輸入

②按詞法規則分割出單詞，識別出其屬性，并轉換成屬性字的形式輸出

⑧刪除注解

④刪除空格及無用字符

⑤行計數、列計數

⑥發現并定位詞法錯誤

⑦建立符號表

a.②③④⑦b.②③④⑥⑦c.①②③④⑥⑦d.①②③④⑤⑥⑦

15.下述正則表達式中與(a*+b)*(c+d)等價(即有相同符號串集)。(x+y亦可寫作x|y)

①a*(c+d)+b(c+d)

②a*(c+d)*+b(c+d)*

③a*(c+d)+b(c+d)

④(a+b)*c+(a+b)*d

⑤(a*+b)*c+(a*+b)*d

a.①③b.③④⑤c.③d.④⑤

16、正則式的“*”讀作。

a,并且L或者c.連接d.閉包

17.在狀態轉換圖中，結點代表,用圓圈表示。

a.輸入緩沖區b.向前搜索c.狀態d.字符串

18.與(a|b)*(a|b)等價的正規式是。

A.a*|b*B.(ab)(a|b)*C.(a|b)(a|b)*D.(a|b)*

19.無符號常數的識別和拼數工作通常都在階段完成。

A.詞法分析B.語法分析C.語義分析D.代碼生成

—.答案：1.b；2.b；3.c；4.d；5.②;6.②，7.@；8.b；9.①；10.B；11.A；

12.B；13.d；14.d：15.d；16.d；17.c；18.C；19.A

二、填空題：

(按照組卷方案，至少15道)

1.詞法分析器對掃描緩沖區進行掃描時一般用兩個指示器，一個

:另一個。

2.一個確定性有限自動機DFAM的化簡是指：尋找一個狀態數比M少的DFA使

得O

3.詞法分析器所的輸出常表示成如下形式的二元式：(,

)。

4.一個狀態轉換圖只包含有限個狀態，其中有一個被認為是,而且實際上至少有

一個。

5.把狀態轉換圖用程序實現時，對于含有回路的狀態結點來說，可以讓它對應一個

程序段。

6.詞法分析階段的任務式從左到右掃描,從而逐個識別。

7.如果一個種別只含有一個單詞符號，那么，對于這個單詞符號，就可以完

全代表它自身了。

8.單詞符號的屬性值是指單詞符號的特性或特征，其屬性值則是反映特性或特征的值。比

如，對于某個標識符，常將作為

其屬性值。

9.單詞符號的屬性值是指單詞符號的特性或特征，其屬性值則是反映特性或特征的值。比

如，對于常數，常將作為其屬性

值。

10.如果一個種別含有多個單詞符號，那么，對于它的每個單詞符號，除了給出種別編碼以

外，還應給出有關.

11.如果,則認為這兩個正規式等價。

12.對于2*中的任何符號串a,如果存在一條從初態結點到某一終態結點的通路，

且,則稱a被該自動機所接受(識別)。

13.一個Lex源程序主要包括兩部分，一部分是,另一部分是。

14.一個DFA可用一個矩陣表示，該矩陣的行表示,列表示,矩陣元素表

示。這個矩陣叫狀態轉換矩陣。

15.對于詞法分析程序來說，當程序到達“錯誤處理”時，意味著現行狀態i和當前所面臨

的輸入串不匹配。如果后面還有狀態圖，出現在這個地方的代碼應該為：

二.答案：1.指向當前正在識別的單詞符號的開始位置，用于向前搜索以尋找單詞符號的

終點；2.L(M)=L(M')；3.單詞種別，單詞符號的屬性值；4.初態，終態；5.由while和if

語句構成的；6.源程序，單詞；7.種別編碼；8.存放它的有關信息的符號表項的指針；9.存

放它的常數表項的指針；10.單詞符號的屬性信息(屬性值)；11.兩個正規式所表示的正規

集相同；12.這條通路上所有弧的標記符號連接起來形成的符號串等于a；13.正規定義式，

識別規則；14.狀態，輸入字符，轉換函數(或3(s,a))的值；15.將搜索器回退一個位置，

并令下一個狀態圖開始工作。

三、判斷題：

(按照組卷方案，至少15道)

1.NFAM的非確定性表現在它有多個終態。()

2.有窮自動機接受的語言是正則語言。()

3.若“和「2是Z上的正規式，則3|「2也是。()

4.設M是一個NFA,并且L(M)={x,y,z},則M的狀態數至少為4個。()

5.令Z={a,b},則E上所有以b為首的字符構成的正規集的正規式為b*(a|b)*。()

6.對任何一個NFAM,都存在一個DFAMl使得L(M')=L(M)。()

7.對一個右線性文法G,必存在?個左線性文法G',使得L(G)=L(G'),反之亦然。()

8.對任意一個右線性文法G,都存在一個NFAM,滿足L(G)=L(M)。()

9.對任意一個右線性文法G,都存在一個DFAM,滿足L(G)=L(M)。()

10.對任何正則表達式r,都存在一個NFAM,滿足L(M)=L(r)。()

11.對任何正則表達式r,都存在一個DFAM,滿足L(M)=L(r)。()

12.一張轉換圖只包含有限個狀態，其中有一個被認為是初態，最多只有一個終態。（）

13.一個正規式只能對應一個有限狀態自動機：（）

14.在詞法分析的狀態轉換圖中，有些結點是帶星號的，這些結點肯定是終態結點。（）

15.適當設置掃描緩沖區的大小（比如容納256個字符）可以保證單詞符號不會被它的邊界

所打斷。（）

四.答案：1.X；2.4；3.44.X；5.X；6.J7.48.49.4；10.A/；117；12X；

13.X；14.4；15.X；

四、名詞解釋：

（按照組卷方案，至少5道）

1.狀態轉換圖；

2.正規式（正規表達式、正則表達式）的形式化定義；

3.給出確定性有限狀態自動機的形式化定義；

4.給出非確定性有限狀態自動機的形式化定義；

5.DFA狀態最小化。

四.答案

1.狀態轉換圖是一張有限方向圖，用于識別（或接受）一定的字符串。

在圖中，結點代表狀態，用圓圈表示；狀態之間用箭弧連結；箭弧上的標記（字符）代

表在射出結點（即箭弧的始結點）狀態下可能出現的字符或字符類。

一張狀態轉換圖只包含有限個狀態（即有限個結點），其中一個被認為是初態，而且實

際上至少要有一個終態（用雙圈表示）。

2.正規式是采用遞歸方式來定義的。

（1）￡和0都是正規式；

（2）任何aGZ，a是X上的一個正規式；

（3）假定?■和s都是Z上的正規式，則r|s、rs＞和r*也都是正規式。

3.一個確定有限自動機（DFA）M是一個五元式：M=（S,Z，8,s0,F）,其中：

（1）S是一個有限集合，它的每一個元素稱為一個狀態；

（2）Z是一個有限字母表，它的每一個元素稱為一個輸入字符；

（3）6是一個從SXZ到S的單值部分映射。5（s,a）=s',意思是:當前狀態是s,輸入

字符為a時，自動機將轉入下一個狀態s\s，稱為s的后繼狀態；

（4）s0GS,是自動機的惟一初態；

（5）FcS,是一個終態集合。

一個非確定有限自動機（NFA）M是一個五元式：M=（S,Z，5,S0,F）,其中：

（1）S是一個有限集合，它的每一個元素稱為一個狀態；

（2）Z是一個有限字母表，它的每一個元素稱為一個輸入字符；

（3）6是一個從SX￡到s的子