編譯原理 3 詞法分析學習課件

第3章詞法分析

哈爾濱工業(yè)大學陳鄞3.1單詞的描述3.2

單詞的識別3.3詞法分析階段的錯誤處理3.4詞法分析器生成工具Lex

提綱3.1單詞的描述語言L={a}{a,b}*({ε}∪({.,_}{a,b}{a,b}*))

正則表達式(RegularExpression，RE)是一種用來描述正則語言的更緊湊的表示方法例：r=a(a|b)*(ε|(.|_)(a|b)(a|b)*)正則表達式可以由較小的正則表達式按照特定規(guī)則遞歸地構建。每個正則表達式r定義（表示）一個語言，記為L(r)。這個語言也是根據(jù)r

的子表達式所表示的語言遞歸定義的假設r和s都是RE，表示的語言分別是L(r)和L(s)，則

r|s是一個RE，L(r|s)=L(r)∪L(s)

rs

是一個RE，L(rs)=L(r)L(s)

r*

是一個RE，L(r*)=(L(r))*

(r)是一個RE，L((r))=L(r)

ε是一個RE，L(ε)={ε}

如果a∈∑，則a是一個RE，L(a)={a}正則表達式的定義運算的優(yōu)先級：*、連接、|令∑={a,b}，則L(a|b)=L(a)∪L(b)={a}∪={a,b}L((a|b)(a|b))=L(a|b)L(a|b)={a,b}{a,b}={aa,ab,ba,bb}L(a*)=(L(a))*={a}*={ε,a,aa,aaa,...}L((a|b)*)=(L(a|b))*

={a,b}*={ε,a,b,aa,ab,ba,bb,aaa,...}L(a|a*b)={a,b,ab,aab,aaab,...}例十進制整數(shù)的RE(1|...|9)(0|...|9)*|0八進制整數(shù)的RE0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*十六進制整數(shù)的RE0x(1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f|A|…|F)*例：C語言無符號整數(shù)的RE可以用RE定義的語言叫做正則語言(regularlanguage)或正則集合(regularset)正則語言RE的代數(shù)定律定律描述r｜s

=s｜r｜是可以交換的r｜（

s｜t

）=（r｜

s）｜

t｜是可結合的r（st

）=（rs）t連接是可結合的r（s｜t

）=rs｜rt;

