詞法分析課件

詞法分析

本章內(nèi)容詞法分析器：把構(gòu)成源程序的字符流翻譯成記號(hào)流，還完成和用戶接口的一些任務(wù)圍繞詞法分析器的自動(dòng)生成展開介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動(dòng)機(jī)概念

詞法分析器語法分析器符號(hào)表記號(hào)(token)取下一個(gè)記號(hào)源程序2.1詞法記號(hào)及屬性

2.1.1詞法記號(hào)、模式、詞法單元

詞法記號(hào) 詞法單元例舉

模式的非形式描述

var

var

varfor for forrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母開頭的字母數(shù)字串num 3.1,10,2.8E12 任何數(shù)值常數(shù)literal “seg.error” 引號(hào)“和”之間的任意字符 串，但引號(hào)本身除外2.1詞法記號(hào)及屬性歷史上詞法定義中的一些問題忽略空格帶來的困難

DO8I

3.75 DO8I

3.75DO8I

3,75關(guān)鍵字是否保留

IFTHENTHENTHEN=ELSE；ELSE…關(guān)鍵字、保留字和標(biāo)準(zhǔn)標(biāo)識(shí)符的區(qū)別2.1詞法記號(hào)及屬性2.1.2詞法記號(hào)的屬性

position:=initial+rate*60的記號(hào)和屬性值：

id，指向符號(hào)表中position條目的指針

assign_op，

id，指向符號(hào)表中initial條目的指針

add_op，+

id，指向符號(hào)表中rate條目的指針

mul_op,*

num，整數(shù)值60

2.1詞法記號(hào)及屬性2.1.3詞法錯(cuò)誤詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)難以發(fā)現(xiàn)下面的錯(cuò)誤

fi(a==f(x))…在實(shí)數(shù)是a.b格式下，可以發(fā)現(xiàn)下面的錯(cuò)誤 123.緊急方式的錯(cuò)誤恢復(fù)錯(cuò)誤修補(bǔ)2.2詞法記號(hào)的描述與識(shí)別

2.2.1串和語言字母表：符號(hào)的有限集合，例：={0,1}串：符號(hào)的有窮序列，例：0110,

語言：字母表上的一個(gè)串集 {,0,00,000,…},{},句子：屬于語言的串串的運(yùn)算連接 xy，s

=s=s

積（指數(shù)） s0為，si為si-1s（i>0）

2.2詞法記號(hào)的描述與識(shí)別

語言的運(yùn)算和：L

M={s|s

L或s

M}連接：LM={st

|s

L且t

M}指數(shù)：L0是{

}，Li是Li-1L

閉包：L

=L0

L1

L2

…正閉包：L+=L1

L2

…例L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L

D,LD,L6,L*,L(L

D)*,D+

2.2詞法記號(hào)的描述與識(shí)別

2.2.2正規(guī)式

正規(guī)式用來表示簡(jiǎn)單的語言，叫做正規(guī)集

正規(guī)式 定義的語言 備注

{

}

a {a} a

(r)|(s) L(r)∪L(s) r和s是正規(guī)式 (r)(s)

L(r)L(s) r和s是正規(guī)式

(r)*

(L(r))* r是正規(guī)式

(r) L(r) r是正規(guī)式 ((a)(b)*)|(c)可以寫成ab*|c

2.2詞法記號(hào)的描述與識(shí)別

正規(guī)式的例子

={a,b}a|b

{a,b}(a|b)(a|b) {aa,ab,ba,bb}aa

|ab

|ba

|bb

{aa,ab,ba,bb}a* 由字母a構(gòu)成的所有串集(a|b)* 由a和b構(gòu)成的所有串集復(fù)雜的例子(00|11|((01|10)(00|11)

(01|10)))

句子：010011010000100000101110012.2詞法記號(hào)的描述與識(shí)別

2.2.3正規(guī)定義

對(duì)正規(guī)式命名，使表示簡(jiǎn)潔。d1

r1d2

r2...

dn

rn各個(gè)di的名字都不同每個(gè)ri都是

{d1,d2,…,di-1}上的正規(guī)式2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子

Pascal語言的標(biāo)識(shí)符集合 letter

A|B|…|Z|a|b|…

|z

digit

0

|1|…|9 id

letter(letter|digit)*

2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子

Pascal無符號(hào)數(shù)集合，例1946,11.28,63E8,1.99E

6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

num

