【正文】 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。連接符“ ? ”一般可省略不寫(xiě)。|(|)| …… 其中 l表示 a~z中的任何一個(gè)英文字母， d表示 0~9中 的任何一個(gè)數(shù)字 13 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 ： ?無(wú)符號(hào)數(shù) d余留無(wú)符號(hào)數(shù) |.十進(jìn)小數(shù) e指數(shù)部分 ?余留無(wú)符號(hào)數(shù) d余留無(wú)符號(hào)數(shù) |.十進(jìn)小數(shù) e指數(shù) 部分 | ? ?十進(jìn)小數(shù) d余留十進(jìn)小數(shù) ?余留十進(jìn)小數(shù) e指數(shù)部分 | d余留十進(jìn)小數(shù) |? ?指數(shù)部分 d余留整指數(shù) |s整指數(shù) ?整指數(shù) d余留整指數(shù) ?余留整指數(shù) d余留整指數(shù) |? 其中， s表示正或負(fù)號(hào) (+,) 14 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .正規(guī)式 ?正規(guī)表達(dá)式（ regular expression）是說(shuō)明單詞的 pattern的一種重要的表示法（記號(hào)），是定義正規(guī)集 的工具 15 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?定義（正規(guī)式和它所表示的正規(guī)集）： ?設(shè)字母表為 ?，輔助字母表 ?`={?， ?， ?， ?， ?， ?， ?} ??和 ?都是 ?上的正規(guī)式，它們所表示的正規(guī)集分別為 {?}和 { } ?任何 a? ?， a是 ?上的一個(gè)正規(guī)式，它所表示的正規(guī)集 為 {a} 16 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?假定 e1和 e2都是 ?上的正規(guī)式，它們所表示的正規(guī)集分別 為 L(e1)和 L(e2)，那么， (e1), e1? e2, e1?e2, e1?也都是正規(guī) 式 ,它們所表示的正規(guī)集分別為 L(e1), L(e1)?L(e2), L(e1)L(e2)和 (L(e1))? ?僅由有限詞使用上述三步驟而定義的表達(dá)式才是 ?上的 正規(guī)式，僅由這些正規(guī)式所表示的字集才是 ?上的正規(guī) 集 17 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?其中的“ ?”讀為“或”（也有使用“ +”代替 “ ?” 的 ）；“ ? ”讀為“連接”；“ ?”讀為“閉包”（即，任 意有限次的自重復(fù)連接）。 ? ） 11 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 三 .將詞法分析工作分離的考慮 、清晰和條理化： ： ： 12 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 167。 詞法分析程序每得到一次調(diào)用，便從源程序文件中讀 入一些字符，直到識(shí)別出一個(gè)單詞，或說(shuō)直到下一單 詞的第一個(gè)字符為止 7 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 二 .詞法分析程序的輸出 ： ?基本字（關(guān)鍵字）： begin、 end、 if、 while、 var ?標(biāo)識(shí)符：常量名、變量名、過(guò)程名 ?常數(shù)（量）： 2 、 true、“ ABC” ?運(yùn)算符：＋、－、 *、＜ = ?界符：逗點(diǎn)、分號(hào)、括號(hào) 8 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ： ?（單詞種別，單詞自身的值） ?單詞種別：語(yǔ)法分析需要的信息 ?單詞自身的值：編譯其他階段需要的信息 9 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?（標(biāo)識(shí)符，指向該標(biāo)識(shí)符所在符號(hào)表中位置的指針） ?單詞的種別可以用整數(shù)編碼表示，假如標(biāo)識(shí)符編碼為 1 ，常數(shù)為 2，關(guān)鍵字為 3，運(yùn)算符為 4，界符為 5 10 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?if i=5 then x:=y ?關(guān)鍵字 if (3, ? if?) ?標(biāo)識(shí)符 i （ 1，指向 i的符號(hào)表入口） ?等號(hào) ＝ （ 4, ?= ?） ?常數(shù) 5 （ 2, ?5? ） ?關(guān)鍵字 then （ 3, ?then ? ） ?標(biāo)識(shí)符 x （ 4,指向 x的符號(hào)表入口） ?賦值號(hào) := （ 4, ?： = ? ） ?標(biāo)識(shí)符 y （ 1, 指向 y的符號(hào)表入口 ） ?分號(hào) 。1 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第四章 詞法分析 ?第一節(jié) 詞法分析程序的設(shè)計(jì) ?第二節(jié) 單詞的描述工具 ?第三節(jié) 有窮自動(dòng)機(jī) ?第四節(jié) 正規(guī)式和有窮自動(dòng)機(jī)的等價(jià)性 ?第五節(jié) 正規(guī)文法和有窮自動(dòng)機(jī)的等價(jià)性 ?第六節(jié) 詞法分析程序的自動(dòng)構(gòu)造工具 ?第七節(jié) 典型例題及解答 2 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 知識(shí)結(jié)構(gòu) 3 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 詞法分析 自動(dòng)構(gòu)造工具 {正規(guī)集 } 正規(guī)式 有窮自動(dòng)機(jī)（ NFA DFA) 正規(guī)文法 知識(shí)結(jié)構(gòu) ① ⑤ ⑥ ② ③ ④ 4 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 第四章 詞法分析 167。 詞法分析程序的設(shè)計(jì) 源程序 詞法分析程序 語(yǔ)法分析程序 Token get token …. ?主要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào) ?其他任務(wù)： ?濾掉空格，跳過(guò)注釋、換行符 ?追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序， ?宏展開(kāi)， …… 5 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 一 .詞法分析程序不語(yǔ)法分析程序的接口方式 ?詞法分析工作可以是獨(dú)立的一遍，把字符流的源程序 變?yōu)?單詞序列 ，輸出在一個(gè) 中間文件 上，這個(gè)文件作 為語(yǔ)法分析程序的 輸入 而繼續(xù)編譯過(guò)程 6 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?更通常情況，常將詞法分析程序設(shè)計(jì)成一個(gè) 子程序 ， 每當(dāng)語(yǔ)法分析程序需要一個(gè)單詞時(shí)，則調(diào)用該子程序。 （ 5, ?。 單詞的描述工具 一 .正規(guī)文法 ?程序設(shè)計(jì)語(yǔ)言中的幾類單詞可用下述規(guī)則描述： ?標(biāo)識(shí)符 l|l字母數(shù)字 ?字母數(shù)字 l|d|l字母數(shù)字 |d字母數(shù)字 ?無(wú)符號(hào)整數(shù) d|d無(wú)符號(hào)整數(shù) ?運(yùn)算符 +||*|/|=|等號(hào) |等號(hào) …… ?等號(hào) = ?界符 ,|。在不致混淆時(shí)，括號(hào)可省去， 但規(guī)定算符的優(yōu)先順序?yàn)椤??”、“ ?”、 “ ?”、“ ? ”、 “ ?” 。“ ?”、“ ? ”和 “ ?” 都是左結(jié)合的 18 盛威網(wǎng)：專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站 ?例 令 ?={a， b}, ?上的正規(guī)式和相應(yīng)的正規(guī)集的例子有： –正規(guī)式 正規(guī)集 –a {a} –a?b {a,b} –ab {ab} –(a?b)(a?b) {aa,ab,ba,bb} –a ? {? ,a,a, …… 任意個(gè) a的串 } –(a?b)? {? ,a,b,aa,ab …… 所有由 a和 b組成 的串 } –(a?b)?(aa?bb)(a?b)? {??上所有含有兩個(gè)相繼的 a或兩個(gè) 相繼