編譯原理視頻配套3lexical analysis

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

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

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

記號(hào)名

詞法單元例舉

模式的非形式描述

if if 字符i,f

for for 字符f,o,rrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母開(kāi)頭的字母數(shù)字串number 3.1,10,2.8E12 任何數(shù)值常數(shù)literal “seg.error” 引號(hào)“和”之間任意不含 引號(hào)本身的字符串2.1詞法記號(hào)及屬性歷史上詞法定義中的一些問(wèn)題忽略空格帶來(lái)的困難

DO8I3.75 等同于 DO8I3.75DO8I3,75關(guān)鍵字不保留

IFTHENTHENTHEN=ELSE；ELSE…關(guān)鍵字、保留字和標(biāo)準(zhǔn)標(biāo)識(shí)符的區(qū)別保留字是語(yǔ)言預(yù)先確定了含義的詞法單元標(biāo)準(zhǔn)標(biāo)識(shí)符也是預(yù)先確定了含義的標(biāo)識(shí)符，但程序可以重新聲明它的含義2.1詞法記號(hào)及屬性2.1.2詞法記號(hào)的屬性

position=initial+rate60的記號(hào)和屬性值：

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

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

mul_op number，整數(shù)值602.1詞法記號(hào)及屬性2.1.3詞法錯(cuò)誤詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)例：難以發(fā)現(xiàn)下面的錯(cuò)誤

fi(a==f(x))

…在實(shí)數(shù)是“數(shù)字串.數(shù)字串”格式下，可以發(fā)現(xiàn)下面的錯(cuò)誤 123.x緊急方式的錯(cuò)誤恢復(fù) 刪掉當(dāng)前若干個(gè)字符，直至能讀出正確的記號(hào)錯(cuò)誤修補(bǔ) 進(jìn)行增、刪、替換和交換字符的嘗試2.2詞法記號(hào)的描述與識(shí)別

2.2.1串和語(yǔ)言字母表：符號(hào)的有限集合，例：={0,1}串：符號(hào)的有窮序列，例：0110,語(yǔ)言：字母表上的一個(gè)串集 {,0,00,000,…},{},句子：屬于語(yǔ)言的串串的運(yùn)算連接（積） xy，s

=s=s

冪

s0為，si為si-1s（i>0）

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

語(yǔ)言的運(yùn)算并： LM={s|s

L或s

M}連接： LM={st|s

L且t

M}冪： 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ī)式用來(lái)表示簡(jiǎn)單的語(yǔ)言，叫做正規(guī)集

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

{}

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)))句子：001110012.2詞法記號(hào)的描述與識(shí)別

2.2.3正規(guī)定義

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

r1 d2

r2 ... dn

rn各個(gè)di的名字都不同每個(gè)ri都是{d1,d2,…,di-1}上的正規(guī)式2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子C語(yǔ)言的標(biāo)識(shí)符是字母、數(shù)字和下劃線組成的串

letter_

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

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

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

正規(guī)定義的例子無(wú)符號(hào)數(shù)集合，例1946,11.28,63E8,1.99E6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+||)digits)|

numberdigitsoptional_fractionoptional_exponent簡(jiǎn)化表示 number

digit+(.digit+)?(E(+|)?digit+)?2.2詞法記號(hào)的描述與識(shí)別

正規(guī)定義的例子（進(jìn)行下一步討論的例子）

while

while do

do relop

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

letter

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

|z id

letter(letter|digit)* number

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)開(kāi)始<=>=>=**otherother2.2詞法記號(hào)的描述與識(shí)別

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

無(wú)符號(hào)數(shù)的轉(zhuǎn)換圖 number

digit+(.digit+)?(E

(+|)?

digit+)?開(kāi)始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(installNum())*2.2詞法記號(hào)的描述與識(shí)別

空白的轉(zhuǎn)換圖delimblank|tab|newlinewsdelim+2122開(kāi)始delimother*delim202.3有限自動(dòng)機(jī)

2.3.1不確定的有限自動(dòng)機(jī)（簡(jiǎn)稱NFA） 一個(gè)數(shù)學(xué)模型，它包括：

1、有限的狀態(tài)集合S

2、輸入符號(hào)集合

3、轉(zhuǎn)換函數(shù)move:S({})

P(S)

4、狀態(tài)s0是唯一的開(kāi)始狀態(tài)

5、F

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

的NFA12開(kāi)始a0abb輸入符號(hào)ab0{0,1}{0}1{2}2狀態(tài)

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

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

的NFA12開(kāi)始a0abb2.3有限自動(dòng)機(jī)

例

識(shí)別aa*|bb*的NFA12開(kāi)始a0abb342.3.2確定的有限自動(dòng)機(jī)（簡(jiǎn)稱DFA)

一個(gè)數(shù)學(xué)模型，包括：1、有限的狀態(tài)集合S2、輸入字母集合3、轉(zhuǎn)換函數(shù)move:SS，且可以是部分函數(shù)4、唯一的開(kāi)始狀態(tài)s05、接受狀態(tài)集合FS12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

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

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

例 DFA，識(shí)別{0,1}上能被5整除的二進(jìn)制數(shù) 已讀過(guò) 尚未讀 已讀部分的值 某時(shí)刻 101 0111000 5 讀進(jìn)0 1010 111000 52=10 讀進(jìn)1 10101 11000 102+1=21