digitsoptional_fractionoptional_exponent簡(jiǎn)化表示 num

digit+(.digit+)?(E(+|

)?digit+)?

2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子

while

while do

do

relop

<|<=|=|<>|>|>= id

letter(letter|digit)* num

digit+(.digit+)?(E(+|

)?

digit+)?

delim

blank|tab|newline

ws

delim+2.2詞法記號(hào)的描述與識(shí)別

2.2.4轉(zhuǎn)換圖

關(guān)系算符的轉(zhuǎn)換圖

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)開始<=>=>=**otherother2.2詞法記號(hào)的描述與識(shí)別

標(biāo)識(shí)符和保留字的轉(zhuǎn)換圖91011開始letterother*letter或digitreturn(install_id())2.2詞法記號(hào)的描述與識(shí)別

無符號(hào)數(shù)的轉(zhuǎn)換圖開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/

Edigitotherotherreturn(install_num())*num

digit+(.digit+)?(E(+|

)?

digit+)?

2.2詞法記號(hào)的描述與識(shí)別

空白的轉(zhuǎn)換圖delim

blank|tab|newline

ws

delim+2122開始delimother*delim202.3有限自動(dòng)機(jī)

2.3.1不確定的有限自動(dòng)機(jī)（簡(jiǎn)稱NFA）

一個(gè)數(shù)學(xué)模型，它包括：狀態(tài)集合S

輸入符號(hào)集合

轉(zhuǎn)換函數(shù)move:S

(

{

})

P(S)

狀態(tài)s0是開始狀態(tài)

F

S是接受狀態(tài)集合12開始a0abb識(shí)別語言(a|b)*ab

的NFA12開始a0abb識(shí)別語言(a|b)*ab

的NFA輸入符號(hào)ab0{0,1}{0}1

{2}2

狀態(tài)

NFA的轉(zhuǎn)換表2.3有限自動(dòng)機(jī)

2.3有限自動(dòng)機(jī)

例

識(shí)別aa*|bb*的NFA12開始a0abb34

2.3.2確定的有限自動(dòng)機(jī)（簡(jiǎn)稱DFA)

一個(gè)數(shù)學(xué)模型，包括：

狀態(tài)集合S

輸入字母表轉(zhuǎn)換函數(shù)move:S

S

唯一的初態(tài)s

S

終態(tài)集合F

S12開始a0abbab識(shí)別語言(a|b)*ab

的DFA2.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4101 01110001010 11100010101 11000

2.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始402.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4102.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41002.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始410012.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100102.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41001012.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始410010102.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100101012.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41001010102.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始410010101012.3有限自動(dòng)機(jī)

例：識(shí)別={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100101010110102=10101112=7102.3有限自動(dòng)機(jī)

例：DFA，接受0和1的個(gè)數(shù)都是偶數(shù)的字符串312011110000開始偶0偶1奇0奇1奇0偶1偶0奇12.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則

DFA到達(dá)狀態(tài){s1,s2,…,

sk}12a開始0abb2.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則

DFA到達(dá)狀態(tài){s1,s2,…,

sk}12a開始0abb{0}{0,1}a2.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則

DFA到達(dá)狀態(tài){s1,s2,…,

sk}12a開始0abb{0}{0,1}ab2.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則

DFA到達(dá)狀態(tài){s1,s2,…,

sk}12a開始0abb{0}{0,1}aba2.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1a2…an后，

NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則

DFA到達(dá)狀態(tài){s1,s2,…,

sk}12a開始0abb{0}{0,1}aba{0,2}b2.3有限自動(dòng)機(jī)

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)ab狀態(tài)

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abA狀態(tài)

A={0,1,2,4,7}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abAB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBBDC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBBDCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCD狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)19開始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCDBC狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動(dòng)機(jī)BD開始aAabbabCba19開始

0ab

ab6782345

輸入符號(hào)abABCBBDCBCDBC狀態(tài)

2.3有限自動(dòng)機(jī)BD開始aAabbabCba12開始a0abbab19開始

0ab

ab6782345

識(shí)別語言(a|b)*ab

的自動(dòng)機(jī)2.3有限自動(dòng)機(jī)BD開始aAabbabCba12開始a0abbab19開始

0ab

ab6782345

識(shí)別語言(a|b)*ab

