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

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