色国产国产欧美诱惑屌,中文字幕视频熟女一区

大學(xué)期間的筆記補(bǔ)全。編譯原理內(nèi)容太多分幾次。
課本《編譯原理》第三版，陳火旺等編著。
筆記總目錄：
一、引論
二、高級(jí)語(yǔ)言及其語(yǔ)法描述
三、詞法分析
四、語(yǔ)法分析——自上而下分析
五、語(yǔ)法分析——自下而上分析
六、屬性文法和語(yǔ)法制導(dǎo)翻譯
七、語(yǔ)義分析和中間代碼生成
八、優(yōu)化
九、目標(biāo)代碼生成

一、引論

1.1 什么叫編譯程序

程序語(yǔ)言技術(shù)的發(fā)展：

機(jī)器語(yǔ)言（表示機(jī)器實(shí)際操作的數(shù)字代碼）-> 匯編語(yǔ)言（以符號(hào)形式給出指令和儲(chǔ)存地址）-> 高級(jí)語(yǔ)言（類似于數(shù)學(xué)定義或自然語(yǔ)言的簡(jiǎn)潔形式編寫(xiě)程序）
程序的兩種執(zhí)行方式
- 解釋：邊解釋邊執(zhí)行源語(yǔ)言程序，不產(chǎn)生目標(biāo)語(yǔ)言程序
  - 優(yōu)點(diǎn)：易于查出錯(cuò)誤；缺點(diǎn)：效率低，運(yùn)行速度慢
  - Javascript，Basic
  - 相當(dāng)于源程序的一個(gè)執(zhí)行系統(tǒng)，生成源程序的執(zhí)行結(jié)果
- 編譯：產(chǎn)生目標(biāo)語(yǔ)言的程序再執(zhí)行，目標(biāo)語(yǔ)言程序與源程序邏輯等價(jià)
  - 優(yōu)點(diǎn)：只需要分析和翻譯一次；缺點(diǎn)：運(yùn)行中發(fā)現(xiàn)錯(cuò)誤必須查找整個(gè)程序確定
  - Pascal，C，C++
  - 相當(dāng)于源程序的一個(gè)轉(zhuǎn)換系統(tǒng)，生成源程序的目標(biāo)代碼
  JAVA兼具兩者，一次編寫(xiě)，逐句運(yùn)行 -> 達(dá)到跨平臺(tái)的效果（將硬件的異構(gòu)轉(zhuǎn)嫁到虛擬機(jī)上）
  
  C#也同理（在虛擬機(jī)上運(yùn)行的高級(jí)語(yǔ)言均同理）

1.2 編譯過(guò)程概述

詞法分析
- 詞法分析程序又稱掃描程序（Scanner）
- 讀取源程序的字符流、識(shí)別單詞（符號(hào)），并轉(zhuǎn)換成內(nèi)部形式
- 依循語(yǔ)言的詞法規(guī)則（正規(guī)文法）
  
  終結(jié)符：能夠查閱的有語(yǔ)法含義的符號(hào)
- 有效工具：正規(guī)式和有限自動(dòng)機(jī)
  
  并不知道每一個(gè)表達(dá)式具體的含義，也判斷不了變量的數(shù)據(jù)類型
- 狀態(tài)轉(zhuǎn)換圖
  
  狀態(tài)轉(zhuǎn)換圖中，終態(tài)帶有""的標(biāo)志，則表示判斷該終態(tài)需要多讀一個(gè)字符，判斷結(jié)束之后要把這個(gè)字符推出*，使之進(jìn)入下一輪判斷。
