【正文】 NER OUTPUT sort 字母 RECOGID 數(shù)字 RECOGDIG / HANDLCOM RECOGDEC 界符 ? RECOGSTR LOOKUP 2022/8/28計算機學(xué)院 辛明影 96 3?2 詞法分析器的手工構(gòu)造 ? 為了構(gòu)造詞法分析器，要研究構(gòu)詞法，每種詞類的結(jié)構(gòu)模式以及識別它的數(shù)學(xué)模型 ——有窮自動機。 Open 源文件 ,TOKEN文件 ,打印機文件 。 { case CH of ?字母 ’ : ?字母 ’ : call RECOGID(CH,TOKEN)。 { WORD:= ? ?。,ENTRY) TOKEN:=(標識符種別碼 ,ENTRY)}。 TOKEN=(?/?的識別碼 ,_)。*39。進入該模塊之前已掃描了一個字符 ‘ /? 輸出： ‘ /?的 TOKEN字或空 TOKEN字 。 return } 2022/8/28計算機學(xué)院 辛明影 107 LEX簡介 一 .原理 單詞的結(jié)構(gòu)用正規(guī)式描述 正規(guī)式 ? NFA ?DFA ?min DFA LEX 編譯器 LEX 源程序 二 .用 LEX建立詞法分析程序的過程 2022/8/28計算機學(xué)院 辛明影 108 C 編譯器 輸入流 單詞序列 三 .lex源程序 lex源程序由三部分組成 2022/8/28計算機學(xué)院 辛明影 109 聲明 %% 翻譯規(guī)則 %% 輔助過程 2022/8/28計算機學(xué)院 辛明影 110 聲明包括變量，符號常量和正規(guī)定義式。 2022/8/28計算機學(xué)院 辛明影 129 大多數(shù)的語法分析器都要求文法是無二義性的 消除二義性： 可以通過改寫文法來消除二義性 例： stmt→if expr then stmt |if expr then stmt else stmt |other 2022/8/28計算機學(xué)院 辛明影 130 通過例子 if E1 then if E2 then S2 else S3 很容易證明這是一個二義性文法 s if E then S else S if E then S 2022/8/28計算機學(xué)院 辛明影 131 S if E then S if E then S else S 2022/8/28計算機學(xué)院 辛明影 132 在程序設(shè)計語言中，我們常常采用?最近匹配?原則來解決這種二義性 文法改寫出為： stmt→ matched_stmt |unmatched_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then matched_stmt else unmatched_stmt | if expr then _stmt 2022/8/28計算機學(xué)院 辛明影 133 四、左遞歸 如果文法 G具有一個非終結(jié)符 A使得對 某個字符串 α存在推導(dǎo) A=A α, 例：下面是描述算術(shù)表達式的算法 S →E E→E+T|T T→T*F|F F→(E)| id 為句子 id*id+id構(gòu)造分析樹 S E + T E + T E + T ： 則稱文法 G是左遞歸的； 如果 A→A α， 則稱文法 G是直接左遞歸 的 + 2022/8/28計算機學(xué)院 辛明影 134 左遞歸會使分析進入到無限循環(huán)之中 消除簡單左遞歸的方法： 對于含有左遞歸的產(chǎn)生式 A→A α| β 可用下面的非左遞歸的產(chǎn)生式 代替： A→ β A? A? → αA?| ε 2022/8/28計算機學(xué)院 辛明影 135 例：下面是描述算術(shù)表達式的算法 E→E+T|T T→T*F|F F→(E)| id 消除 E和 T的直接左遞歸，得到： E→TE‘ E‘ → +TE‘|ε T →FT‘ F→(E)|id T‘→*FT‘| ε 2022/8/28計算機學(xué)院 辛明影 136 對于一般情況而言，若某一文法 G的產(chǎn)生式具有如下形式： 則可用如下方法消除左遞歸 : A→A α1| A α2 |…| A α m| β1| β2|…| β n A→β1A?| β2A? |…| β n A? A? → α1A?| α2A?|… | α mA? | ε 很容易證明改造前后的文法是等價的 2022/8/28計算機學(xué)院 辛明影 137 例：文法 G（ P） ： P → （ Q） |aP|a Q →Q ,P|P 試消除左遞歸 2022/8/28計算機學(xué)院 辛明影 138 消除左遞歸后，方法改為： P →（ Q） |aP｜ a Q →PＱ’ Q → ，ＰＱ’｜ ε 2022/8/28計算機學(xué)院 辛明影 139 S→Qc|c Q → Rb|b R → Sa|a S 這樣的遞歸無法用前面的方法消除 對于含有間接左遞歸的文法： =Qc =Rbc = Sabc 出現(xiàn)了左遞歸 2022/8/28計算機學(xué)院 辛明影 140 消除左遞歸的一般算法： 輸入：無循環(huán)推導(dǎo)和 ε 產(chǎn)生式的方法 G 輸出：與 G等價的無左遞歸文法 算法： 2022/8/28計算機學(xué)院 辛明影 141 A 1A 2… A n i=1 to n do begin for j=1 to i1 do begin 改寫 A i→ A j γ 規(guī)則，方法如下： 如果 A j→ δ 1| δ 2|…| δ k 則 A i→ δ 1 γ | δ 2 γ |…| δ n γ； end 消除 A i中的所有直接左遞歸 End 2所得文法 2022/8/28計算機學(xué)院 辛明影 142 S→Qc|c Q → Rb|b R → Sa|a 對如下文法消除左遞歸： R、 Q、 S ，將 R代入 Q： Q → Sab|ab|b 3. Q不存在左遞歸，將 Q代入 S S→ Sabc|abc|bc|c ，得文法： 2022/8/28計算機學(xué)院 辛明影 143 S→abcS ?| bcS?| cS? S?→abcS ?| ε Q → Rb|b R → Sa|a S→abcS ?| bcS?| cS? S?→abcS ?| ε 2022/8/28計算機學(xué)院 辛明影 144 ZA AaB|aC|Ad|Ae BbBC|f Cc 2022/8/28計算機學(xué)院 辛明影 145 五、提取左因子 為句子 if E1 then S1 else S2構(gòu)造一棵語法樹 文法： stmt→if expr then stmt |S |if expr then stmt else stmt 。 if CH=?=?then TOKEN:=(?=?的種別碼 ,_) else if CH=?? then TOKEN:=(??的種別碼 ,_) else { 列計數(shù) 1。 return } 處理注解 (HANDLECOM)。 call GETCH(CH)。*39。 if WORD 是關(guān)鍵字 then TOKEN:=(關(guān)鍵字種別碼 ,_) else { call LOOPUP(WORD,39。 write TOKEN into TOKEN文件 。 call OUTPUTR。 2022/8/28計算機學(xué)院 辛明影 102 program SCANNER。 一符一碼。 每個階段將源程序從一種表示轉(zhuǎn)換成另一種表示 源程序 詞法分析器 錯 誤 處 理 器 符 號 管 理 表 語法分析器 語義分析器 中間代碼生成器 代碼優(yōu)化器 代碼生成器 編譯的各個階段 2022/8/28計算機學(xué)院 辛明影 83 3 . 2 詞法分析器的手工構(gòu)造 ： 用 DFA 能識別 3 . 3詞法分析程序自動構(gòu)造工具 LEX簡介 3. 1 詞法分析程序的設(shè)計 ： 2022/8/28計算機學(xué)院 辛明影 84 = 8 0 。 y=y+1 輸出： 8 3 Z=z+x。 print a end 2022/8/28計算機學(xué)院 辛明影 78 傳值： a b a+b 實參 形參 x y z 2 3 P(a+b,a,a)。thunk amp。 z=z+x 2022/8/28計算機學(xué)院 辛明影 75 傳值結(jié)果： a b c 實參 形參 X—B1 B2 Y—B1 B2 Z—B1 B2 2 3 4 amp。 2 3 4 y=y+1。 執(zhí)行時，每當要對形參進行訪問時，就調(diào)用 THUNK子程序，以獲得相應(yīng)實參地址或值 4 傳名調(diào)用 對形參的訪問是發(fā)生在實參單元上的 2022/8/28計算機學(xué)院 辛明影 72 例：有程序段： procedure p(x,y,z) begin y=y+1。 y:=temp。 b= 39。goto l1。 boolean partmember。 Pascal Pascal 允許子程序嵌套定義 Program main 說明部分 Begin 可執(zhí)行部分 end Pascal的 程序結(jié)構(gòu) rogram i Begin end Procedure P1 Begin end Procedure P11 Begin end Procedure P2 Begin end 也允許并列定義 2022/8/28計算機學(xué)院 辛明影 44 關(guān)于名字的作用域的規(guī)定： 標識符 X的任意一次出現(xiàn)（除去說明語句中）都意味著對某個說明語句中說明的這個變量 X的引用 此時，說明語句同標識符 X應(yīng)共處一個最小程序 中，即： P1中說明的 X只在 P1中有效 P11是 P1的內(nèi)層子程序， P11中沒有再對 X作新的說明