【正文】 于 LR(0)項(xiàng)目集的識(shí)別活前綴的 DFA （ 2） 指出 DFA中所有含有沖突的項(xiàng)目集 ， 并說明這些沖突可以用 SLR(1)方法解決； E 39。 (0|1)*011(0|1)* ： 至少含一個(gè) 011的 01串 。 end loop。出發(fā) ” ，將 “ 稱為 D的初態(tài) ” 改為 “ 稱為 D39?！? S. then action[i, ]:=acc。 兩種解題的思路： 1. 把自己當(dāng)作計(jì)算機(jī) ， 按照參數(shù)傳遞的實(shí)現(xiàn)方式 “ 運(yùn)行 ” 一遍程序 ， 得出結(jié)果； 2. 找臺(tái)機(jī)子把程序敲進(jìn)去試試 （ 輔助手段 ） 困惑的是： 表達(dá)式 a+b如何作為引用調(diào)用和復(fù)寫 恢復(fù)的實(shí)參 ？ 解決方案： 忽略返回值問題 。 反之亦然 。 0 1 2b ba,ba,b 解： 1. 含有至少兩個(gè)連續(xù) b的 a、 b串 ， 例如 bb、 bbb等 。 ? 總之一句話，學(xué)習(xí)方法的掌握是個(gè)人努力的結(jié)果，單純靠別人教是學(xué)不會(huì)的。語(yǔ)法分析也有雙重含義：根據(jù)一定的規(guī)則構(gòu)成語(yǔ)言的各種結(jié)構(gòu)，即 語(yǔ)法規(guī)則 ；根據(jù)語(yǔ)法規(guī)則識(shí)別輸入序列（記號(hào)流）中的語(yǔ)言結(jié)構(gòu)，即 語(yǔ)法分析 。 語(yǔ)法分析的分析對(duì)象是組成語(yǔ)言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對(duì)語(yǔ)法的分析就有了從根到葉子和從葉子到根兩種分析方法。 21 關(guān)于考試 ? 題目類型： 簡(jiǎn)答題 (25分 )、 填空題 (25分 )、 計(jì)算題 (50分 ) ? 考試范圍： 1－ 4章講過的內(nèi)容 ? 側(cè)重考察： 基本概念與基本方法的掌握 易犯的錯(cuò)誤 1. 不認(rèn)真審題（對(duì)題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。 2. r=(a|b)*bb(a|b)*。 習(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開始的正奇數(shù) } 思路： 首先根據(jù)集合的描述設(shè)計(jì)幾個(gè)句子 ， 然后從句子中找出規(guī)律 （ 或共性 ） ， 把它們的性質(zhì)用產(chǎn)生式表示出來 。 其實(shí)這一思想可以推廣到任何不支持某種方式的情況 （ 放心 ， 考試中不會(huì)有這種很困惑的問題 ） 具體結(jié)果 （ 略 ） 38 To know how to do something well is to enjoy it. 戰(zhàn)略上藐視敵人，戰(zhàn)術(shù)上重視敵人。 else for 每個(gè) a∈FOLLOW(A) loop action[i,a]:=Rk。的初態(tài) ” 45頁(yè)： 10行：將 “ N是僅出現(xiàn) ” 改為 “ 僅 N是可以出現(xiàn) ” 70頁(yè)：例 ：將 FOLLOW集合中的 “ ＄ ” 改為 “ ＃ ” 75頁(yè)：到 4行：將 “ 文法 ‖改為 “ 文法 ‖ 81頁(yè)：圖 ：將 I0中的 “ T→ .F‖改為 “ F→ .F‖ 47 附件 1：教材與習(xí)題答案中的錯(cuò)誤（續(xù) 1） 教材 100頁(yè)：圖 ：將 =(3)―(x,:=,(2))‖改為 “ (:=,x,(2))‖ 129頁(yè)：例 ：將 “ t3:=+r t4‖改為 “ t3:=C +r t4‖ 133頁(yè)：例 ：將 “ t5:=t3*t4‖改為 “ t5:=t3*4‖，將 “ V7‖改為 “ V5‖ 134頁(yè)：圖 ：將 “ V V V7‖分別改為 “ V V V5‖ 136頁(yè)： ：將 “ ptr^.data/=x‖改為 “ ptr^.data=x‖ 138頁(yè)：例 ：將代碼序列中的 “ L1‖改為 “ L2‖， “ L2‖改為“ L1‖ 144頁(yè)：例 ：將 “ mklist‖改為 “ mkchain‖ 習(xí)題解答 4頁(yè)： (1)： A1A|A0A1A0可以簡(jiǎn)化為 A(1|010)A 32頁(yè)：缺少 (1)的解答 32頁(yè)：到 2行：將兩處 “ I10‖均改為 “ I11‖，將 “ I12‖改為“ I13‖ 。 end if。 解： 10*1： 首尾是 1中間有零或若干個(gè) 0的 01串 。 相對(duì)來說分析表的構(gòu)造并不重要 。 emit(*,。 2（ 2分 ） 寫出 ((a+b)*c)+d 的后綴式 。 2. 推導(dǎo)的基本概念： 句子、直接推導(dǎo)、最左推導(dǎo)、左句型（最右推導(dǎo)、右句型）； 3. 分析樹與語(yǔ)法樹： 分析樹和語(yǔ)法樹都反映了語(yǔ)言結(jié)構(gòu)；分析樹還記錄了分析的過程（含有非終結(jié)符）； 4. 文法的二義性： 二義性的本質(zhì)是在文法中缺少對(duì)文法符號(hào)優(yōu)先級(jí)和結(jié)合性的限制，從而使得一個(gè)句子可以推導(dǎo)出多于一棵分析樹。 4 從正規(guī)式到詞法分析器 ? 構(gòu)造 NFA的 Thompson算法 (與 NFA定義的對(duì)應(yīng)關(guān)系 )； ? 模擬 NFA的 “ 并行 ” 算法； ? 從 NFA構(gòu)造 DFA－子集法： smove(S, a)與 ε 閉包 (T)的計(jì)算； ? DFA的最小化－可區(qū)分的概念：所有不可區(qū)分的狀態(tài)看作是一個(gè)狀態(tài)； ? 靈活運(yùn)用各種方法構(gòu)造 DFA(正規(guī)式化簡(jiǎn)、狀態(tài)轉(zhuǎn)換圖等 )，特別是手工構(gòu)造和算法構(gòu)造的區(qū)別。 ? 自己要會(huì)辨別什么是主要的什么是次要的，抓什么丟什么。 (b)（ 3分 ） 寫出與該自動(dòng)機(jī)等價(jià)的正規(guī)式 r。其中 …代表不含 */的字符串 思路： 注釋中若遇到 *：若后邊是 /則結(jié)束注釋否則仍然是注釋 步驟： 1. 注釋串是空； 2. 考慮沒有 *的注釋； 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ǔ)言 問題： 根據(jù) DFA寫出對(duì)應(yīng)的正規(guī)式 ， 通常的考慮和步驟是什么 ？ 再重復(fù)一遍： 正規(guī)式 、 DFA是從兩個(gè)不同的側(cè)面表示一個(gè)集合 (即正規(guī)集 )。 p(a+b, a, a)。