高级语言及其语法描述

高级语言及其语法描述常用的高级语言

FORTRAN 数值计算

COBOL 事务处理

PASCAL 结构程序设计

ADA 大型程序、嵌入式实时系统

PROLOG 逻辑程序设计

ALGOL 算法语言

C/C++ 系统程序设计

Java Internet程序设计第2页,共46页，2024年2月25日，星期天与机器语言或汇编语言比较，高级语言的优点：较接近于数学语言和工程语言，比较直观、自然和易于理解;便于验证其正确性，易于改错;编写效率高;易于移植.第3页,共46页，2024年2月25日，星期天2.1程序语言的定义自然语言与计算机语言的区别与联系：

计算机程序语言——一个记号系统，类似于自然语言，由语法+语义定义

自然语言（1）人与人的通讯工具（2）语义：由环境、背景知识、语气等决定 二义性（常有）——难以形式化计算机语言（1）计算机系统间、人机间通讯工具 （2）具有严格的语法、语义

——易于形式化（严格）

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

一组规则，使用它可以形成和产生一个合式的程序，则这组规则称为语法。定义了程序的形式结构，是判断输入字符串是否构成一个形式上（即合式）正确程序的依据。

词法规则——单词符号的形成规则，即规定了字母表中 哪样的字符串是一个单词符号。

单词符号——语言中具有独立意义的最基本结构。语法规则——语法单位的形成规则，即规定了如何从单 词符号形成更大的结构（即语法单位）。第5页,共46页，2024年2月25日，星期天2.1程序语言的定义二、语义

1、语义规则：一组规则，使用它可以定义一个程序的意义。离开语义，语言只不过是一堆符号的集合；在许多语言中有着形式上完全相同的语法单位，但含义却不尽相同。

２、注意：阐明语义要比阐明语法难得多，现在还没有一 种公认的形式系统，借助于它可以自动地构造 出实用的编译程序。本书基于属性文法的语法制导翻译方法较接近形式化第6页,共46页，2024年2月25日，星期天程序语言的基本功能和层次结构程序语言的基本功能：描述数据和对数据的运算。所谓程序，本质上说是描述一定数据的处理过程。第7页,共46页，2024年2月25日，星期天程序的层次结构程序|子程序或分程序、过程、函数|语句|表达式|数据引用算符函数调用第8页,共46页，2024年2月25日，星期天2.３程序语言的语法描述基本概念1、有穷字母表。∑中的每个元素。由∑中的符号所构成的一个有穷序列。空字，不包含任何符号的序列。∑上的所有符号串的全体，包括ε。注：区分：ε

、｛ε｝、Ф

空集Ф

＝｛｝：不含任何元素的集合∑：符号：∑上的符号串：ε：∑*：第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个V的闭包V的正则闭包注：V*中的每个符号串都是由V中的符号串经有限次连接而成的。第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日，星期天设：V＝{a,aa}那么：

V*

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

={a,aa,aaa,aaaa,…}第12页,共46页，2024年2月25日，星期天2.３程序语言的语法描述一、上下文无关文法1、定义：文法：描述语言的语法结构的形式规则（即语法规则）。上下文无关文法：所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的一种文法。描述语法规则的且独立于环境描述语法规则例：英语中，一般句子是由主——谓二部分构成。第13页,共46页，2024年2月25日，星期天2.３程序语言的语法描述2、文法——语法的类比：分析：Thegreywolfwilleatthegoat.The

greywolfwill

eat

thegoat直接宾语名词动词谓语名词形容词冠词主语句子助动词动词原形冠词第14页,共46页，2024年2月25日，星期天2.３程序语言的语法描述Ａ、产生句子的规则——从产生语言的角度<句子><主语><谓语>

(1)<主语><冠词><形容词><名词>

(2)<冠词>

the <形容词>

grey<谓语><动词><直接宾语>

(5)<动词>

<助动词><动词原形> (6)<直接宾语>

<冠词><名词>

(9)<助动词>

will

<动词原形>

eat

<名词>

wolf <名词>

goat

第15页,共46页，2024年2月25日，星期天2.３程序语言的语法描述B、句子的语法组成——终结符号集，非终结符号集， 语法规则，开始符号终结符号集

VT={the,grey,wolf,will,eat,goat}非终结符号集

VN={<句子>,<主语>,<谓语>,<冠词>,<形容词>,<名词>,<动词>,<直接宾语>,<助动词>,<动词原形>}语法规则集

P={<句子><主语><谓语>,…}开始符号

S=<句子>第16页,共46页，2024年2月25日，星期天2.３程序语言的语法描述C、句子的派生（推导）——根据规则<句子>⇒<主语><谓语>

⇒