語(yǔ)法分析
- 語(yǔ)法分析又稱識(shí)別程序（Parser）
- 讀入由詞法分析程序識(shí)別出的符號(hào)，根據(jù)給定語(yǔ)法規(guī)則識(shí)別出各個(gè)語(yǔ)法單位（短語(yǔ)、程序段等），并聲稱另一個(gè)內(nèi)部表示（如語(yǔ)法分析樹(shù)等）
- 常用上下文無(wú)關(guān)文法描述
  
  非終結(jié)符：自發(fā)引入的語(yǔ)法范疇（可以理解為終結(jié)符的抽象/規(guī)約）
  
  語(yǔ)法分析思路：從上往下做推導(dǎo)（根結(jié)點(diǎn)->葉子結(jié)點(diǎn)），從下而上做裁剪（葉子結(jié)點(diǎn)->根結(jié)點(diǎn)）
- 方法：遞歸子程序法，LR分析法，etc.
語(yǔ)義分析中間代碼生成
- 語(yǔ)義分析
  - 對(duì)語(yǔ)法分析樹(shù)或其他內(nèi)部中間表示進(jìn)行靜態(tài)語(yǔ)義檢查，正確則進(jìn)行翻譯
  - 按照層次關(guān)系和先后順序，伴隨進(jìn)行類型審查等其他補(bǔ)充、修改操作
- 中間代碼生成
  - 中間代碼是一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)
  - 形式：四元式、三元式、逆波蘭式
    
    四元式：算符、運(yùn)算對(duì)象1、運(yùn)算對(duì)象2、運(yùn)算結(jié)果
    
    由語(yǔ)法分析樹(shù)生成四元式，中間節(jié)點(diǎn)全為算符，每一個(gè)算符便構(gòu)成一條四元式代碼（三地址碼）
  - 中間代碼生成的次序與掃描方向有關(guān)。不可人為調(diào)整。
優(yōu)化
- 對(duì)代碼提供教工，提高效率
- 依靠程序的等價(jià)交換原則
目標(biāo)代碼生成
- 把中間代碼（優(yōu)化處理后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼
- 與機(jī)器相關(guān)

1.3 編譯程序的結(jié)構(gòu)

結(jié)構(gòu)

編譯程序的結(jié)構(gòu)
- 表格管理：符號(hào)表——編譯程序使用中最重要的表格
- 出錯(cuò)處理：語(yǔ)法錯(cuò)誤 & 語(yǔ)義錯(cuò)誤
遍(Pass)
- 對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，做相關(guān)處理，生成新的中間結(jié)果或目標(biāo)程序的過(guò)程
  
  四遍掃描
- 編譯程序可由一遍、兩遍or多遍完成：
  - 多遍：少占內(nèi)存，耗時(shí)多
  - 一遍：多占內(nèi)存，耗時(shí)少

1.4 編譯程序的生成

T形圖：源語(yǔ)言S、目標(biāo)語(yǔ)言T、編譯程序?qū)崿F(xiàn)語(yǔ)言I

典型T形圖

如果A機(jī)器上已有一個(gè)用A機(jī)器碼實(shí)現(xiàn)的某高級(jí)語(yǔ)言L1的編譯程序，則我們可以用 L1語(yǔ)言編寫(xiě)另一種高級(jí)語(yǔ)言L2的編譯程序，把寫(xiě)好的L2編譯程序經(jīng)過(guò)L1編譯程序編譯后就可得到A機(jī)器代碼實(shí)現(xiàn)的L2編譯程序
可這樣理解：
- 用L1寫(xiě)成的 L2 -> A
- 用A寫(xiě)成的 L1 -> A (將源代碼為L(zhǎng)1的程序(該程序功能為L(zhǎng)2 -> A)變?yōu)锳(程序功能仍為L(zhǎng)2 -> A))
- 用A寫(xiě)成的 L2 -> A
組合的T形圖

二、高級(jí)語(yǔ)言及其語(yǔ)法描述

2.1 程序設(shè)計(jì)語(yǔ)言的定義

程序語(yǔ)言的內(nèi)涵：
- 語(yǔ)法：組合規(guī)律
- 語(yǔ)義
- 語(yǔ)用：目的

2.2 高級(jí)語(yǔ)言的一般特性

2.3 程序語(yǔ)言的語(yǔ)法描述

