高級語言及其語法描述

高級語言及其語法描述常用的高級語言

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ì)

Java Internet程序設(shè)計(jì)第2頁,共46頁，2024年2月25日，星期天與機(jī)器語言或匯編語言比較，高級語言的優(yōu)點(diǎn)：較接近于數(shù)學(xué)語言和工程語言，比較直觀、自然和易于理解;便于驗(yàn)證其正確性，易于改錯(cuò);編寫效率高;易于移植.第3頁,共46頁，2024年2月25日，星期天2.1程序語言的定義自然語言與計(jì)算機(jī)語言的區(qū)別與聯(lián)系：

計(jì)算機(jī)程序語言——一個(gè)記號系統(tǒng)，類似于自然語言，由語法+語義定義

自然語言（1）人與人的通訊工具（2）語義：由環(huán)境、背景知識、語氣等決定 二義性（常有）——難以形式化計(jì)算機(jī)語言（1）計(jì)算機(jī)系統(tǒng)間、人機(jī)間通訊工具 （2）具有嚴(yán)格的語法、語義

——易于形式化（嚴(yán)格）

第4頁,共46頁，2024年2月25日，星期天2.1程序語言的定義一、語法

一組規(guī)則，使用它可以形成和產(chǎn)生一個(gè)合式的程序，則這組規(guī)則稱為語法。定義了程序的形式結(jié)構(gòu)，是判斷輸入字符串是否構(gòu)成一個(gè)形式上（即合式）正確程序的依據(jù)。

詞法規(guī)則——單詞符號的形成規(guī)則，即規(guī)定了字母表中 哪樣的字符串是一個(gè)單詞符號。

單詞符號——語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。語法規(guī)則——語法單位的形成規(guī)則，即規(guī)定了如何從單 詞符號形成更大的結(jié)構(gòu)（即語法單位）。第5頁,共46頁，2024年2月25日，星期天2.1程序語言的定義二、語義

1、語義規(guī)則：一組規(guī)則，使用它可以定義一個(gè)程序的意義。離開語義，語言只不過是一堆符號的集合；在許多語言中有著形式上完全相同的語法單位，但含義卻不盡相同。

２、注意：闡明語義要比闡明語法難得多，現(xiàn)在還沒有一 種公認(rèn)的形式系統(tǒng)，借助于它可以自動地構(gòu)造 出實(shí)用的編譯程序。本書基于屬性文法的語法制導(dǎo)翻譯方法較接近形式化第6頁,共46頁，2024年2月25日，星期天程序語言的基本功能和層次結(jié)構(gòu)程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運(yùn)算。所謂程序，本質(zhì)上說是描述一定數(shù)據(jù)的處理過程。第7頁,共46頁，2024年2月25日，星期天程序的層次結(jié)構(gòu)程序|子程序或分程序、過程、函數(shù)|語句|表達(dá)式|數(shù)據(jù)引用算符函數(shù)調(diào)用第8頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述基本概念1、有窮字母表。∑中的每個(gè)元素。由∑中的符號所構(gòu)成的一個(gè)有窮序列。空字，不包含任何符號的序列?！粕系乃蟹柎娜w，包括ε。注：區(qū)分：ε

、｛ε｝、Ф

空集Ф

＝｛｝：不含任何元素的集合∑：符號：∑上的符號串：ε：∑*：第9頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述２、（連接）積：UV={αβ|α∈U＆β∈V} U、V?

∑*UV不一定等于

VU,

但(UV)W=U(VW)Vn=VV…V V0={ε}V*=V0∪

V1∪V2∪

V3∪

…V+=VV*n個(gè)V的閉包V的正則閉包注：V*中的每個(gè)符號串都是由V中的符號串經(jīng)有限次連接而成的。第10頁,共46頁，2024年2月25日，星期天例：

