第2章高級語言及其語法描述

1、第2章 高級語言及其語法描述 2.1 2.1 程序語言的定義程序語言的定義 2.2 2.2 高級語言的一般特性（略）高級語言的一般特性（略） 2.3 2.3 程序語言的語法描述程序語言的語法描述 2.1 2.1 程序語言的定義程序語言的定義自然語言與計算機語言的區(qū)別與聯(lián)系：自然語言與計算機語言的區(qū)別與聯(lián)系： 計算機程序語言計算機程序語言一個記號系統(tǒng)，一個記號系統(tǒng)，類似于自然語言，由語法類似于自然語言，由語法+ +語義定義語義定義 自然語言自然語言（1 1）人與人的通訊工具）人與人的通訊工具 （2 2）語義：由環(huán)境、背景知識、語氣等決定）語義：由環(huán)境、背景知識、語氣等決定 二義性（常有）二義性（

2、常有）難以形式化難以形式化計算機語言計算機語言 （1 1）計算機系統(tǒng)間、人機間通訊工具）計算機系統(tǒng)間、人機間通訊工具 （2 2）具有嚴格的語法、語義）具有嚴格的語法、語義 易于形式化（嚴格）易于形式化（嚴格） 22.1 2.1 程序語言的定義程序語言的定義一、語法一、語法 一組規(guī)則，使用它可以形成和產生一個合式的程序，一組規(guī)則，使用它可以形成和產生一個合式的程序，則這組規(guī)則稱為語法則這組規(guī)則稱為語法。定義了程序的形式結構，是判斷輸入字符串是否定義了程序的形式結構，是判斷輸入字符串是否構成一個形式上（即合式）正確程序的依據(jù)。構成一個形式上（即合式）正確程序的依據(jù)。 詞法規(guī)則詞法規(guī)則單詞符號的形成

3、規(guī)則，即規(guī)定了字母表中單詞符號的形成規(guī)則，即規(guī)定了字母表中 哪樣的字符串是一個單詞符號。哪樣的字符串是一個單詞符號。 單詞符號單詞符號語言中具有獨立意義的最基本結構。語言中具有獨立意義的最基本結構。語法規(guī)則語法規(guī)則語法單位的形成規(guī)則，即規(guī)定了如何從單語法單位的形成規(guī)則，即規(guī)定了如何從單單詞符號形成更大的結構（即語法單位）。單詞符號形成更大的結構（即語法單位）。32.1 2.1 程序語言的定義程序語言的定義二、語義二、語義 1、語義規(guī)則：一組規(guī)則，使用它可以定義一個程序的意義、語義規(guī)則：一組規(guī)則，使用它可以定義一個程序的意義。離開語義，語言只不過是一堆符號的集合；在許多語言中離開語義，語言只不過

4、是一堆符號的集合；在許多語言中有著形式上完全相同的語法單位，但含義卻不盡相同。有著形式上完全相同的語法單位，但含義卻不盡相同。 、注意：、注意：闡明語義要比闡明語法難得多，現(xiàn)在還沒有一闡明語義要比闡明語法難得多，現(xiàn)在還沒有一種公認的形式系統(tǒng)，借助于它可以種公認的形式系統(tǒng)，借助于它可以自動地自動地構造構造出實用的編譯程序。出實用的編譯程序。本書本書基于屬性文法的語法制導翻譯方法基于屬性文法的語法制導翻譯方法較接近形式化較接近形式化42. 2.程序語言的語法描述程序語言的語法描述基本概念基本概念1、非空有窮字母表。非空有窮字母表。中的每個元素。中的每個元素。由由中的符號所構成的一個有窮序列。中的符