(s｜t

）r=s

r｜tr連接對｜是可分配的εr=rε

=rε是連接的單位元r*=（

r｜

ε

）*

閉包中一定包含εr**=r*

*具有冪等性對任何正則文法G，存在定義同一語言的正則表達式r對任何正則表達式r，存在生成同一語言的正則文法G

正則文法與正則表達式等價

正則定義是具有如下形式的定義序列： d1→r1 d2→r2 … dn→rn

其中：每個di都是一個新符號，它們都不在字母表Σ中，而且各不相同每個ri是字母表Σ∪{d1,d2

,…,di-1}上的正則表達式給一些RE命名，并在之后的RE中像使用字母表中的符號一樣使用這些名字正則定義（RegularDefinition）C語言中標識符的正則定義digit→0|1|2|…|9letter_→

A|B|…|Z|a|b|…|z|_id→letter_(letter_|digit)*例1（整型或浮點型）無符號數(shù)的正則定義digit→0|1|2|…|9digits→digitdigit*optionalFraction→.digits|εoptionalExponent→(E(+|-|ε)digits)|εnumber→digits

optionalFraction

optionalExponent2 2.15 2.15E+3 2.15E-3 2.15E3 2E-3例23.1單詞的描述3.2單詞的識別3.3詞法分析階段的錯誤處理3.4詞法分析器生成工具Lex

提綱3.2單詞的識別有窮自動機(FiniteAutomata)有窮自動機的分類從正則表達式到有窮自動機有窮自動機(FiniteAutomata，F(xiàn)A)由兩位神經(jīng)物理學家MeCuloch和Pitts于1948年首先提出，是對一類處理系統(tǒng)建立的數(shù)學模型這類系統(tǒng)具有一系列離散的輸入輸出信息和有窮數(shù)目的內(nèi)部狀態(tài)（狀態(tài)：概括了對過去輸入信息處理的狀況）系統(tǒng)只需要根據(jù)當前所處的狀態(tài)和當前面臨的輸入信息就可以決定系統(tǒng)的后繼行為。每當系統(tǒng)處理了當前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生改變3.2.1有窮自動機電梯控制裝置輸入：顧客的乘梯需求（所要到達的層號）狀態(tài)：電梯所處的層數(shù)+運動方向電梯控制裝置并不需要記住先前全部的服務要求，只需要知道電梯當前所處的狀態(tài)以及還沒有滿足的所有服務請求FA的典型例子

輸入帶(inputtape)：用來存放輸入符號串

讀頭(head)：從左向右逐個讀取輸入符號，不能修改（只讀）、

不能往返移動

有窮控制器(finitecontrol)：具有有窮個狀態(tài)數(shù)，根據(jù)當前的

狀態(tài)和當前輸入符號控制轉入下一狀態(tài)有窮控制器讀頭輸入帶FA模型

轉換圖

(TransitionGraph)

結點：FA的狀態(tài)初始狀態(tài)（開始狀態(tài)）：只有一個，由start箭頭指向終止狀態(tài)（接收狀態(tài)）：可以有多個，用雙圈表示帶標記的有向邊：如果對于輸入a，存在一個從狀態(tài)p到狀態(tài)q的的轉換，就在p、q之間畫一條有向邊，并標記上a03startab12abbFA的表示給定輸入串x，如果存在一個對應于串x的從初始狀態(tài)到某個終止狀態(tài)的轉換序列，則稱串x被該FA接收由一個FA接收的所有串構成的集合稱為是該FA定義（或接收）的語言，記為L(M)L(M)=所有以abb結尾的字母表{a,b}上的串的集合03startab12abbabbaabbFA定義（接收）的語言當輸入串的多個前綴與一個或多個模式匹配時，總是選擇最長的前綴進行匹配在到達某個終態(tài)之后，只要輸入帶上還有符號，DFA就繼續(xù)前進，以便尋找盡可能長的匹配0<1=2+4start+3最長子串匹配原則(Longest

StringMatching

Principle)確定的FA(Deterministicfiniteautomata,DFA)非確定的FA(Nondeterministicfiniteautomata,NFA)3.2.2

FA的分類確定的有窮自動機(DFA)M=(S，Σ，δ，s0，F(xiàn))S：有窮狀態(tài)集Σ：輸入字母表，即輸入符號集合。假設ε不是Σ中的元素δ：將S×Σ映射到S的轉換函數(shù)。

s∈S,

a∈Σ,

δ(s,a)表示從狀態(tài)s出發(fā)，沿著標記為a的邊所能到達的狀態(tài)。s0：開始狀態(tài)(或初始狀態(tài))，s0∈SF：接收狀態(tài)（或終止狀態(tài)）集合，F(xiàn)?SM=(S，Σ，δ，s0，F(xiàn))03startb12abbbaaa例：一個DFAab010112213310轉換表狀態(tài)輸入●可以用轉換表表示DFA非確定的有窮自動機（NFA）M=(S，Σ，δ，s0，F(xiàn))S：有窮狀態(tài)集Σ：輸入符號集合，即輸入字母表。假設ε

不是Σ中的元素δ：將S×Σ映射到2S的轉換函數(shù)。

s∈S,

a∈Σ,

δ(s,a)表示從狀態(tài)s出發(fā)，沿著標記為a的邊所能到達的狀態(tài)集合s0：開始狀態(tài)(或初始狀態(tài))，s0∈SF：接收狀態(tài)（或終止狀態(tài)）集合，F(xiàn)?SM=(S，Σ，δ，s0，F(xiàn))03startab12abb例：一個NFA轉換表ab0｛0,1｝｛0｝1?｛2｝2?｛3｝3??狀態(tài)輸入●如果轉換函數(shù)沒有給出對應于某個狀態(tài)-輸入對的信息，就把?放入相應的表項中DFA和NFA可以識別相同的語言NFADFA03startab12abb03startb12abbbaaaDFA和NFA的等價性狀態(tài)1：串以a結尾狀態(tài)2：串以ab結尾狀態(tài)3：串以abb結尾r=(a|b)*abb正則文法?

正則表達式?FA帶有“ε-邊”的NFAA0εBεC1start2r=0*1*2*M=(S，Σ，δ，s0，F(xiàn))S：有窮狀態(tài)集Σ：輸入符號集合，即輸入字母表。假設ε

不是Σ中的元素δ：將S×(Σ∪{ε})映射到2S的轉換函數(shù)。

s∈S,

a∈Σ∪{ε},

δ(s,a)表示從狀態(tài)s出發(fā)，沿著標記為a的邊所能到達的狀態(tài)集合s0：開始狀態(tài)(或初始狀態(tài))，s0∈SF：接收狀態(tài)（或終止狀態(tài)）集合，F(xiàn)?S例帶有和不帶有“ε-邊”的NFA的等價性A0εBεC1start2帶“ε-邊”不帶“ε-邊”A00,1B1,2C1start20,1,2r=0*1*2*狀態(tài)A：0*狀態(tài)B：0*1*狀態(tài)C：0*1*2*輸入：以文件結束符eof結尾的字符串x。DFAD

的開始狀態(tài)s0，接收狀態(tài)集F，轉換函數(shù)move。輸出：如果D接收x，則回答“yes”，否則回答“no”。方法：將下述算法應用于輸入串x。DFA的算法實現(xiàn)s=

s0;c=nextChar（）;while（c!=eof

）｛s=move(s,c);c=nextChar

();｝if(s在F中)return“yes”;else

return

“no”;函數(shù)nextChar()返回輸入串x的下一個符號函數(shù)move(s,c)表示從狀態(tài)s出發(fā)，沿著標記為c的邊所能到達的狀態(tài)3.2.3從正則表達式到有窮自動機REDFAr=(a|b)*abbNFA

ε對應的NFA字母表Σ中符號a對應的NFAq0εqfstartq0aqfstart根據(jù)RE構造NFAr=r1r2對應的NFAr=r1|r2對應的NFAr=(r1)*對應的NFAq0r1startqfr2q1q0startqfr1r2r1q0start(a|b)*abbstartstartabb(a|b)*startabb

a|bstartabb

ab例:r=(a|b)*abb對應的NFA從NFA到DFA的轉換例1NFA：bcaA,BbB,CcC,DaADFA：startAaaBbCbcDcstart轉換表abcA{A,B}??B?{B,C}?C??{C,D}狀態(tài)輸入例2：從帶有ε-邊的NFA到DFA的轉換A0εBεC1start2NFA：轉換表012A{A,B,C}{B,C}{C}B?{B,C}{C}C??{C}狀態(tài)輸入δ(s,a)表示從狀態(tài)s出發(fā)，沿著標記為a的邊所能到達的狀態(tài)集合δ(A,0)=δ(A,0ε)=δ(A,0εε)={A,B,C}δ(A,1)=δ(A,ε1)=δ(A,ε1ε)={B,C}δ(A,2)=δ(A,εε2)=

{C}δ(B,1)=δ(B,1ε)={B,C}δ(B,2)=δ(B,

ε2)={C}δ(C,2)=

{C}例2：從帶有ε-邊的NFA到DFA的轉換A0εBεC1start2NFA：轉換表012A{A,B,C}{B,C}{C}B?{B,C}{C}C??{C}狀態(tài)輸入1202C1BCABCDFA：start2輸入：NFAN輸出：接收同樣語言的DFAD方法：一開始，ε-closure（s0）是Dstates中的唯一狀態(tài)，且它未加標記；

while（在Dstates中有一個未標記狀態(tài)T）｛給T加上標記；

for（每個輸入符號a）｛

U=ε-closure(move(T,a));if

(U不在Dstates中)

將U加入到Dstates中，且不加標記；

Dtran[T,a]=U;}

}操作描述ε-closure(s)能夠從NFA的狀態(tài)s開始只通過ε轉換到達的NFA狀態(tài)集合ε-closure(T)能夠從T中的某個NFA狀態(tài)s開始只通過ε轉換到達的NFA狀態(tài)集合,即Us∈Tε-closure(s)move(T,a)能夠從T中的某個狀態(tài)s出發(fā)通過標號為a的轉換到達的NFA狀態(tài)的集合子集構造法（subsetconstruction）NFAN=(S，Σ，δ，s0，F(xiàn))DFAD=(S’，Σ，δ’，s0’，F(xiàn)’)將T的所有狀態(tài)壓入stack中；將ε-closure（T）初始化為T；

while（stack非空）｛將棧頂元素t給彈出棧中；

for（每個滿足如下條件的u：從t出發(fā)有一個標號為ε的轉換到達狀態(tài)u)

if

(u不在ε-closure（T）中）｛將u加入到ε-closure（T）中；

將u壓入棧中;}}

計算ε-closure(T)識別標識符的DFAdigit→0|1|2|…|9letter_→

A|B|…|Z|a|b|…|z|_id→letter_(letter_|digit)*letter_letter_startdigit213.2.4識別單詞的DFAdigit→0|1|2|…|9digits→digitdigit*optionalFraction→.digits|εoptionalExponent→(E(+|-|ε)digits)|εnumber→digits

optionalFraction

optionalExponent0d1ddε3.2d+4Eε-5d6dεNFA：start識別無符號數(shù)的DFAdd+-5d6d36d45E0d136DFA：start.2Ed0d1ddε3.2d+4Eε-5d6dεNFA：start識別無符號數(shù)的DFA識別各進制無符號整數(shù)的DFA01-90-90DEC→(1|...|9)(0|...|9)*|0start123001-70-7OCT→0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*start46