【正文】 言運(yùn)算示例（續(xù)） L = {A, B,…, Z, a, b, …, z} D = {0, 1, …, 9} L* = { 所有字母串，包括 e } L+ = L* e D+ = L (L ? D )* = {非空數(shù)字串 } {字母開頭的字母數(shù)字串 } ——NUM ——ID ?語言 ??符號(hào)串集合 ??單詞 ?復(fù)雜語言（單詞、符號(hào)串集合）??簡(jiǎn)單語言的運(yùn)算表示 ?單詞 ??簡(jiǎn)單語言（符號(hào)串集合）的運(yùn)算 語言和單詞 ?正規(guī)式 ??語言（符號(hào)串集合）運(yùn)算的簡(jiǎn)潔描述 ? 簡(jiǎn)單語言 ??基本正規(guī)式 ? 語言運(yùn)算 ??正規(guī)式運(yùn)算 語言和單詞（續(xù)） 正規(guī)表達(dá)式 ? regular expression ? Pascal標(biāo)識(shí)符： letter ( letter | digit )* ?正規(guī)集 （ regular set） ——特殊的語言 ?正規(guī)式 r——表示正規(guī)集（語言） L(r) ——利用 一組 規(guī)則 （運(yùn)算）來構(gòu)造 ? 指明如何用符號(hào)表中符號(hào)構(gòu)成特定符號(hào)串集合（正規(guī)集、正規(guī)語言 ） ? 基本、簡(jiǎn)單的正規(guī)式如何遞歸地構(gòu)成復(fù)雜的正規(guī)式 正規(guī)式定義規(guī)則 ? 字母表 Σ 上的正規(guī)式 r的定義規(guī)則，以及 r所表示的語言 L(r)定義如下： 1. e是正規(guī)式，表示語言 {e} 2. 若 a∈ Σ，則 a是正規(guī)式，表示語言 {a} 正規(guī)式定義規(guī)則（續(xù)） 3. r, s為正規(guī)式，表示語言 L(r)和 L(s)，則 a) (r) | (s)是正規(guī)式，表示語言 L(r) ? L(s) b) (r)(s)是正規(guī)式，表示語言 L(r)L(s) c) (r)*是正規(guī)式，表示語言 (L(r))* d) (r) 是正規(guī)式，表示語言 L(r) 優(yōu)先級(jí)降低 例 ? Σ={a, b} 1. a | b ? { a, b} 2. (a | b)(a | b) ? { aa, ab, ba, bb } 3. a* ? {e, a, aa, aaa, … } 例 （續(xù)） 4. (a | b)* = { 所有由 a、 b組成的符號(hào)串 } 5. a | a*b = { a, 所有以若干個(gè) a開頭，后跟一個(gè) b的符號(hào)串 } ? 正規(guī)式 等價(jià) （ equivalent）： r = s?? 表示的語言相同， L(r) = L(s) 正規(guī)式運(yùn)算的特性 公理 描述 r | s = s | r r | (s | t) = (r | s) | t (r s) t = r (s t) e r = r r e = r r* = ( r | e )* r ( s | t ) = r s | r t ( s | t ) r = s r | t r r** = r* | 滿足 交換率 | 滿足 結(jié)合率 連接滿足 結(jié)合率 連接和 | 滿足 分配率 * 和 e間的關(guān)系 e是連接運(yùn)算的 單位元 * 是 冪等 的 正規(guī)定義 ?為正規(guī)式指定名字 d1 ? r1 d2 ? r2 … dn ? rn ?di是不同的名字， ri是 Σ?{d1, d2, …, di1} （即基本符號(hào)與前面定義的名字）上的正規(guī)式 正規(guī)定義例子 ?例 ： Pascal語言標(biāo)識(shí)符 letter ? A | B | C | … | Z | a | b | … | z digit ? 0 | 1 | 2 | … | 9 id ? letter ( letter | digit )* (A | … | Z | a | … | z)(A | … | Z | a | … | z | 0 | … | 9)* 例 ： Pascal語言無符號(hào)數(shù) digit ? 0 | 1 | 2 | … | 9 digits ? digit digit* optional_fraction ? . digits | e optional_exponent ? ( E ( + | | e) digits ) | e num ? digits optional_fraction optional_exponent 符號(hào)簡(jiǎn)寫 ?＋ ：一個(gè)或多個(gè)實(shí)例（一次或多次連接） ? r+ = rr*，表示語言 (L(r))+ ? r* = r+ | e ??： 0個(gè)或一個(gè)實(shí)例， r?=r | e?L(r)∪ {e} ? optional_fraction ? (. digits )? ? optional_exponent ? ( E ( + | )? digits )? 符號(hào)簡(jiǎn)寫（續(xù)） ?字符集 ? [abc] ? a | b | c ? [az] ? a | b | … | z ?標(biāo)識(shí)符： [AZaz][AZaz09]* 非正規(guī)集 ?正規(guī)式無法描述的語言 ? {wcw | w是 a、 b組成的符號(hào)串 } ?正規(guī)式無法描述平衡或嵌套的結(jié)構(gòu) ?正規(guī)式只能表示 ?有限的重復(fù) ?一個(gè) 給定結(jié)構(gòu)的無限重復(fù) ?例： Hollerith串 ——nHa1a2…a n無法用正規(guī)式描述 正規(guī)式練習(xí) ?描述正規(guī)式表示的語言 ? 0*10*10*10*： ? ((e | 0) 1*)*： ?設(shè)計(jì)語言的正規(guī)式 ?能被 5整除的 10進(jìn)制整數(shù) ?包含五個(gè)元音，且按順序排列的所有字母串 con→ [bdfhjnptvz] string→ (con)*a(con | a)*e(con | e)*i(con | i)*o(con | o)* u(con | u)* [19][09]*(0 | 5) | 0 | 5 包含 3個(gè) 1的 01串 所有 01串 Lex ?詞法分析器自動(dòng)生成工具 Lex程序結(jié)構(gòu) 定義段： %{ C語言代碼 %} 定義 %% 規(guī)則段：詞法規(guī)則 %% 用戶子程序段 規(guī)則段形式 ? p1 { action1 } p2 { action2 } … pn { actionn } pi：模式 ——正規(guī)式 actioni：動(dòng)作 ——C語言程序段 ——當(dāng)字符流前綴與 pi匹配時(shí)（識(shí)別出對(duì)應(yīng)單詞的詞素）該做什么動(dòng)作 例 ：超前搜索 ?r1/r2： r1必須后接 r2的情況下才匹配 ?語句： IF(I, J) = 3 IF是數(shù)組名還是分支語句關(guān)鍵字？ IF (condition) THEN 語句 … 分支語句： IF / \( .* \) {letter} Lex中的整數(shù) ?八進(jìn)制 0713 ?十六進(jìn)制 0x7f ?十進(jìn)制 9 0 Lex中的字符 \n——換行 \t——橫向制表符 \v——縱向制表符 \b——退格 \r——回車 \f——換頁 \a——報(bào)警 \\——?\? \ooo——ASCII碼值為八進(jìn)制數(shù) ooo的字符 \xhh——ASCII碼值為十六進(jìn)制數(shù) hh的字符 ? 其他特殊字符 ( ) + * ? { } [ ] . “ | ^ / $ ? \——轉(zhuǎn)義符，放在特殊字符前，使其變?yōu)槠胀ㄗ址? 字符集 [abc]： a | b | c [az]： a | b | … | z [+]： + | [azAZ09_]： a | …| z | A | … | Z | 0 | … | 9 | _ [^abc]：除 a、 b、 c之外的所有字符 [:alpha:]：大小寫字母 [:digit:]：數(shù)字 [[:alpha:]_][[:alpha:]09_]*——標(biāo)識(shí)符 正規(guī)式構(gòu)造 ?|、連接、 *、 ( )、 +、 ?、字符集 ?.——[^\n]，匹配除回車外任意字符 ?指定重復(fù)次數(shù) a{3, 5}——{aaa, aaaa, aaaaa} a{3, }——{aaa, aaaa, aaaaa, aaaaaa, …} a{3}——{aaa} 例 1 %{int num_lines = 0, num_chars = 0。%} %% \n {++num_lines。 ++num_chars。} . {++num_chars。} %% C語言代碼 規(guī)則段 例 1 main(int argc, char *argv[]) { ++argv, argc。 /* skip over program name */ if ( argc 0 ) yyin = fopen( argv[0], r )。 else yyin = stdin。 yylex()。 printf( of lines = %d, of chars = %d\n, num_lines, num_chars )。 } 子程序段 PG默認(rèn) 輸入文件 C語言標(biāo)準(zhǔn)輸入 例 1 C++版 %{ include fstream int num_lines = 0, num_chars = 0。 %} ///////////////////////////////////////////////////////////////////////////// // declarations section // lexical analyser name %name count %% 例 1 C++版（續(xù)） ///////////////////////////////////////////////////////////////////////////// // rules section // place your Lex rules here \n {++num_lines。 ++num_chars。} . {++num_chars。} %% 例 1 C++版（續(xù)） int main(int argc, char *argv[]) { int n = 1。 count lexer。 if (()) { if (argc 1) = new std::ifstream()。 if (!fail()) { n = ()。 } n = ()。 cout num_lines num_chars endl。 } return n。 } 變?yōu)?Lexer的成員 例 2 %{ include %} WS [ \t\n]* %% [0123456789]+ printf(NUMBER\n)。 [azAZ][azAZ09]* printf(WORD\n)。 {WS} /* do nothing */ . printf(“UNKNOWN\n“)。 C語言代碼 規(guī)則段 定義段 例 2 %% main(int argc, char *argv[]) { ++argv, argc。 if ( argc 0 ) yyin = fopen( argv[0], r )。 else yyin = stdin。 yylex()。 } 子程序段 單詞的識(shí)別 ?例 ：考慮文法 stmt ? if expr then stmt | if expr then stmt else stmt | e expr ? term relop term | term term ? id | num 對(duì)應(yīng)的單詞正規(guī)式定義 if ? if then ? then else ? else relop ? | = | | = | = | id ? letter ( letter | digit )* num ? digit+ (. digit+ ) ? ( E(+ | ) ? digit+ ) ? 過濾空白符 ?空白符也可寫成正規(guī)式 blank ? b tab ? ^T newline ? ^M delim ? blank | tab | newline ws ? delim+ 全部正規(guī)式定義 Regular Expression Token AttributeValue ws if then else id num = = = if then else id num relop relop relop relop relop