【文章內(nèi)容簡(jiǎn)介】 狀態(tài)之間用有向邊連接。 – 邊上的標(biāo)記代表在射出結(jié)狀態(tài)下，可能出現(xiàn)的輸入符號(hào)或字符類。 1 2 3 x y Wensheng Li BUPT @ 2022 36/78 標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖 ? 標(biāo)識(shí)符的文法產(chǎn)生式： id ? letter rid rid ? ? | letter rid | digit rid ? 標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖 0 1 2 letter/digit letter other * Wensheng Li BUPT @ 2022 37/78 利用狀態(tài)轉(zhuǎn)換圖識(shí)別記號(hào) ? 語句 DO99K= 中 標(biāo)識(shí)符 DO99K 的識(shí)別過程： 0 1 2 letter/digit letter other * 狀態(tài) 0 讀入 D 狀態(tài) 1 讀入 O 狀態(tài) 1 讀入 9 狀態(tài) 1 讀入 K 狀態(tài) 1 讀入 = 狀態(tài) 2 讀入 9 狀態(tài) 1 Wensheng Li BUPT @ 2022 38/78 為線性文法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖 ? 狀態(tài)集合的構(gòu)成 – 對(duì)文法 G的每一個(gè)非終結(jié)符號(hào)設(shè)置一個(gè)對(duì)應(yīng)的狀態(tài) – 文法的開始符號(hào)對(duì)應(yīng)的狀態(tài)稱為初態(tài) – 增加一個(gè)新的狀態(tài)，稱為終態(tài)。 ? 狀態(tài)之間邊的形成 – 對(duì)產(chǎn)生式 A?aB，從 A狀態(tài)到 B狀態(tài)畫一條標(biāo)記為 a的邊 – 對(duì)產(chǎn)生式 A?a，從 A狀態(tài)到終態(tài)畫一條標(biāo)記為 a的邊 – 對(duì)產(chǎn)生式 A??，從 A狀態(tài)到終態(tài)畫一條標(biāo)記為 ?的邊 Wensheng Li BUPT @ 2022 39/78 無符號(hào)數(shù)的右線性文法的狀態(tài)轉(zhuǎn)換圖 num num1 num2 num3 num4 num5 digits 0 2 4 digit 1 digit 3 digit 6 digit other 7 digit E E 5 +/ digit digit * other . other num ? digit num1 num1 ? digit num1 | . num2 | E num4 | ? num2 ? digit num3 num3 ? digit num3 | E num4 | ? num4 ? + digits | digits | digit num5 digits ? digit num5 num5 ? digit num5 | ? Wensheng Li BUPT @ 2022 40/78 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn) 步驟： 1. 給出描述該語言各種單詞符號(hào)的詞法規(guī)則 2. 畫出狀態(tài)轉(zhuǎn)換圖 3. 根據(jù)狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器 一、文法及狀態(tài)轉(zhuǎn)換圖 1. 語言說明 2. 記號(hào)的正規(guī)文法 3. 狀態(tài)轉(zhuǎn)換圖 二、詞法分析程 序 的構(gòu)造 三、詞法分析程 序 的實(shí)現(xiàn) 1. 輸出形式 2. 設(shè)計(jì)全局變量和過程 3. 編制詞法分析程 序 Wensheng Li BUPT @ 2022 41/78 一、文法及狀態(tài)轉(zhuǎn)換圖 ? 語言說明 標(biāo)識(shí)符 ：以字母開頭的、后跟字母或數(shù)字組成的符號(hào)串。 保留字 ：標(biāo)識(shí)符的子集。 無符號(hào)數(shù) ：同 PASCAL語言中的無符號(hào)數(shù)。 關(guān)系運(yùn)算符 ： 、 =、 =、 、 =、 。 標(biāo)點(diǎn)符號(hào) ： +、 、 *、 /、 (、 )、 :、 ?；等。 賦值號(hào) ： := 注釋標(biāo)記 ：以‘ /*?開始，以‘ */?結(jié)束。 單詞符號(hào)間的分隔符 ：空格 Wensheng Li BUPT @ 2022 42/78 記號(hào)的正規(guī)文法 ? 標(biāo)識(shí)符的文法 id ? letter rid rid ? ? | letter rid | digit rid ? 無符號(hào)整數(shù)的文法 digits ? digit remainder remainder ? ? | digit remainder Wensheng Li BUPT @ 2022 43/78 ? 無符號(hào)數(shù)的文法 num ? digit num1 num1 ? digit num1 | . num2 | E num4 | ? num2 ? digit num3 num3 ? digit num3 | E num4 | ? num4 ? + digits | digits |digit num5 digits ? digit num5 num5 ? digit num5 | ? ? 關(guān)系運(yùn)算符的文法 relop ? |equal | = |greater ||equal greater ? equal ? = 記號(hào)的正規(guī)文法 (續(xù) ) Wensheng Li BUPT @ 2022 44/78 ? 賦值號(hào)的文法 assign_op ? :equal equal ? = ? 標(biāo)點(diǎn)符號(hào)的文法 single ? + | | * | / | ( | ) | : | ? | 。 ? 注釋頭符號(hào)的文法 note ? / star star ? * 記號(hào)的正規(guī)文法 (續(xù) ) Wensheng Li BUPT @ 2022 45/78 狀態(tài)轉(zhuǎn)換圖 讀去注釋狀態(tài) 錯(cuò)誤處理狀態(tài) digit E other * 3 5 digit 2 digit 4 digit 7 digit digit . E 6 +/ digit other * other * 0 letter 1 letter / digit other * 8 = other * 9 = other * = ： 10 = other * + / / * / ( / ) / 。 / ? / 11 * other * 12 13 other 轉(zhuǎn)入口 出口 入口 Wensheng Li BUPT @ 2022 46/78 二、詞法分析程序的構(gòu)造 根據(jù)上述狀態(tài)轉(zhuǎn)換圖，再加上相應(yīng)的語義動(dòng)作，就可以構(gòu)造出的詞法分析程 序 的算法框圖。 Wensheng Li BUPT @ 2022 47/78 開始 讀字符 空白？ Y N Token :=‘ ’ 字母？ Y 組合標(biāo)識(shí)符 R 查保留字表 保留字？ Y N 輸出保留字 輸出標(biāo)識(shí)符 N 數(shù)字？ Y 組數(shù) R 輸出無符號(hào)數(shù) N ？ Y N 讀字符 = ？ Y 輸出 = N ？ Y 輸出 N R 輸出 ？ Y 讀字符 =？ Y 輸出 = N R 輸出 ：？ Y 讀字符 =? Y 輸出賦值號(hào) := N R 輸出冒號(hào)： N / ? 讀字符 * ? 讀去注釋 N R 輸出斜杠 / N Y Y 轉(zhuǎn)入口 N 標(biāo)點(diǎn)符號(hào)？ Y 輸出標(biāo)點(diǎn)符號(hào) N 錯(cuò)誤處理 出口 說明： R 為一過程，其功能是向前指針回退一個(gè)字符； Token 為字符數(shù)組，用于存放單詞符號(hào) Wensheng Li BUPT @ 2022 48/78 三、詞法分析程序的實(shí)現(xiàn) ? 輸出形式 ? 設(shè)計(jì)全局變量和過程 ? 編制詞法分析程 序 Wensheng Li BUPT @ 2022 49/78 輸出形式 ? 利用翻譯表，將識(shí)別出的單詞的記號(hào)以二元式的形式加以輸出 ? 二元式的形式： 記號(hào)，屬性 Wensheng Li BUPT @ 2022 50/78 正規(guī)表達(dá)式 記號(hào) 屬性 if if then then else else id id 符號(hào)表入口指針 num num 常數(shù)表入口指針 relop LT = relop LE = relop EQ relop NE relop GT = relop GE := assignop + + * * / / ( ( ) ) ? ? 。 。 : : Wensheng Li BUPT @ 2022 51/78 設(shè)計(jì)全局變量和過程 ? 轉(zhuǎn)換圖中的每一狀態(tài)，分別用一段程序?qū)崿F(xiàn)。 ? 如果某一狀態(tài)有若干條射出邊，則程序： – 讀一個(gè)字符 – 根據(jù)讀到的字符，選擇標(biāo)記與之匹配的邊到達(dá)下一個(gè)狀態(tài)，即程序控制轉(zhuǎn)去執(zhí)行下一個(gè)狀態(tài)對(duì)應(yīng)的語句序列。 Wensheng Li BUPT @ 2022 52/78 (1) C：字符變量，存放當(dāng)前讀進(jìn)的字符。 (2) iskey：整型變