【正文】 第三章 詞法分析 概述 ?正規(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ū) 。 forward 移動到第一個半?yún)^(qū)的開始 end else forward : = forward + 1 哨兵（ sentinel）技術(shù) ?每個緩沖區(qū)末端添加標(biāo)記 ——哨兵 ?減少條件判斷 eof * M = E eof eof 2 * * C Current token lexeme beginning forward (scans ahead to find pattern match) 使用哨兵技術(shù)的偽代碼 forward : = forward + 1 。 if forward ? = eof then begin 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ū) 。 forward 移動到第一個半?yún)^(qū)的開始 end else / * 緩沖區(qū)內(nèi)部的 eof意味著輸入的結(jié)束 * / 結(jié)束詞法分析 end 2nd eof ? 輸入結(jié)束 ! Block I/O Block I/O lcc的輸入處理 // unsigned char *cp。 /* current input character */ unsigned char *limit。 /* points to last character + 1 */ void nextline(void) { do { if (cp = limit) { fillbuf()。 if (cp = limit) cp = limit。 if (cp == limit) return。 } \n cp limit lcc的輸入處理（續(xù)） else { lineno++。 for (line = (char *)cp。 *cp==39。 39。 || *cp==39。\t39。 cp++) 。 if (*cp == 39。39。) { resynch()。 nextline()。 } } } while (*cp == 39。\n39。 amp。amp。 cp == limit)。 } lcc的輸入處理（續(xù)） void fillbuf(void) { if (bsize == 0) return。 if (cp = limit) cp = amp。buffer[MAXLINE+1]。 else { int n = limit cp。 unsigned char *s = amp。buffer[MAXLINE+1] n。 assert(s = buffer)。 line = (char *)s ((char *)cp line)。 while (cp limit) *s++ = *cp++。 cp = amp。buffer[MAXLINE+1] n。 } \n cp limit lcc的輸入處理（續(xù)） if (feof(stdin)) bsize = 0。 else bsize = fread(amp。buffer[MAXLINE+1], 1, BUFSIZE, stdin)。 if (bsize 0) { error(read error\n)。 exit(EXIT_FAILURE)。 } limit = amp。buffer[MAXLINE+1+bsize]。 *limit = 39。\n39。 } \n cp limit \n cp limit TinyC的輸入處理 static int getNextChar(void) { if (!(linepos bufsize)) { lineno++。 if (fgets(lineBuf,BUFLEN1,source)) { if (EchoSource) fprintf(listing,%4d: %s,lineno,lineBuf)。 bufsize = strlen(lineBuf)。 linepos = 0。 return lineBuf[linepos++]。 } else { EOF_flag = TRUE。 return EOF。 } } else return lineBuf[linepos++]。 } 單詞的描述：正規(guī)表達(dá)式 串和語言 字母表 （ alphabet） 符號的有窮集合 如 {0, 1}, {a, b, c}, {n, m, …, z} 串和語言（續(xù)） 符號串 （ string） 字母表中符號組成的有窮序列 如 0011， abbca， AABBC 也稱作句子（ sentence），字（ word） s為符號串， |s|表示 s的 長度 ——符號數(shù)目 e ： 空符號串 ， |e|=0 相關(guān)術(shù)語 ——符號串 s為 banana 術(shù)語 s的 前綴 （ prefix） s的 后綴 （ suffix） s的 子串 （ substring） s的 真 （ proper） 前綴、 后綴 、 子串 s的 子序列 （ subsequence） 定義 將 s尾部 0個或多個符號刪除得到的符號串，如 ban， banana， e 將 s頭部 0個或多個符號刪除所得符號串， 如 ana， banana， e 將 s刪除一個前綴和后綴所得符號串，如 nan，前綴、后綴都是特殊子串 s的非空前綴、后綴、子串，且不等于 s 在 s中刪除一個或多個符號（不要求連續(xù)）得到的符號串， bnan， nn 語言的定義 一個 語言 （ Language） L： 是一個給定字母表之上的任意符號串集合 Alphabet Languages {0,1} {1,10,100,1000,10000…} {0,1,00,11,000,111,…} {a,b,c} {abc,aabbcc,aaabbbccc,…} {A, … ,Z} {TEE,FORE,BALL,…} {FOR,WHILE,GOTO,…} 語言的定義（續(xù)） Alphabet Languages {A,…,Z,a,…,z,0,…9, { All legal PASCAL progs} +,,…,…} { All grammatically correct English sentences } ?特例： ?—空語言， {e}—只含空字 語言 ??符號串集合 ??單詞 語言和單詞 符號串的運(yùn)算 ?連接 （ concatenation） ?符號串 x, y的連接，寫作 xy——y拼接于 x后 ? x=dog， y=house， xy=doghouse ? s e = e s = s 符號串的運(yùn)算（續(xù)） ?冪 （ exponentiation） ?連接看作積（ product） ? s0 = e ? si = si1s ? s1 = s, s2 = ss, s3 = sss, … 語言的運(yùn)算 運(yùn)算 L和 M的 并 （ union) 寫作 L∪ M L和 M的 連接 寫作 LM L的 Kleene閉包 （ closure） 寫作 L* L的 正則 （ positive） 閉包 寫作 L＋ }s|{ MLssML ???? 或定義 }t|{ MLsstLM ??? 且????0*iiLL???? ?1iiLL?Li表示 L的 i次連接 語言運(yùn)算示例 L = {A, B,…, Z, a, b, …, z} D = {0, 1, …, 9} L ? D = 數(shù)字、字母集合 LD = { 一個字母后接一個數(shù)字的串 } L2 = { 所有兩個字母的串 } L4 = L2 L2 = { 所有四個字母的串 } 語