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

1、2.1考慮文法G[S]其產(chǎn)生式如下:S→(L)|aL→L，S|S(1)試指出此文法的終結(jié)符號(hào)、非終結(jié)符號(hào)。終結(jié)符號(hào)為：()a非終結(jié)符號(hào)為：SL開(kāi)始符號(hào)為：S(2)給出下列各句子的分析樹(shù)：①(aa)②(a(aa))③(a((aa)(aa)))(3)構(gòu)造下列各句子的一個(gè)最左推導(dǎo)：①(aa)S(L)(LS)(SS)(aS)(aa)②(a(aa))S(L)(LS)(SS)(aS)(a(L)(a(LS))(a(SS))(a(aS))(a(aa))

2、③(a((aa)(aa)))S(L)(LS)(SS)(aS)(a(L))(a(LS))(a(SS))(a((L)S))(a((LS)S))(a((SS)S))(a((aS)S))(a((aa)S))(a((aa)(L)))(a((aa)(LS)))(a((aa)(SS)))(a((aa)(aS)))D：E：①(aa)②aa③(a)④a解答：A：①B：③C：①D：②E：④3.13.1有限狀態(tài)自動(dòng)機(jī)可用五元組（VT，Q，δ，q0，Qf）來(lái)描

3、述設(shè)有一有限狀態(tài)自動(dòng)機(jī)M的定義如下：VT=01，Q=q0q1q2，Qf=q2，δ的定義為：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M是一個(gè)A有限狀態(tài)自動(dòng)機(jī)，它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖為B它所能接受的語(yǔ)言可以用正則表達(dá)式表示為C。其含義為D。A:①歧義的②非歧義的③確定的④非確定的B:C：①(0|1)②00(0|1)③(0|1)00④0(0|1)0D：①由0和1所組成的符號(hào)串的集合；②以0為頭符號(hào)和尾符號(hào)