【正文】 end。 end。 Dtran[T, a] = U。 } } } 算法 ： NFA轉(zhuǎn)換為 DFA(3) NFA?DFA的 算法 初始， e closure(s0)是 Dstates（ DFA狀態(tài)集）中唯一狀態(tài)，且未標(biāo)記 。 e closure(T) = T。 c ? nextchar。 return ( NUM )。 else state = 27。 else state = fail()。 install_id()。 else if (isdigit(c)) state = 10。 else state = fail()。 default: /* piler error */ } return start。 case 20: start = 25。 case 9: start = 12。 int lexical_value。 else if (c == ??) state = 6。 ?如何工作 ? ?如何擴(kuò)展 ? 狀態(tài) 實(shí)現(xiàn)代碼 /* c is lookahead character */ if (c== blank || c==tab || c== newline) { state = 0。 else yyin = stdin。 [azAZ][azAZ09]* printf(WORD\n)。 } n = ()。} %% 例 1 C++版（續(xù)） int main(int argc, char *argv[]) { int n = 1。 } 子程序段 PG默認(rèn) 輸入文件 C語言標(biāo)準(zhǔn)輸入 例 1 C++版 %{ include fstream int num_lines = 0, num_chars = 0。 /* skip over program name */ if ( argc 0 ) yyin = fopen( argv[0], r )。%} %% \n {++num_lines。 } else { EOF_flag = TRUE。 if (fgets(lineBuf,BUFLEN1,source)) { if (EchoSource) fprintf(listing,%4d: %s,lineno,lineBuf)。buffer[MAXLINE+1+bsize]。buffer[MAXLINE+1], 1, BUFSIZE, stdin)。 cp = amp。buffer[MAXLINE+1] n。 if (cp = limit) cp = amp。 amp。) { resynch()。\t39。 for (line = (char *)cp。 /* points to last character + 1 */ void nextline(void) { do { if (cp = limit) { fillbuf()。 if forward ? = eof then begin if forward 位于第一半?yún)^(qū)的末端 then begin 裝載第二個半?yún)^(qū) 。第三章 詞法分析 概述 ?正規(guī)式 ——描述單詞 ?有限自動機(jī) ——識別單詞 ?NFA?DFA ?正規(guī)式 ?NFA ?正規(guī)式 ?DFA ?DFA的化簡 詞法分析器的角色 1. 字符流 ?單詞流 2. 用戶接口：過濾注釋、空白符，錯誤信息，預(yù)處理 lexical analyzer parser symbol table source program token get next token 基本術(shù)語 ?單詞 ， token ? 源代碼字符串集的分類 ? identifier, number ?模式 ， pattern ? 描述“字符串集如何分類為單詞”的規(guī)則 ? 正規(guī)表達(dá)式， [AZ]*.* ?詞素 ， lexeme ? 程序中實(shí)際出現(xiàn)的字符串，與模式匹配，分類為單詞 ? i， count， name， 60… 基本術(shù)語（續(xù)） Token Sample Lexemes Informal Description of Pattern const if relation id num literal const if , =, =, , , = pi, count, D2 , 0, “core dumped” const if or = or = or or = or letter followed by letters and digits any numeric constant any characters between “ and ” except “ 單詞類別 實(shí)際詞素，其相關(guān)信息很關(guān)鍵： 1. 保存入符號表 2. 返回給語法分析器 單詞 單詞 ??符號串集合 單詞屬性 ?詞素的更多信息 ?單詞 ——影響語法分析 ?屬性 ——影響翻譯 例 ： E := M * C ** 2 id, 符號表中 E對應(yīng)項(xiàng)指針 assign_op, id, 符號表中 M對應(yīng)項(xiàng)指針 mult_op, id, 符號表中 C對應(yīng)項(xiàng)指針 exp_op, num, 整型值 2 詞法錯誤 ? 較少：詞法分析是對源程序極為局部化的視角 ?fi (a == f(x)) … ——詞法分析無法發(fā)現(xiàn) ? 什么情況下發(fā)生？ ——剩余輸入的前綴無法與任何一個模式相匹配 ? 可能的錯誤修復(fù)方法 ? 刪除、插入字符 ? 替換、交換字符 ? 最短編輯距離 緩沖技術(shù) ? 三種實(shí)現(xiàn)方式 1. 自動生成工具 ——Lex，生成工具提供讀取輸入和緩沖的函數(shù) 2. 高級語言手工編碼，利用高級語言提供的 I/O函數(shù) 3. 匯編語言編程，直接訪問磁盤 ? 1?3，性能 ↗ ，實(shí)現(xiàn)難度 ↗ ? 唯一讀取文件的階段，值得優(yōu)化 雙緩沖技術(shù) ?單字符 I/O＋預(yù)讀和回退 ——效率低下 ?磁盤 ——?緩沖區(qū) ————?詞法分析器 ?雙緩沖技術(shù) ?異步 I/O，高效 ?緩沖區(qū) 1——詞法分析， 同時 緩沖區(qū) 2——讀取磁盤 塊 I/O 單字符讀取 雙緩沖技術(shù)圖示 * M = : E eof eof 2 * * C Current token lexeme beginning forward (scans ahead to find pattern match) 雙緩沖技術(shù)偽代碼 if forward 位于第一半?yún)^(qū)的末端 then begin 裝載第二個半?yún)^(qū) 。 forward : = forward + 1 end else if forward 位于第二個半?yún)^(qū)的末端 then begin 裝載第一個半?yún)^(qū) 。 if (cp = limit) cp = limit。 *cp==39。 cp++) 。 nextline()。amp。buffer[MAXLINE+1]。 assert(s = buffer)。buffer[MAXLINE+1] n。 if (bsize 0) { error(read error\n)。 *limit = 39。 bufsize = strlen(lineBuf)。 return EOF。 ++num_chars。 else yyin = stdin。 %} ///////////////////////////////////////////////////////////////////////////// // declarations section // lexical analyser name %name count %% 例 1 C++版（續(xù)） ///////////////////////////////////////////////////////////////////////////// // rules section // place your Lex rules here \n {++num_lines。 count lexer。 cout num_lines num_chars endl。 {WS} /* do nothing */ . printf(“UNKNOWN\n“)。 yylex()。 lexeme_beginning++。 else state = fail()。 /* “返回” 詞法值 */ int fail() { forward = lexeme beginning。 break。 break。 } 不是比較運(yùn)算符，是不是標(biāo)識符呢？ 也不是標(biāo)識符，是不是數(shù)值常量呢？ 什么都不是，那就是詞法錯誤了。 break。 else state = 11。 return ( gettoken() )。 break。 break。 } } } 有限自動機(jī) ? 正規(guī)式 ————?識別程序（ recognizer） ? 有限自動機(jī)（ finite automata） ? 非確定有限自動機(jī) NonDeterministic Finite Automata (NFAs) 一個狀態(tài)對同一個輸入符號，有多個可能的動作 ? 確定有限自動機(jī) Deterministic Finite Automata (DFAs) 一個狀態(tài)對一個輸入符號，至多有一個動作 如何轉(zhuǎn)換？ NFA和 DFA ? 都可識別正規(guī)式，時－空折衷 ? NFA ? 正規(guī)式 ——?NFA ? “不精確 ” ，占用內(nèi)存少，速度慢 ? DFA ? 正規(guī)式 ——?DFA ? “精確 ” ，占用內(nèi)存大，速度快 ? NFA?DFA， DFA?NFA 簡單 復(fù)雜 非確定有限自動機(jī) ? 數(shù)學(xué)模型，表示為五元組 M = { S, Σ,δ, s0, F }，其中 1. S：有限狀態(tài)集 2. Σ：有窮字母表，其元素為輸入符號 3. δ： S Σ到 S的子集的映射，即 δ: S (Σ?{e}) ?2S，狀態(tài)轉(zhuǎn)換函數(shù) 。 end。 while (棧不空 ) { pop t。 while (Dstates中存在未標(biāo)記狀態(tài) T) { 標(biāo)記 T。 //DFA狀態(tài)轉(zhuǎn)換矩陣 } } e closure(s0)為初態(tài)，包含 NFA終態(tài)的 DFA狀態(tài)為 DFA終態(tài) NFA?DFA例 1 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例 1（續(xù)） e closure({0}) = { 0, 1, 2, 6, 8} e closure(δ({ 0, 1, 2, 6, 8}, a) = e closure({3}) = {3} e closure(δ({ 0, 1, 2, 6, 8}, b) = e closure({}) = {} e closure(δ({ 0, 1, 2, 6, 8}, c) = e closure({7}) = {1, 2, 5, 6, 7, 8} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例 1（續(xù)） e closure(δ({ 3}, a) = e closure({}) = {} e closure(δ({ 3}, b) = e closure({4}) = {1, 2, 4, 5, 6, 8} e closure(δ({ 3}, c) = e closure({}) = {} 0 8 5 4 7 3 6 2 1 e e e e e e e b a c e NFA?DFA例 1（續(xù)） e closure(δ({ 1, 2, 5, 6, 7, 8}, a) = e closure({3}) = {3} e closure(δ