編譯原理：第二章高級語言及其語法描述.ppt

編譯原理 第二章高級語言及其語法描述 第二章高級語言及其語法描述 常用的高級語言FORTRAN數(shù)值計算COBOL事務處理PASCAL結構程序設計ADA大型程序 嵌入式實時系統(tǒng)PROLOG邏輯程序設計ALGOL算法語言C C 系統(tǒng)程序設計JavaInternet程序設計 與機器語言或匯編語言比較 高級語言的優(yōu)點 較接近于數(shù)學語言和工程語言 比較直觀 自然和易于理解 便于驗證其正確性 易于改錯 編寫效率高 易于移植 2 1程序語言的定義 程序語言是一個記號系統(tǒng)程序語言由兩方面定義 語法語義語用 一 語法 程序本質(zhì)上是一定字符集上的字符串 語法 一組規(guī)則 用它可以形成和產(chǎn)生一個合式 well formed 的程序 形式上正確的程序 語法 詞法規(guī)則 單詞符號的形成規(guī)則 單詞符號是語言中具有獨立意義的最基本結構 一般包括 常數(shù) 標識符 基本字 算符 界符等 描述工具 有限自動機語法規(guī)則 語法單位的形成規(guī)則 規(guī)定了如何從單詞符號形成語法單位 語法單位通常包括 表達式 語句 分程序 過程 函數(shù) 程序等 描述工具 上下文無關文法 E iE E EE E EE E 語法規(guī)則和詞法規(guī)則定義了程序的的形式結構 是判斷輸入字符串是否構成一個形式上正確的程序的依據(jù) 定義語法單位的意義屬于語義問題 二 語義 對于語言來說 不僅要給出它的詞法 語法規(guī)則 而且要定義它的單詞符號和語法符號的意義 離開了語義的語言只是一堆符號的集合 各種語言中有形式上完全相同的語法單位 含義卻不相同 語義 對某種語言 定義一組規(guī)則 用它可以定義一個程序的意義 稱為語義規(guī)則 描述方法 自然語言描述 隱藏錯誤 二義性和不完整性形式描述 操作語義 PL 1 指稱語義 ADA 代數(shù)語義 PASCAL 目前大多數(shù)編譯程序使用基于屬性文法的語法制導翻譯方法來分析語義 三 程序語言的基本功能和層次結構 程序語言的基本功能 描述數(shù)據(jù)和對數(shù)據(jù)的運算 所謂程序 本質(zhì)上說是描述一定數(shù)據(jù)的處理過程 程序的層次結構 程序 子程序或分程序 過程 函數(shù) 語句 表達式 數(shù)據(jù)引用算符函數(shù)調(diào)用 程序語言每個組成成分的邏輯和實現(xiàn)意義 抽象的邏輯的意義數(shù)學意義計算機實現(xiàn)的意義具體實現(xiàn) 2 2高級語言的一般特性 自學 高級語言的分類強制式語言 ImperativeLanguge 也稱過程式語言 命令驅(qū)動 面向語句FORTRAN C Pascal Ada應用式語言 ApplicativeLanguage 注重程序所表示的功能 而不是一個語句接一個語句地執(zhí)行LISP ML 基于規(guī)則的語言 Rule basedLanguage 檢查一定的條件 當它滿足值 則執(zhí)行適當?shù)膭幼鱌rolog面向?qū)ο笳Z言 Object OrientedLanguage 封裝性 繼承性和多態(tài)性Smalltalk C Java 2 2 1高級語言的分類 FORTRAN一個程序由一個主程序段和若干輔程序段組成 輔程序段可以是子程序 函數(shù)段或數(shù)據(jù)塊 每個程序段有一系列的說明語句和執(zhí)行語句組成 各段可以獨立編譯 模塊結構 沒有嵌套和遞歸各程序段中的名字相互獨立 同一個標識符在不同的程序段中代表不同的名字 2 2 2程序結構 主程序PROGRAM end輔程序1SUBROUTINE end輔程序2FUNCTION end PASCALPASCAL程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程 過程可以嵌套和遞歸 一個PASCAL過程 過程頭 說明段 由一系列的說明語句組成 begin執(zhí)行體 由一系列的執(zhí)行語句組成 end 作用域 一個名字能被使用的區(qū)域范圍稱作這個名字的作用域 允許同一個標識符在不同的過程中代表不同的名字 名字作用域規(guī)則 最近嵌套原則 一個在子程序B1中說明的名字X只在B1中有效 局部于B1 如果B2是B1的一個內(nèi)層子程序且B2中對標識符X沒有新的說明 則原來的名字X在B2中仍然有效 如果B2對X重新作了說明 那么 B2對X的任何引用都是指重新說明過的這個X programmainvarA B real procedureP1varB boolean begin endprocedureP2varA integer begin endbegin end A real B real B bool A integer PASCAL提供了豐富的數(shù)據(jù)類型和運算方式 它允許用戶動態(tài)地申請和退還存貯空間 ADA程序包 package 把數(shù)據(jù)和操作代碼封裝在一起 支持數(shù)據(jù)抽象 一個程序包分為兩部分 可見的規(guī)范說明部分 它定義了程序包外面可以訪問的對象 程序包體 它實際定義程序包的實現(xiàn)細節(jié) packageSTACKSistypeELEMisprivate typeSTACKislimitedprivate procedurepush S inoutSTACK E inELEM procedurepop S inoutSTACK E outELEM endSTACK packagebodySTACKSisprocedurepush S inoutSTACK E inELEM begin 實現(xiàn)細節(jié)endpush procedurepop S inoutSTACK E outELEM begin 實現(xiàn)細節(jié)endpop end JAVAJava是一種面向?qū)ο蟮母呒壵Z言類 Class 繼承 Inheritance 多態(tài)性 Polymorphism 和動態(tài)綁定 Dynamicbinding classCar intcolor number intdoor number intspeed push break add oil classTrash Carextendscar doubleamount fill trash 2 2 3數(shù)據(jù)類型與操作 一個數(shù)據(jù)類型通常包括以下三種要素 用于區(qū)別這種類型數(shù)據(jù)對象的屬性這種類型的數(shù)據(jù)對象可以具有的值可以作用于這種類型的數(shù)據(jù)對象的操作 一 初等數(shù)據(jù)類型數(shù)值類型 整型 實型 復數(shù) 雙精度 運算 等邏輯類型 布爾運算 字符類型 符號處理指針類型 標識符與名字 標識符 以字母開頭的 由字母數(shù)字組成的字符串 標識符與名字兩者有本質(zhì)區(qū)別 標識符是語法概念名字有確切的意義和屬性 Jordan 標識符 標識符與名字 名字 值 單元中的內(nèi)容屬性 類型和作用域名字的性質(zhì)的說明方式 由說明語句來明確規(guī)定的隱含說明 FORTRAN以I J K N為首的名字代表整型 否則為實型 動態(tài)確定 走到哪里 是什么 算什么 二數(shù)據(jù)結構 1數(shù)組邏輯上 數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結構 沿著每一維的距離 稱為下標 數(shù)組可變與不可變 編譯時能否確定其存貯空間的大小 訪問 給出數(shù)組名和下標值存放方式 按行存放 按列存放 數(shù)組元素地址計算 數(shù)組A 10 20 的A 1 1 為a 各維下標為1 按行存放 那么A i j 地址為 a i 1 20 j 1 數(shù)組元素地址計算公式 內(nèi)情向量 把數(shù)組的有關信息記錄在一個 內(nèi)情向量 中 每個數(shù)組的內(nèi)情向量必須包括 維數(shù) 各維的上 下限 首地址 以及數(shù)組 元素 的類型 2記錄 邏輯上說 記錄結構由已知類型的數(shù)據(jù)組合在一起的一種結構 record charNAME 20 integerAGE boolMARRIED CARD 1000 訪問 復合名CARD k NAME存儲 連續(xù)存放域的地址計算 相對于記錄結構起點的相對數(shù)OFFSET 3字符串 表格 棧 字符串 符號處理 公式處理表格 本質(zhì)上是一種記錄結構線性表 一組順序化的記錄結構棧 一種線性表 后進先出 POP PUSH 三抽象數(shù)據(jù)類型 一個抽象數(shù)據(jù)類型包括 數(shù)據(jù)對象的一個集合 作用于這些數(shù)據(jù)對象的抽象運算的集合 這種類型對象的封裝 即 除了使用類型中所定義的運算外 用戶不能對這些對象進行操作 程序設計語言對抽象數(shù)據(jù)類型的支持Ada語言通過程序包 package 提供了數(shù)據(jù)封裝的支持Smalltalk C 和Java語言則通過類 Class 對抽象數(shù)據(jù)類型提供支持 2 2 4語句與控制結構 一 表達式表達式由運算量 也稱操作數(shù) 即數(shù)據(jù)引用或函數(shù)調(diào)用 和算符 操作符 組成 形式 中綴 前綴 后綴X Y AP 表達式形成規(guī)則 算符的優(yōu)先次序 一般的規(guī)定PASCAL 左結合A B C A B CFORTRAN 對于滿足左 右結合的算符可任取一種 如A B C就可以處理成 A B C 也可以處理成A B C 注意兩點 代數(shù)性質(zhì)能引用到什么程度視具體的語言不同而不同 在數(shù)學上成立的代數(shù)性質(zhì)在計算機上未必完全成立 二 語句 賦值語句 A B名字左值 該名字代表的那個單元 地址 稱為該名字的左值 所代表的存貯單元的地址 右值 一個名字的值稱為該名字的右值 所代表的存貯單元的內(nèi)容 控制語句 無條件轉(zhuǎn)移語句gotoL 條件語句ifBthenSifBthenS1elseS2 循環(huán)語句whileBdoSrepeatSuntilBfori E1stepE2untilE3doS 過程調(diào)用語句callP X1 X2 Xn 返回語句return E 說明語句 定義各種不同數(shù)據(jù)類型的變量或運算 定義名字的性質(zhì) 簡單句和復合句 簡單句 不包含其他語句成分的基本句復合句 句中有句的語句 復習 程序語言的定義 程序語言由兩方面定義 語法 一組規(guī)則 用它可以形成和產(chǎn)生一個合式 well formed 的程序詞法規(guī)則 單詞符號的形成規(guī)則 常數(shù) 標識符 基本字 算符 界符等 有限自動機語法規(guī)則 語法單位的形成規(guī)則 表達式 語句 分程序 過程 函數(shù) 程序等 上下文無關文法語義 一組規(guī)則 用它可以定義一個程序的意義 復習 程序語言的基本功能和層次結構 程序語言的基本功能 描述數(shù)據(jù)和對數(shù)據(jù)的運算 所謂程序 本質(zhì)上說是描述一定數(shù)據(jù)的處理過程 程序 子程序或分程序 過程 函數(shù) 語句 表達式 數(shù)據(jù)引用算符函數(shù)調(diào)用 復習 高級語言的一般特性 高級語言的分類程序結構數(shù)據(jù)類型與操作初等數(shù)據(jù)類型數(shù)據(jù)結構抽象數(shù)據(jù)類型語句與控制結構 2 3程序語言的語法描述 幾個概念 考慮一個有窮字母表 字符集其中每一個元素稱為一個字符 符號 是語言中最基本的不可再分的單位 上的字 也叫字符串 符號串 是指由 中的字符所構成的一個有窮序列不包含任何字符的序列稱為空字 空串 記為 用 表示 上的所有字的全體 包含空字 例如 設 a b 則 a b aa ab ba bb aaa 的子集U和V的連接 積 定義為UV U V 設 U a aa V b bb 那么 UV ab abb aab aabb 的子集U和V的連接 積 定義為UV U記V VV 稱V 是V的正規(guī)閉包 設 U a aa 那么 U a aa aaa aaaa U a aa aaa aaaa 2 3 1上下文無關文法 文法 描述語言的語法結構的形式規(guī)則Hegavemeabook He me book a gave He me book a gave He He Hegave Hegave Hegaveme Hegaveme Hegavemea Hegavemeabook 上下文無關文法的定義 一個上下文無關文法G是一個四元式G VT VN S P 其中VT 終結符集合 非空 VN 非終結符集合 非空 且VT VN S 文法的開始符號 S VNP 產(chǎn)生式集合 有限 每個產(chǎn)生式形式為P P VN VT VN 開始符S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次 例 定義只含 的算術表達式的文法G 其中 P由下列產(chǎn)生式組成 E iE E EE E EE E 幾點規(guī)定 也可以用 表示 這種表示稱為巴科斯范式 BNF P 1P 2可縮寫為P 1 2 n P n其中 讀成 或 稱為P的一個候選式 表示一個文法時 通常只給出開始符號和產(chǎn)生式 如上例 可表示為 G E E i E E E E E 例 定義只含 的算術表達式的文法G 其中 P由下列產(chǎn)生式組成 E iE E EE E EE E 定義 稱 A 直接推出 即 A 僅當A 是一個產(chǎn)生式 且 VT VN 如果 1 2 n 則我們稱這個序列是從 1到 n的一個推導 若存在一個從 1到 n的推導 則稱 1可以推導出 n 對文法G E E i E E E E E E E E E i E i i 通常 用表示 從 1出發(fā) 經(jīng)過一步或若干步 可以推出 n 用表示 從 1出發(fā) 經(jīng)過0步或若干步 可以推出 n 所以 即或 定義 假定G是一個文法 S是它的開始符號 如果 則 稱是一個句型 僅含終結符號的句型是一個句子 文法G所產(chǎn)生的句子的全體是一個語言 將它記為L G 例 i i i 是文法G E E i E E E E E 的一個句子 證明 E E E E E E E i E E i i E i i i E E E E E i i i 是句型 例 文法G1 A A c AbG1 A 的語言 L G1 c cb cbb 以c開頭 后繼若干個b 例 文法G2 S S ABA aA aB bB bG2 S 的語言 L G2 ambn m n 0 例 給出產(chǎn)生語言為 anbn n 1 的文法 G3 S S aSbS ab 例 給出產(chǎn)生語言為 ambn 1 n m 2n 的文法 G4 S S aSb aaSbS ab aab 從一個句型到另一個句型的推導往往不唯一 E E i E i iE E E i i i最左推導 任何一步 都是對 中的最左非終結符進行替換 最右推導 任何一步 都是對 中的最右非終結符進行替換 2 3 2語法樹與二義性 用一張圖表示一個句型的推導 稱為語法樹 i i i 的語法樹 E E E E E E E i E E i i E i i i E E E E E i E E i E i i i i i 一棵語法樹是不同推導過程的共性抽象 G E E i E E E E E i i i 如果使用最左 右 推導 則一個最左 右 推導與語法樹一一對應 一個句型是否只對應唯一一棵語法樹 定義 如果一個文法存在某個句子對應兩顆不同的語法樹 則說這個文法是二義的 G E E i E E E E E 是二義文法 語言的二義性 一個語言是二義性的 如果對它不存在無二義性的文法 可能存在G和G 一個為二義的 一個為無二義的 但L G L G 二義性問題是不可判定問題 即不存在一個算法 它能在有限步驟內(nèi) 確切地判定一個文法是否是二義的 可以找到一組無二義文法的充分條件 二義文法 G E E i E E E E E 表達式 項 表達式 項項 因子 項 因子因子 表達式 i 無二義文法 G E E T E TT F T FF E i E T F E E T T T T F T F F T i F T i