編譯原理視頻配套3lexical analysis

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

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

2.1.1詞法記號、模式、詞法單元

記號名

詞法單元例舉

模式的非形式描述

if if 字符i,f

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

DO8I3.75 等同于 DO8I3.75DO8I3,75關鍵字不保留

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

position=initial+rate60的記號和屬性值：

id，指向符號表中position條目的指針 assign_op

id，指向符號表中initial條目的指針 add_op id，指向符號表中rate條目的指針

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

fi(a==f(x))

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

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

=s=s

冪

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

2.2詞法記號的描述與識別

語言的運算并： 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詞法記號的描述與識別

2.2.2正規(guī)式正規(guī)式用來表示簡單的語言，叫做正規(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詞法記號的描述與識別

正規(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)成的所有串集復雜的例子(00|11|((01|10)(00|11)(01|10)))句子：001110012.2詞法記號的描述與識別

2.2.3正規(guī)定義

對正規(guī)式命名，使表示簡潔 d1

r1 d2

r2 ... dn

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

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

letter_

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

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

2.2詞法記號的描述與識別

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

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+||)digits)|

numberdigitsoptional_fractionoptional_exponent簡化表示 number

digit+(.digit+)?(E(+|)?digit+)?2.2詞法記號的描述與識別

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

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詞法記號的描述與識別

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

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

標識符和關鍵字的轉(zhuǎn)換圖91011開始letterother*letter或digitreturn(installId())2.2詞法記號的描述與識別

無符號數(shù)的轉(zhuǎn)換圖 number

digit+(.digit+)?(E

(+|)?

digit+)?開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/Edigitotherotherreturn(installNum())*2.2詞法記號的描述與識別

空白的轉(zhuǎn)換圖delimblank|tab|newlinewsdelim+2122開始delimother*delim202.3有限自動機

2.3.1不確定的有限自動機（簡稱NFA） 一個數(shù)學模型，它包括：

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

2、輸入符號集合

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

P(S)

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

5、F

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

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

NFA的轉(zhuǎn)換表2.3有限自動機

識別語言(a|b)*ab

的NFA12開始a0abb2.3有限自動機

例

識別aa*|bb*的NFA12開始a0abb342.3.2確定的有限自動機（簡稱DFA)

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

的DFA2.3有限自動機

2.3有限自動機

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

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

10102=10101112=710例 DFA,接受0和1的個數(shù)都是偶數(shù)的字符串00003211奇0奇1奇0偶11011開始偶0偶1偶0奇12.3有限自動機

2.3.3NFA到DFA的變換

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

2、讀了輸入a1a2…an后，

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

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

未畫完19開始0abab6782345

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

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

2.3有限自動機

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

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

2.3有限自動機

19開始0abab6782345輸入符號abAB狀態(tài)

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

2.3有限自動機

19開始0abab6782345輸入符號abABB狀態(tài)

A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

19開始0abab6782345輸入符號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有限自動機

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

BD開始aAabbabCba2.3有限自動機

19開始0abab6782345BD開始aAabbabCba12開始a0abbab識別語言(a|b)*ab

的自動機2.3有限自動機

19開始0abab6782345BD開始aAabbabCba12開始a0abbab識別語言(a|b)*ab

的自動機子集構(gòu)造法不一定得到最簡DFA2.3有限自動機

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

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

從A出發(fā)，讀過單字符b構(gòu)成的串，到達非接受狀態(tài)C，而從B出發(fā)，讀過串b，到達接受狀態(tài)DA和C是不可區(qū)別的狀態(tài) 無任何串可用來像上面這樣 區(qū)別它們BD開始aAabbabCba2.3有限自動機

方法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.3有限自動機

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

fi開始識別正規(guī)式s|t的NFAN(s)N(t)2.4從正規(guī)式到有限自動機構(gòu)造識別主算符為連接的正規(guī)式的NFA重要特點：僅一個接受狀態(tài)，它沒有向外的轉(zhuǎn)換識別正規(guī)式st的NFAiN(s)f開始N(t)2.4從正規(guī)式到有限自動機構(gòu)造識別主算符為閉包的正規(guī)式的NFA重要特點：僅一個接受狀態(tài)，它沒有向外的轉(zhuǎn)換N(s)f開始識別正規(guī)式s*的NFAi2.4從正規(guī)式到有限自動機對于加括號的正規(guī)式(s)，使用N(s)本身作為它的NFA2.4從正規(guī)式到有限自動機本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的狀態(tài)數(shù)最多是r中符號和算符總數(shù)的兩倍N(r)只有一個接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換2.4從正規(guī)式到有限自動機19開始0abab6782345本方法產(chǎn)生的NFA有下列性質(zhì)N(r)的每個狀態(tài)有一個用的符號標記的指向其它結(jié)點的轉(zhuǎn)換，或者最多兩個指向其它結(jié)點的轉(zhuǎn)換2.4從正規(guī)式到有限自動機19開始0abab67823452.4從正規(guī)式到有限自動機

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

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

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

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

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

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

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

用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號序列2.5詞法分析器的生成器Lex程序包括三個部分聲明％％翻譯規(guī)則％％輔助過程Lex程序的翻譯規(guī)則p1 {動作1}p2 {動作2}… …pn {動作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} {/*

沒有動作，也不返回*/}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詞法分析器的生成器例——輔助過程部分installId(){ /*

把詞法單元裝入符號表并返回指針。 yytext指