5、號所構成的一個有窮序列?？兆?，不包含任何符號的序列?？兆?，不包含任何符號的序列。上的所有符號串的全體，包括上的所有符號串的全體，包括。注：注：區(qū)分： 、 空集 ：不含任何元素的集合：符號：符號：上的符號串：上的符號串：* *：52. 2.程序語言的語法描述程序語言的語法描述、（連接）積、（連接）積：UV=| U V U、V * UV不一定等于不一定等于 VU，但但(UV)W=U(VW) Vn=VVVV0 = V*=V0 V1 V2 V3 V+=VV*n個個V的閉包V的正則閉包注：注：V V* *中的每個符號串都是由中的每個符號串都是由V V中的符號串經中的符號串經有限次連接有限次連接而成的。而

6、成的。6例：例： =a,b, U=ab,b, V=aa,bb a,b*=a,b0 a,b1 a,b2 . = ,a,b,ab,aa,bb,ba. a,b+=a,ba,b* = a,b ,a,b,ab,aa,bb,ba. = a,b,ab,aa,bb,ba.ab,b aa,bb=abaa,abbb,baa,bbbUV=*=+=72. 2.程序語言的語法描述程序語言的語法描述一、上下文無關文法一、上下文無關文法1 1、定義：、定義：文法：文法：描述語言的語法結構的形式規(guī)則（即語法規(guī)則）。描述語言的語法結構的形式規(guī)則（即語法規(guī)則）。上下文無關文法：上下文無關文法： 所定義的語法范疇（或語法單位）是所

7、定義的語法范疇（或語法單位）是完全獨立完全獨立于這種范疇可能出現(xiàn)的環(huán)境于這種范疇可能出現(xiàn)的環(huán)境的一種文法。的一種文法。描述語法規(guī)則描述語法規(guī)則例：例：英語中，一般句子是由英語中，一般句子是由主主謂謂二部分構成。二部分構成。82. 2.程序語言的語法描述程序語言的語法描述2 2、文法、文法語法的類比語法的類比分析：分析：The grey wolf will eat the goat.The grey wolf will eat the goat直接賓語直接賓語名詞名詞動詞動詞謂語謂語名詞名詞形容詞形容詞冠詞冠詞主語主語句子句子助動詞助動詞動詞原形動詞原形冠詞冠詞92. 2.程序語言的語法描述程序

8、語言的語法描述、產生句子的規(guī)則、產生句子的規(guī)則從產生語言的角度從產生語言的角度(1) (2) the grey (5) (6) (9) will eat wolf goat 102. 2.程序語言的語法描述程序語言的語法描述B B、句子的語法組成、句子的語法組成終結符號集，非終結符號集，終結符號集，非終結符號集， 語法規(guī)則，開始符號語法規(guī)則，開始符號終結符號集終結符號集 VT=the,grey,wolf,will,eat,goat非終結符號集非終結符號集 VN=, ,語法規(guī)則集語法規(guī)則集 P=,開始符號開始符號 S=112. 2.程序語言的語法描述程序語言的語法描述C C、句子的派生（推導）、

9、句子的派生（推導）根據(jù)規(guī)則根據(jù)規(guī)則 the the grey the grey wolf the grey wolf the grey wolf will eat the goat122. 2.程序語言的語法描述程序語言的語法描述D D、句子的語義要求、句子的語義要求 the grey wolf will eat the goatthe grey wolf will eat the wolfthe grey goat will eat the wolfthe grey goat will eat the goat符合語法且符合語義的句子僅是：符合語法且符合語義的句子僅是： the grey w

10、olf will eat the goat132. 2.程序語言的語法描述程序語言的語法描述3 3、上下文無關文法的形式定義、上下文無關文法的形式定義是一個四元組（是一個四元組（，），）終結符號集，非空有限集終結符號集，非空有限集非終結符號集，非空有限集非終結符號集，非空有限集 終結符號：終結符號：描述單詞符號，描述單詞符號，組成語言的基本符號，是一個組成語言的基本符號，是一個 語言的不可再分的基本符號。語言的不可再分的基本符號。 例如：基本字，標識符，常數(shù)，算符，界符等例如：基本字，標識符，常數(shù)，算符，界符等非終結符：非終結符：代表語法范疇，一個非終結符代表一個一定的語代表語法范疇，一個非終

