【正文】 一、詞法與正規(guī)文法 二、記號的文法 三、狀態(tài)轉(zhuǎn)換圖與記號的識別 Wensheng Li BUPT 2022 22/78 一、詞法與正規(guī)文法 ? 把源語言的文法 G分解為若干子文法： G0、 G G … 、 Gn —— 正規(guī)文法 —— 上下文無關(guān)文法 語法 詞法 ? 詞法：描述語言的標識符、常數(shù)、運算符和標點符號等記號的文法 ? 語法：借助于記號來描述語言的結(jié)構(gòu)的文法 文法？ Wensheng Li BUPT 2022 23/78 二、記號的文法 ? 標識符 ? 常數(shù) – 整數(shù) – 無符號數(shù) ? 運算符 ? 分界符 ? 關(guān)鍵字 Wensheng Li BUPT 2022 24/78 標識符 ? 標識符定義為“由字母打頭的、由字母或數(shù)字組成的符號串” ? 描述標識符集合的正規(guī)表達式： letter(letter|digit)* ? 表示標識符集合的正規(guī)定義式： letter ? A|B|…|Z|a|b|…|z digit ? 0|1|…|9 id ? letter(letter|digit)* 正規(guī)表達式？ 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 標識符的正規(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ī)表達式為： (digit)+ ? 對此正規(guī)表達式進行等價變換： (digit)+ = digit(digit)* (digit)* = ? | digit(digit)* ? 整數(shù)的正規(guī)文法： digits ? digit remainder remainder ? ? | digit remainder Wensheng Li BUPT 2022 28/78 常數(shù) —— 無符號數(shù) ? 無符號數(shù)的正規(guī)表達式為： (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ù)的第一個數(shù)字之后的部分 num2 表示小數(shù)點以后的部分 num3 表示小數(shù)點后第一個數(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 運算符 ? 關(guān)系運算符的正規(guī)表達式為： |= | = | | = | ? 正規(guī)定義式： relop ? |= | = | | = | ? 關(guā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é)點代表狀態(tài)，用圓圈表示。 } Wensheng Li BUPT 2022 18/78 四、詞法分析程序的輸出 —— 記號 ? 記號、模式和單詞 – 記號：是指某一類單詞符號的種別編碼，如標識符的記號為 id，數(shù)的記號為 num等。 Wensheng Li BUPT 2022 16/78 每半?yún)^(qū)帶有結(jié)束標記的緩沖器 開始指針 向前指針 … i f x = y t h eof e n j : = j + 2 。 例：有合法的 FORTRAN語句： DO99K=1,10 和 DO99K= 為了區(qū)別這兩個語句 ， 必須超前掃描到等號后的第一個分界符處 。LI Wensheng, SCST, BUPT 第 3章 詞法分析 基礎(chǔ)知識： PASCAL、 C語言、正規(guī)表達式 正規(guī)文法、有限自動機 知識點：詞法分析器的作用、地位 記號、模式 詞法分析器的狀態(tài)轉(zhuǎn)換圖 Wensheng Li BUPT 2022 2/78 詞法分析 簡介 詞法分析程序與語法