【正文】 前面有0個或多個1。根據(jù)分析，可以把本題分成兩種情況考慮：一種情況時該整數(shù)只有一位，則該整數(shù)有0和5兩種可能；另一種情況是該整數(shù)有多位，則該整數(shù)可以分成三部分考慮：一是第一位必須不為0；二是最后一位必須為0或5；三是中間部分可有可無，并且可以由0到9之間任意數(shù)字構成，所以所求為(1︱2︱3︱4︱5︱6︱7︱8︱9) (0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱5)。解：（1）以01結尾的二進制數(shù)串； 分析題意，要求的是二進制數(shù)串，即由0和1構成的串，并且必須以01結尾，所以本題可以分兩步完成：一部分實現(xiàn)由0和1構成的任意串，一部分即01，然后將它們連結在一起就可以了，所以所求為(1︱0)*01。所以最終劃分結果為5個集合：{0}，{1，2}，{3}，{4}，{5}。 檢查集合{1，2，3}，{1，2，3}0={2，4}，不屬于同一個集合，因此要對集合{1，2，3}進行進一步劃分，劃分結果為5個集合：{0}，{1，2}，{3}，{4}，{5}。 {0，1，2，3，4}0={2，4，}，{0，1，2，3，4}1={1，3，5} 因為{1，3，5}和{2，4，}不在一個集合里面，所以需要對集合{0，1，2，3，4}進行進一步的劃分，檢查其中的所有狀態(tài)。{1，2，3}{1，2，3}{2，3}{2，3，4}{2，3}{2，3}{2，3，4}{2，3，4}{2，3，5}{2，3，4}{2，3，5}{2，3}{2，3，4，Y}{2，3，4，Y}{2，3，5}{2，3，4} 根據(jù)轉換矩陣獲得相應的DFA：01234100010111501 第三步：化簡該DFA，獲得最簡的DFA即為所求。 L(ε∣A A*)=L(ε)∪L(A)L(A*)= L(ε)∪L(A)(L(A) )* =L(ε)∪L(A)((L(A))0∪(L(A))1∪(L(A))2∪(L(A))3∪…) =L(ε)∪(L(A))1∪(L(A))2∪(L(A))3∪(L(A))4∪… =(L(A))*=L(A*) 即：L(ε∣A A*)=L(A*)，所以有：A*=ε∣A A* （4）、(AB)*A=A(BA)* 利用正規(guī)式的分配率和結合律直接推導。 令A、B和C是任意正規(guī)式，證明以下關系成立： A∣A=A (A*)*= A* A*=ε∣A A* (AB)*A=A(BA)* (A∣B)*=(A*B*)*=(A*∣B*)* A=b∣aA當且僅當A=a*b證明： （1）、A∣A=A L(A∣A)=L(A)∪L(A)=L(A)，所以有A∣A=A。 用某種高級語言編寫并調試一個完整的詞法分析器。 請給出以下C++程序段中的單詞符號及其屬性值。 解： L1的文法：S→AC；A→aAb∣ab；C→cC∣ε L2的文法：S→AB；A→aA∣ε；B→bBc∣bc L3的文法：S→AB；A→aAb∣ε；B→aBb∣ε L4的文法： S→1S0∣A； A→0A1∣ε；第三章 詞法分析 編寫一個對于Pascal源程序的預處理程序。 L4不能采用分段處理的方式，它要求中間的0和1的個數(shù)相同，而且一前一后的0和1的個數(shù)相同。因此可以模仿L1生成L2。因此我們可用一個非終結符去生成anbn串，用另外一個非終結符去生成ci。我們將該產(chǎn)生式改造成等價的遞歸結構，消除二義性。 解：考慮句子iiiei，存在如下兩個最右推導： S=iSeS=iSei=iiSei=iiiei S=iS=iiSeS=iiSei=iiiei 由此該文法是二義的。我們知道，程序語言一般都規(guī)定else部分是和它前面離它最近的沒有被匹配的if語句進行匹配。我們首先分析這個文法，根據(jù)我們對程序語言的了解，不難發(fā)現(xiàn)這個文法應該是用來表示if…else…結構的（用“i”表示“if”或語句集，用e代表else）。 解： G(S)：A→2∣4∣6∣8∣D B→A∣0 C→CB∣A D→1∣3∣5∣7∣9 S→CD∣D令文法為E→T∣E+ T∣ET T→F∣T*F∣T/F F→(E)∣i（1） 給出i+i*i、i*(i+i)的最左推導和最右推導；（2） 給出i+i+i、i+i*i和iii的語法樹。因此我們可以把這個文法分3部分完成，分別用3個非終結符來產(chǎn)生句子的第一位、中間部分和最后一位。也就是說它的每個句子都以9中某數(shù)結尾。 （2）、句子01234和568的最左推導： N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127 N=ND=DD=3D=34 N=ND=NDD=DDD=5DD=56D=568 句子01234和568的最右推導： N=ND=N7=ND7=N27=ND27=N127=D127=0127 N=ND=N4=D4=34 N=ND=N8=ND8=N68=D68=568寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。因此，N最終推導出的是由0到9這10個數(shù)字組成的字符串。 解： （1）、1＋1*2↑*1↑2 = 2*2↑*1↑2 = 4↑*1↑2 = 4↑↑2 = （2）、1＋1*2↑*1↑2 = 令文法G6為N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9 （1）、G6的語言L(G6)是什么？ （2）、給出句子01234和568的最左推導和最右推導。令 ＋、* 和↑代表加、乘和乘冪，按如下的非標準優(yōu)先級和結合性質的約定，計算1＋1*2↑*1↑2的值： （1）、優(yōu)先順序（從高至低）為＋、* 和↑，同級優(yōu)先采用左結合。編譯原理課后習題（修訂版）第二章 高級語言及其語法描述何謂“標識符”，何謂“名字”，兩者的區(qū)別是什么？ 解：標識符是高級語言中定義的字符串，一般是以英文字母（包括大小寫字母）或下劃線開頭的，由數(shù)字、字母和下劃線組成的一定長度的字符串，它只是一個標志，沒有其他含義。名字是用標識符表示的，但名字不僅僅是一個字符串，它還具有屬性和值。 （2）、優(yōu)先順序為↑、＋、*，同級優(yōu)先采用右結合。 分析：根據(jù)產(chǎn)生式N→D∣ND可以看出，N最終可推導出1個或多個（可以是無窮多個）D，根據(jù)產(chǎn)生式D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9可以看出，每個D可以推導出0至9中的某一個數(shù)字。 解： （1）、L(G6)是由0到9這10個數(shù)字組成的字符串。 分析：本題要構造一個文法，由它產(chǎn)生的句子是奇數(shù)，且不以0開頭。如果數(shù)字只有一位，則滿足要求；如果有多位，則要求第一位不能是0；而中間有多少位，每位是什么數(shù)字則沒有要求。引入幾個非終結符，其中，一個用作產(chǎn)生句子的開頭，可以是1到9中的數(shù)，不包括0；一個用來產(chǎn)生句子的結尾，為奇數(shù)；另一個則用來產(chǎn)生以非0整數(shù)開頭后面跟任意多個數(shù)字的數(shù)字串，進行分解之后，這個文法就很好寫了。解：（1） 最左推導為： E = E+T = T+T = F+T = i+T = i+T*F = i+F*F = i+i*F = i+i*i E = T = T*F = F*F = i*F = i*(E) = i*(E+ T) = i*(T+ T) = i*(F+ T) = i*(i+ T) = i*(i+ F) = i*(i+ i) 最右推導為： E =E+T =E+T*F =E+T*i =E+F*i =E+i*i = T+i*i = F+i*i = i+i*i E = T = T*F = F*F = F*(E) = F*(E+T) = F*(E+ F) = F*(E+ i) = F*(T+i) = F*(F+i) = F*(i+i) = i*(i+ i)（2） 語法樹：FTETE+EFi+TFiiE+TEFi*TFiTFiEETEFiTFiFi證明下面的文法是二義的：S→iSeS∣iS∣i 分析：根據(jù)文法二義性定義，如果要證明該文法是二義的，必須找到一個句子，使該句子具有兩個不同的最右推導或兩個不同的語法樹。因此我們就要到if…else…結構中去找二義性。而上面的這個文法體現(xiàn)不出這種限制，因此我們可以找這樣一個句子，在else前面有兩個if（如句子iiiei），else和不同的if進行匹配時就會產(chǎn)生不同的語義。把下面文法改為無二義的：S→SS∣(S)∣( ) 分析：本題給出的文法是二義的，關鍵在于S→SS是產(chǎn)生二義性的根源。 解：S→TS∣T，T→(S)∣( )1給出下面語言的相應文法： L1={anbnci∣n≥1，i≥0}， L2={aibn∣n≥1，i≥0} L3={anbnambm∣n，m≥0} L4={1n0m1m0n∣n，m≥0} 分析：語言L1要求a和b的個數(shù)一樣多，且至少為一個；c的個數(shù)為0個以上。 語言L2要求b和c的個數(shù)一樣多，因此可用一個非終結符去生成bn，而使用另外一個非終結符去生成ai。 對于L3，可將anbnambm分兩段考慮，即anbn和ambm，然后用兩個非終結符分別去產(chǎn)生他們。對于這種題型我們可以采用從里向外擴展的方式進行，即先用一個非終結符生成處于中間的m個0和m個1，然后，使用另外一個非終結符在該串的基礎上擴充前后的n個0和n個1。該程序的作用是，每次被調用時都將下一個完整的語句送進掃描緩沖區(qū)，去掉注釋行，同時要對源程序列表打印。 int CInt：：nMulDiv（int n1，int n2） { if （n3= =0）return 0； else return（n1*n2）/n3； } 用類似C或Pascal的語言編寫過程GetChar，GetBC和Concat。 、結合律等五個關系。 （2）、(A*)*= A* （3）、A*=ε∣A A* 通過證明兩個正規(guī)式所表示的語言相同來證明兩個正規(guī)式相等。 (AB)*A=((AB)0∣(AB)1∣(AB)2∣(AB)3∣…)A =εA∣(AB)1A∣(AB)2A∣(AB)3A∣… =Aε∣A (BA)1∣A (BA)2∣A (BA)3∣… =A(ε∣(BA)1∣(BA)2∣(BA)3∣…) =A(BA)* 即：(AB)*A=A(BA)* （5）、(A∣B)*=(A*B*)*=(A*∣B*)*證明:先證(A∣B)*=(A*B*)*因為L(A)L(A) *L(B) *,L(B) L(A) *L(B) *故:L(A) ∪L(B) L(A) *L(B) *于是由本題第二小題結論可知(L(A)∪L(B)) *(L(A) *L(B)*)* ①又L(A)L(A)∪L(B), L(B) L(A)∪L(B)故:L(A)*(L(A)∪L(B))* L(B)*(L(A)∪L(B))*因此有:L(A)*L(B)* (L(A)∪L(B))* (L(A)∪L(B))*=( (L(A)∪L(B))*) 2故(L(A)*L(B)*)*((L(A)∪L(B))*)*由本題第二小題得: ((L(A)∪L(B))*)*= (L(A)∪L(B)) * 故得: (L(A)*L(B)*)*(L(A)∪L(B)) * ②則由①②得: (L(A)∪L(B)) *=(L(A)*L(B)*)*由于L((A*B*))*=(L(A*B*))*=(L(A*)L(B*))*=(L(A)*L(B)*)*即有(L(A)∪L