中科大2021－2022學(xué)年秋季第一學(xué)期《編譯原理與技術(shù)》第二講 詞法分析（1）

1、2022/7/25編譯原理與技術(shù)講義1編譯原理與技術(shù)詞法分析(1)2022/7/25編譯原理與技術(shù)講義2詞法分析詞法分析器介紹正規(guī)式與正規(guī)集有限自動機(jī)詞法分析器的自動生成Lex2022/7/25編譯原理與技術(shù)講義3詞法分析器介紹詞法分析器的功能高級語言源程序詞法分析器語法分析器tokenget_next_token編譯器其它階段符號表字符流記號（流）2022/7/25編譯原理與技術(shù)講義4詞法分析器介紹詞法分析器的功能讀源程序，產(chǎn)生記號序列剝?nèi)ピ闯绦蛑械淖⑨專▔K、行）和“空白”符預(yù)處理宏處理與文件包含2022/7/25編譯原理與技術(shù)講義5詞法分析器介紹詞法分析器作為獨(dú)立子程序簡化設(shè)計提高編譯效率

2、增強(qiáng)可移植性2022/7/25編譯原理與技術(shù)講義6詞法分析器介紹記號、模式與單詞記號同類單詞的總稱模式描述構(gòu)成記號的字符串的規(guī)則單詞源程序中能匹配任一記號的字符串2022/7/25編譯原理與技術(shù)講義7程序語言的記號（1）記號單詞模式關(guān)鍵字WHILEwhilewhileFORforfor標(biāo)識符IDtemp, i,max字母開頭的字母數(shù)字串常數(shù)NUM3.14100數(shù)字字符串.數(shù)字字符串2022/7/25編譯原理與技術(shù)講義8程序語言的記號（2）記號單詞模式運(yùn)算符MUL*GT界符,串常量STRING“hello”there雙（單）引號中間的字符串（不包括引號本身）2022/7/25編譯原理與技術(shù)講義9

3、詞法分析器介紹詞法分析器的二元輸出 單詞（字符串）的類別匹配記號的單詞多于一個時，須提供額外的信息以區(qū)別之2022/7/25編譯原理與技術(shù)講義10詞法分析器介紹詞法分析器的二元輸出記號影響語法分析的決策屬性（如類型、偏移）則關(guān)系到記號的翻譯2022/7/25編譯原理與技術(shù)講義11詞法分析器介紹e.g.1 pascal源程序片段：beginlength := length + 1;if length20 then read(nextch);end;2022/7/25編譯原理與技術(shù)講義12e.g.1 pascal源程序片段的字符流(SP表示空格)beginntlengthSP:=SPlengthS

4、P+SP1;ntifSPlength20SPthenSPread(nextch);nend;2022/7/25編譯原理與技術(shù)講義13e.g. 1 詞法分析器的輸出記號流(1) /不是多余的！ / 屬性是常量“值”本身2022/7/25編譯原理與技術(shù)講義14e.g. 1 詞法分析器的輸出記號流(2)2022/7/25編譯原理與技術(shù)講義15詞法分析器介紹超前搜索FORTRAN中的關(guān)鍵字“不保留”1） DO100K=1,102） DO100K=1.103） IF(5.EQ.M) I=104） IF(5)=55有關(guān)算符的識別C/C+, java的+, -, =, !=, = 等，與之對應(yīng) + , -

5、, !, = 2022/7/25編譯原理與技術(shù)講義16詞法分析器介紹詞法錯誤可檢測非法字符的出現(xiàn)if VS fi詞法分析器的設(shè)計手工編寫采用匯編語言或高級語言自動生成Lex2022/7/25編譯原理與技術(shù)講義17詞法分析器介紹狀態(tài)轉(zhuǎn)換圖用于記號的識別。狀態(tài)之間用帶有標(biāo)記（字符）的有向邊連接；每讀入一個字符會引起狀態(tài)變化，直至單詞（記號）被識別出來。開始狀態(tài)：狀態(tài)轉(zhuǎn)換圖的初始狀態(tài)（尚未讀字符）接受狀態(tài)：某個單詞被識別時所處的狀態(tài)（終態(tài)）單詞（記號）的識別過程即是從開始狀態(tài)出發(fā)到某接受狀態(tài)的變化過程。2022/7/25編譯原理與技術(shù)講義18詞法分析器介紹狀態(tài)轉(zhuǎn)換圖012字母其它字母或數(shù)字識別標(biāo)識符

6、的轉(zhuǎn)換圖*034數(shù)字其它數(shù)字識別整數(shù)的轉(zhuǎn)換圖*2022/7/25編譯原理與技術(shù)講義19詞法分析器介紹狀態(tài)轉(zhuǎn)換圖05數(shù)字.識別Pascal無符號數(shù)的轉(zhuǎn)換圖*數(shù)字67891011數(shù)字?jǐn)?shù)字E+|-數(shù)字?jǐn)?shù)字其它E數(shù)字其它其它2022/7/25編譯原理與技術(shù)講義20詞法分析器介紹狀態(tài)轉(zhuǎn)換圖05數(shù)字.（紅線）識別Pascal無符號整數(shù)的轉(zhuǎn)換圖*數(shù)字67891011數(shù)字?jǐn)?shù)字E+|-數(shù)字?jǐn)?shù)字其它E數(shù)字其它其它2022/7/25編譯原理與技術(shù)講義21詞法分析器介紹狀態(tài)轉(zhuǎn)換圖05數(shù)字.識別Pascal無符號小數(shù)的轉(zhuǎn)換圖*數(shù)字67891011數(shù)字?jǐn)?shù)字E+|-數(shù)字?jǐn)?shù)字其它E數(shù)字其它其它2022/7/25編譯原理與技術(shù)