<冠词><形容词><名词><谓语>⇒

the<形容词><名词><谓语>

⇒

thegrey<名词><谓语>⇒

thegreywolf<谓语>⇒

thegreywolf<动词><直接宾语>⇒

…⇒

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

thegreywolfwilleatthewolf

thegreygoatwilleatthewolf

thegreygoatwilleatthegoat符合语法且符合语义的句子仅是：

thegreywolfwilleatthegoat第18页,共46页，2024年2月25日，星期天2.３程序语言的语法描述3、上下文无关文法Ｇ的形式定义 Ｇ是一个四元组（ＶＴ，ＶＮ，Ｓ，Ｐ）ＶＴ——终结符号集，非空有限集ＶＮ——非终结符号集，非空有限集ＶＮ∩ＶＴ＝Ф

终结符号：描述单词符号,组成语言的基本符号，是一个语言的不可再分的基本符号。

例如：基本字，标识符，常数，算符，界符等．

非终结符：代表语法范畴，一个非终结符代表一个一定的语法概念，每个非终结符表示一定符号串的集合。例如：算术表达式，布尔表达式，赋值句，分程序，过程等．第19页,共46页，2024年2月25日，星期天2.３程序语言的语法描述Ｓ——开始符号，一个特殊的非终结符号Ｐ——产生式集合，有限集产生式：定义语法范畴的一种书写规则．形式：A

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

“

”:“定义为”

“｜”：

“或”

非终结符号:用大写字母Ａ、Ｂ、Ｃ…或汉语组代表

终结符:用小写字母…代表至少必须在某个产生式的左部出现一次第20页,共46页，2024年2月25日，星期天巴科斯范式（BNF：Backus-NaurForm的缩写）描述计算机语言语法的符号集。由JohnBackus和PeterNaur首次引入一种形式化符号来描述给定语言的语法（最早用于描述ALGOL60编程语言）。JohnBackusPeterNaurBNF现在是定义一种计算机语言的标准方式。第21页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例1：上下文无关文法Ｇ：Ei|EAEA+|*非终结符号：开始符号：终结符号：E，AE+，*，iG[E]第22页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例2：算术表达式的文法标识符(id)(常量、变量)是表达式(E)； 表达式加一个表达式是表达式； 表达式减一个表达式是表达式； 表达式乘一个表达式是表达式； 表达式除一个表达式是表达式； 表达式加上括号是表达式；EidEE+EEE-EEE*EEE/EE(E)P:Eid|E+E|E-E|E*E|E/E|(E)第23页,共46页，2024年2月25日，星期天2.３程序语言的语法描述４、文法与语言的关系中心思想：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。一个上下文无关文法如何定义一个语言呢？第24页,共46页，2024年2月25日，星期天2.３程序语言的语法描述Ｅ⇒(Ｅ)⇒(Ｅ+Ｅ)⇒(ｉ+Ｅ)⇒(ｉ+ｉ)例：Eid|E+E|E-E|E*E|E/E|(E)(i+i)注：我们可以从Ｅ出发，进行一系列的推导，推出种种不同的算术表达式出来．该推导过程证明了（ｉ+ｉ）是文法Ｇ所定义的一个算术表达式。第25页,共46页，2024年2月25日，星期天2.３程序语言的语法描述“⇒”：若α１⇒

α２⇒

…

⇒αｎ，则称该序列是从α１至αｎ的一个推导（α１可推导出αｎ）α１⇒

αｎ：α１⇒

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

⇒αγβ,仅当Ａ

γ是一个产生式，且α,β∈(ＶＴ∪ＶＮ)*

“推导”：从α１出发，经过０步或若干步，可推导出αｎ从α１出发，经一步或若干步，可推导出αｎ注：符号的含义第26页,共46页，2024年2月25日，星期天已知文法G：T

T*F|FF

FP|PP(T)|aT*P(T*F)第27页,共46页，2024年2月25日，星期天2.３程序语言的语法描述“句型”：设Ｇ是一个文法，Ｓ是其开始符号，Ｓ⇒α,

α∈(ＶＴ∪VN)**5、语言“句子”：仅含终结符号的句型是一个句子。+“语言”：文法Ｇ所产生的句子的全体是一个语言，记为Ｌ（Ｇ）＝｛α｜Ｓ⇒α＆α∈ＶＴ*｝第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、最左／右推导定义：任何一步α

⇒β都是对α中的最左／最右非终结符

