語法復習題(1)

1、一、單項選擇題1如果文法G是無二義的，則它的任何句子 。 Aa. 最左推導和最右推導對應的語法樹必定相同b. 最左推導和最右推導對應的語法樹可能不同c. 最左推導和最右推導必定相同d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同2.語法分析時所依據(jù)的是 。Aa. 語法規(guī)則 b. 詞法規(guī)則 c. 語義規(guī)則 d. 等價變換規(guī)則3文法G：SxSx|y所識別的語言是 。C a. xyx b. (xyx)* c. xnyxn (n0) d. x*yx*4.由文法的開始符號出發(fā)經(jīng)過若干步（包括0步）推導產(chǎn)生的文法符號序列稱為_B_。A語言 B句型 C句子 D句柄5在自上而下的語法分析中，應從 C

2、開始分析。A句型B句子C文法開始符號D句柄6.文法G：S x xS | y 所識別的語言是（ D）。Axxy* B(xxy)* Cxx*yx D(xx)*y7.文法G：S xS | y 所識別的語言是（ D）。Axy* B(xy)* Cxx*yx Dx*y8.設有文法GT:TT*F|FFFP|PP(T)|a該文法句型T*P(T*F)的句柄是下列符號串（ C ）A.（T*F） B. T*F C. P D. P(T*F)9.最左簡單子樹的葉結(jié)點，自左至右排列組成句型的_C_。A短語 B句型 C句柄 D間接短語二、填空題語法分析部分：（基本概念、遞歸下降子程序）1 語法分析的方法通常分為兩類： 自上

3、而下分析方法 和 自下而上分析方法 。2文法中的終結(jié)符集和非終結(jié)符集的交集是 空集 。3一個句型的最左直接短語稱為該句型的_句柄_。4常用的自上而下語法分析方法有遞歸下降子程序方法和預測分析表方法（LL（1）方法）。5關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：AA|，其中、是任意的符號串且不以A開頭，則可以將A的產(chǎn)生式改寫為右遞歸的形式為： AA , AA|000000000000000000000000 。6在消除回溯，提取公共左因子時，關(guān)于A的產(chǎn)生式A 1 | 2 | | i | i+1 | | j，可以改寫為： A A | i+1 | | j ， A 1 | |i 。7設GS 是一文法，如果符號

4、串x是從識別符號推導出來的，即有x，則稱x是文法GS的_句型_，若x僅由終結(jié)符號組成，即，則稱x為文法GS的_句子 。三、判斷題（第1，2章，第三章概念，遞歸下降子程序）1設r和s分別為正規(guī)式，則有L(r|s) = L(r) | L(s).。( )2一個文法的所有句型的集合形成該文法所能接受的語言。( )3語法分析之所以采用上下文無關(guān)文法是因為它的描述能力最強。( )4自動機M和M的狀態(tài)個數(shù)不同，則二者必不等價。( )5最左推導也被稱為規(guī)范推導。（ ）6用高級語言編寫的源程序必須經(jīng)過編譯，產(chǎn)生目標程序后才能運行。（ ）7對于任何一個正規(guī)式e，都存在一個DFA A，使得L（e）=L（A）。（ ）

5、8最小化的DFA，它的狀態(tài)數(shù)最小。（ ）9NFA的確定化算法具有消除邊的功能。（ ）10每個非終結(jié)符產(chǎn)生的終結(jié)符號串都是該語言的子集。（ ）11一個語言的文法是不唯一的。（ ）12語法錯誤校正的目的是為了把錯誤改正過來。（ ）13源程序和目標程序是等價關(guān)系。（ ）14編譯程序中錯誤處理的任務是對檢查出的錯誤進行修改。（ ）15使用有限自動機可以實現(xiàn)單詞的識別。（ ）16一個非確定的有限自動機NFA可以通過多條路徑識別同一個符號串。（ ）17最小化的DFA所識別接受的正規(guī)集最小。（ ）18一個語言（如C語言）的句子是有窮的。（ ）19語法分析器可以檢查出程序中的所有錯誤。（ ）三、多項選擇題1.

