第2章高級(jí)語言及其語法描述

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

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

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

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

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

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.程序語言的語法描述程序語言的語法描述一、上下文無關(guān)文法一、上下文無關(guān)文法1 1、定義：、定義：文法：文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。上下文無關(guān)文法：上下文無關(guān)文法： 所定義的語法范疇（或語法單位）是所

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

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

9、句子的派生（推導(dǎo)）根據(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、上下文無關(guān)文法的形式定義、上下文無關(guān)文法的形式定義是一個(gè)四元組（是一個(gè)四元組（，），）終結(jié)符號(hào)集，非空有限集終結(jié)符號(hào)集，非空有限集非終結(jié)符號(hào)集，非空有限集非終結(jié)符號(hào)集，非空有限集 終結(jié)符號(hào)：終結(jié)符號(hào)：描述單詞符號(hào)，描述單詞符號(hào)，組成語言的基本符號(hào)，是一個(gè)組成語言的基本符號(hào)，是一個(gè) 語言的不可再分的基本符號(hào)。語言的不可再分的基本符號(hào)。 例如：基本字，標(biāo)識(shí)符，常數(shù)，算符，界符等例如：基本字，標(biāo)識(shí)符，常數(shù)，算符，界符等非終結(jié)符：非終結(jié)符：代表語法范疇，一個(gè)非終結(jié)符代表一個(gè)一定的語代表語法范疇，一個(gè)非終

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

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

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

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

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

16、言的語法描述6 6、最左右推導(dǎo)、最左右推導(dǎo)定義：任何一步定義：任何一步 都是對(duì)都是對(duì) 中的最左最右非終結(jié)符中的最左最右非終結(jié)符進(jìn)行替換的。進(jìn)行替換的。+()(+) (*+) (*+)(+)()+()(+) () () () ()最左推導(dǎo)：最左推導(dǎo)：最右推導(dǎo)：最右推導(dǎo)：22練習(xí)：GS: Sa|(T) TT,S|S分別給出下列句子的最左和最右推導(dǎo)過程： （1）（a,(a,a) （2）(a,(a,)（1）最左推導(dǎo)：S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)（2）最左推導(dǎo)：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、例題、例題例、考慮一個(gè)文法例、考慮一個(gè)文法：定義了一個(gè)什么樣的語言？定義了一個(gè)什么樣的語言？ . . . （）（） ？242. 2.程序語言的語法描述程序語言的語法描述例、考慮文法例、考慮文法：定義了一個(gè)什么樣的語言？定義了一個(gè)什么樣的語言？分析：分析：與類似與類似由由可知，其必產(chǎn)生可知，其必產(chǎn)生，且以此終結(jié)，且以此終結(jié) ？（）（），252. 2.程序語言的語法描述程序語言的語法描述例、構(gòu)造一個(gè)文法例、構(gòu)造一個(gè)文法，使（，使（ ）分析：分析：與

18、與的區(qū)別在于，的區(qū)別在于，必須使、出現(xiàn)的必須使、出現(xiàn)的次數(shù)相次數(shù)相 等等，故而、必須，故而、必須同時(shí)出現(xiàn)。同時(shí)出現(xiàn)。GG：262. 2.程序語言的語法描述程序語言的語法描述例例5 5、構(gòu)造一個(gè)文法、構(gòu)造一個(gè)文法5 5，使（，使（5 5 ）2n2n27例例6 6、構(gòu)造一個(gè)文法、構(gòu)造一個(gè)文法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，寫出產(chǎn)生，寫出產(chǎn)生 L L的文法。的文法。2. 2.程序語言的語法描述程序語言的語法描述思考思考: : 考慮文法考慮文法 D DD; D|TL

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

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