編譯原理 = 形式語(yǔ)言理論 + 編譯技術(shù)

形式語(yǔ)言
- 通過(guò)人們公認(rèn)的符號(hào)、表達(dá)方式所描述的一種語(yǔ)言，是一種通用語(yǔ)言。
- 形式語(yǔ)言是某個(gè)字母表上的字符串的集合，有一定的描述范圍。
文法的形式定義
- 文法G是一個(gè)四元組 $G=(V_N, V_T, S, ￡)$
  - $V_N$ :非終結(jié)符的有限集合
  - $V_T$ :終結(jié)符的有限集合， $V_N ∩ V_T =Φ$
  - $S$ :開(kāi)始符號(hào)且 $S∈ V_N$
  - $￡$ :形式為 $P→α$ 的產(chǎn)生式的有限集合，且 $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^* ，α∈ (V_N∪V_T)^*$
    怎么理解 $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^*$ ？
    1. $P$ 屬于 $(V_N∪V_T)$ 的閉包： $P∈(V_N∪V_T)^*$
    2. 但是必須要至少有一個(gè) $V_N$ ： $P∈(V_N∪V_T)^* V_N$
    3. 然而非終結(jié)符不一定在最后，也可以在最前： $P∈(V_N∪V_T)^* V_N (V_N∪V_T)^*$
  例子：文法 $G1 =( \{ N \}, \{0, 1\},N, \{N→0N, N→1N, N→0, N→1\})$ 其中:
  - $V_N = \{N\}$ ，[非終結(jié)符的有限集合]
  - $V_T = \{0, 1\}$ ，[終結(jié)符的有限集合/字母表]
  - $S = N$ ，[起始符]
  - $￡ = \{N→0N, N→1N, N→0, N→1\}$ 。[產(chǎn)生式]
- 終結(jié)符號(hào) $V_T$ :組成語(yǔ)言字母表中的基本符號(hào)，屬于個(gè)體記號(hào)
- 非終結(jié)符號(hào) $V_N$ :需要進(jìn)一步定義的符號(hào)，非終結(jié)符是一個(gè)類(或集合)記號(hào)，而不是個(gè)體記號(hào)。
- 開(kāi)始符號(hào) $S$ 屬于非終結(jié)符號(hào)，至少在某個(gè)產(chǎn)生式的左部出現(xiàn)一次（是研究目標(biāo)）
- 產(chǎn)生式 $￡$ (規(guī)則) :定義語(yǔ)法單位的一種書(shū)寫(xiě)規(guī)則
  
  若干個(gè)左部相同的產(chǎn)生式如 $P→α_1 , P→α_2 , P→α_3 , ... , P→α_n$ 可合并成一個(gè),縮寫(xiě)為 $P→α_1|α_2|α_3|…|α_n$ , 其中,每個(gè) $α_i$ 稱為是 $P$ 的一個(gè)候選式。
- 為了簡(jiǎn)化，文法表示
  - 只寫(xiě)出產(chǎn)生式部分
  - 約定第一個(gè)產(chǎn)生式的左部符號(hào)為初始符號(hào) 或在產(chǎn)生式前寫(xiě)上“G[A]”，其中G為文法名，A為初始符號(hào)
  例子：
  
  文法G[N]: N→0N, N→1N, N→0, N→1 => 終結(jié)符: {0,1}
  
  文法G[E]: E→E+E│E*E│(E)│i => 終結(jié)符: {+, *, (, ), i }
直接推導(dǎo)與歸約
- 直接推導(dǎo)
  - 如果A→γ是一個(gè)產(chǎn)生式，而 $α，β∈(V_T∪V_N)^*$ ，則將產(chǎn)生式A→γ用于符號(hào)串αAβ得到符號(hào)串αγβ，記為 αAβ => αγβ，稱αAβ直接推出αγβ。
  - 推導(dǎo): 設(shè) $α_1,α_2,...,α_n (n>0)∈(V_T∪V_N)^*$ ，且有 $α_1$ => $α_2$ =>… => $α_n$ ，則稱這個(gè)序列是從α1到αn的一個(gè)推導(dǎo)。
  - 若存在一個(gè)α1到αn的一個(gè)推導(dǎo)，則稱α1可推導(dǎo)出αn。
  - $α1$ => $^+ α_n$ (經(jīng)一步或若干步推導(dǎo))
  - $α_1$ => $^* α_n$ (經(jīng)0步或若干步推導(dǎo))