∑={a,b},U={ab,b}V={aa,bb}{a,b}*={a,b}0∪{a,b}1∪{a,b}2∪......={ε,a,b,ab,aa,bb,ba......}{a,b}+={a,b}{a,b}*={a,b}{ε,a,b,ab,aa,bb,ba......}={a,b,ab,aa,bb,ba......}{ab,b}{aa,bb}={abaa,abbb,baa,bbb}UV=∑*=∑+=第11頁,共46頁，2024年2月25日，星期天設(shè)：V＝{a,aa}那么：

V*

={,a,aa,aaa,aaaa,…}V＋

={a,aa,aaa,aaaa,…}第12頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述一、上下文無關(guān)文法1、定義：文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則（即語法規(guī)則）。上下文無關(guān)文法：所定義的語法范疇（或語法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的一種文法。描述語法規(guī)則的且獨(dú)立于環(huán)境描述語法規(guī)則例：英語中，一般句子是由主——謂二部分構(gòu)成。第13頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述2、文法——語法的類比：分析：Thegreywolfwilleatthegoat.The

greywolfwill

eat

thegoat直接賓語名詞動詞謂語名詞形容詞冠詞主語句子助動詞動詞原形冠詞第14頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述Ａ、產(chǎn)生句子的規(guī)則——從產(chǎn)生語言的角度<句子><主語><謂語>

(1)<主語><冠詞><形容詞><名詞>

(2)<冠詞>

the <形容詞>

grey<謂語><動詞><直接賓語>

(5)<動詞>

<助動詞><動詞原形> (6)<直接賓語>

<冠詞><名詞>

(9)<助動詞>

will

<動詞原形>

eat

<名詞>

wolf <名詞>

goat

第15頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述B、句子的語法組成——終結(jié)符號集，非終結(jié)符號集， 語法規(guī)則，開始符號終結(jié)符號集

VT={the,grey,wolf,will,eat,goat}非終結(jié)符號集

VN={<句子>,<主語>,<謂語>,<冠詞>,<形容詞>,<名詞>,<動詞>,<直接賓語>,<助動詞>,<動詞原形>}語法規(guī)則集

P={<句子><主語><謂語>,…}開始符號

S=<句子>第16頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述C、句子的派生（推導(dǎo)）——根據(jù)規(guī)則<句子>?<主語><謂語>

?

<冠詞><形容詞><名詞><謂語>?

the<形容詞><名詞><謂語>

?

thegrey<名詞><謂語>?

thegreywolf<謂語>?

thegreywolf<動詞><直接賓語>?

…?

thegreywolfwilleatthegoat第17頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述D、句子的語義要求<句子> thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoatwilleatthewolf

thegreygoatwilleatthegoat符合語法且符合語義的句子僅是：

thegreywolfwilleatthegoat第18頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述3、上下文無關(guān)文法Ｇ的形式定義 Ｇ是一個(gè)四元組（ＶＴ，ＶＮ，Ｓ，Ｐ）ＶＴ——終結(jié)符號集，非空有限集ＶＮ——非終結(jié)符號集，非空有限集ＶＮ∩ＶＴ＝Ф

終結(jié)符號：描述單詞符號,組成語言的基本符號，是一個(gè)語言的不可再分的基本符號。

例如：基本字，標(biāo)識符，常數(shù)，算符，界符等．

非終結(jié)符：代表語法范疇，一個(gè)非終結(jié)符代表一個(gè)一定的語法概念，每個(gè)非終結(jié)符表示一定符號串的集合。例如：算術(shù)表達(dá)式，布爾表達(dá)式，賦值句，分程序，過程等．第19頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述Ｓ——開始符號，一個(gè)特殊的非終結(jié)符號Ｐ——產(chǎn)生式集合，有限集產(chǎn)生式：定義語法范疇的一種書寫規(guī)則．形式：A

αA∈VN,α∈(VT∪VN)*注：

“

”:“定義為”

“｜”：

“或”

非終結(jié)符號:用大寫字母Ａ、Ｂ、Ｃ…或漢語組代表