6、 編譯器的各個階段的工作都涉及到（AE）A. 表格處理 B. 詞法分析C. 語法分析 D. 語義分析 E. 出錯處理2. 令Sa,b，則S上的符號串的全體可用下面的正規(guī)式表示。（ABE）A. (a|b)* B. (a*|b*)*C. (a|b)+ D. (ab)* E. (a*b*)*3. 自上而下的分析方法有：（AD）A. 遞歸下降分析法 B. LR（0）分析法C. LALR（1）分析法 D. LL（1）分析法E. SLR（1）分析法4.文法G：GS：SCDAbbA CaCABaaB CbCBBbbB ADaDC BDbDD AabD是（ABE）。A. 0型文法 B. 1型文法C. 2型文法

7、 D. 3型文法 E. 上下文有關(guān)文法5.一個編譯器可能有的階段為（ABCDE）A. 詞法分析 B. 語法分析C. 語義分析 D. 中間代碼生成E. 目標代碼生成6. 令Sa,b，則S上的所有以b開頭，后跟若干個（可為0個）ab的符號串的全體可用下面的正規(guī)式表示。（AB）A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)*7. 一般來說，編譯器可分為前端和后端，下列編譯階段可被劃分為編譯的前端的有：（ABCDE）A. 詞法分析 B. 語法分析C. 語義分析 D. 中間代碼生成 E. 中間代碼優(yōu)化8下列符號串是符號集Sa,b上的正規(guī)式的有：（A

8、BCDE）A. B.a C.ab D.(aba) (aba)E.abab9正規(guī)式服從的代數(shù)規(guī)律有：（ABDE）A. “或”運算服從交換律 B. “或”運算服從結(jié)合律C. “連接”運算服從交換律 D. “連接”運算服從結(jié)合律E. “連接”運算可對“或”運算進行分配10 令Sa,b，則S上的所有以b開頭，后跟若干個（可為0個）ab的符號串的全體可用下面的正規(guī)式表示。（AB）A.b (ab)* B. (ba)*b C. b(a|b)+D. (ba)+b E. b (a|b)*五簡答題1令文法GN為 GN: ND|ND D0|1|2|3|4|5|6|7|8|9給出句子568的最左、最右推導。解：最左推

9、導：N ND NDD DDD 5DD 56D 568最右推導：N ND N8 ND8 N68 D68 5682給出字母表=a,b上的同時只有奇數(shù)個a和奇數(shù)個b的所有串的集合的正規(guī)文法；解： GS：SaA|bBAaS|bC|bBbS|aC|aCbA|aB|3對于文法GE: EE+T | TTT+P | PP(E) | i寫出句型P+T+(E+i)的所有短語、直接短語、句柄。解：短語：P、P+T、i、E+i、(E+i )、P+T+(E+i )；直接短語：P、i；句柄：P；4已知文法GS: SaSbS|bSaS|試證明GS是二義文法證明： 該文法產(chǎn)生的語言是a的個數(shù)和b的個數(shù)相等的串的集合。該文法二

10、義，例如句子abab有兩種不同的最左推導。 SaSbSabSabaSbSababSabab SaSbSabSaSbSabaSbSababSabab5構(gòu)造一文法，使其描述的語言L = | (a, b)*，且中含有相同個數(shù)的a和b。解：S | aA|bBA b| bS| aAAB a| aS| bBB6已知文法G(S)：SS*aP| aP| *aPP+aP| +a(1) 將文法G(S)改寫為確定的文法G(S)；解：（1）消除左遞歸，文法變?yōu)椋?SaPS| *aPS S *aPS | P+aP| +a提取公共左因子，文法變?yōu)镚(S)： SaPS| *aPS S *aPS |P+aPPP| 7設有文法GS:Sa|（T）|eTT,S|S試給出句子(a,a,a)的最左推導?！窘狻?1) (a,a,a)的最左推導S=(T) =(T,S) =( T,S,S) =( S,S,S) =(a,S,S) =(a,a,S) =(a,a,a)8設有文法GS:SS*S|S+S|(S)|i該文法是否為二義文法,并說明理由？【解】該文法是二義文法，因為該文法存在句子i*i+i,該句子有兩棵不同的語法樹如圖所示。9設有如下文法：GE：EEWT|T TT/F|F F（E）|a|b|c W+|-證明符號串a(chǎn)/(