- 歸約是推導(dǎo)的逆過(guò)程
  - 若存在αAβ => αγβ ，則稱αγβ能夠直接歸約成αAβ 。
- 若在推導(dǎo)關(guān)系中，每次最先替換最左(右) 的非終結(jié)符，則稱為最左(右)推導(dǎo);
- 若在歸約過(guò)程中，每次最先歸約最左(右) 的非終結(jié)符，則稱為最左(右)歸約。
- 最左推導(dǎo)的逆過(guò)程是最右歸約。
句型、句子和語(yǔ)言
- 句型：假定G是一個(gè)文法，E是它的開(kāi)始符號(hào)，如果E => $^* α$ ，則稱 $α$ 是文法G的一個(gè)句型。
- 句子：僅由終結(jié)符組成的句型稱為句子。
- 語(yǔ)言：文法G所產(chǎn)生句子的全體。是一個(gè)集合。
Chomsky文法體系
- 相較于普通的形式語(yǔ)言，該體系對(duì)產(chǎn)生式的形式做了一些規(guī)定，分為四類，即0型、1型、2型、3型文法
- 0型：無(wú)限制文法，短語(yǔ)文法
  - 對(duì)應(yīng)的語(yǔ)言:遞歸可枚舉語(yǔ)言
  - 與圖靈機(jī)等價(jià)。
- 1型：也稱上下文有關(guān)文法(CSG:Context-sensitive Grammar)
  - 限制： $|P| \leq |\alpha|$ (在形式為 $P → \alpha$ 的定義中)
  - 對(duì)應(yīng)的語(yǔ)言:上下文有關(guān)語(yǔ)言(CSL:Context-sensitive Language)
  - 若不考慮ε，與線性有界自動(dòng)機(jī)(LBA, Linear Bounded Automaton)等價(jià)。
- 2型：也稱上下文無(wú)關(guān)文法(CFG:Context-free Grammar)
  - 在1型的基礎(chǔ)上，添加限制 $P∈V_N$
  - 對(duì)應(yīng)的語(yǔ)言:上下文無(wú)關(guān)語(yǔ)言 (CFL: Context-free Language)
  - 對(duì)應(yīng)的自動(dòng)機(jī):下推自動(dòng)機(jī)(PDA: Pushdown Automaton)。
- 3型：也稱正規(guī)文法
  - 右線性文法(Right-linear Grammar):任何產(chǎn)生式為 $A→ωB$ 或 $A→ω$ ，其中 $A、B∈ V_N, ω∈ V_T$ 。
  - 左線性文法(Left-linear Grammar):任何產(chǎn)生式為 $A→Bω$ 或 $A→ω$ ，其中 $A、B∈ V_N, ω∈ V_T$ 。
    
    式子右端有且最多只能有一個(gè)非終結(jié)符，且其位置固定在邊緣一側(cè)。
  - 等價(jià)于正規(guī)式
  - 對(duì)應(yīng)的語(yǔ)言:正規(guī)語(yǔ)言
  - 對(duì)應(yīng)的自動(dòng)機(jī):有限自動(dòng)機(jī)(Finite Automaton)。
    
    自動(dòng)機(jī)分類：
    
    有限/無(wú)限自動(dòng)機(jī)：狀態(tài)數(shù)量有限/無(wú)限；
    
    確定/非確定自動(dòng)機(jī)：在某一個(gè)狀態(tài)接收同一輸入時(shí)，轉(zhuǎn)換到的下一個(gè)狀態(tài)確定/不確定。
