【正文】 LI Wensheng, SCST, BUPT 第 3章 詞法分析 基礎(chǔ)知識： PASCAL、 C語言、正規(guī)表達(dá)式 正規(guī)文法、有限自動(dòng)機(jī) 知識點(diǎn)：詞法分析器的作用、地位 記號、模式 詞法分析器的狀態(tài)轉(zhuǎn)換圖 Wensheng Li BUPT @ 2022 2/78 詞法分析 簡介 詞法分析程序與語法分析程序的關(guān)系 詞法分析程序的輸入與輸出 記號的描述和識別 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn) 軟件工具 LEX 小結(jié) Wensheng Li BUPT @ 2022 3/78 簡介 ? 任務(wù)：把構(gòu)成源程序的字符串轉(zhuǎn)換成語義上關(guān)聯(lián)的記號序列 ? 編譯程序是在單詞的級別上來分析和翻譯源程序，因此，詞法分析是編譯的基礎(chǔ) ? 本章內(nèi)容安排 討論用手工方式設(shè)計(jì)并實(shí)現(xiàn)詞法分析程序的方法和步驟 – 詞法分析程 序 的作用 – 詞法分析程序的地位 – 源程序的輸入與詞法分析程 序 的輸出 – 單詞符號的描述及識別 – 詞法分析程 序 的設(shè)計(jì)與實(shí)現(xiàn) 詞法分析程 序自動(dòng) 生成工具 LEX簡介 Wensheng Li BUPT @ 2022 4/78 詞法分析程序的作用 ? 源程序由單詞組成，單詞是最小的語義單位 ? 詞法分析程 序 的作用： 掃描源程序字符流 按照源語言的詞法規(guī)則識別出各類單詞符號 產(chǎn)生用于語法分析的記號序列 詞法檢查 創(chuàng)建符號表 把識別出來的標(biāo)識符插入符號表中 與用戶接口的一些任務(wù)： – 跳過源程序中的注釋和空白 – 把錯(cuò)誤信息和源程序聯(lián)系起來 Wensheng Li BUPT @ 2022 5/78 詞法分析程序與語法分析程序的關(guān)系 ? 詞法分析程序與語法分析程序之間的三種關(guān)系 – 詞法分析程序作為獨(dú)立的一遍 – 詞法分析程 序 作為語法分析程 序 的子程序 – 詞法分析程 序 與語法分析程 序 作為協(xié)同程序 ? 分離詞法分析程 序 的好處 ? 詞法分析的一些難點(diǎn) Wensheng Li BUPT @ 2022 6/78 詞法分析程序作為獨(dú)立的一遍 ? 輸出放入一個(gè)中間文件 磁盤文件 內(nèi)存文件 字符串源程序 字符 詞法分析程序 記號 記號流源程序 Wensheng Li BUPT @ 2022 7/78 詞法分析程序作為語法分析程 序 的子程序 ? 避免了中間文件 ? 省去了取送符號的工作 ? 有利于提高編譯程 序 的效率 語法 分析器 詞法 分析器 取下一記號 字符串 源程序 字符 記號 符號表 Wensheng Li BUPT @ 2022 8/78 詞法分析程序與語法分析程 序 作為協(xié)同程序 ? 協(xié)同程序： 如果兩個(gè)或兩個(gè)以上的程序，它們之間交叉地執(zhí)行，這些程序稱為協(xié)同程序。 詞法分析程序與語法分析程序在同一遍中，以生產(chǎn)者和消費(fèi)者的關(guān)系同步運(yùn)行。 P1 P2 喚醒 P2 喚醒 P1 喚醒 P2 喚醒 P1 Wensheng Li BUPT @ 2022 9/78 分離詞法分析程序的好處 ? 可以簡化設(shè)計(jì) – 詞法程 序 很容易識別并去除空格、注釋，使語法分析程 序致力于語法分析，結(jié)構(gòu)清晰，易于實(shí)現(xiàn)。 ? 可以改進(jìn)編譯程 序 的效率 – 利用專門的讀字符和處理記號的技術(shù)構(gòu)造更有效的詞法分析程 序 。 ? 可以加強(qiáng)編譯程 序 的可移植性 – 在詞法分析程 序 中處理特殊的或非標(biāo)準(zhǔn)的符號。 Wensheng Li BUPT @ 2022 10/78 詞法分析的一些難點(diǎn) ? 位置對準(zhǔn) Fortran要求某些結(jié)構(gòu)出現(xiàn)在輸入行的固定位置 ? 空白不作為分隔符 Fortran中空格是無意義的，可以隨便加入 DO 5 I = （賦值語句， DO5I是標(biāo)識符） DO 5 I = 1,25 （循環(huán)語句， DO是關(guān)鍵字） ? 關(guān)鍵字不保留 PL/I語言的關(guān)鍵字不保留 IF THEN THEN THEN=ELSE。 ELSE ELSE=THEN Wensheng Li BUPT @ 2022 11/78 詞法分析程序的輸入與輸出 一、詞法分析程 序 的實(shí)現(xiàn)方法 二、設(shè)置緩沖區(qū)的必要性 三、配對緩沖區(qū) 四、詞法分析程 序 的輸出 Wensheng Li BUPT @ 2022 12/78 一、詞法分析程序的實(shí)現(xiàn)方法 ? 利用詞法分析程 序自動(dòng) 生成器 – 從基于正規(guī)表達(dá)式的規(guī)范說明自動(dòng)生成詞法分析程 序 。 – 生成器提供用于源程序字符流讀入和緩沖的若干子程序 ? 利用傳統(tǒng)的系統(tǒng)程序設(shè)計(jì)語言來編寫 – 利用該語言所具有的輸入 /輸出能力來處理讀入操作 ? 利用匯編語言來編寫 – 直接管理源程序字符流的讀入 Wensheng Li BUPT @ 2022 13/78 二、設(shè)置緩沖區(qū)的必要性 ? 超前搜索：為了得到某一個(gè)單詞符號的確切性質(zhì)，需要超前掃描若干個(gè)字符。 例：有合法的 FORTRAN語句： DO99K=1,10 和 DO99K= 為了區(qū)別這兩個(gè)語句 ， 必須超前掃描到等號后的第一個(gè)分界符處 。 例： Pascal語言中： 、 :=、 （ * 例： C語言中： ==、 /*、 //、 ++ ? 方便實(shí)現(xiàn)讀字符和退字符操作 ， 提高詞法分析器的效率 Wensheng Li BUPT @ 2022 14/78 三、配對緩沖區(qū) ? 原因：不論緩沖器多大都不能保證單詞不被它的邊界打斷 ? 把一個(gè)緩沖器分為相同的兩半，每半各含 N個(gè)字符，一般 N=1KB或 4KB。 ? 基本方法 開始指針 向前指針 … … i f x = y t h e n j : = j + 2 。 eof … Wensheng Li BUPT @ 2022 15/78 測試指針的過程 (1) IF (向前指針在左半?yún)^(qū)的終點(diǎn) ) { 讀入字符串 ， 填充右半?yún)^(qū) 。 向前指針前移一個(gè)位置 。 } ELSE IF (向前指針在右半?yún)^(qū)的終點(diǎn) ) { 讀入字符串 ， 填充左半?yún)^(qū) 。 向前指針移到緩沖區(qū)的開始位置 。 } ELSE 向前指針前移一個(gè)位置 。 Wensheng Li BUPT @ 2022 16/78 每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器 開始指針 向前指針 … i f x = y t h eof e n j : = j + 2 。 eof eof ? 基本方法的缺點(diǎn)： 更新向前指針時(shí)要做二次測試 ? 改進(jìn)：每半?yún)^(qū)帶有結(jié)束標(biāo)記的緩沖器 更新向前指針時(shí)只要做一次測試 Wensheng Li BUPT @ 2022 17/78 測試指針的過程 (2) 向前指針前移一個(gè)位置； IF (向前指針指向 eof ) { IF (向前指針在左半?yún)^(qū)的終點(diǎn) ) { 讀入字符串 ， 填充右半?yún)^(qū) 。 向前指針前移一個(gè)位置 。 }。 ELSE IF (向前指針在右半?yún)^(qū)的終點(diǎn) ) { 讀入字符串 ， 填充左半?yún)^(qū) 。 向前指針指向緩沖區(qū)的開始位置 。 }。 ELSE 終止詞法分析 。 } Wensheng Li BUPT @ 2022 18/78 四、詞法分析程序的輸出 —— 記號 ? 記號、模式和單詞 – 記號：是指某一類單詞符號的種別編碼，如標(biāo)識符的記號為 id，數(shù)的記號為 num等。 – 模式：是指某一類單詞符號的構(gòu)詞規(guī)則，如標(biāo)識符的模式是“由字母開頭的字母數(shù)字串”。 – 單詞：是指某一類單詞符號的一個(gè)特例，如 position是標(biāo)識符。 機(jī)內(nèi)表示 外部表示 構(gòu)詞規(guī)則 ? 記號的種類 Wensheng Li BUPT @ 2022 19/78 記號的屬性 ? 詞法分析程序在識別出一個(gè)記號后，要把與之有關(guān)的信息作為它的屬性保留下來。 ? 記號影響語法分析的決策，屬性影響記號的翻譯。 ? 在詞法分析階段，對記號只能確定一種屬性 – 關(guān)鍵字