的自動(dòng)機(jī)子集構(gòu)造法不一定得到最簡(jiǎn)DFA2.3有限自動(dòng)機(jī)BD開始aAabbaa,bCbaEb2.3.4DFA的化簡(jiǎn)死狀態(tài)左圖無須加死狀態(tài)，右圖加入死狀態(tài)E。BD開始aAabbabCba2.3有限自動(dòng)機(jī)可區(qū)別的狀態(tài)A和B是可區(qū)別的狀態(tài)A和C是不可區(qū)別的狀態(tài)BD開始aAabbabCba2.3有限自動(dòng)機(jī)方法1.{A,B,C},{D}move({A,B,C},a}={B}move({A,B,C},b}={C,D}2.{A,C},{B},{D}move({A,C},a}={B}move({A,C},b}={C}BD開始aAabbabCba2.3有限自動(dòng)機(jī)方法1.{A,B,C},{D}move({A,B,C},a}={B}move({A,B,C},b}={C,D}2.{A,C},{B},{D}move({A,C},a}={B}move({A,C},b}={C}BD開始aAabbabCba12開始a0abbab2.4從正規(guī)式到有限自動(dòng)機(jī)

從正規(guī)式建立識(shí)別器從正規(guī)式構(gòu)造NFA（本節(jié)介紹） 用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)構(gòu)造過程把NFA變成DFA（子集構(gòu)造法，已介紹）將DFA化簡(jiǎn)（合并不可區(qū)別狀態(tài)，也已介紹）2.4從正規(guī)式到有限自動(dòng)機(jī)

首先構(gòu)造識(shí)別

和字母表中一個(gè)符號(hào)的NFAi開始

識(shí)別正規(guī)式

的NFAafif開始識(shí)別正規(guī)式a的NFA2.4從正規(guī)式到有限自動(dòng)機(jī)

構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFA

fi開始識(shí)別正規(guī)式s|t的NFAN(s)N(t)

2.4從正規(guī)式到有限自動(dòng)機(jī)

構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFA

iN(s)f開始識(shí)別正規(guī)式st

的NFAN(t)2.4從正規(guī)式到有限自動(dòng)機(jī)

構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFA

N(s)f開始識(shí)別正規(guī)式s*的NFAi

2.4從正規(guī)式到有限自動(dòng)機(jī)

對(duì)于加括號(hào)的正規(guī)式(s)，使用N(s)本身作為它的NFA。2.4從正規(guī)式到有限自動(dòng)機(jī)

本方法產(chǎn)生的NFA有下列性質(zhì):N(r)的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍N(r)只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換N(r)的每個(gè)狀態(tài)有一個(gè)用

的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個(gè)指向其它結(jié)點(diǎn)的

轉(zhuǎn)換2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0

ab678ab2345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規(guī)式到有限自動(dòng)機(jī)

(a|b)*ab的兩個(gè)NFA的比較12開始a0abb19開始

0ab

ab6782345

手工構(gòu)造:算法構(gòu)造:2.4從正規(guī)式到有限自動(dòng)機(jī)

小結(jié)：從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造NFA把NFA變成DFA將DFA化簡(jiǎn)存在其它辦法2.5詞法分析器的生成器

用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號(hào)序列2.5詞法分析器的生成器Lex程序包括三個(gè)部分聲明％％翻譯規(guī)則％％輔助過程Lex程序的翻譯規(guī)則p1 {動(dòng)作1}p2 {動(dòng)作2}… …

pn

{動(dòng)作n}2.5詞法分析器的生成器例---聲明部分%{/*常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定義*/%}/*正規(guī)定義*/delim [\t\n]ws {delim}+letter [A

Za

z]digit [0

9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\

]?{digit}+)?2.5詞法分析器的生成器例---翻譯規(guī)則部分{ws} {/*

沒有動(dòng)作，也不返回*/}while {return(WHILE);}do {return(DO);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num();return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}2.5詞法分析器的生成器例---輔助過程部分install_id(){ /*

把詞法單元裝入符號(hào)表并返回指針。

yytext指向該詞法單元的第一個(gè)字符，

yyleng給出的它的長(zhǎng)度 */}install_num(){ /*

類似上面的過程，但詞法單元不是標(biāo)識(shí)符而是數(shù)*/}本章要點(diǎn)詞法分析器的作用和接口，用高級(jí)語言編寫詞法分析器等內(nèi)容，它們與詞法分析器的實(shí)現(xiàn)有關(guān)掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法非形式描述的語言

正規(guī)式正規(guī)式

NFA非形式描述的