語(yǔ)法樹(shù)：語(yǔ)法樹(shù)是表示一個(gè)句型推導(dǎo)過(guò)程的圖，是一棵倒立的樹(shù)。
二義性：如果一個(gè)文法的句子(句型)存在兩棵語(yǔ)法樹(shù)，那么，該句子是二義性的。如果一個(gè)文法包含二義性的句子,則稱這個(gè) 文法是二義性的; 否則，該文法是無(wú)二義性的。

三、詞法分析

3.1 對(duì)詞法分析器的要求

單詞符號(hào)
- 分類：關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、界符
  - 一個(gè)語(yǔ)言的單詞符號(hào)如何分類，分成幾類，怎樣編碼取決于處理上的方便。
    - 標(biāo)識(shí)符一般統(tǒng)歸為一種。
    - 常數(shù)則宜按類型（整、實(shí)、布爾等）分種。
    - 關(guān)鍵字可視其全體為一種，也可以一字一種。采用一字一種的分法實(shí)際處理起來(lái)較為方便。
    - 運(yùn)算符可采用一符一種的分法，但也可以把具有一定共性的運(yùn)算符視為一類。
    - 至于界符一般用一符一種的分法。
- 表示形式：詞法分析器輸出的單詞符號(hào)常表示成二元式：（單詞種別，單詞符號(hào)的屬性值）
  - 單詞種別是語(yǔ)法分析需要的信息
  - 單詞符號(hào)屬性值則是編譯其它階段需要的信息，簡(jiǎn)稱單詞值。
- 屬性：?jiǎn)卧~符號(hào)的屬性是指單詞符號(hào)的特征或特性。屬性值則是反映特性或特征的值。
語(yǔ)法分析器的實(shí)現(xiàn)方式
- 完全獨(dú)立方式：詞法分析程序作為單獨(dú)一遍來(lái)實(shí)現(xiàn)。詞法分析程序讀入整個(gè)源程序，它的輸出作為語(yǔ)法分析程序的輸入。
  - 編譯程序結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化
- 相對(duì)獨(dú)立方式：把詞法分析程序作為語(yǔ)法分析程序的一個(gè)獨(dú)立子程序。語(yǔ)法分析程序需要新符號(hào)時(shí)調(diào)用這個(gè)子程序。
  - 避免了中間文件生成，可以提高效率。

3.2 語(yǔ)法分析器的設(shè)計(jì)

分析器結(jié)構(gòu)

分析器的結(jié)構(gòu)

超前搜索：一般在常數(shù)，算符和界符需要
狀態(tài)轉(zhuǎn)換圖：一個(gè)有限方向圖

3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)

詞法規(guī)則 -> 正規(guī)式 -> NFA（非確定有限自動(dòng)機(jī)） -> DFA（確定有限自動(dòng)機(jī)） -> 詞法分析器(Scanner)

正規(guī)式與正規(guī)集

字母表上的正規(guī)式和正規(guī)集遞歸定義如下：

（1） $ε$ 和 $φ$ 都是 $∑$ 上的正規(guī)式，它們所表示的正規(guī)集分別為 $\lbrace ε \rbrace$ 和 $φ$ 。
（2）任意元素 $a∈∑$ ， $a$ 是 $∑$ 上的一個(gè)正規(guī)式，它所表示的正規(guī)集是 ${a}$ ；
（3）假定 $U$ 和 $V$ 都是 $∑$ 上的正規(guī)式，它們所表示的正規(guī)集記為 $L(U)$ 和 $L(V)$ ，那么 $(U|V)$ ， $(U·V)$ 和 $(U)^*$ 都是正規(guī)式，他們所表示的正規(guī)集分別記為 $L(U)∪L(V)$ ， $L(U)L(V)$ 和 $(L(U))^*$ 。
（4）僅由有限次使用上述三步而得到的表達(dá)式才是 $∑$ 上的正規(guī)式，它們所表示的字集才是 $∑$ 上的正規(guī)集。
- 運(yùn)算符：
  - |讀為”或”
  - ·讀為”連接”
  - *讀為”閉包”
  一般地，連接符.可省略不寫(xiě)，在不引起混淆的情況下，括號(hào)可省去
