有限自動(dòng)機(jī)與詞法分析器

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

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

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

4、 pcode代碼,PL/0源程序,,,輸入,輸出,PL/0編譯系統(tǒng)的結(jié)構(gòu)框架,PL/0程序示例,CONST A=10; （* 常量說(shuō)明部分 *） VAR B,C; （* 變量說(shuō)明部分 *） PROCEDURE P; （* 過(guò)程說(shuō)明部分 *） 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的過(guò)程體,p的過(guò)程體,主程序體,,,,,,,,,,,程序,,分程序,,,.,,內(nèi)的文字表示非終結(jié)符,,或,,內(nèi)

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

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

8、HEN等運(yùn)算符： 如：+、-、*、/、：=、#、>=、<=等標(biāo)識(shí)符： 用戶定義的變量名、常數(shù)名、過(guò)程名常數(shù)： 如：10、25、100等整數(shù)界符： 如：‘,’、‘.’ 、‘;’ 、‘(’ 、‘)’等,,詞法分析過(guò)程GETSYM所要完成的任務(wù)：讀源程序（getch)濾空格識(shí)別保留字識(shí)別標(biāo)識(shí)符拼數(shù)識(shí)別單字符單詞拼雙字符單詞,實(shí)驗(yàn)報(bào)告格式,格式實(shí)驗(yàn)?zāi)康闹饕浖治鲞^(guò)程（算法、重點(diǎn)語(yǔ)句、對(duì)應(yīng)書中的原