有限自動機與詞法分析器

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

2、表達式到有窮自動機,結(jié)構(gòu)化自動機RE = εRE = a,1 正則表達式到有窮自動機,結(jié)構(gòu)化自動機RE = A | BRE = AB,1 正則表達式到有窮自動機,結(jié)構(gòu)化自動機RE = A*,1 正則表達式到有窮自動機,結(jié)構(gòu)化自動機舉例aa | baba*a(b|c)(a|b)(a|c)(a|b)c*,2 有窮自動機到正則表達式,舉例Φεaa*,2 有窮自動機到正則表達式,舉例,2 有窮自動機到正則表達式

3、,舉例,3 實例,正則表達式到有窮自動機示例((a|bc)*d)+((0|1)* (2|3)+)|0011練習P60 2(1,2), 3(1,2),4(1),PL/0編譯程序,,,,PL/0編譯程序,PL/0 語言程序,類 pcode 代嗎,,,源語言(PL/0)目標語言(類 pcode)實現(xiàn)語言（pascal),,,,,,,PL/0,類 pcode,pascal,,,,,PL/0編譯程序,類 pcode解釋程序,,,,類

4、 pcode代碼,PL/0源程序,,,輸入,輸出,PL/0編譯系統(tǒng)的結(jié)構(gòu)框架,PL/0程序示例,CONST A=10; （* 常量說明部分 *） VAR B,C; （* 變量說明部分 *） PROCEDURE P; （* 過程說明部分 *） VAR D; PROCEDURE Q; VAR X; BEGIN READ(X);

5、 D:=X; WHILE X#0 DO CALL P; END; BEGIN WRITE(D); CALL Q; END; BEGIN CALL P; END.,Q的過程體,p的過程體,主程序體,,,,,,,,,,,程序,,分程序,,,.,,內(nèi)的文字表示非終結(jié)符,,或,,內(nèi)

6、的文字或符號表示終結(jié)符,,const,,ident,number,=,,,,,;,var,ident,,,;,;,procedure,ident,;,分程序,語句,,,,,,,,,,,,,,,,,,,分程序,,,,,,PL/0編譯程序的結(jié)構(gòu),詞法分析程序,語法語義分析程序,代碼生成程序,表格管理程序,出錯處理程序,,,,,,,PL/0源程序,目標程序,PL/0編譯程序的總體設計,其編譯過程采用一趟掃描方式以語法、語義分析程序為核心

7、 詞法分析程序和代碼生成程序都作為一個過程，當語法分析需要讀單詞時就調(diào)用詞法分析程序，而當語法、語義分析正確，需要生成相應的目標代碼時，則調(diào)用代碼生成程序。表格管理程序?qū)崿F(xiàn)變量，常量和過程標識符的信息的登錄與查找。出錯處理程序，對詞法和語法、語義分析遇到的錯誤給出在源程序中出錯的位置和與錯誤 性質(zhì)有關(guān)的編號，并進行錯誤恢復。,PL/0編譯程序詞法分析的設計與實現(xiàn),識別的單詞：保留字或關(guān)鍵字：如：BEGIN、 END、 IF、 T

8、HEN等運算符： 如：+、-、*、/、：=、#、>=、<=等標識符： 用戶定義的變量名、常數(shù)名、過程名常數(shù)： 如：10、25、100等整數(shù)界符： 如：‘,’、‘.’ 、‘;’ 、‘(’ 、‘)’等,,詞法分析過程GETSYM所要完成的任務：讀源程序（getch)濾空格識別保留字識別標識符拼數(shù)識別單字符單詞拼雙字符單詞,實驗報告格式,格式實驗目的主要軟件分析過程（算法、重點語句、對應書中的原