- 正規(guī)式運(yùn)算符的優(yōu)先順序?yàn)椋?code>*最高，·次之，|最低。
- 若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者等價(jià)，記為U=V。
自動(dòng)機(jī)
- 自動(dòng)機(jī)的定義：
  - 具有離散輸入輸出的數(shù)學(xué)模型。
  - 自動(dòng)機(jī)接受一定的輸入，執(zhí)行一定的動(dòng)作，產(chǎn)生一定的結(jié)果。使用狀態(tài)遷移描述整個(gè)工作過(guò)程。
    
    狀態(tài)：一個(gè)標(biāo)識(shí)，能區(qū)分自動(dòng)機(jī)在不同時(shí)刻的狀況。有限狀態(tài)系統(tǒng)具有任意有限數(shù)目的內(nèi)部“狀態(tài)”。
  可能的狀態(tài)、運(yùn)行的規(guī)則都是事先確定的。一旦開(kāi)始運(yùn)行，就按照事先確定的規(guī)則工作，因此叫“自動(dòng)機(jī)”。
  - 自動(dòng)機(jī)的本質(zhì)
    - 根據(jù)狀態(tài)、輸入和規(guī)則決定下一個(gè)狀態(tài)
    - 狀態(tài) ＋輸入＋規(guī)則 ―> 狀態(tài)遷移
確定有限自動(dòng)機(jī)（DFA）
- DFA是一個(gè)五元組 $M=(S,Σ,δ,s_0,F)$
  - $S$ : 有限的狀態(tài)集合，每個(gè)元素稱為一個(gè)狀態(tài)；
  - $Σ$ : 有限的輸入字母表，每個(gè)元素稱為一個(gè)輸入字符；
  - $δ$ : 轉(zhuǎn)換函數(shù)(狀態(tài)轉(zhuǎn)移集合) : $S×Σ→S$ ；
  - $s_0$ : 初始狀態(tài)， $s_0∈ S$ ；（初始狀態(tài)只能有一個(gè)）
  - $F$ : 終止?fàn)顟B(tài)集， $F\subseteq S$ ；
- 狀態(tài)轉(zhuǎn)移矩陣：一個(gè)DFA可用一個(gè)矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示的值。
- 狀態(tài)轉(zhuǎn)換圖：一個(gè)DFA可以表示成一個(gè)（確定的）狀態(tài)轉(zhuǎn)換圖。
- 擴(kuò)展轉(zhuǎn)移函數(shù)：
  - $δ '$ 函數(shù)
    - 接收一個(gè)字符串的狀態(tài)轉(zhuǎn)移函數(shù)。
    - $δ ' :S×Σ^*→S$
  - 對(duì)任何 $s∈ S$ ，定義：
    1. $δ '(s,ε)=s$
    2. 若 $ω$ 是一個(gè)字符串, $a$ 是一個(gè)字符，定義： $δ '(s,ωa)=δ(δ '(s,ω)a)$
  - 對(duì)于DFA： $δ '(s,a)=δ(δ '(s,ε)a)=δ (s,a)$ ，即對(duì)于單字符， $δ '$ 和 $δ$ 是相等的。
  - 被DFA接收的字符串 : 輸入結(jié)束后使DFA的狀態(tài)到達(dá)終止?fàn)顟B(tài)。否則該字符串不能被DFA接收。
  - DFA接收的語(yǔ)言 : 被DFA接收的字符串的集合。 $L(M) =\lbrace α|δ’ (s_0,α)∈F \rbrace$
