高級語言及其語法描述

高級語言及其語法描述第一頁，共四十六頁，編輯于2023年，星期二常用的高級語言

FORTRAN 數(shù)值計算

COBOL 事務處理

PASCAL 結構程序設計

ADA 大型程序、嵌入式實時系統(tǒng)

PROLOG 邏輯程序設計

ALGOL 算法語言

C/C++ 系統(tǒng)程序設計

Java Internet程序設計第二頁，共四十六頁，編輯于2023年，星期二與機器語言或匯編語言比較，高級語言的優(yōu)點：較接近于數(shù)學語言和工程語言，比較直觀、自然和易于理解;便于驗證其正確性，易于改錯;編寫效率高;易于移植.第三頁，共四十六頁，編輯于2023年，星期二2.1程序語言的定義自然語言與計算機語言的區(qū)別與聯(lián)系：

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

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

——易于形式化（嚴格）

第四頁，共四十六頁，編輯于2023年，星期二2.1程序語言的定義一、語法

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

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

單詞符號——語言中具有獨立意義的最基本結構。語法規(guī)則——語法單位的形成規(guī)則，即規(guī)定了如何從單 詞符號形成更大的結構（即語法單位）。第五頁，共四十六頁，編輯于2023年，星期二2.1程序語言的定義二、語義

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

２、注意：闡明語義要比闡明語法難得多，現(xiàn)在還沒有一 種公認的形式系統(tǒng)，借助于它可以自動地構造 出實用的編譯程序。本書基于屬性文法的語法制導翻譯方法較接近形式化第六頁，共四十六頁，編輯于2023年，星期二程序語言的基本功能和層次結構程序語言的基本功能：描述數(shù)據(jù)和對數(shù)據(jù)的運算。所謂程序，本質上說是描述一定數(shù)據(jù)的處理過程。第七頁，共四十六頁，編輯于2023年，星期二程序的層次結構程序|子程序或分程序、過程、函數(shù)|語句|表達式|數(shù)據(jù)引用算符函數(shù)調(diào)用第八頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述基本概念1、有窮字母表。∑中的每個元素。由∑中的符號所構成的一個有窮序列。空字，不包含任何符號的序列。∑上的所有符號串的全體，包括ε。注：區(qū)分：ε

、｛ε｝、Ф

空集Ф

＝｛｝：不含任何元素的集合∑：符號：∑上的符號串：ε：∑*：第九頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述２、（連接）積：UV={αβ|α∈U＆β∈V} U、V?

∑*UV不一定等于

VU,

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

V1∪V2∪

V3∪

…V+=VV*n個V的閉包V的正則閉包注：V*中的每個符號串都是由V中的符號串經(jīng)有限次連接而成的。第十頁，共四十六頁，編輯于2023年，星期二例：

∑={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=∑*=∑+=第十一頁，共四十六頁，編輯于2023年，星期二設：V＝{a,aa}那么：

V*

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

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

greywolfwill

eat

thegoat直接賓語名詞動詞謂語名詞形容詞冠詞主語句子助動詞動詞原形冠詞第十四頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述Ａ、產(chǎn)生句子的規(guī)則——從產(chǎn)生語言的角度<句子><主語><謂語>

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

(2)<冠詞>the <形容詞>grey<謂語><動詞><直接賓語>

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

(9)<助動詞>will

<動詞原形>eat

<名詞>wolf <名詞>goat

第十五頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述B、句子的語法組成——終結符號集，非終結符號集， 語法規(guī)則，開始符號終結符號集

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

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

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

S=<句子>第十六頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述C、句子的派生（推導）——根據(jù)規(guī)則<句子>?<主語><謂語>

?

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

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

?

thegrey<名詞><謂語>?

thegreywolf<謂語>?

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

…?

thegreywolfwilleatthegoat第十七頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述D、句子的語義要求<句子> thegreywolfwilleatthegoat

thegreywolfwilleatthewolf

thegreygoatwilleatthewolf

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

thegreywolfwilleatthegoat第十八頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述3、上下文無關文法Ｇ的形式定義 Ｇ是一個四元組（ＶＴ，ＶＮ，Ｓ，Ｐ）ＶＴ——終結符號集，非空有限集ＶＮ——非終結符號集，非空有限集ＶＮ∩ＶＴ＝Ф

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

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

非終結符：代表語法范疇，一個非終結符代表一個一定的語法概念，每個非終結符表示一定符號串的集合。例如：算術表達式，布爾表達式，賦值句，分程序，過程等．第十九頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述Ｓ——開始符號，一個特殊的非終結符號Ｐ——產(chǎn)生式集合，有限集產(chǎn)生式：定義語法范疇的一種書寫規(guī)則．形式：AαA∈VN,α∈(VT∪VN)*注：

“”:“定義為”

“｜”：

“或”

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

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

α２?

…

?αｎ，則稱該序列是從α１至αｎ的一個推導（α１可推導出αｎ）α１?

αｎ：α１?

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

?αγβ,僅當Ａγ是一個產(chǎn)生式，且α,β∈(ＶＴ∪ＶＮ)*

“推導”：從α１出發(fā)，經(jīng)過０步或若干步，可推導出αｎ從α１出發(fā)，經(jīng)一步或若干步，可推導出αｎ注：符號的含義第二十六頁，共四十六頁，編輯于2023年，星期二已知文法G：TT*F|FFFP|PP(T)|aT*P(T*F)第二十七頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述“句型”：設Ｇ是一個文法，Ｓ是其開始符號，Ｓ?α,

α∈(ＶＴ∪VN)**5、語言“句子”：僅含終結符號的句型是一個句子。+“語言”：文法Ｇ所產(chǎn)生的句子的全體是一個語言，記為Ｌ（Ｇ）＝｛α｜Ｓ?α＆α∈ＶＴ*｝第二十八頁，共四十六頁，編輯于2023年，星期二已知文法G：SaAbABcA|BBidt|ε(1)aidtcBcAb(2)aidtccb(3)ab(4)abidt句型句子？？？第二十九頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述6、最左／右推導定義：任何一步α

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

進行替換的。Ｅ?Ｅ+Ｅ?ｉ+Ｅ?ｉ＋ｉＥ?（Ｅ）?（Ｅ*Ｅ+Ｅ）?（ｉ*Ｅ+Ｅ）?（ｉ＊ｉ+Ｅ）?（ｉ＊ｉ＋ｉ）Ｅ?Ｅ+Ｅ?Ｅ＋ｉ?ｉ＋ｉＥ?（Ｅ）?（Ｅ+Ｅ）?（Ｅ＋ｉ）?（Ｅ＊Ｅ＋ｉ）?（Ｅ＊ｉ＋ｉ）?（ｉ＊ｉ＋ｉ）最左推導：最右推導：第三十頁，共四十六頁，編輯于2023年，星期二練習：G[S]: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)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,))第三十一頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述7、例題例１.考慮一個文法Ｇ１：ＳｂＡ ＡａＡ｜ａ 定義了一個什么樣的語言？Ｓ?ｂＡ?ｂａＳ?ｂＡ?ｂａＡ?ｂａａ

