編譯原理課件匯總.ppt

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