非確定有限自動(dòng)機(jī)（NFA）
- NFA是一個(gè)五元組
  - $S,Σ$ : 定義同上；
  - $δ$ : 轉(zhuǎn)換函數(shù) : $S×Σ^*→2^S$ (狀態(tài)子集) ；對(duì)于某個(gè)狀態(tài) $s∈ S$ 和一個(gè)輸入字母 $a$ : $δ (s,a)=S'\subseteq S$
  - $S_0$ : $S_0∈ S$ 為非空初態(tài)集；
  - $F$ : 終止?fàn)顟B(tài)集， $F\subseteq S$ ；
- 狀態(tài)轉(zhuǎn)移矩陣：狀態(tài)轉(zhuǎn)換矩陣中的每一項(xiàng)都是一個(gè)集合。包含空集。
- 被NFA接收的字符串 : 接受一個(gè)字符后NFA進(jìn)入一個(gè)狀態(tài)集，此集合包含至少一個(gè)中的狀態(tài)。
- NFA接收的語(yǔ)言 : 被NFA接收的字符串的集合。 $L(M) =\lbrace α|δ’ (s_0,α)\bigcap F \neq \phi \rbrace$
DFA和NFA的比較：

比較
- 輸入字母
  - DFA的每一個(gè)狀態(tài)對(duì)于字母表中的每一個(gè)符號(hào)都有一個(gè)轉(zhuǎn)移函數(shù)。
  - NFA中，一個(gè)狀態(tài)對(duì)于字母表中的每一個(gè)符號(hào)可能不存在轉(zhuǎn)移函數(shù)或者存在空轉(zhuǎn)換。
- 轉(zhuǎn)移狀態(tài)
  - DFA中的下一狀態(tài)是確定的，即唯一的
  - NFA中的下一狀態(tài)是不確定的，可能存在多個(gè)轉(zhuǎn)移狀態(tài)。
- NFA和DFA的等價(jià)性：DFA是NFA的特例，所以NFA必然能接收DFA能接收的語(yǔ)言。
  
  NFA轉(zhuǎn)化DFA_1
  
  NFA轉(zhuǎn)化DFA_2
轉(zhuǎn)換矩陣中的集合內(nèi)都是等價(jià)狀態(tài)（可經(jīng)過(guò)n個(gè)達(dá)到）

轉(zhuǎn)換矩陣構(gòu)成方法：由起始態(tài)構(gòu)造等價(jià)狀態(tài)集，開(kāi)始推導(dǎo)。直到右側(cè)出現(xiàn)的等價(jià)集全部已經(jīng)被推導(dǎo)過(guò)為止。

對(duì)于有多個(gè)初態(tài)的NFA，則可以將這些初態(tài)視為等價(jià)集（可以在初態(tài)前加一個(gè)新的初態(tài)，通過(guò)與所有初態(tài)相連）。同理，多個(gè)終態(tài)也可以視為等價(jià)集。
正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性
- 正規(guī)式與有限自動(dòng)機(jī)是等價(jià)的。
  1. 對(duì)任何FA M，都存在一個(gè)正規(guī)式V，使得：；
  2. 對(duì)任何正規(guī)式V，都存在一個(gè)FA M，使得：；
- 由NFA構(gòu)造等價(jià)正規(guī)式：
  
  NFA構(gòu)造正軌式
- 從正規(guī)式構(gòu)造等價(jià)的NFA：（Thompson算法）
  
  正規(guī)式構(gòu)造NFA_1
  
  正規(guī)式構(gòu)造NFA_2
  
  所有的閉包可化簡(jiǎn)為自循環(huán)。
DFA的化簡(jiǎn)
- DFA的化簡(jiǎn)釋之尋找一個(gè)狀態(tài)數(shù)比M少的DFA M'，使L(M)=L(M')。
  
  狀態(tài)s和t等價(jià)：若任意從狀態(tài)s出發(fā)能讀出字α停于終態(tài)，則從t出發(fā)也能讀出α而停于終態(tài)；反之,若從狀態(tài)t出發(fā)能讀出字α停于終態(tài)，則從s出發(fā)也能讀出α而停于終態(tài)。
  
  狀態(tài)s和t可區(qū)別：狀態(tài)s和t不等價(jià)。存在狀態(tài)s讀入α停于終態(tài)，但狀態(tài)t讀入α不停于終態(tài)。