.

.

.Ｓ?ｂＡ?ｂａＡ?ｂａａＡ?…?ｂａａ…ａＬ（Ｇ１）＝｛ｂａｎ｜ｎ≥１｝ＳｂＡＡａＡ｜ε？第三十二頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述例２.考慮文法Ｇ２：ＳＡＢ ＡａＡ｜ａ ＢｂＢ｜ｂ 定義了一個什么樣的語言？分析：Ｓ?ＡＢ

ＳＡＢＡａＡ｜ε

？

ＢｂＢ｜ｂ

與Ａ類似由ＡａＡ｜ａ可知，其必產(chǎn)生ａ…ａ，且以此終結?Ｌ（Ｇ２）＝｛ａｍｂｎ｜ｍ，ｎ≥１｝第三十三頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述例３、構造一個文法Ｇ３，使Ｌ（Ｇ３

）＝｛ａｎｂｎ｜ｎ≥１｝分析：Ｇ２與Ｇ３的區(qū)別在于，Ｇ３必須使ａ、ｂ出現(xiàn)的次數(shù)相等，故而ａ、ｂ必須同時出現(xiàn)。G：ＳａＳｂ｜ａｂ第三十四頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述思考:

考慮文法

DD；D|TLTint|charLL，id|id定義了一個什么樣的語言？第三十五頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述二、語法分析樹與二義性１、語法分析樹

用樹的形式表示一個句型的推導生成，有助于理解一個句子語法結構的層次。樹根：開始符號中間結點：非終結符葉結點：終結符／非終結符第三十六頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述例：（ｉ＊ｉ＋ｉ）的最左推導－（Ａ）Ｅ（根）（ ）Ｅ Ｅ+Ｅ Ｅ*Ｅ ｉｉｉ次１２３４５層結論：一個句型不一定有唯一的一棵語法樹。即一個句型的最左／右推導可能不唯一。第三十七頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述例：（ｉ＊ｉ＋ｉ）關于文法Ｇ的另一個最左推導－（Ａ’）Ｅ（ ）Ｅ Ｅ*Ｅ ｉ Ｅ+Ｅ ｉ ｉＥ?（Ｅ）?（Ｅ*Ｅ）?（ｉ＊Ｅ）?（ｉ＊Ｅ+Ｅ）?（ｉ＊ｉ＋Ｅ）?（ｉ＊ｉ＋ｉ）第三十八頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述2、二義文法

用若一個文法中存在某個句子，它有兩個不同的最左／右推導，則該文法為二義文法．例：上述文法ＧＥＥ＋Ｅ｜Ｅ*Ｅ｜（Ｅ）｜ｉ實質：同一個句子存在兩棵語法分析樹。第三十九頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述例：句子ｉ+ｉ＊ｉ的最左推導過程ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉ最左推導Ｅ?Ｅ+Ｅ?ｉ＋Ｅ?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ?ｉ＋ｉ＊ｉＥ?Ｅ*Ｅ?Ｅ＋Ｅ*Ｅ?ｉ＋Ｅ*Ｅ?ｉ＋ｉ＊Ｅ?ｉ＋ｉ＊ｉ第四十頁，共四十六頁，編輯于2023年，星期二2.３程序語言的語法描述最右推導ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉＥ?Ｅ+Ｅ?Ｅ＋Ｅ