10-第三章有限自動機(jī)與詞法分析器

1、第三章第三章 有限自動有限自動 機(jī)與詞法分析器機(jī)與詞法分析器 任課教師任課教師 王養(yǎng)廷王養(yǎng)廷 主要內(nèi)容主要內(nèi)容 n正則表達(dá)式到有窮自動機(jī)的轉(zhuǎn)換正則表達(dá)式到有窮自動機(jī)的轉(zhuǎn)換 n有窮自動機(jī)到正則表達(dá)式的轉(zhuǎn)換有窮自動機(jī)到正則表達(dá)式的轉(zhuǎn)換 n實例實例 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) n正則定理正則定理 對任意正則表達(dá)式對任意正則表達(dá)式RE，均可構(gòu)造出一個有，均可構(gòu)造出一個有 窮自動機(jī)窮自動機(jī)FA，使得，使得FA所接受的字符串等所接受的字符串等 價于價于RE所定義的正則集。所定義的正則集。 正則表達(dá)式正則表達(dá)式RE與有窮自動機(jī)與有窮自動機(jī)FA等價等價 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)

2、式到有窮自動機(jī) n正則表達(dá)式到有窮自動機(jī)的轉(zhuǎn)換正則表達(dá)式到有窮自動機(jī)的轉(zhuǎn)換 正則表達(dá)式到正則表達(dá)式到NFA NFA到到DFA轉(zhuǎn)換轉(zhuǎn)換 DFA極小化極小化 DFA等價性等價性 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) n結(jié)構(gòu)化自動機(jī)結(jié)構(gòu)化自動機(jī) RE = RE = aRE = a 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) n結(jié)構(gòu)化自動機(jī)結(jié)構(gòu)化自動機(jī) RE = A | B RE = AB 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) n結(jié)構(gòu)化自動機(jī)結(jié)構(gòu)化自動機(jī) RE = A* 1 正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) n結(jié)構(gòu)化自動機(jī)舉例結(jié)構(gòu)化自動機(jī)舉例 a a | b

3、ab a* a(b|c) (a|b)(a|c) (a|b)c* 2 有窮自動機(jī)到正則表達(dá)式有窮自動機(jī)到正則表達(dá)式 n舉例舉例 a a a a* * 2 有窮自動機(jī)到正則表達(dá)式有窮自動機(jī)到正則表達(dá)式 n舉例舉例 2 有窮自動機(jī)到正則表達(dá)式有窮自動機(jī)到正則表達(dá)式 n舉例舉例 3 實例實例 n正則表達(dá)式到有窮自動機(jī)正則表達(dá)式到有窮自動機(jī) 示例示例 (a|bc)*d)+ (0|1)* (2|3)+)|0011 練習(xí)練習(xí) P60 2(1,2), 3(1,2),4(1) PL/0PL/0編譯程序編譯程序 PL/0編譯程序編譯程序 PL/0 語言程序語言程序 類類 pcode 代嗎代嗎 源語言源語言(PL/

4、0) 目標(biāo)語言目標(biāo)語言(類類 pcode) 實現(xiàn)語言（實現(xiàn)語言（pascal) PL/0 類類 pcode pascal PL/0PL/0編譯程序編譯程序 類類 pcodepcode解釋解釋程序程序 類類 pcode代碼代碼 PL/0源程序源程序 輸入輸入 輸出輸出 PL/0PL/0編譯系統(tǒng)的結(jié)構(gòu)框架編譯系統(tǒng)的結(jié)構(gòu)框架 PL/0PL/0程序示例程序示例 CONST A=10; CONST A=10; （* * 常量說明部分常量說明部分 * *） VAR B,C; VAR B,C; （* * 變量變量說明部分說明部分 * *） PROCEDURE PROCEDURE P; P; （* * 過程過

5、程說明部分說明部分 * *） VAR D;VAR D; PROCEDURE PROCEDURE Q;Q; VAR X; VAR X; BEGINBEGIN READ(X); READ(X); D:=X; D:=X; WHILE X#0 WHILE X#0 DO CALL P; DO CALL P; END; END; BEGINBEGIN WRITE(D); WRITE(D); CALL Q; CALL Q; END; END; BEGINBEGIN CALL P; CALL P; END. END. Q的過程體的過程體 p的過程體的過程體 主主程序程序體體 程序程序 分程序分程序 . 內(nèi)的文

6、字表示內(nèi)的文字表示非終結(jié)符非終結(jié)符 或內(nèi)的文字或符號表示內(nèi)的文字或符號表示終結(jié)符終結(jié)符 const identnumber varident procedure ident 分程序分程序 語句語句 分程序分程序 PL/0PL/0編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 詞法分析程詞法分析程 序序 語法語義分析程序語法語義分析程序 代碼生成程序代碼生成程序 表格管理程序表格管理程序 出錯處理程序出錯處理程序 PL/0PL/0源程序源程序 目標(biāo)程序目標(biāo)程序 PL/0PL/0編譯程序的總體設(shè)計編譯程序的總體設(shè)計 n其編譯過程采用其編譯過程采用一趟掃描方式一趟掃描方式 n以語法以語法、語義分析語義分析程序程序為核

7、心為核心 詞法分析詞法分析程序和程序和代碼生成代碼生成程序都作為一個程序都作為一個過程過程，當(dāng)語法分，當(dāng)語法分 析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語法析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語法、語義語義 分析正確，需要生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生分析正確，需要生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生 成程序。成程序。 n表格管理表格管理程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)變量變量，常量常量和和過程過程標(biāo)識符的標(biāo)識符的信息的登信息的登 錄與查找錄與查找。 n出錯處理出錯處理程序，對詞法和語法程序，對詞法和語法、語義分析遇到的錯誤給語義分析遇到的錯誤給 出在源程序中出在源程序中出錯的位置出錯的位置和與和與錯誤錯誤

8、 性質(zhì)有關(guān)性質(zhì)有關(guān)的編號，并的編號，并 進(jìn)行錯誤恢復(fù)。進(jìn)行錯誤恢復(fù)。 PL/0PL/0編譯程序詞法分析的設(shè)計與實現(xiàn)編譯程序詞法分析的設(shè)計與實現(xiàn) 識別的單詞：識別的單詞： 保留字或關(guān)鍵字：如：保留字或關(guān)鍵字：如：BEGINBEGIN、 ENDEND、 IFIF、 THENTHEN 等等 運算符運算符： 如：如：+ +、- -、* *、/ /、：、：= =、# #、=、=等等 標(biāo)識符標(biāo)識符： 用戶定義的變量名、常數(shù)名、過程名用戶定義的變量名、常數(shù)名、過程名 常數(shù)常數(shù)： 如：如：1010、2525、100100等整數(shù)等整數(shù) 界符界符： 如：如：,、. . 、; ; 、( ( 、 )等等 詞法分析過程詞法分析過程GETSYMGETSYM所要完成的任務(wù)：所要完成的任務(wù)： 讀源程序（讀源程序（getch)getch) 濾空格濾空格 識別識別保留字保留字 識別標(biāo)識符識別標(biāo)識符 拼數(shù)拼數(shù) 識別單字符單詞識別單字符單詞 拼雙字符單詞拼雙字符單詞 實驗報告格式實驗報告格式 n格式格式 實驗?zāi)康膶嶒災(zāi)康?主要軟件主要軟件 分析過程（算法、重點語句、對應(yīng)書中的原理）分析過程（