[理學(xué)]編譯原理復(fù)習(xí)(編輯修改稿)
2025-03-17 21:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 s表示的正規(guī)集 3 a*(b|ba)* 4 FIRST(S)= {e， d， ε ， a， b} ， FIRST(D)= {a， b} ，F(xiàn)IRST(T)= {ε ， a， b} ， FIRST(R)= {d， ε} 。 三、計(jì)算題（ 1） 1（ 13分 ） 已知一個(gè) NFA如圖 。 (a)(4分 ) 用自然語(yǔ)言簡(jiǎn)要敘述該自動(dòng)機(jī)所識(shí)別的語(yǔ)言 的特點(diǎn) ， 列舉兩個(gè)它可識(shí)別的串 。 (b)（ 3分 ） 寫(xiě)出與該自動(dòng)機(jī)等價(jià)的正規(guī)式 r。 (c)（ 6分 ） 用子集法構(gòu)造識(shí)別 r的最小 DFA。 0 1 2b ba,ba,b 解： 1. 含有至少兩個(gè)連續(xù) b的 a、 b串 ， 例如 bb、 bbb等 。 2. r=(a|b)*bb(a|b)*。 3. 直接用狀態(tài)轉(zhuǎn)換矩陣構(gòu)造： 初態(tài)： {0} 子集法得： （ 2是終態(tài) ） a b {0} {0} {0,1} {0,1} {0} {0,1,2} {0,1,2} {0,2} {0,1,2} {0,2} {0,2} {0,1,2} 令： {0}=A， {0,1}=B， {0,1,2}=C， {0,2}=D 得： a b A A B B A C C D C D D C 最小化 DFA得： （ C和 D不可區(qū)分 ） a b A A B B A C C C C A B Cb baaa , b三、計(jì)算題（ 2） 2（ 15分 ） 有文法 G和 G的語(yǔ)法制導(dǎo)翻譯如下： E→E 1*T { =newtemp。 emit(*,。 } | T { =。 } T→T 1+F { =newtemp。 emit(+,。 } | F { =。 } F→(E) { =。 } | id { =。 } (a)（ 4分 ） 求句型 (T+F)*id 的短語(yǔ) 、 直接短語(yǔ)以及句柄； (b)（ 4分 ） 根據(jù)語(yǔ)法制導(dǎo)翻譯寫(xiě)出句子 a*b+c*d的中間代碼； (c)（ 3分 ） 若 a=3， b=5， c=7， d=8， 請(qǐng)給出中間代碼計(jì)算結(jié)果； (d)（ 4分） 將文法 G簡(jiǎn)化為： E→E*T|T ， T→T+F|F ， F→id 。給出它的識(shí)別活前綴的 DFA。 解： (a) 短 語(yǔ)： (T+F)*id、 (T+F)、 T+F、 id 直接短語(yǔ)： T+F、 id 句柄： T+F (b) a*b+c*d的中間代碼： (1) (+, b, c, t1) (2) (*, a, t1, t2) (3) (*, t2, d, t3) (c) 計(jì)算結(jié)果： t3=288 (d) 識(shí)別活前綴的 DFA： E ’→. EE →. E * TE →. TT →. T + FT →. FF →. i dE ’→E .E →E . * TE →T .T →T . + FT →F .F →i d .E →E * . TT →. T + FT →. FF →. i dT →T + . FF →. i dE →E * T .T →T . + FFETFid*+ +TididI0I1I2I3I4I5I6I7T →T + F . I8F28 部分習(xí)題解答 習(xí)題 寫(xiě)出下述語(yǔ)言的正規(guī)式描述 （ 1） 由偶數(shù)個(gè) 0和奇數(shù)個(gè) 1構(gòu)成的所有 01串 （ 2） 所有不含子串 011的 01串 （ 3） 每個(gè) a后面至少緊隨兩個(gè) b的 ab串 （ 4） C的形如 /*…*/ 的注釋 。 其中 …代表不含 */的字符串 思路： 分析題意 ， 從最簡(jiǎn)單的例子考慮 ， 然后找出統(tǒng)一規(guī)律 （ 1） 的解題步驟： 1. 最簡(jiǎn)單的符合要求的串： 010（ 還有 100、 00 111等 ） 2. 所有 01均為偶數(shù)的串： A=((00|11)|(01|10)(00|11)*(10|01))* 3. 符合要求的所有串： A1A、 A0A1A0A（ 為什么沒(méi)有后三個(gè) ？ ） 結(jié)果： A1A | A0A1A0A 思考： 識(shí)別它的 DFA又應(yīng)該如何構(gòu)造 ？ （ 4） C的形如 /*…*/ 的注釋。其中 …代表不含 */的字符串 思路： 注釋中若遇到 *：若后邊是 /則結(jié)束注釋否則仍然是注釋 步驟： 1. 注釋串是空； 2. 考慮沒(méi)有 *的注釋； 3. 考慮含 *的注釋 結(jié)果： (4) /* ([^*]|*[^/])* */ （ 2） 所有不含子串 011的 01串： 1*(01|0)* （ 3） 每個(gè) a后面至少緊隨兩個(gè) b的 ab串： (b|abb)* 習(xí)題 有一 NFA的狀態(tài)轉(zhuǎn)換矩陣下表，其中 S為初態(tài)， D為終態(tài) a b c ε S A,B C,D D A,B,C A A C B B A D C C B A A D C B S 1. 求出它的最小 DFA 2. 用正規(guī)式描述 DFA所接受的語(yǔ)言 問(wèn)題： 根據(jù) DFA寫(xiě)出對(duì)應(yīng)的正規(guī)式 ， 通常的考慮和步驟是什么 ？ 再重復(fù)一遍： 正規(guī)式 、 DFA是從兩個(gè)不同的側(cè)面表示一個(gè)集合 (即正規(guī)集 )。 所以 ， 根本的方法是把正規(guī)集作為橋梁 ， 先分析清楚 DFA識(shí)別出的是一個(gè)什么集合 ， 然后再設(shè)計(jì)此集合的正規(guī)式 。 反之亦然 。 習(xí)題 （ 2） 的解 20a1b , cb , ca , cab 該 DFA從初態(tài)到終態(tài)有三條路徑： b|c|a(a|c)*b， 而且是這三條路徑的至少一次重復(fù) ， 故正規(guī)式為： (b|c|a(a|c)*b)+ 習(xí)題 設(shè)計(jì)一文法 G， 使得 L(G)={ω|ω 是不以 0開(kāi)始的正奇數(shù) } 思路： 首先根據(jù)集合的描述設(shè)計(jì)幾個(gè)句子 ， 然后從句子中找出規(guī)律 （ 或共性 ） ， 把它們的性質(zhì)用產(chǎn)生式表示出來(lái) 。 解： 正規(guī)式： 個(gè)位： [13579] 個(gè)位以上： [09]* 最高位： [19] 三段連起來(lái)： [19][09]*[13579] 兩種情況： [19][09]*[13579] | [13579] 產(chǎn)生式： S→ACB|B A→ 1|2|3|4|5|6|7|8|9 B→ 1|3|5|7|9 C→ε| 0C|AC 習(xí)題 對(duì)于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1