編譯原理及實現(xiàn)技術(shù)：5-詞法分析-自動機與正則表達(dá)式、詞法分析器的設(shè)計

第二章：詞法分析

自動機與正則表達(dá)式

詞法分析器的設(shè)計內(nèi)容介紹自動機與正則表達(dá)式的關(guān)系詞法分析器的具體設(shè)計1.自動機與正則表達(dá)式的關(guān)系定理：對任一確定有限自動機A，存在一正則表達(dá)式e,使得L(A)=L(e),反之亦然。DFA正則表達(dá)式NFA1.1DFA到正則表達(dá)式123ab12ab12313ab12a|b13ab*

cabc1.1DFA到正則表達(dá)式S1α12α23α3ZεεεSα1|α2|α3Z1.1DFA到正則表達(dá)式a651324aabbaba(ab|ba)a*bSZ1.2正則表達(dá)式到NFA12ab12a|b12b*123ab12ab123bSWZα7εε1.2正則表達(dá)式到NFA1ε2b1ab|d*2錯誤的例子1ε21abd1.3相關(guān)的例子給出一個正則表達(dá)式(a|b)(c|d)*(e|f)0a24bεcdε13ef1.3相關(guān)的例子轉(zhuǎn)化成DFAabcdefA{0}+{123}{123}B{123}{23}{23}{4}{4}C{23}{23}{23}{4}{4}D{4}*1.3相關(guān)的例子最小化{A,B,C}{D}{A}{B,C}{D}AaDbcdBCef類型題構(gòu)造與正則表達(dá)式a((a|b)*ab*a)b等價的最簡DFA，要求給出中間轉(zhuǎn)換步驟和結(jié)果

Fεεa,bSCBaZba

A

Ea

D

Gεεb{S}+{A,F,D}{F,E,D,G,C}{F,E,D,G,C}{F,D}{A,F,D}{F,E,B,D,G,C}{F,G,D,C}*{F,D}{F,D}{F,E,D,G,C}{F,G,D,C}{F,E,B,D,G,C}{F,G,D,C}{F,E,B,D,G,C}{F,G,Z,D,C}{F,E,B,D,G,C}{F,G,Z,D,C}{F,E,B,D,G,C}{F,G,D,C}ab0+1223145*332545464645

b102

a3456

b

a

b

a

a

b

a

b

a

b確定化結(jié)果

a1,302,5

a46

b

a

b

a

b

a

a

b2.詞法分析器的設(shè)計設(shè)計步驟確定詞法分析的接口確定單詞的結(jié)構(gòu)給出單詞的描述設(shè)計算法2.1詞法分析器的工作過程詞法分析器（Scanner）輸入流詞法描述（正則表達(dá)式）NFADFATokenListerror2.2詞法分析器的接口詞法分析器有兩類，一類是僅作為語法分析的子程序：另一類是作為編譯器的獨立一遍處理器：源程序詞法分析語法分析charreadTokencall源程序詞法分析語法分析charToken2.3單詞的結(jié)構(gòu)源程序的處理過程是，首先從源程序文件一個字符一個字符進行讀取，并逐個分離出單詞，然后構(gòu)造它們的機內(nèi)表示Token。關(guān)于Token的結(jié)構(gòu)沒有統(tǒng)一的規(guī)定，但至少包括兩部分內(nèi)容：單詞的類型（語法信息）單詞的內(nèi)容（語義信息）Token結(jié)構(gòu)

2.4一種可行的Token樣例類型內(nèi)容如果單詞為標(biāo)識符，則類型填1如果單詞為常量，則類型填2如果類型為保留字或特殊符號，則類型填該保留字或特殊符號所對應(yīng)的數(shù)字標(biāo)識符索引表123......n保留字、特殊符號表3while4if5%......56}常量索引表123......n2.4一種可行的Token樣例例子程序段：{intx,y;x=10;y=11;x=x+y;....}2.5程序的實現(xiàn)標(biāo)識符的實現(xiàn)拼接標(biāo)識符，停留在某狀態(tài)，確定是標(biāo)識符狀態(tài)，查找保留字表，查找標(biāo)識符表，確定其在標(biāo)識符表中位置，生成對應(yīng)Token整數(shù)的實現(xiàn)特殊符號的實現(xiàn)2.6注意的問題名字的的實現(xiàn)方式復(fù)合單詞的識別數(shù)的轉(zhuǎn)換向前看若干個字符