編譯原理課件匯總.ppt

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