哈工大編譯原理習題及答案

何謂源程序、目標程序、翻譯程序、編譯程序和解說程序它們之間可能有何種關(guān)系一個典型的編譯系統(tǒng)往常由哪些部分構(gòu)成各部分的主要功能是什么選擇一種你所熟習的程序設計語言，試列出此語言中的所有重點字，并經(jīng)過上機使用該語言以判明這些重點字能否為保存字。選用一種你所熟習的語言，試對它進行剖析，以找出此語言中的括號、重點字不一樣的用途。

END以及逗號有多少種試用你常用的一種高級語言編寫一短小的程序，上機進行編譯和運轉(zhuǎn)，記錄下操作步驟和輸出信息，假如可能，請卸出中間代碼和目標代碼。第一章習題解答解：源程序是指以某種程序設計語言所編寫的程序。目標程序是指編譯程序（或解說程序）將源程序辦理加工而得的另一種語言（目口號言）的程序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與解說程序均為翻譯程序，但二者工作方法不一樣。解說程序的特色是其實不先將高級語言程序所有翻譯成機器代碼，而是每讀入一條高級語言程序語句，就用解說程序?qū)⑵浞g成一段機器指令并履行之，而后再讀入下一條語句持續(xù)進行解說、履行，這樣頻頻。即邊解說邊履行，翻譯所得的指令序列其實不保存。編譯程序的特色是先將高級語言程序翻譯成機器語言程序，將其保存到指定的空間中，在用戶需要時再履行之。即先翻譯、后履行。解：一般說來，編譯程序主要由詞法剖析程序、語法剖析程序、語義剖析程序、中間代碼生成程序、代碼優(yōu)化程序、目標代碼生成程序、信息表管理程序、錯誤檢查辦理程序構(gòu)成。3.解：C語言的重點字有：autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述重點字在C語言中均為保存字。4.解：C語言中括號有三種：{}，[]，（）。此中，{}用于語句括號；[]用于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達式運算（改變運算次序）。C語言中無END重點字。逗號在C語言中被視為分開符和運算符，作為優(yōu)先級最低的運算符，運算結(jié)果為逗號表達式最右邊子表達式的值（如：(a,b,c,d)的值為d）。略第二章前后文沒關(guān)文法和語言設有字母表A1={a,b,,z}，A2={0,1,,9}，試回答以下問題：字母表A1上長度為2的符號串有多少個會合A1A2含有多少個元素(3)列出會合A1(A1∪A2)*中的所有長度不大于3的符號串。試分別結(jié)構(gòu)產(chǎn)生以下語言的文法。{anbn|n≥0}；{anbmcp|n,m,p≥0}；(3){an#bn|n≥0}∪{cn#dn|n≥0}；(4){w#wr#|w∈{0,1}*，wr是將w中的符號按逆序擺列所得的符號串}；任何不是以0開始的所有奇整數(shù)所構(gòu)成的會合；所有由偶數(shù)個0和偶數(shù)個1所構(gòu)成的符號串的會合。23試描繪由以下文法所產(chǎn)生的語言的特色(文法的開始符號均為S)。S→10S0S→aAA→bAA→aS→SSS→1A0A→1A0A→εS→1AS→B0A→1AA→CB→B0B→CC→1C0C→εS→bAdcA→AGSG→εA→aS→aSSS→a24設已給文法G=(VN,VT,P,S)，此中：VN={S}VT={a1,a2,,an,∨,∧,~,［,］}P={S→ai|i=1,2,,n}∪{S→~S,S→［S∨S］,S→［S∧S］}，試指出此文法所產(chǎn)生的語言。25觀察文法G=(VN,VT,P,S)，此中：VN={S,A,B,C,D,E,F,G}VT={a},P={S→ABC,C→BC,C→A,BA→GE,BG→GBF,AG→AD,DB→BD,DE→AE,FB→BF,FE→Ea,AA→ε}指出此文法的種類；證明此文法所產(chǎn)生的語言為L(G)={at(n)|n≥1}t(n)=∑n[]i=1i26設已給文法G［〈程序〉］：〈程序〉→〈分程序〉|〈復合語句〉〈分程序〉→〈無標號分程序〉|〈標號〉：〈分程序〉〈復合語句〉→〈無標號復合語句〉|〈標號〉：〈復合語句〉〈無標號分程序〉→〈分程序首部〉；〈復合尾部〉〈無標號復合語句〉→begin〈復合尾部〉〈分程序首部〉→begin〈說明〉|〈分程序首部〉；〈說明〉〈復合尾部〉→〈語句〉end|〈語句〉；〈復合尾部〉〈說明〉→d〈語句〉→s〈標號〉→L給出句子L:L:begind;d;s;send的最左推導和最右推導。畫出上述句子的語法樹。設已給文法G［S］：S→aAcBS→BdSB→aScAB→cABA→BaBA→aBcA→aB→b試查驗以下符號串中哪些是G［S］中的句子，給出這些句子的最左推導、最右推導和相應的語法樹。aacbaabacbadcdaacbccbaacabcbcccaacdcaaacabcbcccaacbca28設G=(VN,VT,P,S)為CFG，α1,α2,,αn為V上的符號串，試證明：若α1α2αn*β則存在V上的符號串β1,β2，,βn，使β=β1β2βn，且有ai*βi(i=1,2,,n)29設G=(VN,VT,P,S)為CFG，α和β都是V上的符號串，且α*β，試證明：當α的首符號為終結(jié)符號時，β的首符號也必為終結(jié)符號；當β的首符號為非終結(jié)符號時，則α的首符號也必為非終結(jié)符號。210試證明：文法S→ABS→DCA→aAA→aB→bBcB→bcC→cCC→cD→aDbD→ab為二義性文法。關(guān)于以下的文法和相應的句子，試指出這些句子的所有短語；分別給出句子的最右推導，并指出各步直接推導所得句型的句柄。S→ABS→cA→bAA→aB→aSbB→cbbaacbS→(AS)S→(b)A→(SaA)A→(a)(((b)a(a))(b))E→ET+E→TT→TF*T→FF→FP↑F→PP→EP→iiii*i+↑212在自底向上的剖析中，用來歸約句型句柄的產(chǎn)生式稱為句柄產(chǎn)生式。試證明：一個文法是無二義性的，當且僅當此文法的每一句型至多只有一個句柄和一個句柄產(chǎn)生式?；喴韵赂鱾€文法。S→aABSS→bCACdA→bABA→cSAA→cCCB→bABB→cSBC→cSC→cS→aABS→EA→dDAA→eB→bEB→fC→cABC→dSDC→aD→eAE→fAE→gS→acS→bAA→cBCB→SAC→bCC→d214消去以下文法中的ε產(chǎn)生式。S→aASS→bA→cSA→εS→aAAA→bAcA→dAeA→ε消去以下文法中的無用產(chǎn)生式和單產(chǎn)生式。(1)S→aBS→BCA→aAA→cA→aDbB→DBB→CD→BC→b(2)S→SAS→SBA→BB→［S］A→(S)S→AB→［］A→( )E→E+TE→TT→T*FT→FF→P↑FF→PP→(E)P→i第二章習題解答1.（1）答：26*26=6762）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658個2.結(jié)構(gòu)產(chǎn)生以下語言的文法（1）{anbn|n≥0}解：對應文法為G(S)=({S},{a,b},{S→ε|aSb},S)（2）{anbmcp|n,m,p≥0}解：對應文法為G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{an#bn|n≥∪0}{cn#dn|n≥0}解：對應文法為G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S)（4）{w#wr#|w{0,1}*,wr是w的逆序擺列}解：G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S)（5）任何不是以0打頭的所有奇整數(shù)所構(gòu)成的會合解：G(S)=({S,A,B,I,J},{,0,1,2,3,4,5,6,7,8,9},{S-→J|IBJ,B→0B|IB|e,I→J|2|4|6|8,Jà1|3|5|7|9},S)6）所有偶數(shù)個0和偶數(shù)個1所構(gòu)成的符號串會合解：對應文法為S→0A|1B|e，A→0S|1CB→0C|1SC→1A|0B3.描繪語言特色1）S→10S0S→aAA→bAA→a解：本文法構(gòu)成的語言集為：L(G)={(10)nabma0n|n,m。≥0}2）S→SSS→1A0A→1A0A→ε解：L(G)={1n10n11n20n21nm0nm|n1,n2,；,nm且≥0n1,n2,nm不全為零}該語言特色是：產(chǎn)生的句子中，0、1個數(shù)相同，而且若干相接的1后必定緊接數(shù)目相同連續(xù)的0。3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε解：本文法構(gòu)成的語言集為：L(G)={1p1n0n|p≥1,n∪≥{1n0n0q|q0}≥1,n≥，特0}點是擁有1p1n0n或1n0n0q形式，進一步，可知其擁有形式1n0mn,m≥0,且n+m>0。4）S→bAdcA→AGSG→εA→a解：可知，S=>=>baSndcn≥0該語言特色是：產(chǎn)生的句子中，是以ba開頭dc結(jié)尾的串,且ba、dc個數(shù)相同。5）S→aSSS→a解：L(G)={a(2n-1)|n≥可1}知：奇數(shù)個a4.解：此文法產(chǎn)生的語言是：以終結(jié)符a1、a2an為運算對象，以∧、∨、~為運算符，以[、]為分隔符的布爾表達式串5.解：因為此文法包含以下規(guī)則：AA→e，所以此文法是0型文法。證明：略6.解：（1）最左推導：<程序>T<分程序>T<標號>：<分程序>TL：<分程序>TL：<標號>：<分程序>L：L：<分程序>TL：L：<無標號分程序>TL：L：<分程序首部>；<復合尾部>TL：L：<分程序首部>；<說明>；<復合尾部>L：L：begin<說明>；<說明>；<復合尾部>TL：L：begind；<說明>；<復合尾部>TL：L：begind；d；<復合尾部>TL：L：begind；d；<語句>；<復合尾部>L：L：begind；d；s；<復合尾部.TL：L：begind；d；s；<語句>endTL：L：begind；d；s；send最右推導：<程序>T<分程序>T<標號>：<分程序>T<標號>：<標號>：<分程序>T<標號>：<標號>：<無標號分程序>T<標號>：<標號>：<分程序首部>；<復合尾部>T<標號>：<標號>：<分程序首部>；<語句>；<復合尾部>T<標號>：<標號>：<分程序首部>；<語句>；<語句>；endT<標號>：<標號>：<分程序首部>；<語句>；s；endT<標號>：<標號>：<分程序首部>；s；s；endT<標號>：<標號>：<分程序首部>；說明；s；s；endT<標號>：<標號>：<分程序首部>；d；s；s；endT<標號>：<標號>：begin說明；d；s；s；endT<標號>：<標號>：begind；d；s；s；endT<標號>：L：begind；d；s；s；endTL：L：begind；d；s；s；end（2）句子L：L：begind；d；s；send的相應語法樹是：7.解：aacb是文法G[S]中的句子，相應語法樹是：最右推導：S=>aAcB=>aAcb=>aacb最左推導：S=>aAcB=>aacB=>aacb2）aabacbadcd不是文法G[S]中的句子因為文法中的句子不行能以非終結(jié)符d結(jié)尾3）aacbccb不是文法G[S]中的句子可知，aacbccb僅是文法G[S]的一個句型的一部分，而不是一個句子。4）aacabcbcccaacdca不是文法G[S]中的句子因為終結(jié)符d后必定要跟終結(jié)符a，所以不行能出現(xiàn)dc這樣的句子。5）aacabcbcccaacbca不是文法G[S]中的句子由（1）可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符

c后不行能跟非終結(jié)符

S，所以不可能出現(xiàn)caacb這樣的句子。8.證明：用概括法于n，n=1時，結(jié)論明顯成立。設n=k時，關(guān)于α1α2...α存kT*b,在βi：i=1,2,..,k，αiT*bi成立，此刻設α1α2...b的一個后綴

αkα，k+1T*b因文法是前后文沒關(guān)的，所以α1α2...可αk推導出b的一個前綴=b"(不如稱為bk+1)。由概括假定，關(guān)于b'，存在βi：i=1,2,..,k，b'=

b'，αk+1可推導出β1β2...使得βk,iT*bi成立，此外,我們有αk+1T*b"(=bk+1）。即n=k+1時亦成立。證畢。9.證明：(1)用反證法。假定α首符號為終結(jié)符時，β的首符號為非終結(jié)符。即設：α=aω；β=Aω’且α=>*。β由題意可知：α=aωTTAω’，由=β于文法是CFG，終結(jié)符a不行能被替代空串或非終結(jié)符，所以假定有誤。得證；（2）同（1），假定：β的首符號為非終結(jié)符時，α首符號為終結(jié)符。即設：α=aω；β=Aω’且α=aωTTAω’，=β與（1）同理，得證。10.證明：因為存在句子：abc，它對應有兩個語法樹（或最右推導）：STABTAbcTabcSTDCTDcTabc所以，本文法擁有二義性。11.解：(1)STABTAaSbTAacbTbAacbTbbAacbTbbaacb上邊推導中，下劃線部分為目前句型的句柄。對應的語法樹為：所有的短語：第一個a(a1)是句子bbaacb相關(guān)于非終結(jié)符A(A1)(產(chǎn)生式Aa）的短語（直接短語）；b1a1是句子bbaacb相關(guān)于非終結(jié)符A2的短語；b2b1a1是句子bbaacb相關(guān)于非終結(jié)符A3的短語；c是句子bbaacb相關(guān)于非終結(jié)符S1（產(chǎn)生式Sc）的短語（直接短語）；a2cb3是句子bbaacb相關(guān)于非終結(jié)符B的短語；b2b1a1a2cb3是句子bbaacb相關(guān)于非終結(jié)符S2的短語；注：符號的下標是為了描繪方便加上去的。（2）句子（（（b）a（a））（b））的最右推導：ST（AS）T（A（b））T（（SaA）（b））T（（Sa（a））（b））T（（（b）a（a））（b））相應的語法樹是：（3）解：iii*i+↑應的語法樹略。對最右推導：ETT=>F=>FP↑TFE↑TFET+↑TFEF+↑TFEP+↑TFEi+↑TFTi+↑TFTF*i+↑TFTP*i+↑TFTi*i+↑TFFi*i+↑TFPi*i+↑TFii*i+↑TPii*i+↑Tiii*i+↑12.證明：充分性：目前文法下的每一符號串僅有一個句柄和一個句柄產(chǎn)生式T對目前符號串有獨一的最左歸約T對每一步推導都有獨一的最右推導T有獨一的語法樹。必需性：有獨一的語法樹T對每一步推導都有獨一的最右推導T對目前符號串有獨一的最左歸約T目前文法下的每一符號串僅有一個句柄和一個句柄產(chǎn)生式13.化簡以下各個文法1）解：S→bCACdA→cSA|cCCC→cS|c（2）解：S→aAB|fA|gA→e|dDAD→eAB→f3）解：S→ac14.除去以下文法中的ε產(chǎn)生式（1）解：S→aAS|aS|bA→cS（2）解：S→aAA|aA|aA→bAc|bc|dAe|de15.除去以下文法中的無用產(chǎn)生式和單產(chǎn)生式（1）除去后的產(chǎn)生式以下：S→aB|BCB→DB|bC→bD→b|DB（2）除去后的產(chǎn)生式以下：S→SA|SB|（）|（S）|[]|[S]A→( )|（S）|[]|[S]Bà[]|[S]（3）除去后的產(chǎn)生式以下：E→E+T|T*F|(E)|P↑F|iT→T*F|(E)|P↑F|iF→P↑F|(E)|iP→(E)|i第三章詞法剖析及詞法剖析程序試用某種高級語言編寫一個FORTRAN源程序的預辦理子程序，其功能是：每調(diào)用它一次，即把源程序中的一個完好語句送入掃描緩沖區(qū)。要求刪去語句中的說明行；刪去續(xù)行標志字符，把語句中的各行連結(jié)起來，并在語句的尾端加上語句結(jié)束符。其他，還要求此程序擁有組織源程序列表輸出的功能。畫出用來辨別以下三個重點字的狀態(tài)轉(zhuǎn)移圖。STEPSTRINGSWITCH假定有一個獵人帶著一只狼、一頭山羊和一棵白菜到達一條河的左岸，擬擺渡過河，而岸邊只有一條小船，其大小僅能裝載人和其他三件東西中的一件，也就是說，每一次獵人只好將隨行者中的一件帶到此岸。若獵人將狼和山羊留在同一岸上而無人照料，那么，狼就會將羊吃掉；假如獵人把山羊和白菜留在同一岸，山羊也會把白菜吃掉。此刻，請你用狀態(tài)變換圖作為工具，描繪獵人可能采納的各種擺渡方案，并從中找出可將上述三件東西安全地帶到右岸的方案來。設已給文法G=(VN,VT,P,S)，此中，P僅含形如A→αBA→αα∈V*T，B∈VN的產(chǎn)生式，試證明：由此種文法所產(chǎn)生的語言是一正規(guī)語言。試證明：任何有限個符號串所構(gòu)成的會合L={x1,x3,,xn}xi∈Σ+都是3型語言。試結(jié)構(gòu)一右線性文法，使得它與以下的文法等價S→ABA→UTU→a|aUT→b|bTB→c|cB并依據(jù)所得的右線性文法，結(jié)構(gòu)出相應的狀態(tài)變換圖。關(guān)于如題圖37所示的狀態(tài)變換圖寫出相應的右線性文法；指出它接受的最短輸入串；隨意列出它接受的此外四個輸入串；隨意列出它拒絕接受的四個輸入串。題圖37關(guān)于有限自動機M=(K,Σ,S0,Z),f此中，K={S0,S1,S2,S3,S4,S5},Σ={a,b},Z={S1,S4,S5}。由以下的狀態(tài)轉(zhuǎn)移矩陣給出：[]a[]bS0[]S2[]S1S1[]S3[]S1S2[]S0[]S4S3[]S0[]S0S4[]S5[]S4S5[]S4[]S0試找出一個長度最小的輸入串，使得：在辨別此輸入串的過程中，每一狀態(tài)起碼經(jīng)歷一次；每一狀態(tài)變換起碼經(jīng)歷一次。關(guān)于以下的狀態(tài)變換矩陣：[]a[]bS[]A[]SA[]A[]BB[]B[]B(i)初態(tài)：S終態(tài)：B[][][]a[]bS[]A[]BA[]B[]AB[]B[]B(ii)初態(tài)：S終態(tài)：A[]a[]bS[]A[]BA[]C[]AB[]B[]CC[]C[]C(iii)初態(tài)：S終態(tài)：A,C[][][]a[]bS[]A[]SA[]C[]BB[]B[]CC[]C[]C(iv)初態(tài)：S終態(tài)：C分別畫出相應的狀態(tài)變換圖；寫出相應的3型文法；用自然語言分別描繪它們所識其他輸入串的特色。關(guān)于下邊所給的文法：G1=({S,A,B,C,D},{a,b,c,d},P1,S)P1由以下產(chǎn)生式構(gòu)成：S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB以及G2=({S,A,B,C,D},{a,b,c,d},P2,S)P2由以下產(chǎn)生式構(gòu)成：S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d(1)試分別對G1和G2結(jié)構(gòu)相應的狀態(tài)變換圖(提示：關(guān)于右線性文法，可將形如C→D的產(chǎn)生式視為C→εD；而對左線性文法，則可將它視為C→Dε)。(2)關(guān)于G1，結(jié)構(gòu)一等價的左線性文法G1′；關(guān)于G2結(jié)構(gòu)一等價的右線性文法G2′。關(guān)于G1和G1′，分別給出以下符號串的推導序列：abbaababbbcdcbb關(guān)于G2和G2′分別給出以下符號串的推導序列：aabaaabcadca(4)試給出若干個不可以由G1或G2產(chǎn)生的符號串，并考證它們相同不可以用G1′和G2′產(chǎn)生。分別結(jié)構(gòu)將左線性文法變換為右線性文法以及將右線性文法變換為左線性文法的算法。將如題圖312所示的NFA確立化和最小化。題圖312將如題圖313所示的擁有ε動作的NFA確立化。題圖313將如題圖314所示的有限自動機最小化。試用一種高級語言分別寫出將NFA確立化以及將DFA最小化的算法。結(jié)構(gòu)一產(chǎn)生FORTRAN語言COMMON語句的3型文法(假定分別用λ和μ代表表記符和整常數(shù)，它們都是終結(jié)符號，且假定數(shù)組的維數(shù)不加限制)，結(jié)構(gòu)相應的DFA，并寫出描繪COMMON語句的正規(guī)式。設r,s等為隨意的正規(guī)式，試證明以下的關(guān)系式成立：(1)r*=(ε|r)*=ε|rr*=(r*)*(2)(rs)*r=r(sr)*(3)(r|s)*=(r*s*)*=(r*|s*)*關(guān)于解習題36所得的文法，試用正規(guī)式描繪它所產(chǎn)生的語言。[]a[]bS0[]S1[]S5S1[]S2[]S7S2[]S3[]S5S3[]S5[]S7S4[]S5[]S5S5[]S3[]S1S6[]S3[]S0S7[]S0[]S1S8[]S3[]S8(1)初態(tài)：S0終態(tài)：S1，S2，S6，S7[][][]a[]bS0[]S5[]S2S1[]S6[]S2S2[]S0[]S4S3[]S3[]S5S4[]S6[]S2S5[]S3[]S0S6[]S3[]S1(2)初態(tài)：S0終態(tài)：S4,S5,S6題圖314關(guān)于習題310所給的文法G1和G2，試分別用正規(guī)式描繪它們所產(chǎn)生的語言。設有以下的文法G［〈標號說明〉］：〈標號說明〉→′LABEL〈′標號表〉〈標號表〉→d〈標號段〉〈標號段〉→d〈標號段〉|,〈標號〉|；〈標號〉→d〈標號段〉此中′LABEL′,′d′等,為′終,結(jié)′符,′號;?！湓嚽蟪雒枥L此文法所產(chǎn)生語言的正規(guī)式；結(jié)構(gòu)辨別此語言的擁有最少狀態(tài)的DFA。求出描繪習題37所給有限自動機所辨別語言的正規(guī)式。分別結(jié)構(gòu)辨別以下正規(guī)語言的DFA：((0*|1)(1*0))*(b|a(aa*b)*b)*a(abab*|a(bab)*a)*b(b|aa|ac|aaa|aac)*a(a|b)*b(a|b)*a(a|b)*b(a|b)*試設計一個辨別器，它辨別由以下英語單詞：ONE,TWO,THREE,，NINE，TEN，ELEVEN，TWELVE，THIRTEEN，，NINETEEN，TWENTY，THIRTY，F(xiàn)ORTY，，NINETY，HUNDRED所表示的從1到999間的任何整數(shù)(各單詞間用空格分開，如THREEHUNDREDFIFTYSIX)，并將它們翻譯為相應的阿拉伯數(shù)字(如356)作為輸出。設有協(xié)助定義式D0=a|bD1=D0D0D2=D1D1Dn=Dn-1Dn-1試回答以下問題：由Dn所表述的正規(guī)集是什么(2)假如將Dn中所出現(xiàn)的Dn-1用前面已定義的協(xié)助定義式頻頻進行替代，則可最后將Dn化為Σ={a,b}上的正規(guī)式，此正規(guī)式有多長用來辨別Dn的DFA至多需要幾個狀態(tài)試將LEX中的“動作子程序”Ai的功能加以擴大，使之可用來生成文本編寫程序。指出以下LEX正規(guī)式所般配的字符串："{"［^{］*"}"^［^a-z］［A-Z］［0-9］$［^0-9］|［＼r＼n］＼′(［^′＼n］|＼′＼′＼)+′＼"(［^"＼n］|＼＼［"＼n］)*＼"寫出一個LEX正規(guī)式，它能般配C語言的所有無符號整數(shù)(比如：OX89ab，0123，45，′Z＼′t,′＼,′xab′＼,′012′,等等)。寫出一個LEX正規(guī)式，它能般配C語言的表記符。編寫一個LEX源程序，它將一個正文文件中的所有小寫字母均換為大寫字母，并將此中的制表字符、空白字符序列均用單個空格字符進行替代(提示：在語義動作中使用全程變量yytext)。編寫一個LEX源程序，它能統(tǒng)計一個PASCAL程序中所含用戶定義之表記符個數(shù)，并能找出最長表記符中的字符個數(shù)(提示：使用全程變量yytext及yyleng)。上機實習題關(guān)于以下文法所定義的PASCAL語言子集，試編寫并上機調(diào)試一個詞法剖析程序：〈程序〉→〈變量說明〉BEGIN〈語句表〉END.〈變量說明〉→VAR〈變量表〉：〈種類〉；|〈空〉〈變量表〉→〈變量表〉，〈變量〉|〈變量〉〈種類〉→INTEGER〈語句表〉→〈語句表〉；〈語句〉|〈語句〉〈語句〉→〈賦值語句〉|〈條件語句〉|〈WHILE語句〉|〈復合語句〉|〈過程定義〉〈賦值語句〉→〈變量〉∶=〈算術(shù)表達式〉〈條件語句〉→IF〈關(guān)系表達式〉THEN〈語句〉ELSE〈語句〉〈WHILE語句〉→WHILE〈關(guān)系表達式〉DO〈語句〉〈復合語句〉→BEGIN〈語句表〉END〈過程定義〉→PROCEDURE〈表記符〉〈參數(shù)表〉；BEGIN〈語句表〉END〈參數(shù)表〉→(〈表記符表〉)|〈空〉〈表記符表〉→〈表記符表〉，〈表記符〉|〈表記符〉〈算術(shù)表達式〉→〈算術(shù)表達式〉+〈項〉|〈項〉〈項〉→〈項〉*〈初等量〉|〈初等量〉〈初等量〉→(〈算術(shù)表達式〉)|〈變量〉|〈無符號數(shù)〉〈關(guān)系表達式〉→〈算術(shù)表達式〉〈關(guān)系符〉〈算術(shù)表達式〉〈變量〉→〈表記符〉〈表記符〉→〈表記符〉〈字母〉|〈表記符〉〈數(shù)學〉|〈字母〉〈無符號數(shù)〉→〈無符號數(shù)〉〈數(shù)字〉|〈數(shù)字〉〈關(guān)系符〉→=|＜|＜=|＞|＞=|＜＞〈字母〉→A|B|C||X|Y|Z〈數(shù)字〉→0|1|2||8|9〈空〉→要乞降提示：單詞的分類?？蓪⑺斜碛浄麣w為一類；將常數(shù)歸為另一類；保存字和分開符則可采納一詞一類。符號表的成立?？深A先成立一保存字表，以備在辨別保存字時進行查問。變量名表及常數(shù)表則在詞法剖析過程中成立。單詞串的輸出形式。所輸出的每一單詞，均按形如(CLASS，VALUE)的二元式編碼。關(guān)于變量表記符和常數(shù)，CLASS字段為相應的類型碼，VALUE字段則是該表記符、常數(shù)在其符號表中登記項的序號(要求在變量名表登記項中寄存該表記符的字符串，其最大長度為四個字符；常數(shù)表登記項中則寄存該整數(shù)的二進制形式)。對于保存字和分開號，因為采納一詞一類的編碼方式，所以僅需在二元式的CLASS字段上擱置相應的單詞的類型碼，VALUE字段則為“空”。可是，為便于查察由詞法剖析程序所輸出的單詞串，也能夠在CLASS字段上直接擱置單詞符號串自己。能夠模仿程序34的結(jié)構(gòu)來編寫上述詞法剖析程序，但此中的若干語義過程有待于詳細編寫。寫出它的LEX源程序，并上機進行辦理。第三章習題解答1．從略2．3假定W:表示載狐貍過河，G:表示載山羊過河，C:表示載白菜過河用到的狀態(tài)1：狐貍和山羊在左岸2：狐貍和白菜載左岸3:羊和白菜在左岸4:狐貍和山羊在右岸5:狐貍和白菜在右岸6:山羊和白菜在右岸F:全在右岸證明：只須證明文法G:A→αB或A→α（A,B∈VN,α∈VT+）等價于G1:A→aB或A→a(a∈VT+)G1的產(chǎn)生式中A→aB,則B也有B→bC,C→cD.所以有A→abcB’,a,b,c∈VT,B’∈VN所以與G等價。2）G的產(chǎn)生式A→αB，α∈VT+，因為α是字符串，所以一定存在著一個終結(jié)符a，使A→aB可見二者等價，所以由此文法產(chǎn)生的語言是正規(guī)語言。5依據(jù)文法知其產(chǎn)生的語言是L={ambnci|m,n,i≧1}能夠結(jié)構(gòu)以下的文法VN={S,A,B,C},VT={a,b,c}P={S→aA,A→aA,A→bB,B→bB,B→cC,C→cC,C→c}其狀態(tài)變換圖以下:7(1)其對應的右線性文法是:A→0D,B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B最短輸入串011隨意接受的四個串011,0110,0011,000011(4)隨意以1打頭的串.從略。9（2）相應的3型文法(i)S→aAS→bSA→aAA→bBB→a|aBB→b|bB(ii)S→aA|aS→bBB→aB|bBA→aBA→b|bAS→aAS→bBA→bAA→aCB→aBB→bCC→a|aCC→b|bCS→bSS→aAA→aCA→bBB→aBB→bCC→a|aCC→b|bC（3）用自然語言描繪輸入串的特色以隨意個(包含0)b開頭，中間有隨意個（大于1）a，跟一個b,還能夠有一個由a,b構(gòu)成的隨意字符串(ii)以a打頭，后跟隨意個（包含0）b以a打頭，中間有隨意個（包含0）b,再跟a,最后由一個a,b所構(gòu)成的隨意串結(jié)尾或許以b打頭，中間有隨意個（包含0）a,再跟b,最后由一個a,b所構(gòu)成的隨意串結(jié)尾以隨意個（包含0）b開頭,中間跟aa最后由一個a,b所構(gòu)成的隨意串結(jié)尾或許以隨意個（包含0）b開頭，中間跟ab后再接隨意（包含0）a再接b，最后由一個a,b所構(gòu)成的隨意串結(jié)尾（1）G1的狀態(tài)變換圖：G2的狀態(tài)變換圖：G1等價的左線性文法：S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→aG2等價的右線性文法：S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a（3）對G1文法,abb的推導序列是：S=>aA=>abB=>abb對G1’文法，abb的推導序列是：S=>Bb=>Abb=>abb對G2文法，aabca的推導序列是：S=>Aa=>Cca=>Babca=>aabca對G2’文法，aabca的推導序列是：S=>aB=>aabC=>aabcA=>aabca（4）對串a(chǎn)cbd來說，G1,G1’文法都不可以產(chǎn)生。將右線性文法化為左線性文法的算法：o（1）關(guān)于

G中每一個形如

A→aB的產(chǎn)生式且

A是開始符，將其變成

B→a,不然若

A不是開始符，

B→Aa;o（2）關(guān)于

G中每一個形如

A→a的產(chǎn)生式

,將其變成

S→Aa12(1)狀態(tài)矩陣是：記[S]=q0[B]=q1[AB]=q2[SA]=q3,最小化和確立化后如圖（2）記[S]=q0,[A]=q1,[BS]=q2最小化和確立化后的狀態(tài)變換圖以下（1）將擁有ε動作的NFA確立化后，其狀態(tài)變換圖如圖：記{S0,S1,S3}=q0{S1}=q1{S2S3}=q2{S3}=q3(2)記{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q7（1）從略(2)化簡后S0和S1作為一個狀態(tài)，S5和S6作為一個狀態(tài)。狀態(tài)變換圖如圖(1)r*{ε,r,rr,rrr,}(ε|r)*{ε,εε{r,rr,rrr,}}={ε,r,rr,rrr,}ε|rr*{ε,r,rr,rrr,}(r*)*=r*={ε,r,rr,rrr,}(2)rs*r{ε,rs,rsrs,rsrsrs,}r={r,rsr,rsrsr,rsrsrsr,}r(sr)*r{ε,sr,srsr,srsrsr,}={r,rsr,rsrsr,rsrsrsr,}S=aT+aS(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*cG1:S=aA+B(1)B=cC+b(2)A=abS+bB(3)C=D(4)D=bB+d(5)把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b得B=(cb)*(cd|b),代入（3）得A=abS+b(cb)*(cd|b)把它打入（1）得S=a(abS+b(cb)*(cd|b))+(cb)*(cd|b)=aabS+ab(cb)*(cd|b)+(cb)*(cd|b)=(aab)*(ab(cb)*(cd|b)|(cb)*(cd|b))G2:S=Aa+B(1)A=Cc+Bb(2)B=Bb+a(3)C=D+Bab(4)D=d(5)可得D=dB=ab*C=ab*ab|bA=(ab*ab|b)c+ab*bS=(ab*ab|b)ca+ab*ba+ab*=(ab*ab|b)ca|ab*ba|ab*20辨別此語言的正規(guī)式是S=’LABEL’d(d|,d)*;從略。從略。結(jié)構(gòu)NFA其他從略。23下邊舉一個能夠辨別1,2,3,10,20,100的例子，讀者能夠推而廣之。%{#include<>#include<>#include<>#defineON1#defineTW2#defineTHRE3#defineTE10#defineTWENT20#defineHUNDRE100#defineWHITE9999%}upper[A-Z]%%ONEreturnON;TWOreturnTW;THREEreturnTHRE;TENreturnTE;TWENTYreturnTWENT;HUNDREDreturnHUNDRE;"+|\treturnWHITE;\nreturn0;%%main(intargc,char*argv[]){intc,i=0;chartmp[30];if(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can'topen%s\n",argv[1]);exit(0);}}while((c=yylex( ))!=0){switch(c){caseON:c=yylex( );if(c==0)goto{i+=1;label;}c=yylex( );if(c==HUNDRE)i+=100;elsei+=1;break;caseTW:c=yylex( );c=yylex( );if(c==HUNDRE)i+=200;elsei+=2;break;caseTWENT:i+=20;break;caseTE:i+=10;break;default:break;}}/*while*/label:printf("%d\n",i);return;}24（1）Dn表示的正規(guī)集是長度為2n隨意a和b構(gòu)成的字符串。此正規(guī)式的長度是2n用來辨別Dn的DFA至多需要2n＋1個狀態(tài)。從略。26（1）由{}括住的,中間由隨意個非{構(gòu)成的字符串,如{},{}},{a},{defg}等等。（2）般配一行僅由一個大寫字母和一個數(shù)字構(gòu)成的串，如A1,F8,Z2等。（3）辨別\r\n和除數(shù)字字符外的任何字符。由’和’括住的，中間由兩個’’或許非’和\n構(gòu)成的隨意次的字符串。如’’’’,‘，a’’,’等’’’bb等,’def’’([a’)28^[a-zA-Z_]+[0-9]*[a-zA-Z_]*參照程序以下：%{#include<>#include<>#include<>#defineUPPER2#defineWHITE3%}upper[A-Z]%%{upper}+returnUPPER;\t|""+returnWHITE;%%main(intargc,char*argv[]){intc,i;if(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can'topen%s\n",argv[1]);exit(0);}}while