进行替换的。Ｅ⇒Ｅ+Ｅ⇒ｉ+Ｅ⇒ｉ＋ｉＥ⇒（Ｅ）⇒（Ｅ*Ｅ+Ｅ）⇒（ｉ*Ｅ+Ｅ）⇒（ｉ＊ｉ+Ｅ）⇒（ｉ＊ｉ＋ｉ）Ｅ⇒Ｅ+Ｅ⇒Ｅ＋ｉ⇒ｉ＋ｉＥ⇒（Ｅ）⇒（Ｅ+Ｅ）⇒（Ｅ＋ｉ）⇒（Ｅ＊Ｅ＋ｉ）⇒（Ｅ＊ｉ＋ｉ）⇒（ｉ＊ｉ＋ｉ）最左推导：最右推导：第30页,共46页，2024年2月25日，星期天练习：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,))第31页,共46页，2024年2月25日，星期天2.３程序语言的语法描述7、例题例１.考虑一个文法Ｇ１：ＳｂＡ ＡａＡ｜ａ 定义了一个什么样的语言？Ｓ⇒ｂＡ⇒ｂａＳ⇒ｂＡ⇒ｂａＡ⇒ｂａａ

.

.

.Ｓ⇒ｂＡ⇒ｂａＡ⇒ｂａａＡ⇒…⇒ｂａａ…ａＬ（Ｇ１）＝｛ｂａｎ｜ｎ≥１｝ＳｂＡＡａＡ｜ε？第32页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例２.考虑文法Ｇ２：ＳＡＢ ＡａＡ｜ａ ＢｂＢ｜ｂ 定义了一个什么样的语言？分析：Ｓ⇒ＡＢ

ＳＡＢＡａＡ｜ε

？

ＢｂＢ｜ｂ

与Ａ类似由ＡａＡ｜ａ可知，其必产生ａ…ａ，且以此终结⇒Ｌ（Ｇ２）＝｛ａｍｂｎ｜ｍ，ｎ≥１｝第33页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例３、构造一个文法Ｇ３，使Ｌ（Ｇ３

）＝｛ａｎｂｎ｜ｎ≥１｝分析：Ｇ２与Ｇ３的区别在于，Ｇ３必须使ａ、ｂ出现的次数相等，故而ａ、ｂ必须同时出现。G：ＳａＳｂ｜ａｂ第34页,共46页，2024年2月25日，星期天2.３程序语言的语法描述思考:

考虑文法

DD；D|TLTint|charLL，id|id定义了一个什么样的语言？第35页,共46页，2024年2月25日，星期天2.３程序语言的语法描述二、语法分析树与二义性１、语法分析树

用树的形式表示一个句型的推导生成，有助于理解一个句子语法结构的层次。树根：开始符号中间结点：非终结符叶结点：终结符／非终结符第36页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例：（ｉ＊ｉ＋ｉ）的最左推导－（Ａ）Ｅ（根）（ ）Ｅ Ｅ+Ｅ Ｅ*Ｅ ｉｉｉ次１２３４５层结论：一个句型不一定有唯一的一棵语法树。即一个句型的最左／右推导可能不唯一。第37页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例：（ｉ＊ｉ＋ｉ）关于文法Ｇ的另一个最左推导－（Ａ’）Ｅ（ ）Ｅ Ｅ*Ｅ ｉ Ｅ+Ｅ ｉ ｉＥ⇒（Ｅ）⇒（Ｅ*Ｅ）⇒（ｉ＊Ｅ）⇒（ｉ＊Ｅ+Ｅ）⇒（ｉ＊ｉ＋Ｅ）⇒（ｉ＊ｉ＋ｉ）第38页,共46页，2024年2月25日，星期天2.３程序语言的语法描述2、二义文法

用若一个文法中存在某个句子，它有两个不同的最左／右推导，则该文法为二义文法．例：上述文法ＧＥＥ＋Ｅ｜Ｅ*Ｅ｜（Ｅ）｜ｉ实质：同一个句子存在两棵语法分析树。第39页,共46页，2024年2月25日，星期天2.３程序语言的语法描述例：句子ｉ+ｉ＊ｉ的最左推导过程ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉ最左推导Ｅ⇒Ｅ+Ｅ⇒ｉ＋Ｅ⇒ｉ＋Ｅ*Ｅ⇒ｉ＋ｉ＊Ｅ⇒ｉ＋ｉ＊ｉＥ⇒Ｅ*Ｅ⇒Ｅ＋Ｅ*Ｅ⇒ｉ＋Ｅ*Ｅ⇒ｉ＋ｉ＊Ｅ⇒ｉ＋ｉ＊ｉ第40页,共46页，2024年2月25日，星期天2.３程序语言的语法描述最右推导ＥＥＥＥ*Ｅ+ｉｉｉＥＥＥＥ+Ｅ*ｉｉｉＥ⇒Ｅ+Ｅ⇒Ｅ＋Ｅ*Ｅ

⇒Ｅ＋Ｅ*ｉ⇒Ｅ+