編譯原理 - 陳火旺版 - 第二章.ppt

1、1,編譯方法,中國人民大學(xué)信息學(xué)院 陳文萍,2,第二章 高級語言及其語法描述,高級程序語言:描述算法和計算機(jī)實(shí)現(xiàn) 不同的應(yīng)用側(cè)重點(diǎn)不同: 數(shù)值計算- FORTRAN 系統(tǒng)程序設(shè)計-C 事務(wù)處理-COBOL VLSI設(shè)計-VHDL 人工智能-PROLOG 大型嵌入式實(shí)時處理-Ada 符號處理-SNOBOL,3,內(nèi)容,2.1 程序語言的定義 2.2 高級語言的一般特性 2.3 程序語言的語法描述,4,2.1 程序語言的定義,程序設(shè)計語言：是由一組記號所構(gòu)成的集合。 語言的定義 語言用戶：語言的成分，使用意義 編譯程序：語言的規(guī)則，語法單位對應(yīng)的含義 組成部分 語法 （Syntax） 語義（ Sem

2、antics） 語用（ Pragmatics）,5,語法,語法 （Syntax）：程序構(gòu)成的一組規(guī)則 詞法規(guī)則：單詞符號的形成規(guī)則 單詞符號：語言中具有獨(dú)立意義的最基本的結(jié)構(gòu) 類型：常數(shù)，標(biāo)識符，基本字，算符，界符 例如：字符串 100-(8a)*0.5 100，8：整型常數(shù)；0.5：實(shí)型常數(shù)； -,=,*：算符； (,)：界符 分析工具：正規(guī)式和有限自動機(jī),6,語法,語法規(guī)則：語法單位的形成規(guī)則 語法單位：比單詞符號更大的語法結(jié)構(gòu) 例如：表達(dá)式，語句，分程序，函數(shù)，過程，程序 分析工具：上下文無關(guān)文法,7,語義,語義（ Semantics）定義程序的含義的一組規(guī)則 例如：C 語句 a = 1

3、8+b; 分析方法：基于屬性文法的語法制導(dǎo)翻譯方法 語用（ Pragmatics）程序設(shè)計技術(shù)和語言成分的使用方法,8,程序的層次結(jié)構(gòu),程序,子程序,語句,表達(dá)式,數(shù)據(jù)引用,算符,函數(shù)調(diào)用,9,2.2 高級語言的一般特性,高級高級語言的分類：按語言范型 強(qiáng)制式語言，應(yīng)用式語言，基于規(guī)則的語言，面向?qū)ο蟮恼Z言 強(qiáng)制式語言：命令驅(qū)動，面向語句。一個強(qiáng)制式語言程序由一系列的語句組成，每個語句的執(zhí)行引起若干存儲單元中的值的改變，這種語言的語法形式通常具有如下形式： 語句1； 語句2； 語句n； 例如-C, Fortran, Pascal,10,應(yīng)用式語言,注重程序所表示的功能，而不是一個語句接一個語句

