【正文】 igits ? digit num5 num5 ? digit num5 | ? Wensheng Li BUPT 2022 40/78 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn) 步驟： 1. 給出描述該語言各種單詞符號的詞法規(guī)則 2. 畫出狀態(tài)轉(zhuǎn)換圖 3. 根據(jù)狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析器 一、文法及狀態(tài)轉(zhuǎn)換圖 1. 語言說明 2. 記號的正規(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ù)字組成的符號串。 – 邊上的標(biāo)記代表在射出結(jié)狀態(tài)下，可能出現(xiàn)的輸入符號或字符類。 – 二者具有同等表達(dá)能力 – 正規(guī)表達(dá)式：清晰、簡潔 – 正規(guī)文法：便于識別 一、詞法與正規(guī)文法 二、記號的文法 三、狀態(tài)轉(zhuǎn)換圖與記號的識別 Wensheng Li BUPT 2022 22/78 一、詞法與正規(guī)文法 ? 把源語言的文法 G分解為若干子文法： G0、 G G … 、 Gn —— 正規(guī)文法 —— 上下文無關(guān)文法 語法 詞法 ? 詞法：描述語言的標(biāo)識符、常數(shù)、運(yùn)算符和標(biāo)點(diǎn)符號等記號的文法 ? 語法：借助于記號來描述語言的結(jié)構(gòu)的文法 文法？ Wensheng Li BUPT 2022 23/78 二、記號的文法 ? 標(biāo)識符 ? 常數(shù) – 整數(shù) – 無符號數(shù) ? 運(yùn)算符 ? 分界符 ? 關(guān)鍵字 Wensheng Li BUPT 2022 24/78 標(biāo)識符 ? 標(biāo)識符定義為“由字母打頭的、由字母或數(shù)字組成的符號串” ? 描述標(biāo)識符集合的正規(guī)表達(dá)式： letter(letter|digit)* ? 表示標(biāo)識符集合的正規(guī)定義式： letter ? A|B|…|Z|a|b|…|z digit ? 0|1|…|9 id ? letter(letter|digit)* 正規(guī)表達(dá)式？ Wensheng Li BUPT 2022 25/78 把正規(guī)定義式轉(zhuǎn)換為相應(yīng)的正規(guī)文法 ( letter | digit )* = ? | ( letter | digit )+ = ? | ( letter | digit ) ( letter | digit )* = ? | letter ( letter | digit )* | digit ( letter | digit )* = ? | (A|… |Z|a|… |z) ( letter | digit )* | (0|… |9)( letter | digit )* = ? | A ( letter | digit )* | … | Z ( letter | digit )* | a ( letter | digit )* | … | z ( letter | digit )* | 0 ( letter | digit )* | … | 9 ( letter | digit )* Wensheng Li BUPT 2022 26/78 標(biāo)識符的正規(guī)文法 id ? A rid|…|Z rid|a rid|…|z rid rid ? ? |A rid|B rid|…|Z rid |a rid|b rid|…|z rid |0 rid|1 rid|…|9 rid ? 一般寫作： id ? letter rid rid ? ? | letter rid | digit rid Wensheng Li BUPT 2022 27/78 常數(shù) —— 整數(shù) ? 描述整數(shù)結(jié)構(gòu)的正規(guī)表達(dá)式為： (digit)+ ? 對此正規(guī)表達(dá)式進(jìn)行等價(jià)變換： (digit)+ = digit(digit)* (digit)* = ? | digit(digit)* ? 整數(shù)的正規(guī)文法： digits ? digit remainder remainder ? ? | digit remainder Wensheng Li BUPT 2022 28/78 常數(shù) —— 無符號數(shù) ? 無符號數(shù)的正規(guī)表達(dá)式為： (digit)+ (.(digit)+)? (E(+|)?(digit)+)? ? 正規(guī)定義式為 digit ? 0|1|…|9 digits ? digit+ optional_fraction ? (.digits)? optional_exponent ? (E(+|)?digits)? num ? digits optional_fraction optional_exponent Wensheng Li BUPT 2022 29/78 把正規(guī)定義式轉(zhuǎn)換為正規(guī)文法 ( digit )+ ( . ( digit )+ )? ( E( + | )?( digit )+ )? =( digit )+ ( . ( digit )+ |? ) ( E(+ | | ?) ( digit )+ | ? ) =digit (digit)* ( . digit ( digit )*|?) ( E (+||?) digit ( digit )* | ? ) num1 表示無符號數(shù)的第一個(gè)數(shù)字之后的部分 num2 表示小數(shù)點(diǎn)以后的部分 num3 表示小數(shù)點(diǎn)后第一個(gè)數(shù)字以后的部分 num4 表示 E之后的部分 num5 表示 (digit)* digits 表示 (digit)+ Wensheng Li BUPT 2022 30/78 無符號數(shù)分析圖 digit (digit)* (. digit (digit)*|?) (E (+||?) digit (digit)* |?) num3 num2 num1 num4 num 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 31/78 無符號數(shù)的正規(guī)文法 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 32/78 無符號數(shù) 的分析樹 numd i g it n u m 1. n u m 2d i g it n u m 3E n u m 4 d i g i t sd i g it n u m 5 468? Wensheng Li BUPT 2022 33/78 運(yùn)算符 ? 關(guān)系運(yùn)算符的正規(guī)表達(dá)式為： |= | = | | = | ? 正規(guī)定義式： relop ? |= | = | | = | ? 關(guān)系運(yùn)算符的正規(guī)文法： relop ? | equal | = |greater | | equal greater ? equal ? = Wensheng Li BUPT 2022 34/78 三、狀態(tài)轉(zhuǎn)換圖與記號的識別 ? 狀態(tài)轉(zhuǎn)換圖 ? 利用狀態(tài)轉(zhuǎn)換圖識別記號 ? 為線性文法構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖 – 狀態(tài)集合的構(gòu)成 – 狀態(tài)之間邊的形成 Wensheng Li BUPT 2022 35/78 狀態(tài)轉(zhuǎn)換圖 ? 狀態(tài)轉(zhuǎn)換圖是一張有限的方向圖 – 圖中結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。 – 為設(shè)計(jì)詞法程序，對模式要給出規(guī)范、系統(tǒng)的描述。 ? 記號影響語法分析的決策，屬性影響記號的翻譯。 – 單詞：是指某一類單詞符號的一個(gè)特例，如 position是標(biāo)識符。 } Wensheng Li