編譯原理與技術 詞法分析

1、2021-6-13編譯原理與技術講義1 編譯原理與技術 詞法分析(1) 2021-6-13編譯原理與技術講義2 詞法分析 詞法分析器介紹 正規(guī)式與正規(guī)集 有限自動機 詞法分析器的自動生成lex 2021-6-13編譯原理與技術講義3 詞法分析器介紹 詞法分析器的功能 高級語言 源程序 詞法分 析器 語法分 析器 token get_next_token 編譯器其 它階段 符號表 字符流 記號 （流） 2021-6-13編譯原理與技術講義4 詞法分析器介紹 詞法分析器的功能 讀源程序，產生記號序列 剝去源程序中的注釋（塊、行）和“空白”符 預處理宏處理與文件包含 2021-6-13編譯原理與技術

2、講義5 詞法分析器介紹 詞法分析器作為獨立子程序 簡化設計 提高編譯效率 增強可移植性 2021-6-13編譯原理與技術講義6 詞法分析器介紹 記號、模式與單詞 記號同類單詞的總稱 模式描述構成記號的字符串的規(guī)則 單詞源程序中能匹配任一記號的字符串 2021-6-13編譯原理與技術講義7 程序語言的記號（1） 記號單詞模式 關鍵字 whilewhilewhile forforfor 標識符id temp, i, max 字母開頭的字母數(shù)字串 常數(shù)num 3.14 100 數(shù)字字符串.數(shù)字字符串 2021-6-13編譯原理與技術講義8 程序語言的記號（2） 記號單詞模式 運算符 mul* gt

3、界符, 串常量string “hello” there 雙（單）引號中間的字符 串（不包括引號本身） 2021-6-13編譯原理與技術講義9 詞法分析器介紹 詞法分析器的二元輸出 單詞（字符 串）的類別 匹配記號的單詞多于 一個時，須提供額外 的信息以區(qū)別之 2021-6-13編譯原理與技術講義10 詞法分析器介紹 詞法分析器的二元輸出 記號影響語法 分析的決策 屬性（如類型、 偏移）則關系到 記號的翻譯 2021-6-13編譯原理與技術講義11 詞法分析器介紹 e.g.1 pascal源程序片段： begin length := length + 1; if length20 then re

4、ad(nextch); end; 2021-6-13編譯原理與技術講義12 e.g.1 pascal源程序片段的字符流(sp表示空格) beginntl engthsp:= splengthsp +sp1;ntif splength 20spthensp read(nex tch);nen d; 2021-6-13編譯原理與技術講義13 e.g. 1 詞法分析器的輸出記號流(1) /不是多余的！ / 屬性是常量“值”本身 2021-6-13編譯原理與技術講義14 e.g. 1 詞法分析器的輸出記號流(2) 2021-6-13編譯原理與技術講義15 詞法分析器介紹 超前搜索 fortran中的關

5、鍵字“不保留” 1） do100k=1,10 2） do100k=1.10 3） if(5.eq.m) i=10 4） if(5)=55 有關算符的識別 c/c+, java的+, -, =, !=, = 等，與之對應 + , - , !, = 2021-6-13編譯原理與技術講義16 詞法分析器介紹 詞法錯誤 可檢測非法字符的出現(xiàn) if vs fi 詞法分析器的設計 手工編寫采用匯編語言或高級語言 自動生成lex 2021-6-13編譯原理與技術講義17 詞法分析器介紹 狀態(tài)轉換圖 用于記號的識別。狀態(tài)之間用帶有標記（字符）的 有向邊連接；每讀入一個字符會引起狀態(tài)變化，直 至單詞（記號）被識

6、別出來。 開始狀態(tài)：狀態(tài)轉換圖的初始狀態(tài)（尚未讀字符） 接受狀態(tài)：某個單詞被識別時所處的狀態(tài)（終態(tài)） 單詞（記號）的識別過程即是從開始狀態(tài)出發(fā)到某 接受狀態(tài)的變化過程。 2021-6-13編譯原理與技術講義18 詞法分析器介紹 狀態(tài)轉換圖 01 2 字母 其它 字母或數(shù)字 識別標識符的轉換圖 * 03 4 數(shù)字 其它 數(shù)字 識別整數(shù)的轉換圖 * 2021-6-13編譯原理與技術講義19 詞法分析器介紹 狀態(tài)轉換圖 05 數(shù)字. 識別pascal無符號數(shù)的轉換圖 * 數(shù)字 67891011 數(shù)字 數(shù)字 e +|- 數(shù)字 數(shù)字 其它 e 數(shù)字 其它 其它 2021-6-13編譯原理與技術講義20

7、詞法分析器介紹 狀態(tài)轉換圖 05 數(shù)字. （紅線）識別pascal無符號整數(shù)的轉換圖 * 數(shù)字 67891011 數(shù)字 數(shù)字 e +|- 數(shù)字 數(shù)字 其它 e 數(shù)字 其它 其它 2021-6-13編譯原理與技術講義21 詞法分析器介紹 狀態(tài)轉換圖 05 數(shù)字 . 識別pascal無符號小數(shù)的轉換圖 * 數(shù)字 67891011 數(shù)字 數(shù)字 e +|- 數(shù)字 數(shù)字 其它 e 數(shù)字 其它 其它 2021-6-13編譯原理與技術講義22 狀態(tài)轉換圖的實現(xiàn) e.g. 2 簡單詞法分析的轉換圖（識別關鍵字、標識符、 無符號整數(shù)、算符和界符） 01 空白符（n,t,sp） 字母或數(shù)字 字母非字母數(shù)字 2 *