4、地執(zhí)行 程序的開發(fā)過程是從前面已有的函數(shù)出發(fā)構(gòu)造出更復(fù)雜的函數(shù) 這種語言通常的語法形式是： Function n(function2(function1(data) 程序執(zhí)行：執(zhí)行一個個函數(shù)，得到數(shù)據(jù)上的變換，最終得到的結(jié)果 例如：ML，Lisp,11,基于規(guī)則的語言,程序的執(zhí)行過程：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭幼鳌?也稱邏輯程序設(shè)計語言：基本允許條件是謂詞邏輯表達(dá)式。 這類語言的語法形式通常為： 條件1 動作1 條件2 動作2 條件3 動作3 例如：Prolog,12,面向?qū)ο蟮恼Z言,主要特征：封裝性，繼承性和多態(tài)性 例如：C+, JAVA,13,程序結(jié)構(gòu),不同的語言，如 Fo

5、rtran, Pascal， Ada，Java 程序結(jié)構(gòu)不同 名字的作用域不同 例如：Pascal 的最近嵌套原則 procedure P; var x: interger ; procedure Q; var x: real ; begin x := 1.2; end; begin x := 5; end;,14,數(shù)據(jù)類型,數(shù)據(jù)類型的三要素：屬性，值，操作 屬性：包括類型和作用域 類型：決定數(shù)據(jù)可以是什么樣的值，允許的運(yùn)算，計算機(jī)內(nèi)如何表示 作用域：值的有效范圍 初等數(shù)據(jù)類型 數(shù)值數(shù)據(jù)：如整型，實(shí)型 邏輯數(shù)據(jù)：布爾型 字符數(shù)據(jù)：字符型（字符串型） 指針類型：指向另一種數(shù)據(jù)類型,15,數(shù)據(jù)類型

6、,數(shù)據(jù)結(jié)構(gòu)：從初級數(shù)據(jù)定義的復(fù)雜（高級）數(shù)據(jù) 數(shù)組 內(nèi)情向量：便于計算數(shù)據(jù)元素的地址，包括：維數(shù)，各維的上、下限，首地址，數(shù)組元素類型等。 例如： Pascal的說明 var a: array1.50 of char 是一個下標(biāo)從1至50的字符數(shù)組 記錄：由已知類型的數(shù)據(jù)組合而成 例如： Pascal 語言中 Student: record name: array 120 of char ; age: integer ; id: array 18 of char ; major: integer ; classid: integer ; end; 字符串，表格，棧，隊(duì)列 抽象數(shù)據(jù)類型：數(shù)據(jù)對象

7、，運(yùn)算，封裝,16,語句與控制結(jié)構(gòu),表達(dá)式：由操作數(shù)和算符組成 例如：x-y, -x 通常的形成規(guī)則 變量，常數(shù)是表達(dá)式 若E1,E2是表達(dá)式，是二元算符，則E1E2是表達(dá)式 若E是表達(dá)式，是一元算符，則E或 E是表達(dá)式 若E是表達(dá)式，則(E)是表達(dá)式 算符的優(yōu)先級,17,語句,分類：按功能 說明性語句：定義名字的性質(zhì) 執(zhí)行性語句：描述程序動作 賦值語句 控制語句 轉(zhuǎn)移語句：goto 條件語句：如 if then else 循環(huán) 語句：如while do 過程調(diào)用語句：如 call 返回語句： 如 return 輸入/輸出語句: 如 read, write,18,2.3 程序語言的語法描述,預(yù)

8、備知識 上下文無關(guān)文法 語法分析與二義性 形式語言概述,19,預(yù)備知識,符號：可以相互區(qū)別的記號（元素） 字母表：符號（元素）的非空有窮集合，用表示 符號串：由字母表中的符號組成的任何有窮序列 1.空符號串(沒有符號的符號串)是上的符號串 2.若x是上的符號串,a是的元素,則xa是上的符號串 3. y是上的符號串,當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。 例如， 字母表=a,b，則,a,b,aa,ab,ba,bb,aaa,aab,都是上的符號串,20,預(yù)備知識,符號串的運(yùn)算 符號串的長度：符號串中符號的個數(shù). 符號串s的長度記為|s|，的長度為0 連接：符號串x、y的連接,是把y的符號寫在x的符號之后得到

9、的符號串xy 如 x=ab,y=cd 則 xy=abcd 有a = a 方冪：符號串自身連接n次得到的符號串 an 定義為 aaaa （n個a） a1=a, a2=aa a0=,21,預(yù)備知識,符號串的集合：若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。 * ：表示上的所有符號串的全體 空集：，不含任何元素 符號串集合的運(yùn)算： 積（連接）：兩個符號串集合A和B的積定義為 AB =xy|xA且yB 例如： 集合A=ab,cde B = 0,1， 則 AB =ab1,ab0,cde0,cde1 閉包： V* = V 0 V 1 V 2 V 3 ., *稱為的閉包 V 0=

10、 ,22,預(yù)備知識,正則閉包：V+= V 1 V 2 V 3 ., V *= V + ， +稱為的正閉包。 例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,23,上下文無關(guān)文法,語言的表示 語言有窮：將句子逐一列出 語言無窮：找出語言的有窮表示，兩個途徑： 生成方式 （文法）：語言中的每個句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造。 識別方式（自動機(jī)）：用一個過程，當(dāng)輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回答“是”；若不屬于，要么能停止并回答“不是”，要么永遠(yuǎn)繼續(xù)下去,24,上下文無關(guān)文法,文法：描述語言的語法結(jié)構(gòu)

11、的形式規(guī)則。 形式數(shù)學(xué)系統(tǒng)：可由下列基本成分來刻畫：一組基本符號，一組形成規(guī)則，一組公理，一組推理規(guī)則 上下文無關(guān)文法：所定義的語法范疇完全獨(dú)立于語法范疇可能出現(xiàn)的環(huán)境。 例如：語法規(guī)則： I am a student,25,上下文無關(guān)文法,分析句子：I am a student 句子 主語 謂語 賓語 代詞 謂語 賓語 I 謂語 賓語 I 動詞 賓語 I am 賓語 I am 冠詞 名詞 I am a student 語法樹：如右圖,26,上下文無關(guān)文法,四個組成部分：四元式（VT,VN,S,P） 終結(jié)符號：VT, 不可再分的基本符號，如基本字、標(biāo)識符、常數(shù)、算符、界符等詞法符號。 非終結(jié)符

12、號：VN, 語法范疇，表示類記號，不是個體記號。 VN和VT不含公共的元素，即VN VT = , 用V表示VN VT ，稱為文法G的字母表或字匯表 開始符號：S,特殊的非終結(jié)符號，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 產(chǎn)生式：P，定義語法范疇的一種書寫規(guī)則。 形如或 =的( ，)有序?qū)?，其中是字母表V的正閉包V+中的一個符號，是V*中的一個符號。 稱為規(guī)則的左部， 稱作規(guī)則的右部。 例如：E i | E+E | E*E | (E) 候選式,27,上下文無關(guān)文法,舉例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號 習(xí)慣上只將產(chǎn)生式寫出