11、結符代表一個一定的語 法概念，每個非終結符表示一定符號串的集合。法概念，每個非終結符表示一定符號串的集合。例如：算術表達式，布爾表達式，賦值句，分程序，過程等例如：算術表達式，布爾表達式，賦值句，分程序，過程等142. 2.程序語言的語法描述程序語言的語法描述開始符號，一個特殊的非終結符號開始符號，一個特殊的非終結符號產生式集合，有限集產生式集合，有限集產生式：定義語法范疇的一種書寫規(guī)則。產生式：定義語法范疇的一種書寫規(guī)則。形式：形式：A AVN, (VTVN)*注： “”: “定義為”“”： “或” 非終結符號：用大寫字母、或漢語組代表 終結符：用小寫字母a，b，c代表 符號串：用，代表至少

12、必須在某個產生至少必須在某個產生式的左部出現(xiàn)一次式的左部出現(xiàn)一次152. 2.程序語言的語法描述程序語言的語法描述例例1：上下文無關文法：Ei | EAE A+|*終結符號：非終結符號：開始符號：E，AE+，*，iGE162. 2.程序語言的語法描述程序語言的語法描述例2：算術表達式的文法標識符標識符(id)(常量、變量常量、變量)是表達式是表達式(E)；表達式加一個表達式是表達式；表達式加一個表達式是表達式； 表達式減一個表達式是表達式；表達式減一個表達式是表達式； 表達式乘一個表達式是表達式；表達式乘一個表達式是表達式；表達式除一個表達式是表達式；表達式除一個表達式是表達式；表達式加上括號

13、是表達式；表達式加上括號是表達式； Eid EE+E EE-E EE*E EE/E E(E)P: Eid|E+E|E-E|E*E|E/E|(E)172. 2.程序語言的語法描述程序語言的語法描述、文法與語言的關系、文法與語言的關系中心思想：從文法的開始符號出發(fā)，反復連續(xù)中心思想：從文法的開始符號出發(fā)，反復連續(xù) 使用產生式，對非終結符施行替換使用產生式，對非終結符施行替換 和展開。和展開。 一個上下文無關文法如何定義一個語言呢？一個上下文無關文法如何定義一個語言呢？182. 2.程序語言的語法描述程序語言的語法描述( () ) ( (+ +) ) ( (+ +) ) ( (+ +) )例：例：E

14、id | E+E | E-E | E*E | E/E | (E) (i+i)注：注：我們可以從出發(fā)，進行一系列的推導，推出種種不我們可以從出發(fā)，進行一系列的推導，推出種種不 同的算術表達式出來同的算術表達式出來該推導過程證明了（該推導過程證明了（+ +）是文法所定義的一個算術表達式。）是文法所定義的一個算術表達式。192. 2.程序語言的語法描述程序語言的語法描述“”：若若 ，則稱該序列是從，則稱該序列是從至至的一個推導（的一個推導（可推導出可推導出） ： ：+*表示表示“直接推出直接推出”，即僅推出一步。，即僅推出一步。AA ，僅當，僅當是一個產生式，是一個產生式，且且,(,() )* *

15、“推導推導”：從從出發(fā)，經過出發(fā)，經過步步或或若干步若干步，可推導出，可推導出從從出發(fā)，經出發(fā)，經一步一步或或若干步若干步，可推導出，可推導出注：符號的含義注：符號的含義202. 2.程序語言的語法描述程序語言的語法描述“句型句型”：設是一個文法，是其開始符號，設是一個文法，是其開始符號，, , ( (V VN N) )* *，則，則稱為文法稱為文法G G的一個句型。的一個句型?！熬渥泳渥印保簝H含終結符號的句型。僅含終結符號的句型?！罢Z言語言”：文法所產生的句子的全體是一個語言，記為文法所產生的句子的全體是一個語言，記為 （）（）* *+5 5、語言、語言212. 2.程序語言的語法描述程序語