終結(jié)符:用小寫字母…代表至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次第20頁,共46頁，2024年2月25日，星期天巴科斯范式（BNF：Backus-NaurForm的縮寫）描述計(jì)算機(jī)語言語法的符號集。由JohnBackus和PeterNaur首次引入一種形式化符號來描述給定語言的語法（最早用于描述ALGOL60編程語言）。JohnBackusPeterNaurBNF現(xiàn)在是定義一種計(jì)算機(jī)語言的標(biāo)準(zhǔn)方式。第21頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例1：上下文無關(guān)文法Ｇ：Ei|EAEA+|*非終結(jié)符號：開始符號：終結(jié)符號：E，AE+，*，iG[E]第22頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例2：算術(shù)表達(dá)式的文法標(biāo)識符(id)(常量、變量)是表達(dá)式(E)； 表達(dá)式加一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式減一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式乘一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式除一個(gè)表達(dá)式是表達(dá)式； 表達(dá)式加上括號是表達(dá)式；EidEE+EEE-EEE*EEE/EE(E)P:Eid|E+E|E-E|E*E|E/E|(E)第23頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述４、文法與語言的關(guān)系中心思想：從文法的開始符號出發(fā)，反復(fù)連續(xù)使用產(chǎn)生式，對非終結(jié)符施行替換和展開。一個(gè)上下文無關(guān)文法如何定義一個(gè)語言呢？第24頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述Ｅ?(Ｅ)?(Ｅ+Ｅ)?(ｉ+Ｅ)?(ｉ+ｉ)例：Eid|E+E|E-E|E*E|E/E|(E)(i+i)注：我們可以從Ｅ出發(fā)，進(jìn)行一系列的推導(dǎo)，推出種種不同的算術(shù)表達(dá)式出來．該推導(dǎo)過程證明了（ｉ+ｉ）是文法Ｇ所定義的一個(gè)算術(shù)表達(dá)式。第25頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述“?”：若α１?

α２?

…

?αｎ，則稱該序列是從α１至αｎ的一個(gè)推導(dǎo)（α１可推導(dǎo)出αｎ）α１?

αｎ：α１?

αｎ：+*表示“直接推出”，即僅推出一步。αAβ

?αγβ,僅當(dāng)Ａ

γ是一個(gè)產(chǎn)生式，且α,β∈(ＶＴ∪ＶＮ)*

“推導(dǎo)”：從α１出發(fā)，經(jīng)過０步或若干步，可推導(dǎo)出αｎ從α１出發(fā)，經(jīng)一步或若干步，可推導(dǎo)出αｎ注：符號的含義第26頁,共46頁，2024年2月25日，星期天已知文法G：T

T*F|FF

FP|PP(T)|aT*P(T*F)第27頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述“句型”：設(shè)Ｇ是一個(gè)文法，Ｓ是其開始符號，Ｓ?α,

α∈(ＶＴ∪VN)**5、語言“句子”：僅含終結(jié)符號的句型是一個(gè)句子。+“語言”：文法Ｇ所產(chǎn)生的句子的全體是一個(gè)語言，記為Ｌ（Ｇ）＝｛α｜Ｓ?α＆α∈ＶＴ*｝第28頁,共46頁，2024年2月25日，星期天已知文法G：S

aAbA

BcA|BBidt|ε(1)aidtcBcAb(2)aidtccb(3)ab(4)abidt句型句子？？？第29頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述6、最左／右推導(dǎo)定義：任何一步α

?β都是對α中的最左／最右非終結(jié)符

進(jìn)行替換的。Ｅ?Ｅ+Ｅ?ｉ+Ｅ?ｉ＋ｉＥ?（Ｅ）?（Ｅ*Ｅ+Ｅ）?（ｉ*Ｅ+Ｅ）?（ｉ＊ｉ+Ｅ）?（ｉ＊ｉ＋ｉ）Ｅ?Ｅ+Ｅ?Ｅ＋ｉ?ｉ＋ｉＥ?（Ｅ）?（Ｅ+Ｅ）?（Ｅ＋ｉ）?（Ｅ＊Ｅ＋ｉ）?（Ｅ＊ｉ＋ｉ）?（ｉ＊ｉ＋ｉ）最左推導(dǎo)：最右推導(dǎo)：第30頁,共46頁，2024年2月25日，星期天練習(xí)：G[S]: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)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,))第31頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述7、例題例１.考慮一個(gè)文法Ｇ１：ＳｂＡ ＡａＡ｜ａ 定義了一個(gè)什么樣的語言？Ｓ?ｂＡ?ｂａＳ?ｂＡ?ｂａＡ?ｂａａ