13、，并有如下約定： 第一條產(chǎn)生式的左部是開始符號 用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符 G可寫成GS，S是開始符號 G：SaAb Aab AaAb A GS： SaAb Aab AaAb A 縮寫形式 GS：SaAb Aab |aAb |,28,上下文無關(guān)文法,直接推出： “” 定義：是文法G的產(chǎn)生式，若有v,w滿足：v=,w= , 其中,（VTVN），則稱v直接推出到w,記作 v w 推導(dǎo)：若存在v w0 w1 . wn=w,(n0)， 則稱此序列為v到w的一個推導(dǎo)記為 ：經(jīng)過至少一步推導(dǎo) ：經(jīng)0步或若干步 推導(dǎo)每前進(jìn)一步總是引用文法中的一個產(chǎn)生

14、式 若有 則或 v=wn，或,29,上下文無關(guān)文法,句型 對文法G，若 ，則稱是文法G的句型。 句子 有文法G，若 ，且VT*，則稱是文法G的句子。例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型：S,0S1 ,00S11 ,000S111,00001111 G的句子：00001111, 01 由文法G生成的語言記為L(G),它是文法G的一切句子的集合:,30,上下文無關(guān)文法,例：文法G: SAB，AaA|a，BbB|b 從開始符號出發(fā)，可以推出如下句子： 所以， 最左推導(dǎo)：任何一步推導(dǎo)，都對右部最左非終結(jié)符進(jìn)行替換 最右推導(dǎo)：任何一步推導(dǎo)，都對

15、右部最右非終結(jié)符進(jìn)行替換,31,思考,1，文法G： S0S1， S01， L(G)？ 2，文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L(G)？,32,上下文無關(guān)文法,已知語言描述，寫出文法 例：若語言由0、1符號串組成，串中0和1的個數(shù)相同，構(gòu)造其文法G(A) A 0B|1CB 1|1A|0BBC 0|0A|1CC,33,上下文無關(guān)文法,文法G1A：ADB 與G2S：S0S1 ADE S01 EAB D0 B1 文法的等價：若L（G1）=L（G2），則稱文法G1和G2是等價的。,34,語法分析樹,語法分析樹：句

16、型推導(dǎo)的直觀方法 文法： ，推導(dǎo)（i*i+i),E i | E+E | E*E | (E),E,E,）,（,E,E,E,E,*,i,i,E,E,）,（,*,E,E,E,E,+,i,i,i,i,35,語法分析樹,給定文法G，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹（推導(dǎo)樹）。這棵樹滿足下列4個條件： 1、每個結(jié)點(diǎn)都有一個V中的符號作標(biāo)記 2、根的標(biāo)記是開始符號S 3、若一結(jié)點(diǎn)n至少有一個子孫，并且n有標(biāo)記A，則AVN 4、如果結(jié)點(diǎn)n的直接子孫，從左到右的次序是結(jié)點(diǎn)n1,n2,nk，其標(biāo)記分別為A1,A2,Ak，那么AA1A2,Ak一定是P中的一個產(chǎn)生式,36,二義性,文法的二義性：一個文法存在某

17、個句子對應(yīng)兩個不同的語法樹，或者，若一個文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的。 上例中，句型 （i*i+i） 的兩個不同的最左推導(dǎo)： 推導(dǎo)1：E （E） （E+E） （E*E+E） （i*E+E） （i*i+E） （i*i+i） 推導(dǎo)2：E （E） （ E*E） （i*E） （i*E+E） （i*i+E） （i*i+i） 消除二義性：修改文法，規(guī)定優(yōu)先順序和結(jié)合律 ET|E+T TF|T*F F(E)|i,37,上下文無關(guān)文法,對文法的限制 不含PP形式的產(chǎn)生式 每個非終結(jié)符P都必須有用 必須存在含P的句型（可到達(dá)） 且P不存在永不終結(jié)的回路（可終止）,38,形式語

18、言概述,形式語言：從語法這一側(cè)面來看語言。 分類：通過對產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類型 /wiki/Chomsky_hierarchy 0型文法（短語結(jié)構(gòu)文法）：對任一產(chǎn)生式，都有(VNVT)+， (VNVT)*。識別系統(tǒng)是圖靈機(jī)。 1型文法（上下文有關(guān)文法）：對任一產(chǎn)生式，都有|； 僅僅 S除外，但S不能出現(xiàn)在任何產(chǎn)生式右部。識別系統(tǒng)為線性有界自動機(jī)。,39,形式語言概述,2型文法（上下文無關(guān)文法）：對任一產(chǎn)生式，都有VN。識別系統(tǒng)為下推自動機(jī)。 3型文法（正規(guī)文法）：任一產(chǎn)生式的形式都為AB或A，其中AVN ，BVN ，VT *。識別系統(tǒng)為有限自動機(jī)。 右線性文法：任一產(chǎn)生式的形式都為AaB或Aa 左線性文法（正規(guī)文法）：任一產(chǎn)生式的形式都為ABa或Aa,40,文法類型,例1: 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD,41,文法類