7、講義22狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)e.g. 2 簡單詞法分析的轉(zhuǎn)換圖（識別關(guān)鍵字、標(biāo)識符、無符號整數(shù)、算符和界符）01空白符（n,t,SP）字母或數(shù)字字母非字母數(shù)字2*return( ID, 符號表?xiàng)l目指針） or return( 關(guān)鍵字，）3數(shù)字?jǐn)?shù)字非數(shù)字字符4*return(NUM, 常量值或者常量表?xiàng)l目指針）to be continued 2022/7/25編譯原理與技術(shù)講義23e.g. 2簡單詞法分析的轉(zhuǎn)換圖+5return（+, ）-6return（-, ）7*非*字符8*return（*, ）9return（*, ）*to be continued 2022/7/25編譯原理與技術(shù)講義24e

8、.g. 2簡單詞法分析的轉(zhuǎn)換圖1013return（LT, ）其它字符=14return（EQ, ）*15=16*return（GE, ）17return（GT, ）其它字符to be continued 2022/7/25編譯原理與技術(shù)講義25e.g. 2簡單詞法分析的轉(zhuǎn)換圖18：=19return（ASSIGN, ）20return（:, ）其它字符*；21return（；, ）其它22Error()簡單掃描程序狀態(tài)轉(zhuǎn)換程序2022/7/25編譯原理與技術(shù)講義26串與語言語言語言L s | s 是上任一字符串，s稱為語言L的一個句子。字母表符號/字符的非空有限集合e.g. 二進(jìn)制數(shù)的0,1

9、，而十進(jìn)制數(shù)的0,1,9*表示上所有字符串的集合；L*字符串 上若干字符組成的有窮序列 2022/7/25編譯原理與技術(shù)講義27串與語言語言字符串e.g. 0,1上的0，1串（二進(jìn)制數(shù)）如0111，10101；a,b上的 a, b, aa , abab, 空串， *，串長|s|s中所含字符的個數(shù)，| |=0串的連接運(yùn)算任意串x，y，一般地，xyyx， x= x串的前綴 任意串x，從其第一個字符（最左字符）起的字符序列是其前綴。亦是。e.g. x = abc, 則，a，ab，abc均是x的前綴2022/7/25編譯原理與技術(shù)講義28語言的運(yùn)算語言的運(yùn)算 描述運(yùn)算語言L和語言M連接（積）LM= x

10、y| xL 且 yM 合并（和）LM=x| xL 或 xM 閉包L*=L0L1L2=正閉包L+=L1L2L3=2022/7/25編譯原理與技術(shù)講義29語言e.g. L=a,b,z, D=0,1,9, B= _ LD = LD= L*= L(LD)*= (L B)(LDB)*= D+= 2022/7/25編譯原理與技術(shù)講義30正規(guī)式與正規(guī)集正規(guī)式用于描述記號的構(gòu)成規(guī)則正規(guī)集正規(guī)式描述的語言（匹配正規(guī)式的串集）正規(guī)式正規(guī)集aa2022/7/25編譯原理與技術(shù)講義31正規(guī)式與正規(guī)集正規(guī)式正規(guī)集R | SL(R) L(S)R SL(R) L(S)R*(L(R)*(R)L(R)如果R和S是上的正規(guī)式，分

11、別對應(yīng)上的正規(guī)集L(R)和L(S)，則2022/7/25編譯原理與技術(shù)講義32正規(guī)式與正規(guī)集運(yùn)算符優(yōu)先級結(jié)合性或|低左結(jié)合連接 高左結(jié)合閉包*最高左結(jié)合 上的正規(guī)式，其運(yùn)算有 | 、 和 *2022/7/25編譯原理與技術(shù)講義33正規(guī)式與正規(guī)集代數(shù)定律描述交換律R | S S | R結(jié)合律R | (S|T) = (R|S) | TR (ST) = (RS) T分配律R (S|T) = (RS) | (RT)(R|S) T = (RT) | (ST)同一律 R = R = R上的正規(guī)式，滿足如下代數(shù)定律2022/7/25編譯原理與技術(shù)講義34正規(guī)式與正規(guī)集上的正規(guī)式，也具有如下代數(shù)定律( R*

12、) * = R *( R | ) * = R * R+ = R R*2022/7/25編譯原理與技術(shù)講義35正規(guī)式與正規(guī)集e.g.3 設(shè)=a, b, 則正規(guī)式正規(guī)集a(a|b)*上以a開頭的串集ba*上以b開頭后跟任意個a的串集(a|b)*a(a|b)(a|b)上倒數(shù)第三個字符是a的串集2022/7/25編譯原理與技術(shù)講義36正規(guī)式與正規(guī)集e.g.3 設(shè)=a, b，R = a(a|b)*，事實(shí)上有 L(R) = L( a(a|b)* )= L(a) L(a|b)*)= L(a) ( L(a|b) )*= L(a) ( L(a) L(b) )*= a ( a b )*= a ( a, b )*=

13、 a , a, b, aa, ab, ba, bb, abb, = a,aa, ab, aaa, aab, aba, abb, aabb, 即L(R)是 上以a開頭的串集。2022/7/25編譯原理與技術(shù)講義37正規(guī)式與正規(guī)集正規(guī)定義d1 r1d2 r2dn rn各個di的名字不同；每個ri是d1 ,d2, di-1上的正規(guī)式 2022/7/25編譯原理與技術(shù)講義38正規(guī)式與正規(guī)集e.g.4 Pascal 標(biāo)識符letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9 id letter ( letter | digit )*英文字母集合十進(jìn)制數(shù)字集合標(biāo)識符的正規(guī)定義2022/7/25編譯原理與技術(shù)講義39正規(guī)式與正規(guī)集e.g.5 Pascal 無符號數(shù)digit 0 | 1 | | 9digits digit di