編譯原理課件匯總.ppt

編譯原理 主講 閆健恩Email yanjianen 寫在課程之前 木桶原理 一個木桶由許多塊木板組成 如果組成木桶的這些木板長短不一 那么這個木桶的最大容量不取決于長的木板 而取決于最短的那塊木板 蝴蝶效應 1963年12月 洛倫茲 Lorenz 在華盛頓的美國科學促進會的一次講演中提出 一只蝴蝶在巴西扇動翅膀 有可能會在美國的德克薩斯引起一場龍卷風 他的演講和結論給人們留下了極其深刻的印象 馬太效應 馬太福音 第二十五章由這么幾句話 凡有的 還要加給他叫他多余 沒有的 連他所有的也要奪過來 1968年 美國科學史研究者羅伯特 莫頓 RobertK Merton 提出這個術語用以概括一種社會心理現(xiàn)象 相對于那些不知名的研究者 聲名顯赫的科學家通常得到更多的聲望即使他們的成就是相似的 同樣地 在同一個項目上 聲譽通常給予那些已經出名的研究者 例如 一個獎項幾乎總是授予最資深的研究者 即使所有工作都是一個研究生完成的 學時與參考教材 學時 44 16學時參考教材 1 AlfredAhoect 編譯原理 趙建華等譯 機械工業(yè)出版社 2009 10 2 KennethC Louden 編譯原理及實踐 馮博琴等譯 機械工業(yè)出版社 2001 2 3 金成植 編譯程序構造原理和實現(xiàn)技術 高等教育出版社 2000 7 4 陳火旺等 程序設計語言編譯原理 國防工業(yè)出版社 2003 8 印刷 學時與參考教材 5 何炎祥等 編譯原理 華中理工大學出版社 2000 10 6 蔣立源 編譯原理 西北工業(yè)大學出版社 2000 7 7 肖軍模 程序設計語言編譯方法 大連理工大學出版社 2000 88 蔣宗禮等 形式語言與自動機理論 清華大學出版社 2003 1 主要內容 編譯系統(tǒng)及其設計概述 總體結構 設計方法 語言與文法 文法 推導 歸約 分類 分析樹 詞法分析 詞法分析 正規(guī)式與正規(guī)文法 DFA的狀態(tài)轉移圖 語法分析 自頂向下 LL 1 遞歸子程序 自底向上 LR 語義分析 屬性文法 各種語句的語法制導翻譯 運行環(huán)境 存儲分配 過程調用 符號表管理 代碼優(yōu)化 基本塊的優(yōu)化 循環(huán)優(yōu)化等 代碼生成 目標機器模型 基本塊和流圖 寄存器分配 基本塊的DAG表示 從DAG生成目標代碼 教學目的 編譯原理 是一門非常好的課程 AlfredV Aho 編寫編譯器的原理和技術具有十分普遍的意義 以至于在每個計算機科學家的研究生涯中 本書中的原理和技術都會反復用到涉及的是一個比較適當?shù)某橄髮用嫔系臄?shù)據(jù)變換 既抽象 又實際 一些具體的表示和變換算法 自頂向下的方法 和 自底向上的方法 系統(tǒng)設計方法 思想 方法 實現(xiàn)全方位討論 一個相當規(guī)模的系統(tǒng)的設計 含總體結構 計算機專業(yè)最為恰當 有效的知識載體之一 教學要求 掌握編譯程序總體結構在系統(tǒng)級上認識算法 系統(tǒng)的設計具有把握系統(tǒng)的能力學習有關的原理 實現(xiàn)方法和技術 了解計算學科的基本方法 思想掌握典型方法 在每一個計算機科技工作者的職業(yè)生涯中 這些原理和技術都被反復用到 兼顧語言的描述方法 設計 應用 形式化能形式化就能自動化進一步培養(yǎng) 計算機思維能力 軟件系統(tǒng)的非物理性質 學習成果 以學生為中心 理解和掌握編譯過程各個階段的工作原理理解標準編譯器各個組成部分的任務熟悉編譯過程各階段所要解決的問題及其采用的方法和技術應用一些標準的技術解決編譯器構造過程中所產生的相關問題理解編譯器在生成代碼時如何充分利用特定處理器的特征 第1章引論 1 1計算機語言的發(fā)展1 2翻譯系統(tǒng)1 3編譯系統(tǒng)的功能分析1 4編譯程序總體結構1 5編譯程序的生成1 6編譯技術的應用 1 1計算機語言的發(fā)展 機器語言 MachineLanguage 與匯編語言 AssembleLanguage 0 1代碼與助記符 更接近于計算機硬件指令系統(tǒng)的工作高級語言 HighLevelLanguage 其表示方法更接近于待解問題的表示方法定義數(shù)據(jù) 描述運算 控制流程 傳輸數(shù)據(jù)如 C FORTRAN PASCAL C JAVA SQL 數(shù)據(jù)定義 數(shù)據(jù)操作 命令語言 CommandLanguage 控制系統(tǒng)的工作 以功能封裝為特征如UNIX上的shell 1 2翻譯系統(tǒng) 翻譯程序 Translator 將某一種語言描述的程序 源程序 SourceProgram 翻譯成等價的另一種語言描述的程序 目標程序 ObjectProgram 的程序 翻譯程序 源程序 目標程序 C PAS OBJ EXE 1 2翻譯系統(tǒng) 解釋程序 Interpreter 口譯與筆譯 單句提交與整篇提交 源程序 輸入數(shù)據(jù) 計算結果 解釋程序 1 2翻譯系統(tǒng) 編譯程序 Compiler 高級語言程序 匯編 機器語言程序 源程序 目標程序 編譯程序 1 2編譯系統(tǒng) SPCompilerS SourceO ObjectOPP ProgramInputRSRS RunSys Output 編譯系統(tǒng) CompilingSystem 編譯系統(tǒng) 編譯程序 運行系統(tǒng) 支撐環(huán)境 運行庫等 1 2翻譯系統(tǒng) 其它 診斷編譯程序 DiagnosticCompiler 優(yōu)化編譯程序 OptimizingCompiler 交叉編譯程序 CrossCompiler 可變目標編譯程序 RetargetableCompiler 并行編譯程序 ParallelizingCompiler 匯編程序 Assembler 交叉匯編程序 CrossAssembler 反匯編程序 Disassembler 1 2翻譯系統(tǒng) 匯總 MLMLPAssemblerDisassemblerALALPTranslatorCompilerDataHLHLPInterpreterResult M MachineL LangugeP ProgramA AssembleH HighLevel 1 3編譯系統(tǒng)的功能分析 程序分析詞法 語法 語義分析綜合語句的翻譯 代碼生成標識符處理 左值與右值的綁定 binding 變量 存儲單元函數(shù) 目標代碼序列 1 4編譯程序總體結構 目標代碼生成器 代碼優(yōu)化器 語義分析與中間代碼生成器 語法分析器 1 詞法分析 例 main printf hello 結果IDNmain IDNprintf STRhello 1 詞法分析 詞法分析由詞法分析器完成 LexicalAnalyzer 詞法分析器又叫做掃描器 Scanner 詞法分析器從左到右掃描源程序 發(fā)現(xiàn)一個字符串 則將該字符串轉換成單詞 記號 Token 串 同時要 查詞法錯誤 進行標識符登記 符號表管理 輸入 字符串輸出 種別碼 屬性值 序對屬性值 token的機內表示 2 語法分析 語法分析由語法分析器 SyntaxAnalyzer 完成 語法分析器又叫Parser 功能 Parser實現(xiàn) 組詞成句 將詞組成各類語法成分 表達式 因子 項 語句 子程序 構造分析樹指出語法錯誤指導翻譯輸入 Token序列輸出 語法成分 2 語法分析 res fact term1 term2 賦值語句 表達式 fact 表達式 res 表達式 表達式 表達式 表達式 term1 term2 3 語義分析 功能 分析由語法分析器識別出的語法單位的語義獲取標識符的屬性 類型 作用域等語義檢查 運算的合法性 取值范圍等子程序的靜態(tài)綁定 代碼的相對地址變量的靜態(tài)綁定 數(shù)據(jù)的相對地址 4 中間代碼生成 中間代碼 intermediateCode 例 id1 id2 id3 后綴表示 逆波蘭Anti PolishNotation id1id2id3 前綴表示 波蘭PolishNotation id1 id2id3 四元式表示 三地址碼 1 id1 id2 T1 2 id3 T1 T2 三元式表示1 id2 id3 2 id1 1 4 中間代碼生成 中間代碼的特點簡單規(guī)范與機器無關易于優(yōu)化與轉換 三地址碼的另一種表示形式T1 id2 id3T2 id1 T1 其它類型的語句例 printf hello x s 賦值 paramx 參數(shù) callf 函數(shù)調用 注釋s是hello的地址f是函數(shù)printf的地址 對中間代碼的優(yōu)化處理 對代碼進行等價變換以求提高執(zhí)行效率 提高運行速度和節(jié)省存儲空間與機器無關的優(yōu)化與機器有關的優(yōu)化 5 代碼優(yōu)化 與機器無關的優(yōu)化 局部優(yōu)化常量合并 常數(shù)運算在編譯期間完成 如8 9 4公共子表達式的提取 基本塊內循環(huán)優(yōu)化強度削減用較快的操作代替較慢的操作代碼外提將循環(huán)不變計算移出循環(huán) 與機器有關的優(yōu)化 寄存器的利用將常用量放入寄存器 以減少訪問內存的次數(shù)體系結構MIMD SIMD SPMD 向量機 流水機存儲策略根據(jù)算法訪存的要求安排 Cache 并行存儲體系 減少訪問沖突任務劃分按運行的算法及體系結構 劃分子任務 MPMD 6 目標代碼生成 CodeGenerator 將中間代碼轉換成目標機上的機器指令代碼或匯編代碼確定源語言的各種語法成分的目標代碼結構 機器指令組 匯編語句組 制定從中間代碼到目標代碼的翻譯策略或算法目標代碼的形式具有絕對地址的機器指令匯編語言形式的目標程序模塊結構的機器指令 需要鏈接程序 7 表格管理 管理各種符號表 常數(shù) 標號 變量 過程 結構 查 填 登記 查找 源程序中出現(xiàn)的符號和編譯程序生成的符號 為編譯的各個階段提供信息 輔助語法檢查 語義檢查完成靜態(tài)綁定 管理編譯過程Hash表 鏈表等各種查 填表技術 8 錯誤處理 進行各種錯誤的檢查 報告 糾正 以及相應的續(xù)編譯處理 如 錯誤的定位與局部化 詞法 拼寫 語法 語句結構 表達式結構 語義 類型不匹配 編譯系統(tǒng) 模塊分類 分析 詞法分析 語法分析 語義分析 中間代碼生成綜合 代碼優(yōu)化 目標代碼生成輔助 符號表管理 出錯處理8項功能對應8個模塊 例一個語句的翻譯 9編譯的遍 Pass 根據(jù)系統(tǒng)資源的狀況 運行目標的要求 等 可以將一個編譯程序設計成多遍掃描的形式 在每一遍掃描中 完成不同的任務 如 首遍構造語法樹 二遍處理中間表示 增加信息等 遍可以和階段相對應 也可無關單遍代碼不太有效 10 編譯的前端與后端 前端與源語言有關 與目標機無關的部分詞法分析 語法分析 語義分析與中間代碼生成 與機器無關的代碼優(yōu)化后端與目標機有關的部分與機器有關的代碼優(yōu)化 目標代碼生成 1 5編譯程序的生成 設計目標目標程序小 執(zhí)行速度快 編譯程序小 執(zhí)行速度快 診斷能力強 可靠性強 可移植性 可擴充性 如何實現(xiàn)編譯器 直接用可運行的代碼編制 太費力 自舉 使用語言提供的功能來編譯該語言自身 第一個編譯器是怎樣被編譯的 問題 直接在一個機上實現(xiàn)C語言編譯器 還有別的技術么 解決 用匯編語言實現(xiàn)一個 子集的編譯程序 P0 人 用匯編程序處理該程序 得到 P2 可直接運行 用 子集編制 語言的編譯程序 P3 人 用P2編譯P3 得到P4 1 編譯程序的自展技術 2 利用編譯程序自動生成器 詞法分析器的自動生成程序 詞法規(guī)則說明 詞法分析程序 C程序 輸入 詞法 正規(guī)表達式 識別動作 程序段 輸出 yylex 函數(shù) 語法分析器的自動生成程序 語法規(guī)則說明 語法分析程序 C程序 輸入 語法規(guī)則 產生式 語義動作 程序段 輸出 yyparse 函數(shù) 1 6編譯技術的應用 把復雜數(shù)據(jù)看作一條語句數(shù)據(jù)格式的分析利用詞法分析 語法分析方法數(shù)據(jù)處理的框架基于語法制導的語義處理框架編譯技術可以用于各種復雜數(shù)據(jù)的分析處理 1 6編譯技術的應用 語法制導的結構化編輯器程序格式化工具軟件測試工具程序理解工具高級語言的翻譯工具 例1 1 DOS命令date的輸出格式例 9 2 1993 09 03 1993 9 03 93語法date month day year詞法month DIGITDIGIT DIGITday DIGITDIGIT DIGITyear DIGITDIGIT DIGIIDIGITDIGITDIGIT 例1 1 續(xù) 語義year 年 month 月 day 日 語義約束條件0 month value 130 day value 32 31 300 year value 10000 小結 計算機語言的發(fā)展翻譯系統(tǒng)及其功能編譯的總體結構編譯的各個階段編譯的生成及應用相關概念 習題 1 試分析一個簡短的C程序 找出幾個屬于語法 詞法 語義的語言現(xiàn)象 2 試分析例1 1的date輸出數(shù)據(jù)的處理中 應該做哪些詞法分析 語法分析 語義處理 高級語言及其文法 2 1語言概述2 2基本定義2 3文法 Grammar 的定義2 4CFG的分析樹 ParseTree 2 5文法的分類2 6文法的構造 本章主要內容 2 1語言概述 什么是語言 2 1語言概述 語言特征自然語言 NaturalLanguage 是人與人的通訊工具語義 semantics 環(huán)境 背景知識 語氣 二義性 難以形式化計算機語言 ComputerLanguage 計算機系統(tǒng)間 人機間通訊工具嚴格的語法 Grammar 語義 semantics 易于形式化 嚴格 2 1語言概述 語言的描述方法 現(xiàn)狀自然語言 自然 方便 非形式化數(shù)學語言 符號 嚴格 準確 形式化形式化描述高度的抽象 嚴格的理論基礎和方便的計算機表示 2 1語言概述 語言 形式化的內容提取語言 Language 滿足一定條件的句子集合句子 Sentence 滿足一定規(guī)則的單詞序列單詞 Token 滿足一定規(guī)則的字符 Character 串語言是字和組合字的規(guī)則例 自然語言 第譯始一天課今開編上節(jié) 今天開始上第一節(jié)編譯課 2 1語言概述 程序設計語言 形式化的內容提取程序設計語言 ProgrammingLanguage 組成程序的所有語句的集合 程序 Program 滿足語法規(guī)則的語句序列 語句 Sentence 滿足語法規(guī)則的單詞序列 單詞 Token 滿足詞法規(guī)則的字符串 例 變量 表達式if條件then語句while條件do語句call過程名 參數(shù)表 2 1語言概述 描述形式 文法語法 語句語句的組成規(guī)則描述方法 BNF范式 語法 描述 圖詞法 單詞單詞的組成規(guī)則描述方法 BNF范式 正規(guī)式 形式語言于自動機理論的產生與作用 語言學家Chomsky最初從產生語言的角度研究語言 1956年 通過抽象 他將語言形式地定義為是由一個字母表中的字母組成的一些串的集合 可以在字母表上按照一定的規(guī)則定義一個文法 Grammar 該文法所能產生的所有句子組成的集合就是該文法產生的語言 克林 Kleene 在1951年到1956年間 從識別語言的角度研究語言 給出了語言的另一種描述 克林是在研究神經細胞中 建立了自動機 他用這種自動機來識別語言 對于按照一定的規(guī)則構造的任一個自動機 該自動機就定義了一個語言 這個語言由該自動機所能識別的所有句子組成 形式語言于自動機理論的產生與作用 1959年 Chomsky通過深入研究 將他本人的研究成果與克林的研究成果結合了起來 不僅確定了文法和自動機分別從生成和識別的角度去表達語言 而且證明了文法與自動機的等價性 20世紀50年代 人們用巴科斯范式 BackusNourForm或BackusNormalForm 簡記為BNF 成功地對高級語言ALGOL 60進行了描述 實際上 巴科斯范式就是上下文無關文法 ContextFreeGrammar 的一種表示形式 這一成功 使得形式語言在20世紀60年代得到了大力的發(fā)展 形式語言于自動機理論的產生與作用 形式語言與自動機理論除了在計算機科學領域中的直接應用外 更在計算學科人才的計算思維的培養(yǎng)中占有極其重要的地位計算思維能力的培養(yǎng) 主要是由基礎理論系列課程實現(xiàn)的 該系列主要由從數(shù)學分析開始到形式語言結束的一些數(shù)學和抽象程度比較高的內容的課程組成 它們構成的是一個梯級訓練系統(tǒng) 在此系統(tǒng)中 連續(xù)數(shù)學 離散數(shù)學 計算模型等三部分內容要按階段分開 三個階段對應與本學科的學生在大學學習期間的思維方式和能力的變化與提高過程的三個步驟 計算思維能力的培養(yǎng)過程 中學數(shù)學數(shù)學分析離散數(shù)學具體 靜止變量 運動離散 抽象形式 模型 基本運算系統(tǒng) 計算系統(tǒng) 實數(shù)抽象集合單一 具體的計算一般 形式化的計算 實例計算 模型化計算 高水平計算專業(yè)人才的計算思維能力的漸進培養(yǎng) 2 2基本定義 字母表 Alphabet 是一個非空有窮集合 字母表中的元素稱為該字母表的一個字母 Letter 也叫字符 Character 例以下是不同的字母表 a b c d a b c z 0 1 4 ASCII字母表 2 2基本定義 符號串的定義由字母表中的符號所組成的任何有窮序列被稱之為該字母表上的符號串 也稱作 字 1 是 上的一個符號串 2 若x是 上的符號串 而a是 的元素 則xa是 上的符號串 3 y是 上的符號串 當且僅當它由 1 和 2 導出 2 2基本定義 設s是符號串 則s的前綴 移走s的尾部的零個或多于零個符號后綴 刪去s的頭部的零個或多于零個符號子串 從s中刪去一個前綴和一個后綴子序列 從s中刪去零或多于零個符號 這些符號不要求連續(xù) 逆轉 將S中的符號按相反次序寫出而得到的符號串長度 是該符號串中的符號的數(shù)目 例如 aab 3 0 2 2基本定義 符號串的連接和方冪1 連接 設x和y是符號串 它們的連接xy是把y的符號寫在x的符號之后得到的符號串 例如 x ba y nana xy banana 2 方冪 x0 x1 x x2 xx xn xn 1x 例如 設x ba 則x1 ba x2 baba x3 bababa 2 2基本定義 定義1設 1 2是兩個字母表 1與 2的乘積 Product 定義為 1 2 ab a 1 b 2 例 1 0 1 2 a b 1 2 0a 0b 1a 1b 定義2設 是一個字母表 的n次冪 Power 遞歸地定義為 0 n n 1 n 1例 13 000 001 010 011 100 101 110 111 2 2基本定義 定義3設 是一個字母表 的正閉包 PositiveClosure 定義為 2 3 4 的克林閉包 KleeneClosure 為 0 0 2 3 2 2基本定義 例 0 1 0 1 00 01 11 000 001 010 011 100 0 1 0 1 00 01 11 000 001 010 011 100 2 2基本定義 定義5設 是一個字母表 L L稱為字母表 上的一個語言 Language x L x叫做L的一個句子 例 字母表 0 1 上的語言 0 1 00 11 0 1 00 11 0 1 00 11 01 10 00 11 01 10 2 3文法的定義 如何實現(xiàn)語言結構的形式化描述 考慮一個句子 文法要素的提取 分析 Thegreywolfwilleatthegoat 句子 主語 謂語 1 主語 冠詞 形容詞 名詞 2 冠詞 the 3 形容詞 grey 4 謂語 動詞 直接賓語 5 動詞 助動詞 動詞原形 6 助動詞 will 7 動詞原形 eat 8 直接賓語 冠詞 名詞 9 名詞 wolf 10 名詞 goat 11 句子的組成規(guī)則 問題 如何用符號來描述 即如何形式化 終結符號集VT the grey wolf will eat goat 非終結符號集VN 句子 主語 謂語 冠詞 形容詞 名詞 動詞 直接賓語 助動詞 動詞原形 語法規(guī)則集P 句子 主語 謂語 開始符號S 句子 定義句子的規(guī)則的語法組成 終結符號集 非終結符號集 語法規(guī)則 開始符號 問題 有了定義句子的規(guī)則 如何判定某一句子是否屬于某語言 句子 主語 謂語 冠詞 形容詞 名詞 謂語 the 形容詞 名詞 謂語 thegrey 名詞 謂語 thegreywolf 謂語 thegreywolf 動詞 直接賓語 thegreywolfwilleatthegoat 句子的派生 推導 從產生語言的角度句子的歸約 從識別語言的角度 均根據(jù)規(guī)則 句子 thegreywolfwilleatthegoatthegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthegrey符合語法且符合語義的句子僅是 thegreywolfwilleatthegoat 句子的語義要求 文法G的形式定義 文法G為一個四元組 T N T 終結符 Terminal 集 N 非終結符 Variable 集 T N 語法成分 代表某個語言的各種子結構 開始符號 StartSymbol S N代表文法所定義的語言 至少在產生式左側出現(xiàn)一次 文法G的形式定義 產生式 Product 集合 被稱為產生式 定義式 讀作 定義為 其中 T N 且 中至少有 N中元素的一個出現(xiàn) T N 稱為產生式 的左部 LeftPart 稱為產生式 的右部 RightPart 產生式定義各個語法成分的結構 組成規(guī)則 例2 1算術表達式的文法 遞歸定義 中綴表示標識符 id 常數(shù) 變量 是表達式 E 表達式加一個表達式是表達式 表達式減一個表達式是表達式 表達式乘一個表達式是表達式 表達式除一個表達式是表達式 表達式加上括號后是表達式 例2 1算術表達式的文法 考慮簡單算術表達式組成的語言G id E P E P E E EE E EE E E id約定 只寫產生式簡寫E E E E E E id 2 1 產生式的簡寫 對一組有相同左部的產生式 1 2 n可以簡單地記為 1 2 n讀作 定義為或者 1 或者 2 或者 n 并且稱它們?yōu)?產生式 1 2 n稱為候選式 Candidate 基于產生式的變換 推導或歸約 E E E E E E idE由第一個候選式可以變成E EE E中的第一個E由第二個候選式可以變成E E 從而E E變成E E E根據(jù)第4個候選式 E E E中的E都可以變成id E E E變成id E Eid E E變成id E idid E id變成id id id也就是說 根據(jù)第4個候選式 E E E經3步變換變成id id id 直接推導與歸約 根據(jù)產生式對符號串進行變換的過程 是文法 的一個產生式 且 T N 稱 直接推導 派生 Derive 出 也稱 直接歸約 Reduce 為 記為 例 id E id E E 多步 推導 0 1 2 n記為 0 n n 恰用n步 0 n 至少一步 0 n 若干步 零步或多步 推導 歸約舉例 E E E 1 串中含有變量 id E 4 串中含有變量 id E E 2 串中含有變量 id id E 4 串中含有變量 id id id 4 串中沒有變量到此串中已經沒有 語法 變量了 不能再推導了 1 E E E2 E E E3 E E 4 E id 句型與句子 E 5id id id句子 如果S x 且x T 則稱x是G產生的一個句子 Sentence E E E E E EE 4id id E句型 如果S T N 則稱 是G產生的一個句型 SententialForm 文法G產生的語言 x xandx T 文法E E E E E E id可以派生出多少個句子 文法G的作用 語言的有窮描述以有限的規(guī)則描述無限的語言現(xiàn)象有限 產生式集合 終結符集合 非終結符集合無限 可以導出無窮多個句子 L也可是有窮 id id id的不同推導E E E E E E id E E E id E id E E id id E id id id E E E E E E E E id E id id id id id E E E E E E E id E id id E id id id 不做限制句型 sententialForm 歸約 E id id id 施于最右變量右句型 規(guī)范句型 canonical 最左 規(guī)范歸約 E id id id 施于最左變量左句型 left 最右歸約 E 5id id id 最左推導與最右推導 最左推導 Left mostDerivation 每次推導都施加在句型的最左邊的語法變量上 與最右歸約對應最右推導 Right mostDerivation 每次推導都施加在句型的最右邊的語法變量上 與最左歸約 規(guī)范規(guī)約 對應的規(guī)范 Canonical 句型 例2 2標識符的文法1 S L LTT L N TL TNL a b c dletterN 0 1 2 3 4 5digit問題 正整數(shù)的文法 正實數(shù)的文法 2 文法的分類 Chomsky體系 根據(jù)語言結構的復雜程度 形式語言 涉及文法的復雜程度 分析方法的選擇反映文法描述語言的能力如果G滿足文法定義的要求 則 是 型文法 短語結構文法PSG PhraseStructureGrammar L G 為PSL 上下文有關文法 CSG 若產生式集合中所有 除 外 則 是 型文法即 上下文有關文法 CSG ContextSensitiveGrammar L G 為1型 上下文有關 敏感語言 CSL 上下文無關文法 CFG 若 N N T 則 是 型文法即 上下文無關文法 CFG ContextFreeGrammar L G 為2型 上下文無關語言 CFL CFG能描述程序設計語言的多數(shù)語法成分 例2 3標識符的文法2 S L LTT L N TL TNL a b c dN 0 1 2 3 4 5 S a b c dS aT bT cT dTT a b c d 0 1 2 3 4 5T aT bT cT dT 0T 1T 2T 3T 4T 5T 正規(guī)文法 RG 設 N T或為 右線性 RightLinear 文法 或 左線性 LeftLinear 文法 或 都是 型文法 正規(guī)文法RegularGrammar RG L G 為3型 正規(guī)集 正則集 正則語言 RL 能描述程序設計語言的多數(shù)單詞左 右線性文法不可混用 例非CFL的文法 L anbncn n 0 的文法S aBC aSBCCB BCaB abbB bbbC bc 可以證明 不存在CFGG 使L G L 在我們使用的程序設計語言中 有些語言結構不能用上下文無關文法來描述 例2 4L1 wcw w a b 例 aabcaab就是L1的一個句子 這個語言是檢查程序中標識符的聲明應先于引用的抽象 例2 5L2 anbmcndm n m 0 它是檢查過程聲明的形參個數(shù)和過程引用的參數(shù)個數(shù)是否一致問題的抽象 非上下文無關的語言結構 Chomsky體系 總結 T N 是一個文法 P G是0型文法 L G 是0型語言 其能力相當于圖靈機 G是1型文法 L G 是1型語言 除 其識別系統(tǒng)是線性界限自動機 N G是2型文法 L G 是2型語言 其識別系統(tǒng)是不確定的下推自動機 A aB或A a G是右線性文法 L G 是3型語言A Ba或A G是左線性文法 L G 是3型語言 其識別系統(tǒng)是有窮自動機 文法的類型 四種文法之間的關系是將產生式作進一步限制而定義的 四種文法之間的逐級 包含 關系如下 范式 Backus NaurFormBackus NormalForm 表示為 非終結符用 括起來終結符 基本符號集其他 1 2 n 1 2 n 范式 BackusNormalForm 例簡單算術表達式 只寫產生式 id即 id哪些是終結符 哪些是變量 例2 6句子結構的表示 文法E E E E E E id E E E id E id E E id id E id id id 一棵樹 2 5CFG的分析樹 ParseTree用樹的形式表示句型的生成樹根 開始符號中間結點 非終結符葉結點 終結符或者非終結符每個推導對應一個中間結點及其兒子 一個二級子樹 直接短語又稱為語法分析樹 E E T T T F T a1 T a1 T F a1 F F a1 a2 F E T T T T F F T a1 a1 T a1 T F a1 T F a1 F F F a1 F F a1 a2 a1 a2 F a2 F a1 a2 a3 a2 a3a1 a2 a3 E E T T F a1 T F F a2 a3 a1 a2 a3 短語 二義性文法與先天二義性語言 對同一句子存在兩棵語法分析樹在理論上不可判定 1 描述一個句子的文法不是唯一的 2 對于一個句子的分析應是唯一的 考慮表達式下面的文法G E 其產生式如下 E E E E E E a對于句子a a a 有如下兩個最左推導 E E E a E a E E a a E a a aE E E E E E a E E a a E a a a 文法的二義性 E E E a E a E E a a E a a a E E E E E E a E E a a E a a a E E E E E a a a E E E E E a a a 最左推導 E E E E E E E E a E a a a a a E E E E a E E a E a a a a a E E E E E a a a E E E E E a a a 最右推導 如果一個文法的句子存在兩棵分析樹 那么 該句子是二義性的 如果一個文法包含二義性的句子 則稱這個文法是二義性的 否則 該文法是無二義性的 幾點說明 1 一般來說 程序語言存在無二義性文法 對于表達式來說 文法 2 1 是二義性的 對于條件語句 經常使用二義性文法描述它 S ifexprthenS ifexprthenSelseS other二義性的句子 ife1thenife2thens1elses2 二義性 歧義性 ambiquity 的定義 下面是S matched s unmatched smatched s ifexprthenmatched selsematched s otherunmatched s ifexprthenS ifexprthenmatched selseunmatched s它顯然比較復雜 因此 2 在能駕馭的情況下 使用二義性文法 描述if語句的無二義性文法的產生式 3 對于任意一個上下文無關文法 不存在一個算法 判定它是無二義性的 但能給出一組充分條件 滿足這組充分條件的文法是無二義性的 4 存在先天二義性語言 例如 aibicj i j 1 aibjcj i j 1 存在一個二義性的句子akbkck 抽象 語法樹與分析樹不同 2 6文法的構造 明確描述對象 語言合法的語言結構確定基本符號集 T引入非終結符各種語法成分的結構定義句子的組成規(guī)則BNF范式或產生式 文法舉例 x x是長度為偶數(shù)的0 1串 S 00S 01S 10S 11S 0m1n m n 1 RLS 0S 0AA 1A 1 0n1n n 1 CFLS 0S1 01 ww w a b PSLS aCAE bCBEAa aAAb bAAE aRERE DaR RabR RbCR aCA bCBBa aBBb bBBE bREaR RabR RbCR aCA bCBaD DabD DbED 值得注意的問題 文法描述描述句子的組成規(guī)則 不涉及語義文法正確不能保證語義正確 例 明確目標要描述語言的結構確認基本符號集合理引入非終結符 語義明確 本章小結 幾個基本概念文法是語言的一種有窮描述 它嚴格 準確 簡潔 文法的形式定義句型 句子 語言文法的分類 的分析樹 詞法分析 第三章詞法分析 詞法分析器 Scanner 的功能正則表達式狀態(tài)轉換圖詞法分析器的設計與實現(xiàn)有窮自動機FA 3 1詞法分析 掃描 器的功能 功能 輸入源程序 輸出單詞符號 token 即 把構成源程序的字符串轉換成單詞符號的序列單詞符號的形式按照最小的語義單位設計通常表示為二元組 單詞種別 屬性值 關鍵 找出符號的分割符 1 單詞符號的表示 常用單詞種別 分類 肖軍模P53 杜P46 各關鍵字 保留字 基本字 各種運算符 各種分界符 各用一個種別碼標識標識符 用一個種別碼標識整 實 字符常數(shù) 各用一個種別碼標識屬性 值 單詞的值常數(shù)的值 標識符的名字等保留字 運算符 分界符的屬性值可以省略 例3 1 單詞符號序列while pointer 0 pointer while WHILE SLP FETCH pointer IDN 符號表入口指針 RELOP NE 0 CONST 0 SRP LP pointer IDN 符號表入口指針 INC SEMI RP 跟實現(xiàn)有關 2 相關問題 超前掃描雙字符運算符 DO90k 1 10DO90k 1 10預處理問題剔除源程序中的無用符號 空格 換行 注釋等掃描器的運行方式作為獨立的遍 簡單 但需增加額外的開銷作為獨立的子程序 節(jié)省內存 掃描器作為獨立的子程序 2 相關問題 符號表的查填兼顧問題兼顧 token自身值作為符號表的入口Token串長度統(tǒng)一 可放寬對標識符的限制 但要增加額外負擔不兼顧 token自身值就是標識符 常數(shù)本身的符號串速度快 但要限制標識符的長度 2 相關問題 錯誤處理行 列計數(shù)發(fā)現(xiàn)并定位詞法錯誤處理方法恐慌模式刪除剩余輸入中的一個字符向剩余輸入插入一個字符字符替換等 3 符號表的作用 符號表是一張表格 由編譯程序建立 存在于內存或磁盤中 用于存儲程序編譯或運行過程中所使用的變量 標識符 和常量 數(shù)字常數(shù) 字符常數(shù) 等信息 詞法分析階段 建立符號表 查填符號表 將不重復的標識符 數(shù)字常數(shù)和字符常數(shù)的性質填入符號表中 如 名字 類型 數(shù)值等 并且將變量 或常數(shù) 在符號表中的入口地址寫到其自身的TOKEN字中 語法分析階段 主要是使用符號表 在分析過程中 需要用到某個標識符 或常數(shù) 時 就從符號表的指定入口處查找出該符號 語義分析及中間代碼生成階段 主要是查填符號表 在生成四元式時 通常不使用變量的名字 而是使用它們在符號表中的入口位置 另外 在翻譯說明語句時 要向符號表中填入變量的類型信息等 符號表的作用 2 數(shù)據(jù)存儲分配 將變量 或常數(shù) 所使用的數(shù)據(jù)區(qū)映像地址寫入符號表中的地址 ADDR 欄 若數(shù)據(jù)區(qū)是動態(tài)數(shù)據(jù) 則在符號表中存儲過程層號和位移量等信息 待運行時再計算具體地址 代碼優(yōu)化階段 使用符號表 一方面 遇到變量時 要到符號表中查找它的具體信息 另一方面 在優(yōu)化過程中 也有可能要使用符號表 例如在進行合并已知量的優(yōu)化時 要檢查變量是否有常數(shù)值 這時要使用符號表的數(shù)值 VAL 欄進行判斷 目標代碼生成階段 在此過程中主要是查找符號表 為最終生成目標代碼提供必要的信息 如建立DAG節(jié)點標記時使用符號表暫存變量的引用活躍信息 4 符號表的內容 符號表中包括名字 NAME 類型 TYPE 種屬 KIND 數(shù)值 VAL 和地址 ADDR 等欄 還帶有一個字符串表 其中名字欄包括兩個子欄 一個用于存放標識符在字符串表中的起始位置 另一個存放該標識符的長度 類型欄表示該標識符的類型 整 實 布爾和字符型四者之一 種屬欄表示該標識符屬于哪一種類的名字 簡單變量 常數(shù)名 數(shù)組名 過程名等 數(shù)值欄存放常數(shù)標識符的值 地址欄存放分配給該符號的地址 5 一種符號表的數(shù)據(jù)結構 6 輸入緩沖 每次移動向前指針都需要做兩次測試 雙緩沖區(qū)問題 超前掃描導致的效率問題 如何設計和實現(xiàn)掃描器 大小問題128Byte 2 1024Byte 2 4096Byte 2 ifforward在緩沖區(qū)第一部分末尾thenbegin重裝緩沖區(qū)第二部分 forward forward 1endelseifforward在緩沖區(qū)第二部分末尾thenbegin重裝緩沖區(qū)第一部分 將forward移到緩沖區(qū)第一部分開始endelseforward forward 1 forward forward 1 ifforward eofthenbeginifforward在第一部分末尾thenbegin重裝第二部分 forward forward 1endelseifforward在第二部分末尾thenbegin重裝第一部分 將forward移到第一部分開始endelse eof在表示輸入結束 終止詞法分析end 6 輸入緩沖 1 3 2詞法單元的識別 詞法分析器要求能夠檢查輸入字符串 在前綴中找出和某個模式匹配的詞素 通過正則定義來描述各種詞法單元的模式 1 正則表達式 RE 設 是一個字母表 是 上的RE L 是 上的RE L 對于 a a是RE L a a 如果r和s是RE L r R L s S 則 r與s的 和 r s 是RE L r s R S r與s的 乘積 rs 是RE L rs RS r的克林閉包 r 是RE L r R 只有滿足 的才是RE 2 正則定義的例子 C語言標識符的正則定義letter A B Z a b z digit 0 1 9id letter letter digit id對應的正則表達式為 A B Z a b z A B Z a b z 0 1 9 3 正則表達式的擴展 基本運算符 并 連接 Kleen閉包擴展的運算符 一個或多個實例 單目后綴 r 等價于rr 零個或一個實例 r 等價于 r字符類 a1a2 an 等價于a1 a2 an a e 等價于a b c d e用來使得正則表達式更加簡潔 但是不會使得正則表達式能夠描述更多的語言 4 運算的優(yōu)先級 運算優(yōu)先級和結合性 高于 連接 和 連接 高于 具有交換律 結合律 連接 具有結合律 和對 的分配律 指定優(yōu)先關系意義清楚時 括號可以省略例 L a a b a b a b a a b a b a b 5 狀態(tài)轉換圖 狀態(tài)轉換圖是詞法分析器的重要組件之一狀態(tài)轉換圖 transitiondiagram 狀態(tài) state 表示了可能在識別詞素的過程中可能出現(xiàn)的情況狀態(tài)看作是已處理部分的總結 某些狀態(tài)為接受狀態(tài)或最終狀態(tài) 表明已經找到詞素 加上 的接受狀態(tài)表示最后讀入的符號不在詞素中 開始狀態(tài) 初始狀態(tài) 用start邊表示 邊 edge 從一個狀態(tài)指向另一個狀態(tài) 邊的標號是一個或者多個符號 如果當前符號為s 下一個輸入符號為a 就沿著從s離開 標號為a的邊到達下一個狀態(tài) 狀態(tài)轉換圖的例子 6 保留字和標識符的識別 在很多程序設計語言中 保留字也符合標識符的模式 識別標識符的狀態(tài)轉換圖也會識別保留字 解決方法在符號表中預先填寫保留字 并指明它們不是普通標識符 為關鍵字 保留字建立單獨的狀態(tài)轉換圖 并設定保留字的優(yōu)先級高于標識符 3 3詞法分析器的設計和實現(xiàn) 從轉換圖構造詞法分析器的方法變量state記錄當前狀態(tài)一個switch根據(jù)state的值轉到相應的代碼每個狀態(tài)對應于一段代碼 這段代碼根據(jù)讀入的符號 確定下一個狀態(tài)如果找不到相應的邊 則調用fail 進行錯誤恢復進入某個接受狀態(tài)時 返回相應的詞法單元 注意狀態(tài)有 標記時 需要回退forward指針 狀態(tài)轉換圖的例子 Relop對應的代碼概要 處理多個模式的方法 詞法分析器需要匹配多個模式解決方法順序地嘗試各個詞法單元對應的狀態(tài)轉換圖 如果引發(fā)fail 回退并啟動下一個狀態(tài)圖 可以根據(jù)優(yōu)先級確定嘗試順序 并行地 運行各個狀態(tài)轉換圖 通過greedy策略 識別最長的和某個模式匹配的輸入前綴預先把各個狀態(tài)轉換圖合成一個狀態(tài)轉換圖 然后運行這個狀態(tài)轉換圖 3 4有窮自動機FA 本質上和狀態(tài)轉換圖類似 分為兩類 不確定的有窮自動機 NondeterministicFiniteAutomata NFA 邊上的標號沒有限制 一個符號可出現(xiàn)在離開同一個狀態(tài)的多條邊上 可以做標號確定的有窮自動機 DeterministicFiniteAutomata DFA 對于每個狀態(tài)以及每個符號 有且只有一條邊 兩種自動機都識別正則語言 1 不確定的有窮自動機 NFA由以下幾部分組成一個有窮的狀態(tài)集合S一個輸入符號集合 inputalphabet 轉換函數(shù) transitionfunction 對于每個狀態(tài)和 U 中的符號 給出相應的后繼狀態(tài)集合一個狀態(tài)s0被指定為開始狀態(tài) 初始狀態(tài) 有些定義中可以有多個開始狀態(tài) S的一個子集被指定為接受狀態(tài) 2 NFA的例子 狀態(tài)集合S 0 1 2 3 開始狀態(tài)0接受狀態(tài)集合 3 轉換函數(shù) 0 a 0 1 0 b 0 1 b 2 2 b 3 相應的圖形表示 3 輸入字符串的接受 一個NFA接受輸入字符串x 當且僅當對應的轉換圖中存在一條從開始狀態(tài)到某個接受狀態(tài)的路徑 該路徑中各條邊上的標號組成x 標號不考慮 前面的NFA接受aabb 因為 NFA接受的語言 從開始狀態(tài)到達接受狀態(tài)的所有路徑上的標號串的集合 就是它接受的所有符號串的集合 4 確定有窮自動機 一個NFA被稱為DFA 如果沒有 之上的轉換動作對于每個狀態(tài)s和每個輸入符號 有且僅有一條標號為a的離開s的邊可以高效判斷一個串能否被一個DFA接受 每個NFA都有一個等價的DFA 即它們接受同樣的語言 5 從正則表達式到自動機的轉換 正則表達式可以簡潔 精確地描述詞法單元的模式但是在進行模式匹配時需要模擬DFA的執(zhí)行 因此 需要將正則表達式轉換為DFA步驟 正則表達式到NFANFA到DFA 6 正則表達式到NFA 基本思想根據(jù)正則表達式的遞歸定義 按照正則表達式的結構遞歸地構造出相應的NFA 算法分成兩個部分 基本規(guī)則處理 和單符號的情況對于每個正則表達式的運算 建立組合組合相應NFA的方法 轉換算法 1 基本規(guī)則部分表達式 表達式a 歸納部分s rsr 轉換算法 2 歸納部分s 轉換算法 3 7 轉換得到的NFA的特性 狀態(tài)數(shù)量最多為r中的運算符和運算符分量總數(shù)的兩倍因為每個步驟只引入兩個狀態(tài)有且只有一個開始狀態(tài)和有關接受狀態(tài)除接受狀態(tài)之外 每個狀態(tài)要么由一條標號不等于 的出邊 要么有兩條標號為 的出邊 正則表達式到NFA的例子 1 正則表達式 a b abb第一個a對應的NFA第一個b對應的NFA a b 的NFA第二個a的NFA 正則表達式到NFA的例子 2 a b 的NFA 正則表達式到NFA的例子 3 8 NFA合并的方法 合并方法 引入新的開始狀態(tài) 并引入從這個開始狀態(tài)到各個原開始狀態(tài)的 轉換 詞法分析程序的設計與實現(xiàn) 狀態(tài)轉移圖 教材P68狀態(tài)轉移圖的實現(xiàn) 教材P68 72子程序scan 輸入 字符流輸出 Symbol 單詞種別Attr 屬性 全局變量 數(shù)據(jù)結構與子例程 數(shù)據(jù)結構ch當前輸入字符token輸入緩沖區(qū) 字符數(shù)組 symbol單詞種別 子程序的返回值 attr屬性 全局變量 子例程Lookup token 將token存入符號表 返回入口指針isKeyword token 判別token是關鍵字 返回關鍵字種別或 1getchar 從輸入緩沖區(qū)中讀入一個字符放入chisLetter isalpha 狀態(tài)圖的實現(xiàn)算法 1 getchar 2 WHILEch是空格 跳過空格2 1DOgetchar 3 CASEchOF4 isdigit ch 4 1ch token getchar 4 2WHILEisdigit ch DOch token getchar 4 3輸入指針回退一個字符 4 4將token中的字符串變成數(shù)值 attr4 5返回NUM 5 isalpha ch 5 1ch token getchar 5 2WHILEisalpha ch ORisdigit ch DOch token getchar 5 3輸入指針回退一個字符 5 4key isKeyword token 5 5IFkey 0THEN返回key5 6Lookup tok