.

.

.Ｓ?ｂＡ?ｂａＡ?ｂａａＡ?…?ｂａａ…ａＬ（Ｇ１）＝｛ｂａｎ｜ｎ≥１｝ＳｂＡＡａＡ｜ε？第32頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例２.考慮文法Ｇ２：ＳＡＢ ＡａＡ｜ａ ＢｂＢ｜ｂ 定義了一個(gè)什么樣的語言？分析：Ｓ?ＡＢ

ＳＡＢＡａＡ｜ε

？

ＢｂＢ｜ｂ

與Ａ類似由ＡａＡ｜ａ可知，其必產(chǎn)生ａ…ａ，且以此終結(jié)?Ｌ（Ｇ２）＝｛ａｍｂｎ｜ｍ，ｎ≥１｝第33頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例３、構(gòu)造一個(gè)文法Ｇ３，使Ｌ（Ｇ３

）＝｛ａｎｂｎ｜ｎ≥１｝分析：Ｇ２與Ｇ３的區(qū)別在于，Ｇ３必須使ａ、ｂ出現(xiàn)的次數(shù)相等，故而ａ、ｂ必須同時(shí)出現(xiàn)。G：ＳａＳｂ｜ａｂ第34頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述思考:

考慮文法

DD；D|TLTint|charLL，id|id定義了一個(gè)什么樣的語言？第35頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述二、語法分析樹與二義性１、語法分析樹

用樹的形式表示一個(gè)句型的推導(dǎo)生成，有助于理解一個(gè)句子語法結(jié)構(gòu)的層次。樹根：開始符號中間結(jié)點(diǎn)：非終結(jié)符葉結(jié)點(diǎn)：終結(jié)符／非終結(jié)符第36頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例：（ｉ＊ｉ＋ｉ）的最左推導(dǎo)－（Ａ）Ｅ（根）（ ）Ｅ Ｅ+Ｅ Ｅ*Ｅ ｉｉｉ次１２３４５層結(jié)論：一個(gè)句型不一定有唯一的一棵語法樹。即一個(gè)句型的最左／右推導(dǎo)可能不唯一。第37頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例：（ｉ＊ｉ＋ｉ）關(guān)于文法Ｇ的另一個(gè)最左推導(dǎo)－（Ａ’）Ｅ（ ）Ｅ Ｅ*Ｅ ｉ Ｅ+Ｅ ｉ ｉＥ?（Ｅ）?（Ｅ*Ｅ）?（ｉ＊Ｅ）?（ｉ＊Ｅ+Ｅ）?（ｉ＊ｉ＋Ｅ）?（ｉ＊ｉ＋ｉ）第38頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述2、二義文法

用若一個(gè)文法中存在某個(gè)句子，它有兩個(gè)不同的最左／右推導(dǎo)，則該文法為二義文法．例：上述文法ＧＥＥ＋Ｅ｜Ｅ*Ｅ｜（Ｅ）｜ｉ實(shí)質(zhì)：同一個(gè)句子存在兩棵語法分析樹。第39頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述例：句子ｉ+ｉ＊ｉ的最左推導(dǎo)過程ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉ最左推導(dǎo)Ｅ?Ｅ+Ｅ?ｉ＋Ｅ?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ?ｉ＋ｉ＊ｉＥ?Ｅ*Ｅ?Ｅ＋Ｅ*Ｅ?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ?ｉ＋ｉ＊ｉ第40頁,共46頁，2024年2月25日，星期天2.３程序語言的語法描述最右推導(dǎo)ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉＥ?Ｅ+Ｅ?Ｅ＋Ｅ*Ｅ

?Ｅ＋Ｅ*ｉ?Ｅ+