1、第三章 詞法(cf)分析本章內容詞法分析器：把構成源程序的字符流翻譯成記號流，還完成和用戶接口(ji ku)的一些任務圍繞詞法分析器的自動生成展開介紹正則式、狀態轉換圖和有限自動機概念 詞法分析器詞法分析器語法分析器語法分析器符號表符號表記號記號(token)取下一個記號取下一個記號源程序源程序第1頁/共26頁第一頁，共27頁。詞法分析(fnx)初步：正則表達式，狀態轉換圖3.13.4第2頁/共26頁第二頁，共27頁。3.1 詞法記號詞法記號(j ho)及屬性及屬性 3.1.1 詞法記號、模式、詞法單元 記號名 詞法單元例舉模式的非形式描述 if if 字符i, f for for字符f, o

2、, r relation , = , = , 或 0） 第7頁/共26頁第七頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 語言(yyn)(yyn)的運算 并：L L M = s | s M = s | s L L 或 s s M M 連接：LM = st | s LM = st | s L L 且 t t M M 冪：L0L0是 ，LiLi是Li-1L Li-1L 閉包：L L = L0 = L0 L1 L1 L2 L2 正閉包： L+ = L1 L+ = L1 L2 L2 例 L: A, B, , Z, a, b, , z , D: 0, 1, , 9 L: A

3、, B, , Z, a, b, , z , D: 0, 1, , 9 L L D, LD, L6, L D, LD, L6, L* *, L(L , L(L D ) D )* *, D+ , D+ 第8頁/共26頁第八頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 3.2.2 正則式正則式用來表示簡單的語言，叫做正則集正則式定義(dngy)的語言備注aa a (r) | (s)L(r)L(s) r和s是正則式(r)(s)L(r)L(s) r和s是正則式(r)*(L(r)* r是正則式(r)L(r) r是正則式(a) (b)*)| (c)可以寫成ab*| c 第9頁/共2

4、6頁第九頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 正則(zhn z)(zhn z)式的例子 = a, b = a, b a | ba | ba, ba, b (a | b) (a | b )(a | b) (a | b )aa, ab, ba, bbaa, ab, ba, bb aa | ab | ba | bbaa | ab | ba | bbaa, ab, ba, bbaa, ab, ba, bb a a* *由字母a a構成的所有串集 (a | b)(a | b)* *由a a和b b構成的所有串集 復雜的例子 ( 00 | 11 | ( (01 | 10)

5、 (00 | 11) ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) (01 | 10) ) ) 句子：0100110100001000001011100101001101000010000010111001第10頁/共26頁第十頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 正則式等價：表示同樣(tngyng)語言的正則式第11頁/共26頁第十一頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 3.2.3 正則定義對正則式命名(mng mng)，使表示簡潔 d1 r1 d2 r2 . . .

6、 dn rn各個di的名字都不同每個ri都是 d1, d2, , di-1 上的正則式第12頁/共26頁第十二頁，共27頁。3.2 詞法記號的描述詞法記號的描述(mio sh)與識別與識別 正則定義的例子(l zi) C語言的標識符是字母、數字和下劃線組成的串 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_(letter_ |digit)* 第13頁/共26頁第十三頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 正則定義(dngy)的例子 無符號數集合，例1946,11.28,63

7、E8,1.99E6digit 0 | 1 | | 9digits digit digit*optional_fraction .digits|optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 簡化表示number digit+ (.digit+)? (E(+|)? digit+)?第14頁/共26頁第十四頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 正則(zhn z)定義的例子（進行下一步討論的例子）while whiledo do

8、relop | = | = | | | =letter A | B | | Z | a | b | | z id letter (letter | digit )*number digit+ (.digit+)? (E (+ | )? digit+)? delim blank | tab | newline ws delim+第15頁/共26頁第十五頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 詞法(cf)單元的識別stmt if expr then stmt | if expr then stmt else stmt | expr term relop term |

9、 termterm id | number第16頁/共26頁第十六頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 詞法(cf)單元的識別stmt if expr then stmt | if expr then stmt else stmt | expr term relop term | termterm id | numberdigit 0-9digits digit+number digits(.digits)?(E+-?digits)?letter A-Za-zid letter (letter | digit)*if ifthen thenelse elser

10、elop | = | = | 第17頁/共26頁第十七頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 詞法(cf)單元的識別詞素詞法單元名字屬性值Any ws-ifif-Thenthen-elseelse-Any idid指向符號表條目的指針Any numbernumber指向符號表條目的指針relopLT=relopLE=relopEQrelopNErelopGT=relopGE第18頁/共26頁第十八頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 3.2.4 轉換(zhunhun)圖關系算符的轉換(zhunhun)圖 051624837r

11、eturn(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)開始開始=*otherother第19頁/共26頁第十九頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 標識符和關鍵字的轉換(zhunhun)圖91011開始開始letterother*letter或或digitreturn(install_id()第20頁/共26頁第二十頁，共27頁。3.2 詞法記號的描述詞法記號的描述(mio sh)與識別與識別 無符號(fho)

12、數的轉換圖 number digit+ (.digit+)? (E (+ | )? digit+)?開始開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*第21頁/共26頁第二十一頁，共27頁。3.2 詞法記號詞法記號(j ho)的描述與識別的描述與識別 空白(kngbi)(kngbi)的轉換圖 delim delim blank | tab | newline blank | tab | newline ws ws delim+ delim+212

13、2開始開始delimother*delim20第22頁/共26頁第二十二頁，共27頁。3.2 詞法詞法(cf)記號的描述與識別記號的描述與識別 合成(hchng)(hchng)整體轉換圖開始開始912200第23頁/共26頁第二十三頁，共27頁。作業(zuy) 字符串匹配。給你兩個字符串，尋找其中一個字符串是否包含另一個字符串，如果包含，返回包含的起始位置(wi zhi)。 如下面兩個字符串： 時間復雜度O(N2)char *str = bacbababadababacambabacaddababacasdsd; char *ptr = ababaca;第24頁/共26頁第二十四頁，共27頁。重點(zhngdin) 串和語言(yyn) 語言(yyn)的運算 正則表達式 狀態轉換圖第25頁/共26頁第二十五頁，共27頁。26/34感謝您的觀看(gunkn)！第26頁/共26頁第二十六頁，共27頁。NoImage內容(nirng)總結第三