[理學(xué)]編譯原理復(fù)習(xí)-wenkub
2023-03-05 21:57:55 本頁面
【正文】 4 從正規(guī)式到詞法分析器 詞法分析器的作用： ? 濾掉源程序中的無用成分； ? 處理與具體操作系統(tǒng)或機(jī)器有關(guān)的輸入； ? 識(shí)別記號(hào)并交給語法分析器； ? 調(diào)用符號(hào)表管理器和出錯(cuò)處理器進(jìn)行相關(guān)處理?！?編譯原理 》 復(fù)習(xí) 延安大學(xué)計(jì)算機(jī)學(xué)院 郝繼升 2 課程內(nèi)容 要求（希望） 1. 牢固掌握基本概念 2. 靈活使用基本方法 3. 歸納總結(jié)所學(xué)內(nèi)容（鍛煉提高抽象能力） 一、引言 二、詞法分析 三、語法分析 四、語義分析 —語法制導(dǎo)翻譯生成中間代碼 學(xué)習(xí)不能走捷徑，付出多少勞動(dòng)就有多少收獲。 7 1 記號(hào)、模式與單詞 ? 模式 （ pattern） ：規(guī)定單詞識(shí)別的規(guī)則 ? 記號(hào) （ token） ：按照某模式識(shí)別出的一類單詞 （ 記號(hào)種類 ） ? 單詞 （ lexeme） ：被識(shí)別出的字符串本身 ? 詞法分析器的輸出：記號(hào) =記號(hào)種類 +記號(hào)屬性 2 記號(hào)的說明－模式的形式化描述 1. 正規(guī)式與正規(guī)集： ? 正規(guī)式與正規(guī)集的定義 (基本正規(guī)式、三個(gè)運(yùn)算 ) ? 正規(guī)式的等價(jià) (描述相同的集合 ) ? 利用正規(guī)式的等價(jià)對(duì)正規(guī)式進(jìn)行化簡 (正規(guī)式的代數(shù)性質(zhì) ) 2. 用正規(guī)式形式化描述模式： ? 如何用正規(guī)式描述程序設(shè)計(jì)語言中常見的記號(hào)，如標(biāo)識(shí)符、數(shù)字、運(yùn)算符和分隔符等 ? 正規(guī)式的簡化形式以及輔助定義與規(guī)則 8 3 記號(hào)的識(shí)別－有限自動(dòng)機(jī)（ FA） ? NFA與 DFA的定義： FA = (S, Σ, move, s0, F) ； ? NFA與 DFA的表示：定義表示、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣； ? NFA與 DFA的關(guān)鍵區(qū)別： NFA的不確定性（當(dāng)前狀態(tài)下，對(duì)同一字符可能有多于一個(gè)的下一狀態(tài)轉(zhuǎn)移）； ? 用 NFA識(shí)別輸入序列的弱點(diǎn)：嘗試所有路徑才能確定一個(gè)輸入不被接收、回溯帶來的問題； ? 模擬 DFA的算法：用 DFA識(shí)別記號(hào)。 語法分析的分析對(duì)象是組成語言的句子，句子具有層次結(jié)構(gòu)的特征，表征該結(jié)構(gòu)的最好方法是樹，從而使得對(duì)語法的分析就有了從根到葉子和從葉子到根兩種分析方法。 13 3 自上而下分析 1. 分析方法： 推導(dǎo)，從上到下構(gòu)造分析樹，是一種預(yù)測(cè)的、試探的方法； 2. 對(duì)文法的要求： 沒有公共左因子和左遞歸； 3. 遞歸下降子程序方法： 匹配終結(jié)符，展開非終結(jié)符（子程序調(diào)用） 4. 預(yù)測(cè)分析表方法 : ? 工作方式與過程： PDA（ DPDA） 、格局與改變格局的動(dòng)作； ? 預(yù)測(cè)分析表的構(gòu)造： FIRST集合與 FOLLOW集合， FIRST與 FOLLOW的計(jì)算； ? LL(1)文法及其判別： 預(yù)測(cè)分析表中沒有多重定義條目（推論 ）。 主要內(nèi)容 1 語法制導(dǎo)翻譯與中間代碼 2 符號(hào)表的組織 3 聲明語句的翻譯 4 可執(zhí)行語句的翻譯 17 1 語法制導(dǎo)翻譯與中間代碼 1. 語法與語義：語法和語義描述語言的不同方面、二者之間沒有嚴(yán)格界線、語義形式化描述的困難性； 2. 屬性：用屬性表示語義特征（語義值），屬性的計(jì)算和屬性之間的依賴關(guān)系； 3. 語法制導(dǎo)翻譯：為產(chǎn)生式配上 “ 語義規(guī)則 ” 并在適當(dāng)?shù)臅r(shí)刻執(zhí)行；語義規(guī)則的兩種形式； 4. 分析方法與翻譯方案：以語法分析為基礎(chǔ)，分析樹的作用； 5. 中間代碼：為什么生成中間代碼，中間代碼的特征，各種形式的中間代碼及它們之間的關(guān)系，最常用中間代碼形式。太繁瑣步驟或太難等需要耗費(fèi)大量時(shí)間的題是不可能出的，大部分應(yīng)該是基本概念題，但也會(huì)有一些綜合性的題目。 21 關(guān)于考試 ? 題目類型： 簡答題 (25分 )、 填空題 (25分 )、 計(jì)算題 (50分 ) ? 考試范圍： 1－ 4章講過的內(nèi)容 ? 側(cè)重考察： 基本概念與基本方法的掌握 易犯的錯(cuò)誤 1. 不認(rèn)真審題（對(duì)題目的要求理解錯(cuò)誤：意思理解錯(cuò)、難題想容易、容易題想難。 1 （ 1） 改寫文法 （ 2） 規(guī)定文法符號(hào)的優(yōu)先級(jí)和結(jié)合性 2 ab+c*d+（ 或 ab+c*d+） 3 證明： 考慮 L((ab)*a)中的任意一個(gè)串 ababab...aba， 由串連接的結(jié)合性可得： a(ba)(ba)(b...a)(ba)，它恰好是 L(a(ba)*)，即 L((ab)*a)= L(a(ba)*)。 3（ 2分 ） 不含子串 baa的所有 a、 b符號(hào)串的正規(guī)式是 。 (a)(4分 ) 用自然語言簡要敘述該自動(dòng)機(jī)所識(shí)別的語言 的特點(diǎn) ， 列舉兩個(gè)它可識(shí)別的串 。 2. r=(a|b)*bb(a|b)*。 } T→T 1+F { =newtemp。 } | id { =。 其中 …代表不含 */的字符串 思路： 分析題意 ， 從最簡單的例子考慮 ， 然后找出統(tǒng)一規(guī)律 （ 1） 的解題步驟： 1. 最簡單的符合要求的串： 010（ 還有 100、 00 111等 ） 2. 所有 01均為偶數(shù)的串： A=((00|11)|(01|10)(00|11)*(10|01))* 3. 符合要求的所有串： A1A、 A0A1A0A（ 為什么沒有后三個(gè) ？ ） 結(jié)果： A1A | A0A1A0A 思考： 識(shí)別它的 DFA又應(yīng)該如何構(gòu)造 ？ （ 4） C的形如 /*…*/ 的注釋。 習(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)生式表示出來 。 → . E E → . E + T E → . T T → . T * F T → . F F → . ( E ) F → . F F → . i d E 39。 procedure p(x,y,z)。 b:=3。 其實(shí)這一思想可以推廣到任何不支持某種方式的情況 （ 放心 ， 考試中不會(huì)有這種很困惑的問題 ） 具體結(jié)果 （ 略 ） 38 To know how to do something well is to enjo
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1