8、 return( id, 符號表條目指針） or return( 關鍵字，） 3 數(shù)字 數(shù)字非數(shù)字字符 4 * return(num, 常量值或者常量 表條目指針） to be continued 2021-6-13編譯原理與技術講義23 e.g. 2簡單詞法分析的轉換圖 + 5return（+, ） - 6return（-, ） 7 *非*字符 8 * return（*, ） 9 return（*, ） * to be continued 2021-6-13編譯原理與技術講義24 e.g. 2簡單詞法分析的轉換圖 10 13 return（lt, ） 其它字符 = 14return（eq,

9、） * 15 = 16 * return（ge, ） 17 return（gt, ） 其它字符 to be continued 2021-6-13編譯原理與技術講義25 e.g. 2簡單詞法分析的轉換圖 18 ： = 19 return（assign, ） 20return（:, ） 其它字符 * ； 21return（；, ） 其它 22error() 狀態(tài)轉換程序 2021-6-13編譯原理與技術講義26 串與語言 語言 語言l s | s 是上任一字符串， s稱為語言l的一個句子。 字母表符號/字符的非空有限集合 e.g. 二進制數(shù)的0,1，而十進制數(shù)的 0,1,9 *表示上所有字符串的

10、集合；l* 字符串 上若干字符組成的有窮序列 2021-6-13編譯原理與技術講義27 串與語言 語言 字符串 e.g. 0,1上的0，1串（二進制數(shù)）如0111， 10101；a,b上的 a, b, aa , abab, 空串， *， 串長|s|s中所含字符的個數(shù)，| |=0 串的連接運算任意串x，y，一般地，xyyx， x= x 串的前綴 任意串x，從其第一個字符（最左字符） 起的字符序列是其前綴。亦是。 e.g. x = abc, 則，a，ab，abc均是x的前綴 2021-6-13編譯原理與技術講義28 語言的運算 語言的運算 描述 運算 語言l和語言m 連接（積） lm= xy| x

11、l 且 ym 合并（和） lm=x| xl 或 xm 閉包l*=l0l1l2= 正閉包l+=l1l2l3= 0 i i l 1 i i l 2021-6-13編譯原理與技術講義29 語言 e.g. l=a,b,z, d=0,1,9, b= _ ld = ld= l*= l(ld)*= (l b)(ldb)*= d+= 2021-6-13編譯原理與技術講義30 正規(guī)式與正規(guī)集 正規(guī)式用于描述記號的構成規(guī)則 正規(guī)集正規(guī)式描述的語言（匹配正規(guī)式的 串集） 正規(guī)式正規(guī)集 aa 2021-6-13編譯原理與技術講義31 正規(guī)式與正規(guī)集 正規(guī)式正規(guī)集 r | sl(r) l(s) r sl(r) l(s)

12、 r*(l(r)* (r)l(r) 如果r和s是上的正規(guī)式，分別對應上的正規(guī) 集l(r)和l(s)，則 2021-6-13編譯原理與技術講義32 正規(guī)式與正規(guī)集 運算符優(yōu)先級結合性 或|低左結合 連接 高左結合 閉包*最高左結合 上的正規(guī)式，其運算有 | 、 和 * 2021-6-13編譯原理與技術講義33 正規(guī)式與正規(guī)集 代數(shù)定律描述 交換律r | s s | r 結合律 r | (s|t) = (r|s) | t r (st) = (rs) t 分配律 r (s|t) = (rs) | (rt) (r|s) t = (rt) | (st) 同一律 r = r = r 上的正規(guī)式，滿足如下代

13、數(shù)定律 2021-6-13編譯原理與技術講義34 正規(guī)式與正規(guī)集 上的正規(guī)式，也具有如下代數(shù)定律 ( r* ) * = r * ( r | ) * = r * r+ = r r* 2021-6-13編譯原理與技術講義35 正規(guī)式與正規(guī)集 e.g.3 設=a, b, 則 正規(guī)式正規(guī)集 a(a|b)*上以a開頭的串集 ba*上以b開頭后跟任意個a的串集 (a|b)*a(a|b)(a|b)上倒數(shù)第三個字符是a的串集 2021-6-13編譯原理與技術講義36 正規(guī)式與正規(guī)集 e.g.3 設=a, b，r = a(a|b)*，事實上有 l(r) = l( a(a|b)* ) = l(a) l(a|b)*

14、) = l(a) ( l(a|b) )* = l(a) ( l(a) l(b) )* = a ( a b )* = a ( a, b )* = a , a, b, aa, ab, ba, bb, abb, = a,aa, ab, aaa, aab, aba, abb, aabb, 即l(r)是 上以a開頭的串集。 2021-6-13編譯原理與技術講義37 正規(guī)式與正規(guī)集 正規(guī)定義 d1 r1 d2 r2 dn rn 各個di的名字不同；每個ri是d1 ,d2, di-1 上的正規(guī)式 2021-6-13編譯原理與技術講義38 正規(guī)式與正規(guī)集 e.g.4 pascal 標識符 letter a | b | | z | a | b | | z digit 0 | 1 | | 9 id letter ( letter | digit )* 英文字母 集合 十進制數(shù) 字集合 標識符的 正規(guī)定義 2021-6-13編譯原理與技術講義39 正規(guī)式與正規(guī)集 e.g.5 pascal 無符號數(shù) digit 0 | 1 | | 9 digits