5個(gè)狀態(tài)即可，分別代表已讀部分的值除以5的余數(shù)例 DFA，識(shí)別{0,1}上能被5整除的二進(jìn)制數(shù)0123開(kāi)始410010101012.3有限自動(dòng)機(jī)

10102=10101112=710例 DFA,接受0和1的個(gè)數(shù)都是偶數(shù)的字符串00003211奇0奇1奇0偶11011開(kāi)始偶0偶1偶0奇12.3有限自動(dòng)機(jī)

2.3.3NFA到DFA的變換

子集構(gòu)造法 1、DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合

2、讀了輸入a1a2…an后，

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

DFA到達(dá)狀態(tài){s1,s2,…,sk}12a開(kāi)始0abb{0}{0,1}aba{0,2}b2.3有限自動(dòng)機(jī)

未畫完19開(kāi)始0abab6782345

例 (a|b)*ab，NFA如下，把它變換為DFA2.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345輸入符號(hào)ab狀態(tài)

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

19開(kāi)始0abab6782345輸入符號(hào)abA狀態(tài)

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

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

19開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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開(kāi)始0abab6782345輸入符號(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ī)

19開(kāi)始0abab6782345輸入符號(hào)abABCBBDCBCDBC狀態(tài)

BD開(kāi)始aAabbabCba2.3有限自動(dòng)機(jī)

19開(kāi)始0abab6782345BD開(kāi)始aAabbabCba12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

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

19開(kāi)始0abab6782345BD開(kāi)始aAabbabCba12開(kāi)始a0abbab識(shí)別語(yǔ)言(a|b)*ab

的自動(dòng)機(jī)子集構(gòu)造法不一定得到最簡(jiǎn)DFA2.3有限自動(dòng)機(jī)

BD開(kāi)始aAabbaa,bCbaEb2.3.4DFA的化簡(jiǎn)死狀態(tài)在轉(zhuǎn)換函數(shù)由部分函數(shù)改成全函數(shù)表示時(shí)引入左圖需要引入死狀態(tài)E；右圖無(wú)須引入死狀態(tài)BD開(kāi)始aAabbabCba2.3有限自動(dòng)機(jī)

可區(qū)別的狀態(tài)A和B是可區(qū)別的狀態(tài)

從A出發(fā)，讀過(guò)單字符b構(gòu)成的串，到達(dá)非接受狀態(tài)C，而從B出發(fā)，讀過(guò)串b，到達(dá)接受狀態(tài)DA和C是不可區(qū)別的狀態(tài) 無(wú)任何串可用來(lái)像上面這樣 區(qū)別它們BD開(kāi)始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開(kāi)始aAabbabCba12開(kāi)始a0abbab2.3有限自動(dòng)機(jī)

從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造NFA（本節(jié)介紹） 用語(yǔ)法制導(dǎo)的算法，它用正規(guī)式語(yǔ)法結(jié)構(gòu)來(lái)指導(dǎo)構(gòu)造過(guò)程把NFA變成DFA（子集構(gòu)造法，已介紹）將DFA化簡(jiǎn)（合并不可區(qū)別狀態(tài)，也已介紹）2.4從正規(guī)式到有限自動(dòng)機(jī)首先構(gòu)造識(shí)別和字母表中一個(gè)符號(hào)的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換i開(kāi)始識(shí)別正規(guī)式的NFAafif開(kāi)始識(shí)別正規(guī)式a的NFA2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換

fi開(kāi)始識(shí)別正規(guī)式s|t的NFAN(s)N(t)2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換識(shí)別正規(guī)式st的NFAiN(s)f開(kāi)始N(t)2.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFA重要特點(diǎn)：僅一個(gè)接受狀態(tài)，它沒(méi)有向外的轉(zhuǎn)換N(s)f開(kāi)始識(shí)別正規(guī)式s*的NFAi2.4從正規(guī)式到有限自動(dòng)機(jī)對(duì)于加括號(hào)的正規(guī)式(s)，使用N(s)本身作為它的NFA2.4從正規(guī)式到有限自動(dòng)機(jī)本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍N(r)只有一個(gè)接受狀態(tài)，接受狀態(tài)沒(méi)有向外的轉(zhuǎn)換2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始0abab6782345本方法產(chǎn)生的NFA有下列性質(zhì)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開(kāi)始0abab67823452.4從正規(guī)式到有限自動(dòng)機(jī)

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

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

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

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

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

19開(kāi)始0abab6782345r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解

(a|b)*ab的兩個(gè)NFA的比較12開(kāi)始a0abb手工構(gòu)造:算法構(gòu)造:2.4從正規(guī)式到有限自動(dòng)機(jī)19開(kāi)始0abab6782345小結(jié)：從正規(guī)式建立識(shí)別器的步驟從正規(guī)式構(gòu)造NFA把NFA變成DFA將DFA化簡(jiǎn)存在其它辦法2.4從正規(guī)式到有限自動(dòng)機(jī)

用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號(hào)序列2.5詞法分析器的生成器Lex程序包括三個(gè)部分聲明％％翻譯規(guī)則％％輔助過(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 [AZaz]digit [09]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\]?{digit}+)?2.5詞法分析器的生成器例——翻譯規(guī)則部分{ws} {/*

沒(méi)有動(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詞法分析器的生成器例——輔助過(guò)程部分installId(){ /*

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