第三章詞法分析 對于詞法分析器的要求詞法分析器的設計正規表達式與有窮自動機詞法分析器的自動產生 LEX 詞法分析 詞法分析的任務 從左至右逐個字符地對源程序進行掃描 產生一個個單詞符號 詞法分析器 LexicalAnalyzer 又稱掃描器 Scanner 執行詞法分析的程序 3 1對于詞法分析器的要求 一 詞法分析器的功能和輸出形式功能 輸入源程序 輸出單詞符號單詞符號的種類 基本字 如begin repeat 標識符 表示各種名字 如變量名 數組名和過程名常數 各種類型的常數運算符 界符 逗號 分號 括號和空白 輸出的單詞符號的表示形式 單詞種別 單詞自身的值 單詞種別通常用整數編碼表示 若一個種別只有一個單詞符號 則種別編碼就代表該單詞符號 假定基本字 運算符和界符都是一符一種 若一個種別有多個單詞符號 則對于每個單詞符號 給出種別編碼和自身的值 標識符單列一種 標識符自身的值表示成按機器字節劃分的內部碼 常數按類型分種 常數的值則表示成標準的二進制形式 例FORTRAN程序 IF 5 EQ M GOTO100輸出單詞符號 邏輯IF 34 左括號 2 整常數 20 5 的二進制 等號 6 標識符 26 M 右括號 16 GOTO 30 標號 19 100 的二進制 助憶符 直接用編碼表示不便于記憶 因此用助憶符來表示編碼 例 IF 34 IF 左括號 2 等號 6 例C程序 while i j i 輸出單詞符號 二 詞法分析器作為一個獨立子程序 詞法分析是作為一個獨立的階段 是否應當將其處理為一遍呢 作為獨立階段的優點 結構簡潔 清晰和條理化 有利于集中考慮詞法分析一些枝節問題 不作為一遍 將其處理為一個子程序 詞法分析器 詞法分析器的結構 預處理子程序 掃描器 輸入緩沖區 掃描緩沖區 單詞符號 輸入 3 2詞法分析器的設計 刪除無用的空白 跳格 回車和換行等編輯性字符區分標號區 捻接續行和給出句末符等 WhatALong Word WhatALong Wo rd WhatALong Wo rd WhatALong Wo 掃描緩沖區 起點搜索指示器指示器 一 掃描緩沖區 二 單詞符號的識別 超前搜索 以基本字的識別為例 例如 DO99K 1 10DO99K 1 10IF 5 EQ M GOTO55IF 5 EQ M GOTO55DO99K 1 10IF 5 55需要超前搜索才能確定哪些是基本字 幾點限制 不必使用超前搜索 所有基本字都是保留字 用戶不能用它們作自己的標識符 基本字作為特殊的標識符來處理 不用特殊的狀態圖來識別 只要查保留字表 如果基本字 標識符和常數 或標號 之間沒有確定的運算符或界符作間隔 則必須使用一個空白符作間隔 三 狀態轉換圖 1概念狀態轉換圖是一張有限方向圖 結點代表狀態 用圓圈表示 狀態之間用箭弧連結 箭弧上的標記 字符 代表射出結狀態下可能出現的輸入字符或字符類 一張轉換圖只包含有限個狀態 其中有一個為初態 至少要有一個終態 識別標識符的狀態轉換圖 1 2 3 字母 其他 字母或數字 識別整常數的狀態轉換圖 一個狀態轉換圖可用于識別 或接受 一定的字符串 詞法分析器設計流程 某程序設計語言的單詞符號串集 分析詞法規則 畫出識別單詞的狀態圖 根據狀態圖寫詞法分析器程序 3狀態轉換圖的實現思想 每個狀態結對應一小段程序 做法 1 對不含回路的分叉結 可用一個CASE語句或一組IF THEN ELSE語句實現 GetChar if IsLetter 狀態j的對應程序段 elseif IsDigit 狀態k的對應程序段 elseif ch 狀態l的對應程序段 else 錯誤處理 3狀態轉換圖的實現2 對含回路的狀態結 可對應一段由WHILE語句構成的程序 GetChar while IsLetter orIsDigit GetChar 狀態j的對應程序段 3狀態轉換圖的實現3 終態結表示識別出某種單詞符號 因此 對應語句為RETURN C VAL 其中 C為單詞種別 VAL為單詞自身值 全局變量與過程1 ch字符變量 存放最新讀入的源程序字符2 strToken字符數組 存放構成單詞符號的字符串3 GetChar子程序過程 把下一個字符讀入到ch中4 GetBC子程序過程 跳過空白符 直至ch中讀入一非空白符5 Concat子程序 把ch中的字符連接到strToken 6 IsLetter和IsDisgital布爾函數 判斷ch中字符是否為字母和數字7 Reserve整型函數 對于strToken中的字符串查找保留字表 若它是保留字則給出它的編碼 否則回送08 Retract子程序 把搜索指針回調一個字符位置9 InsertId整型函數 將strToken中的標識符插入符號表 返回符號表指針10 InsertConst整型函數過程 將strToken中的常數插入常數表 返回常數表指針 intcode value strToken 置strToken為空串 GetChar GetBC if IsLetter beginwhile IsLetter orIsDigit beginConcat GetChar endRetract 搜索指針回調code Reserve 判斷是否為保留字if code 0 標識符beginvalue InsertId strToken return ID value endelsereturn code 保留字end elseif IsDigit beginwhile IsDigit beginConcat GetChar endRetract value InsertConst strToken return INT value endelseif ch return ASSIGN elseif ch return PLUS elseif ch beginGetChar if ch return POWER Retract return STAR endelseif ch return SEMICOLON elseif ch return LPAR elseif ch return RPAR elseProcError 錯誤處理 將狀態圖的代碼一般化 變量curState用于保存現有的狀態用二維數組表示狀態圖 stateTrans state char curState 初態GetChar While stateTrans curState ch 有定義 存在后繼狀態 讀入 拼接Contact 轉入下一狀態 讀入下一字符curState stateTrans curState ch IfcurState是終態then返回strToken中的單詞GetChar 此處給出的只是一個框架 還有很多細節需要考慮 FA 正規集 正規式 DFA NFA 正規文法 3 3 1 3 3 23 3 3 3 3 4 3 3 5 DFA 3 3 6 3 3正規表達式與有限自動機 易于程序實現 易于人工設計 程序的單詞集合 詞法規則 詞法規則 3 3正規表達式與有限自動機 幾個概念 考慮一個有窮字母表 字符集其中每一個元素稱為一個字符 上的字 也叫字符串 是指由 中的字符所構成的一個有窮序列不包含任何字符的序列稱為空字 記為 用 表示 上的所有字的全體 包含空字 例如 設 a b 則 a b aa ab ba bb aaa 的子集U和V的連接 積 定義為UV U記V VV 稱V 是V的正規閉包 3 3 1正規式和正規集 正規集可以用正規表達式 簡稱正規式 表示 正規表達式是表示正規集一種方法 一個字集合是正規集當且僅當它能用正規式表示 正規式和正規集的遞歸定義 對給定的字母表 1 和 都是 上的正規式 它們所表示的正規集為 和 2 任何a a是 上的正規式 它所表示的正規集為 a 3 假定e1和e2都是 上的正規式 它們所表示的正規集為L e1 和L e2 則i e1 e2 為正規式 它所表示的正規集為L e1 L e2 ii e1 e2 為正規式 它所表示的正規集為L e1 L e2 連接積 iii e1 為正規式 它所表示的正規集為 L e1 閉包 即任意有限次的自重復連接 僅由有限次使用上述三步驟而定義的表達式才是 上的正規式 僅由這些正規式表示的字集才是 上的正規集 所有詞法結構一般都可以用正規式描述 若兩個正規式所表示的正規集相同 則稱這兩個正規式等價 如b ab ba b a b a b L ba b L ba L b L ba L b L b L a L b ba b ba baba bababa b b bab babab bababab L b ab L b L ab L b L ab L b L a L b b ab b ab abab ababab b bab babab bababab L b ab L ba b b ab ba b 對正規式 下列等價成立 e1 e2 e2 e1交換律e1 e2 e3 e1 e2 e3結合律e1 e2e3 e1e2 e3結合律e1 e2 e3 e1e2 e1e3分配律 e2 e3 e1 e2e1 e3e1分配律e e ee1e2e2e1 L e1 e2 L e1 L e2 L e2 L e1 L e2 e1 FA 正規集 正規式 DFA NFA 3 3 1 3 3 23 3 3 程序的單詞集合 詞法規則 3 3 2確定有限自動機 DFA 對狀態圖進行形式化 則可以下定義 自動機M是一個五元式M S f S0 F 其中 1 S 有窮狀態集 2 輸入字母表 有窮 3 f 狀態轉換函數 為S S的單值部分映射 f s a s 表示 當現行狀態為s 輸入字符為a時 將狀態轉換到下一狀態s 我們把s 稱為s的一個后繼狀態 4 S0 S是唯一的一個初態 5F S 終態集 可空 例如 DFAM 0 1 2 3 a b f 0 3 其中 f定義如下 f 0 a 1f 0 b 2f 1 a 3f 1 b 2f 2 a 1f 2 b 3f 3 a 3f 3 b 3 狀態轉換矩陣 對于 中的任何字符串 若存在一條從初態到某一終態的道路 且這條路上所有弧上的標記符連接成的字符串等于 則稱 為DFAM所識別 接收 DFAM所識別的字符串的全體記為L M 練習下圖DFA識別的L M 是什么 A L M 以aa或bb開頭的字符串 B L M 含aa或bb的字符串 C L M 以aa或bb結尾的字符串 答案 B 3 3 3非確定有限自動機 NFA 1976年圖靈獎Fortheirjointpaper Finiteautomataandtheirdecisionproblems whichintroducedtheideaofnondeterministicmachines whichhasprovedtobeanenormouslyvaluableconcept Theirclassicpaperhasbeenacontinuoussourceofinspirationforsubsequentworkinthisfield 3 3 3非確定有限自動機 NFA 定義 一個非確定有限自動機 NFA M是一個五元式M S f S0 F 其中 1S 有窮狀態集 2 輸入字母表 有窮 3f 狀態轉換函數 為S 2S的部分映射 非單值 4S0 S是非空的初態集 5F S 終態集 可空 從狀態圖可看出NFA和DFA的區別 1可有多個初態2弧上的標記可以是 中的一個字 甚至可以是一個正規式 而不一定是單個字符 3同一個字可能出現在同狀態射出的多條弧上 DFA是NFA的特例 NFA DFA 對于 中的任何字 若存在一條從初態到某一終態的道路 且這條路上所有弧上的標記符連接成的字等于 忽略那些標記為 的弧 則稱 為NFAM所識別 接收 NFAM所識別的字符串的全體記為L M 識別所有含相繼兩個a或相繼兩個b的字 ambn m n 1 NFA示例 定義 對于任何兩個有限自動機M和M 如果L M L M 則稱M與M 等價 自動機理論中一個重要的結論 判定兩個自動機等價性的算法是存在的 對于每個NFAM存在一個DFAM 使得L M L M 亦即DFA與NFA描述能力相同 NFA與DFA 1 假定NFAM 我們對NFAM的狀態轉換圖進行以下改造 1 引進新的初態結點X和終態結點Y X Y S 從X到S0中任意狀態結點連一條 箭弧 從F中任意狀態結點連一條 箭弧到Y 2 按以下3條規則對NFAM的狀態轉換圖進一步施行替換 直到把這個圖轉變為每條弧只標記為 上的一個字符或 其中k是新引入的狀態 NFA轉換為等價的DFA 代之為 代之為 代之為 按下面的3條規則對箭弧進行分裂 例 識別所有含相繼兩個a或相繼兩個b的字 2 把上述NFA確定化 采用子集法 設I是NFA的狀態集的一個子集 定義I的 閉包 closure I 為 i 若s I 則s closure I ii 若s I 則從s出發經過任意條 弧而能到達的任何狀態s 都屬于 closure I 即 closure I I s 從某個s I出發經過任意條 弧能到達s 設a是 中的一個字符 定義Ia closure J 其中 J為I中的某個狀態出發經過一條a弧而到達的狀態集合 closure 1 1 2 IJ 5 4 3 Ia closure J closure 5 4 3 5 4 3 6 2 7 8 設a是 中的一個字符 定義Ia closure J 其中 J為I中的某個狀態出發經過一條a弧而到達的狀態集合 Ia 確定化的過程 不失一般性 設字母表只包含兩個a和b 我們構造一張表 首先 置第1行第1列為 closure X 求出這一列的Ia Ib 然后 檢查這兩個Ia Ib 看它們是否已在表中的第一列中出現 把未曾出現的填入后面的空行的第1列上 求出每行第2 3列上的集合 重復上述過程 知道所有第2 3列子集全部出現在第一列為止 I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y 現在把這張表看成一個狀態轉換矩陣 把其中的每個子集看成一個狀態 這張表唯一刻劃了一個確定的有限自動機M 它的初態是 closure X 它的終態是含有原終態Y的子集 不難看出 這個DFAM與M 等價 I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y I Ia Ib X 5 1 5 3 1 5 4 1 5 3 1 5 2 3 1 6 Y 5 4 1 5 4 1 5 3 1 5 2 4 1 6 Y 5 2 3 1 6 Y 5 2 3 1 6 Y 5 4 6 1 Y 5 4 6 1 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 4 1 6 Y 5 3 6 1 Y 5 2 3 1 6 Y 5 4 6 1 Y FA 正規集 正規式 DFA NFA 3 3 1 3 3 23 3 3 程序的單詞集合 詞法規則 3 3 5 3 3 5正規式與有限自動機的等價性 定理 1 對任何FAM 都存在一個正規式r 使得L r L M 2 對任何正規式r 都存在一個FAM 使得L M L r 對轉換圖概念拓廣 令每條弧可用一個正規式作標記 對一類輸入符號 證明 1對 上任一NFAM 構造一個 上的正規式r 使得L r L M 首先 在M的轉換圖上加進兩個狀態X和Y 從X用 弧連接到M的所有初態結點 從M的所有終態結點用 弧連接到Y 從而形成一個新的NFA 記為M 它只有一個初態X和一個終態Y 顯然L M L M 然后 反復使用下面的一條規則 逐步消去的所有結點 直到只剩下X和Y為止 代之為 代之為 代之為 1 2 5 4 V1 U1 U2 W1 V1 U1 U2 W2 V2 U1 U2 W2 V2 U1 U2 W1 最后 X到Y的弧上標記的正規式即為所構造的正規式r顯然L r L M L M 定理 1 對任何FAM 都存在一個正規式r 使得L r L M 2 對任何正規式r 都存在一個FAM 使得L M L r 證明2 對于 上的正規式r 構造一個NFAM 使L M L r 并且M只有一個終態 而且沒有從該終態出發的箭弧 下面使用關于r中運算符數目的歸納法證明上述結論 1 若r具有零個運算符 則r 或r 或r a 其中a 此時下圖所示的三個有限自動機顯然符合上述要求 2 假設結論對于少于k k 1 個運算符的正規式成立 當r中含有k個運算符時 r有三種情形 情形1 r r1 r2 r1 r2中運算符個數少于k 從而 由歸納假設 對ri存在Mi 使得L Mi L ri 并且Mi沒有從終態出發的箭弧 i 1 2 不妨設S1 S2 在S1 S2中加入兩個新狀態q0 f0 令M 其中 定義如下 a q0 q1 q2 b q a 1 q a 當q S1 f1 a 1 c q a 2 q a 當q S2 f2 a 2 d f1 f2 f0 M的狀態轉換如右圖所示 L M L M1 L M2 L r1 L r2 L r q0 f0 情形2 r r1r2 設Mi同情形1 i 1 2 令M 其中 定義如下 a q a 1 q a 當q S1 f1 a 1 b q a 2 q a 當q S2 a 2 c f1 q2 M的狀態轉換如右圖所示 L M L M1 L M2 L r1 L r2 L r 情形3 r r1 設M1同情形1 令M 其中q0 f0 S1 定義如下 a q0 f1 q1 f0 b q a 1 q a 當q S1 f1 a 1 M的狀態轉換如右圖所示 L M L M1 L r1 L r 至此 結論2獲證 q0 f0 1 構造 上的NFAM 使得L V L M 首先 把V表示成 上述證明過程實質上是一個將正規表達式轉換為有限自動機的算法 代之為 代之為 代之為 然后 按下面的三條規則對V進行分裂 逐步把這個圖轉變為每條弧只標記為 上的一個字符或 最后得到一個NFAM 顯然L M L V a b aa bb a b FA 正規集 正規式 DFA NFA 3 3 1 3 3 23 3 3 3 3 5 程序的單詞集合 詞法規則 易于程序實現 易于人工設計 DFA 3 3 6 3 3 6確定有限自動機的化簡 對DFAM的化簡 尋找一個狀態數比M少的DFAM 使得L M L M 假設s和t為M的兩個狀態 稱s和t等價 如果從狀態s出發能讀出某個字 而停止于終態 那么同樣 從t出發也能讀出 而停止于終態 反之亦然 兩個狀態不等價 則稱它們是可區別的 對一個DFAM最少化的基本思想 把M的狀態集劃分為一些不相交的子集 使得任何兩個不同子集的狀態是可區別的 而同一子集的任何兩個狀態是等價的 最后 讓每個子集選出一個代表 同時消去其他狀態 具體做法 對M的狀態集進行劃分首先 把S劃分為終態和非終態兩個子集 形成基本劃分 假定到某個時候 已含m個子集 記為 I 1 I 2 I m 檢查 中的每個子集看是否能進一步劃分 對某個I i 令I i s1 s2 sk 若存在一個輸入字符a使得Ia i 不會包含在現行 的某個子集I j 中 即 Ia i 中的元素分布在現行劃分的多個子集中 則至少應把I i 分為兩個部分 例如 假定狀態s1和s2經a弧分別到達t1和t2 而t1和t2屬于現行 中的兩個不同子集 說明有一個字 t1讀出 后到達終態 而t2讀出 后不能到達終態 或者反之 那么對于字a s1讀出a 后到達終態 而s2讀出a 不能到達終態 或者反之 所以s1和s2不等價 s1 t1 a s2 t2 a j i 則將I i 分成兩半 使得一半含有s1 I i1 s s I i 且s經a弧到達t 且t與t1屬于現行 中的同一子集 另一半含有s2 I i2 I i I i1 一般地 對某個a和I i 若Ia i 落入現行 中N個不同子集 則應把I i 劃分成N個不相交的組 使得每個組J的Ja都落入的 同一子集 這樣構成新的劃分 重復上述過程 直到 所含子集數不再增長 對于上述最后劃分 中的每個子集 我們選取每個子集I中的一個狀態代表其他狀態 則可得到化簡后的DFAM 若I含有原來的初態 則其代表為新的初態 若I含有原來的終態 則其代表為新的終態 I 1 0 1 2 I 2 3 4 5 6 Ia 1 1 3 I 11 0 2 I 12 1 I 2 3 4 5 6 I 11 0 2 Ia 11 1 Ib 11 2 5 I 111 0 I 112 2 I 12 1 I 2 3 4 5 6 Ia 2 3 6 Ib 2 4 5 FA 正規集 正規式 DFA NFA 3 3 1 3 3 23 3 3 3 3 5 DFA 3 3 6 程序的單詞集合 詞法規則 易于程序實現 易于人工設計 85 一 原理單詞的詞法規則用正規式描述正規式 NFA DFA minDFA LEX編譯器 LEX源程序lex 1 詞法分析程序Lex yy c 二 用LEX建立詞法分析程序的過程 3 4詞法分析器的自動產生 LEX 86 C編譯器 詞法分析程序Lex yy c 詞法分析程序Lex out或lex exe 詞法分析程序L 單詞符號 輸入串 狀態轉換矩陣 控制執行程序 3 4詞法分析器的自動產生 LEX 3 4詞法分析器的自動產生 LEX lex源程序lex源程序由三部分組成 聲明 識別規則