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

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

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

3、ab a* a(b|c) (a|b)(a|c) (a|b)c* 2 有窮自動(dòng)機(jī)到正則表達(dá)式有窮自動(dòng)機(jī)到正則表達(dá)式 n舉例舉例 a a a a* * 2 有窮自動(dòng)機(jī)到正則表達(dá)式有窮自動(dòng)機(jī)到正則表達(dá)式 n舉例舉例 2 有窮自動(dòng)機(jī)到正則表達(dá)式有窮自動(dòng)機(jī)到正則表達(dá)式 n舉例舉例 3 實(shí)例實(shí)例 n正則表達(dá)式到有窮自動(dòng)機(jī)正則表達(dá)式到有窮自動(dòng)機(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 語(yǔ)言程序語(yǔ)言程序 類類 pcode 代嗎代嗎 源語(yǔ)言源語(yǔ)言(PL/

4、0) 目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言(類類 pcode) 實(shí)現(xiàn)語(yǔ)言（實(shí)現(xiàn)語(yǔ)言（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; （* * 常量說(shuō)明部分常量說(shuō)明部分 * *） VAR B,C; VAR B,C; （* * 變量變量說(shuō)明部分說(shuō)明部分 * *） PROCEDURE PROCEDURE P; P; （* * 過(guò)程過(guò)

5、程說(shuō)明部分說(shuō)明部分 * *） 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的過(guò)程體的過(guò)程體 p的過(guò)程體的過(guò)程體 主主程序程序體體 程序程序 分程序分程序 . 內(nèi)的文

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

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

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