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

第二章：詞法分析

自動機與正則表達式

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

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

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確定化結果

a1,302,5

a46

b

a

b

a

b

a

a

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

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