【正文】 begin read(n)。 call rec。 end. 計算 sum = 1! + 2 ! + ... + n!, n從控制臺讀入 ? var n, m, fact, sum。 ? { 遞規(guī)計算 fact = m! } ? procedure factorial。 ? begin ? if m 0 then ? begin ? fact := fact * m。 ? m := m 1。 ? call factorial。 ? end。 ? end。 ? begin ? { 讀入 n } ? read(n)。 ? sum := 0。 ? while n 0 do ? begin ? m := n。 ? fact := 1。 ? call factorial。 ? sum := sum + fact。 ? n := n 1。 ? end。 ? { 輸出 n !} ? write(sum)。 ? end. 程序 分程序 . 內(nèi)的文字表示 語法成分（短語） 或 內(nèi)的文字表示單詞符號 程序內(nèi)的文字表示 語法成分（短語）語法圖 const ident number = , 。 var ident , 。 。 procedure ident 。 分程序 語句 分程序 PL/0語言的 EBNF表示 構(gòu)成 EBNF的元素 —（非終結(jié)符，終結(jié)符，開始符，規(guī)則） EBNF 的元符號： 用左右尖括號括起來的內(nèi)容為 非終結(jié)符 ∷ = 讀做 ‘ 定義為 ’ ∷ =的 左部由 右部 定義 → 讀做 ‘ 定義為 ’ → 的 左部由 右部 定義 | 讀做 ‘ 或 ’ 表示右部候選內(nèi)容 { } 表示花括號內(nèi)的內(nèi)容 可重復(fù) 任意次或限 定次數(shù) [ ] 表示方括號內(nèi)的內(nèi)容為 任選項 ( ) 表示圓括號內(nèi)的內(nèi)容 優(yōu)先 例：用 EBNF描述 整數(shù) 的定義 ： 整數(shù) ∷=[+| ]數(shù)字 {數(shù)字 } 數(shù)字 ∷=0|1|2|3|4|5|6|7|8|9 或 整數(shù) ∷=[+| ]非零數(shù)字 {數(shù)字 }|0 非零數(shù)字 ∷=1|2|3|4|5|6|7|8|9 數(shù)字 ∷=0| 非零數(shù)字 PL/0語言是 PASCAL語言的 子集 同 PASCAL 作用域規(guī)則（內(nèi)層 可引用包圍它的外層定義的 標(biāo)識符），上下文約束， 過程可 嵌套定義 ， 可遞歸調(diào)用 子集 ? 數(shù)據(jù)類型 ,只有整型 ? 數(shù)據(jù)結(jié)構(gòu) ,只有簡變和常數(shù) ? 數(shù)字最多為 14位 ? 標(biāo)識符的有效長度是 10 ? 語句種類 ? 過程無參，最多可 嵌套 三層 目標(biāo)代碼 類 pcode 目標(biāo)代碼 類 pcode是 一種 棧式機 的 匯編語言 。 棧式機系統(tǒng)結(jié)構(gòu) :沒有累加器和寄存器，只有存儲棧指針 所有運算都在棧頂（零地址機） 指令格式： f l a f 功能碼 l 層次差 （標(biāo)識符 引用層 減去 定義層 ） a 根據(jù)不同的指令有所區(qū)別 LIT 0 a 將常數(shù)值取到棧頂， a 為常數(shù)值 LOD l a 將變量值取到棧頂， a 為偏移量， l 為層差 STO l a 將棧頂內(nèi)容送入某變量單元中， a 為偏移量， l 為層差 CAL l a 調(diào)用過程， a 為過程地址， l 為層差 INT 0 a 在運行棧中為被調(diào)用的過程開辟 a 個單元的數(shù)據(jù)區(qū) JMP 0 a 無條件跳轉(zhuǎn)至 a 地址 JPC 0 a 條件跳轉(zhuǎn)，當(dāng)棧頂布爾值非真則跳轉(zhuǎn)至 a 地址，否則順序執(zhí)行 OPR 0 0 過程調(diào)用結(jié)束后 , 返回調(diào)用點并退棧 OPR 0 1 棧頂元素取反 OPR 0 2 次棧頂與棧 頂相加，退兩個棧元素，結(jié)果值進棧 OPR 0 3 次棧頂減去棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 4 次棧頂乘以棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 5 次棧頂除以棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 6 棧頂元素的奇偶判斷，結(jié)果值在棧頂 OPR 0 7 OPR 0 8 次棧頂與棧頂是否相等，退兩個棧元素，結(jié)果值進棧 OPR 0 9 次棧頂與棧頂是否不等，退兩個棧元素，結(jié)果值進棧 OPR 0 10 次棧頂是否小于棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 11 次棧頂是 否大于等于棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 12 次棧頂是否大于棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 13 次棧頂是否小于等于棧頂，退兩個棧元素，結(jié)果值進棧 OPR 0 14 棧頂值輸出至屏幕 OPR 0 15 屏幕輸出換行 OPR 0 16 從命令行讀入一個輸入置于棧頂 指 令 功 能 表 const a=10。 var b,c。 procedure p。 begin c:=b+a。 end。 begin read(b)。 while b0 do begin call p。 write(2*c)。 read(b)。 end end. ( 0) jmp 0 8 轉(zhuǎn)向 主程序入口 ( 1) jmp 0 2 轉(zhuǎn)向 過程 p入口 ( 2) int 0 3 過程 p入口 ,為過程 p開辟空間 ( 3) lod 1 3 取變量 b的值到棧頂 ( 4) lit 0 10 取常數(shù) 10到棧頂 ( 5) opr 0 2 次棧頂與棧頂相加 ( 6) sto 1 4 棧頂值送變量 c中 ( 7) opr 0 0 退棧并返回調(diào)用點 (16) ( 8) int 0 5 主程序入口開辟 5個?？臻g ( 9) opr 0 16 從命令行讀入值置于棧頂 (10) sto 0 3 將棧頂值存入變量 b中 (11) lod 0 3 將變量 b的值取至棧頂 (12) lit 0 0 將常數(shù)值 0進棧 (13) opr 0 9 次棧頂與棧頂是否不等 (14) jpc 0 24 等時轉(zhuǎn) (24)（ 條件不滿足轉(zhuǎn) ） (15) cal 0 2 調(diào)用過程 p (16) lit 0 2 常數(shù)值 2進棧 (17) lod 0 4 將變量 c的值取至棧頂 (18) opr 0 4 次棧頂與棧頂相乘 (2*c) (19) opr 0 14 棧頂值輸出至屏幕 (20) opr 0 15 換行 (21) opr 0 16 從命令行讀取值到棧頂 (22) sto 0 3 棧頂值送變量 b中 (23) jmp 0 11 無條件轉(zhuǎn)到循環(huán)入口 (11) (24) opr 0 0 結(jié)束退棧 PL/0編譯程序的結(jié)構(gòu) 詞法分析程序 語法語義分析程序 代碼生成程序 表格管理程序 出錯處理程序 PL/0源程序 目標(biāo)程序 PL/0編譯程序的總體設(shè)計 ? 以語法 、 語義分析 程序 為核心 詞法分析 程序和 代碼生成 程序都作為一個 過程 ，當(dāng)語法分析需要讀單詞時就調(diào)用詞法分析程序，而當(dāng)語法 、 語義分析正確，需要生成相應(yīng)的目標(biāo)代碼時，則調(diào)用代碼生成程序。 ? 表格管理 程序?qū)崿F(xiàn) 變量 ， 常量 和 過程 標(biāo)識符的 信息的登錄與查找 。 ? 出錯處理 程序，對詞法和語法 、 語義分析遇到的錯誤給出在源程序中 出錯的位置 和與 錯誤 性質(zhì)有關(guān) 的編號，并進行錯誤恢復(fù)。 第 2章 PL/0編譯程序 本章目的：以 PL/0編譯程序 為實例 ,學(xué)習(xí)編譯程序?qū)崿F(xiàn)的基本步驟和相關(guān)技術(shù) 1 PL/0編譯程序的結(jié)構(gòu) 2 PL/0編譯程序的分析工作 (詞法，語法和語義）實現(xiàn) 3 PL/0編譯程序的 錯誤處理方法 4 目標(biāo)代碼生成和 類 pcode代碼解釋器 2 PL/0編譯程序的分析工作 (詞法，語法和語義） 識別的單詞： – 保留字或關(guān)鍵字：如： BEGIN、 END、 IF、 THEN等 – 運算符 ： 如： +、 、 *、 /、： =、 、 =、 =等 – 標(biāo)識符 ： 用戶定義的變量名、常數(shù)名、過程名 – 常數(shù) ： 如： 2 100等整數(shù) – 界符 ： 如： ‘ ,’、 ‘ .’ 、 ‘ ?！?、 ‘ (’ 、 ‘ )’等 詞法分析過程 GETSYM所要完成的任務(wù)： – 從源程序讀字符（ getch) – 濾空格 – 識別 保留字 – 識別標(biāo)識符 – 拼數(shù) – 識別單字符單詞 – 拼雙字符單詞 ? 詞法分析過程 :GETSYM框圖（見教材圖 ） ? 程序（ procedure getsym） 當(dāng)識別到標(biāo)識符時先查 保留字 表 ? 保留 字 表：（ begin (* main * ) ） word[1]:=‘begin ‘； word[2]:=‘call ‘； ... word[13]:=‘write ‘； 查到時找到相應(yīng)的 內(nèi)部表示 Wsym[1]:=beginsym。 wsym[2]:=callsym； … wsym[13]:=writesym； ? 字符對應(yīng)的 單詞表： ssym[‘+’]:=plus。 ssym[‘’]:=minus。 … ssym[‘。’]:=semicolon。 ? 詞法分析如何把單詞傳遞給語法分析 type symbol=(nul,ident,number,plus,… ,varsym,procsym)； 3個 全程量 SYM:symbol。 ID:alfa。 NUM:integer。 通過三個 全程量 SYM 、 ID和 NUM 將識別出的單詞信息 傳遞 給 語法分析 程序。 – SYM：存放單詞的類別 如：有程序段落為： begin initial := 60； end 對應(yīng)單詞翻譯后變?yōu)椋? begin beginsym, initial ident, ‘:= ‘ bees, 60 number, ‘； ’ semicolon， end endsym 。 – ID： 存放用戶所定義的標(biāo)識符的值 如： initial （在SYM中放 ident，在 ID中放 initial） – NUM：存放用戶定義的數(shù) 如： 60 – （在 SYM中放 number,在 NUM中放 60） 使用狀態(tài)轉(zhuǎn)換圖實現(xiàn)詞法分析程序的設(shè)計方法 詞法分析程序的設(shè)計 使用狀態(tài)轉(zhuǎn)換圖實現(xiàn) 表示 狀態(tài) ，對應(yīng)每個狀態(tài)編一段程序，每個狀態(tài) 調(diào)用 取字符 程序，根據(jù)當(dāng)前字符 轉(zhuǎn)到不同的狀態(tài)，并做相應(yīng)操作。 表示 終態(tài) ，已 識別出一個 單詞 。 1 2 35141312109786411空格字母字母數(shù)字非字母數(shù)字數(shù)字數(shù)字非數(shù)字：= =非 = =非 =, + ( ?? PL/0編譯程序語法分析 自頂向下 的語法分析 遞歸子程序法 （ 上下文無關(guān)文法） 句型的分析 句型分析 就是 識別 一個符號串是否為某文法的 句型的 過程，或者說是某個 推導(dǎo) 的構(gòu)造過程。 對于一個給定的文法，要想判定一個符號串是否為該文法的句子，需要考察是否可以從該文法的開始符號派生出（推導(dǎo)出）此符號串。－編譯程序的語法分析工作。 分析算法分類 分析算法可分為： 自上而下分析法 ： 從文法的開始符號出發(fā) ， 尋找 與 輸入符號串 匹配 的 推導(dǎo)， 或者說，為輸入串尋找一個最左推導(dǎo)。 自下而上分析法 ： 從 輸入符號串 開始 ， 逐步進行 歸約 ，直至歸約 到 文法的 開始符號 。 語法分析－（從概念上講）建立一棵與輸入串相匹配的語法樹。 語法樹－推導(dǎo)的幾何表示 ? 句型 aabbaa的可能 推導(dǎo) 序列和語法樹 例 : G[S]: S→ aAS A→ SbA A→ SS S→ a A→ ba S a