【正文】 |e2 = e2|e1 交換律 ?e1 |(e2|e3) = (e1|e2)|e3 結合律 ?e1(e2e3) = (e1e2)e3 結合律 ?e1(e2|e3) = e1e2|e1e3 分配律 ?(e2|e3)e1 = e2e1|e3 e1 分配律 ?e? = ? e = e e1e2 e2 e1 國防科技大學計算機系 602教研室 確定有限自動機 (DFA) ? 對狀態(tài)圖進行形式化 ， 則可以下定義： 自動機 M是一個五元式 M=(S, ?, f, S0, F),其中： 1. S: 有窮狀態(tài)集 ， 2. ?：輸入字母表 (有窮 )， 3. f: 狀態(tài)轉換函數 ， 為 S???S的單值部分映射 ，f(s， a)=s?表示：當現(xiàn)行狀態(tài)為 s， 輸入字符為a時 ， 將狀態(tài)轉換到下一狀態(tài) s?。 國防科技大學計算機系 602教研室 ? 所有詞法結構一般都可以用正規(guī)式描述 。 2) 任何 a?? ， a是 ?上的正規(guī)式，它所表示的正規(guī)集為 {a}。 一個字集合是正規(guī)集當且僅當它能用正規(guī)式表示 。 國防科技大學計算機系 602教研室 正規(guī)式和正規(guī)集 ? 正規(guī)集可以用正規(guī)表達式 （ 簡稱正規(guī)式 ）表示 。 ??V } V自身的 n次積記為 Vn=VV…V ? 規(guī)定 V0={?}， 令 V*=V0∪ V1∪ V2∪ V3∪ … 稱 V*是 V的 閉包 。 else ProcError( )。 else if (ch =?{?) return ($LBRACE, )。 else if (ch =?(?) return ($LPAR, )。 end else if (ch =?。 Retract()。 國防科技大學計算機系 602教研室 else if (ch =?*?) begin GetChar()。 end else if (ch =?=?) return ($ASSIGN, )。 value := InsertConst(strToken)。 GetChar( )。 end else return (code, )。 if (code = 0) begin value := InsertId(strToken)。 end Retract()。 if (IsLetter()) begin while (IsLetter() or IsDigit()) begin Concat()。 /*置 strToken為空串 */ GetChar()。 國防科技大學計算機系 602教研室 int code, value。 while (IsLetter( ) or IsDigit( )) GetChar( )。} else {… 錯誤處理 …。} else if (IsDigit( )) {… 狀態(tài) k的對應程序段 …。 ? 做法 : 1)對不含回路的分叉結，可用一個 CASE語句或一組 IFTHENELSE語句實現(xiàn) GetChar( )。 ?如果基本字 、 標識符和常數 (或標號 )之間沒有確定的運算符或界符作間隔 ， 則必須使用一個空白符作間隔 。用戶不能用它們作自己的標識符 ?基本字作為特殊的標識符來處理 。 國防科技大學計算機系 602教研室 2 例子 ?助憶符 ：直接用編碼表示不便于記憶，因此用助憶符來表示編碼。 ?一張轉換圖只包含有限個狀態(tài)，其中有一個為初態(tài)，至少要有一個終態(tài)。 2 1 3 X Y ?結點代表狀態(tài)，用圓圈表示 。 ? 預處理子程序：剔除無用的空白 、 跳格 、回車和換行等編輯性字符 。 ?不作為一遍：將其處理為一個子程序 。 ?常數按類型分種；常數的值則表示成標準的二進制形式。 ?若一個種別有多個單詞符號，則對于每個單詞符號，給出種別編碼和自身的值。 ?若一個種別只有一個單詞符號，則種別編碼就代表該單詞符號。國防科技大學計算機系 602教研室 第三章 詞法分析 ? 詞法分析的任務：從左至右逐個字符地對源程序進行掃描，產生一個個單詞符號。 ? 詞法分析器 (Lexical Analyzer) 又稱掃描器 (Scanner)：執(zhí)行詞法分析的程序 國防科技大學計算機系 602教研室 對于詞法分析器的要求 一、詞法分析器的功能和輸出形式 ? 功能 :輸入源程序、輸出單詞符號 ? 單詞符號的種類： ?基本字：如 begin， repeat， ? ?標識符 ——表示各種名字：如變量名、數組名和過程名 ?常數：各種類型的常數 ?運算符： +， ， *， /， ? ?界符：逗號、分號、括號和空白 國防科技大學計算機系 602教研室 ? 輸出的單詞符號的表示形式 : (單詞種別，單詞自身的值 ) ? 單詞種別通常用整數編碼表示。假定基本字、運算符和界符都是一符一種。 ?標識符單列一種；標識符自身的值表示成按機器字節(jié)劃分的內部碼。 國防科技大學計算機系 602教研室 二、詞法分析器作為一個獨立子程序 ? 詞法分析是作為一個獨立的階段，是否應當將其處理為一遍呢？ ?作為獨立階段的優(yōu)點：結構簡潔、清晰和條理化，有利于集中考慮詞法分析一些枝節(jié)問題。 國防科技大學計算機系 602教研室 詞法分析器的結構 預處理子程序 掃描器 輸入緩沖區(qū) 掃描緩沖區(qū) 單詞符號 輸入 列表 詞法分析器的設計 國防科技大學計算機系 602教研室 ? 輸入串放在輸入緩沖區(qū)中。區(qū)分標號區(qū) 、捻接續(xù)行和給出句末符等 ? 掃描緩沖區(qū) ↑ ↑ 起點 搜索 指示器 指示器 一、輸入、預處理 國防科技大學計算機系 602教研室 二、單詞符號的識別 :超前搜索 1 基本字識別 2 標識符識別 3 常數識別 4 算符和界符的識別 國防科技大學計算機系 602教研室 三 、 狀態(tài)轉換圖 1 概念 ?狀態(tài)轉換圖是一張有限方向圖。 ?狀態(tài)之間用箭弧連結，箭弧上的標記 (字符 )代表射出結狀態(tài)下可能出現(xiàn)的輸入字符或字符類。 國防科技大學計算機系 602教研室 識別標識符的狀態(tài)轉換圖 1 2 3 字母 其他 字母或數字 * 識別 整常數 的狀態(tài)轉換圖 1 2 3 數字 其他 數字 * ? 一個狀態(tài)轉換圖可用于識別 (或接受 )一定的字符串。 國防科技大學計算機系 602教研室 單詞符號 種別編碼 助憶符 內碼值 DIM 1 $DIM IF 2 $IF DO 3 $DO STOP 4 $STOP END 5 $END 標識符 6 $ID 內部字符串 常數 ( 數 ) 7 $INT 標準二進制形式 = 8 $ASSIGN _ 9 $PLUS * 10 $STAR ** 11 $POWER ， 12 $COMMA ( 13 $LPAR ) 14 $RPAR 國防科技大學計算機系 602教研室 1 2 3 4 5 6 7 8 9 10 11 12 13 0 空白 字母 字母或數字 非字母與數字 數字 非數字 數字 = + * 非 * , ( ) 其它 * * * * 國防科技大學計算機系 602教研室 ? 幾點重要限制 ——不必使用超前搜索 ?所有基本字都是保留字 。不用特殊的狀態(tài)圖來識別 ， 只要查保留字表 。 DO99K=1， 10