- 化簡(jiǎn)思路：將DFA M的狀態(tài)集劃分為不相交的子集，使不同的兩個(gè)子集的狀態(tài)可區(qū)別，同一個(gè)子集的狀態(tài)都等價(jià)。
- 化簡(jiǎn)步驟
  - 把狀態(tài)集S劃分為兩個(gè)子集，得初始劃分 $∏= \lbrace I^{(1)}, I^{(2)} \rbrace$ ，其中 $I^{(1)}$ 為終態(tài)集， $I^{(2)}$ 為非終態(tài)集；
  - 設(shè)當(dāng)前 $∏= \lbrace I^{(1)}, I^{(2)}, … ,I^{(m)}\rbrace,$ 檢查 $∏$ 中每個(gè) $I^{(k)}$ 是否可以再分
    
    依據(jù)為:如果存在一個(gè)輸入字符 $a$ ，使得 $I^{(k)}_a$ 不全包含在現(xiàn)行 $∏$ 的子集中，就將 $I^{(k)}$ 進(jìn)行劃分。
  - 一般地，如果 $I^{(k)}_a$ 落入現(xiàn)行 $∏$ 的N個(gè)子集中，則應(yīng)將 $I^{(k)}$ 劃分成N個(gè)不相交的組，使得每個(gè)組 $I^{(k_i)}$ 的 $I^{(k_i)}_a$ 都落入 $∏$ 的同一子集。
  - 重復(fù)第二步,直至 $∏$ 中子集數(shù)不再增長(zhǎng)為止。
  步驟舉例

正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性
- 對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，只要證明L(G)=L(M)，即可證明G和M等價(jià)。
- 右線性文法：以結(jié)束狀態(tài)為空（純終結(jié)符），從起始狀態(tài)作為非終結(jié)符開(kāi)始分析
- 左線性文法：以起始狀態(tài)為空（純終結(jié)符），從結(jié)束狀態(tài)作為非終結(jié)符開(kāi)始分析

3.4 詞法分析器的自動(dòng)生成

Lex：輸入為構(gòu)詞規(guī)則（以正規(guī)表達(dá)式的形式），輸出為該構(gòu)詞規(guī)則下的詞法分析器

正規(guī)表達(dá)式的定義是什么？ ??

Yacc

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

kN_編譯原理_1

kN_編譯原理_1

一、引論

1.1 什么叫編譯程序

1.2 編譯過(guò)程概述

1.3 編譯程序的結(jié)構(gòu)

1.4 編譯程序的生成

二、高級(jí)語(yǔ)言及其語(yǔ)法描述

2.1 程序設(shè)計(jì)語(yǔ)言的定義

2.2 高級(jí)語(yǔ)言的一般特性

2.3 程序語(yǔ)言的語(yǔ)法描述

三、詞法分析

3.1 對(duì)詞法分析器的要求

3.2 語(yǔ)法分析器的設(shè)計(jì)

3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)

3.4 詞法分析器的自動(dòng)生成

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

kN_編譯原理_1

一、引論

1.1 什么叫編譯程序

1.2 編譯過(guò)程概述

1.3 編譯程序的結(jié)構(gòu)

1.4 編譯程序的生成

二、高級(jí)語(yǔ)言及其語(yǔ)法描述

2.1 程序設(shè)計(jì)語(yǔ)言的定義

2.2 高級(jí)語(yǔ)言的一般特性

2.3 程序語(yǔ)言的語(yǔ)法描述

三、詞法分析

3.1 對(duì)詞法分析器的要求

3.2 語(yǔ)法分析器的設(shè)計(jì)

3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)

3.4 詞法分析器的自動(dòng)生成

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、引論

三、詞法分析