16、言的語法描述6 6、最左右推導、最左右推導定義：任何一步定義：任何一步 都是對都是對 中的最左最右非終結符中的最左最右非終結符進行替換的。進行替換的。+()(+) (*+) (*+)(+)()+()(+) () () () ()最左推導：最左推導：最右推導：最右推導：22練習：GS: Sa|(T) TT,S|S分別給出下列句子的最左和最右推導過程： （1）（a,(a,a) （2）(a,(a,)（1）最左推導：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)（2）最左推導：S=(T)=(T,S)=(S,S)=(

17、a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,)232. 2.程序語言的語法描述程序語言的語法描述7 7、例題、例題例、考慮一個文法例、考慮一個文法：定義了一個什么樣的語言？定義了一個什么樣的語言？ . . . （）（） ？242. 2.程序語言的語法描述程序語言的語法描述例、考慮文法例、考慮文法：定義了一個什么樣的語言？定義了一個什么樣的語言？分析：分析：與類似與類似由由可知，其必產生可知，其必產生，且以此終結，且以此終結 ？（）（），252. 2.程序語言的語法描述程序語言的語法描述例、構造一個文法例、構造一個文法，使（，使（ ）分析：分析：與

18、與的區(qū)別在于，的區(qū)別在于，必須使、出現(xiàn)的必須使、出現(xiàn)的次數(shù)相次數(shù)相 等等，故而、必須，故而、必須同時出現(xiàn)。同時出現(xiàn)。GG：262. 2.程序語言的語法描述程序語言的語法描述例例5 5、構造一個文法、構造一個文法5 5，使（，使（5 5 ）2n2n27例例6 6、構造一個文法、構造一個文法6 6，使（，使（6 6 ）i ij j c c k k i i，j j， kk 且且a a，b b，c c 例例4 4、已知語言（、已知語言（4 4 ）n n b b，寫出產生，寫出產生 L L的文法。的文法。2. 2.程序語言的語法描述程序語言的語法描述思考思考: : 考慮文法考慮文法 D DD; D|TL

19、D; D|TL T Tint|charint|char L LL, id|idL, id|id定義了一個什么樣的語言？定義了一個什么樣的語言？282. 2.程序語言的語法描述程序語言的語法描述二、語法分析樹與二義性二、語法分析樹與二義性、語法分析樹、語法分析樹 用用樹的形式表示一個句型的推導生成樹的形式表示一個句型的推導生成，有助于理解一，有助于理解一個句子語法結構的層次。個句子語法結構的層次。樹根：開始符號樹根：開始符號中間結點：非終結符中間結點：非終結符葉結點：終結符非終結符葉結點：終結符非終結符292. 2.程序語言的語法描述程序語言的語法描述例例：（）的最左推導（）（）的最左推導（）（

20、根）（根）（）+* 次次 代代302. 2.程序語言的語法描述程序語言的語法描述 例：例：（）關于文法的另一個最左推導（）關于文法的另一個最左推導（）（）*+（）（）（* *）（）（）（+ +）（）（）（）（）結論：結論：一個句型不一定有唯一的一棵語法樹。一個句型不一定有唯一的一棵語法樹。 即即一個句型的最左右推導可能不唯一。一個句型的最左右推導可能不唯一。2. 2.程序語言的語法描述程序語言的語法描述2 2、二義文法、二義文法用若一個文法中存在某個句子，它有兩個不同的用若一個文法中存在某個句子，它有兩個不同的最左右推導，則該文法為二義文法最左右推導，則該文法為二義文法例：上述文法例：上述文法* *（）（）實質：實質：同一個句子存在兩棵語法分析樹。同一個句子存在兩棵語法分析樹。322. 2.程序語言的語法描述程序語言的語法描述例：句子例：句子+ +的最左推導過程的最左推導過程最最左左推導