高级程序设计语言-编译原理ppt课件.ppt

第二章高级语言及其语法描述任何语言实现的基础是语言的定义。
在定义方面，编译程序研制者与一般用户有所不同
用户关心语言如何使用
开发人员关心文法的定义。他们对哪些构造允许出现更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它。
程序语言主要由语法和语义两方面定义。2.1.1语法几个概念程序设计语言的定义2.2高级语言的一般特性2.2.1高级语言分类2.2.1高级语言分类2.2.1高级语言分类2.2.1高级语言分类2.2.2程序结构Pascal是一个允许子程序嵌套定义的语言程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：
a.用于区别这种类型的数据对象的属性
b.这种类型的数据对象可以具有的值
c.可以作用于这种类型数据对象的操作
一.初等数据类型（基本数据类型）名字和标识符二.构造数据类型b.记录
从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。

记录结构是许多程序语言的一类重要的数据结构。Pascal语言采用下面形式定义记录：

CARD:record
NAME:array[1..20]ofchar;
AGE:integer;
MARRIED:boolean
end;如：就CARD而言，NAME,AGE,MARRIED的相对数OFFSET分别为0、20、24。于是，假定CARD的首地址为a，那么，
CARD.NAME地址为a
CARD.AGE地址为a+20
CARD.MARRIED地址为a+24
2.2.4语句与控制结构一.表达式

组成：运算量（亦称操作数，即数据引用或函数调用）和算符组成的。
表示形式:
前缀式：+a*bc
中缀式：a+b*c
后缀式：abc*+表达式中的算符算符的代数性质二.语句2.3程序语言的语法描述字母表：由若干元素组成的有限非空集合，用表示，它的每个元素称为一个符号。
符号串：由中的符号所构成的有穷序列。
符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串。空串（字）：不包含符号的序列称为空串（字），记为。
用*表示上的所有符号串的全体，空字也包括在其中。如：若={a,b}则*={,a,b,aa,ab,bb,aaa,…}。表示不含人何元素的空集{}。这里要注意、{}和{}的区别。符号串及符号串集合的运算应用举例符号串及符号串集合的运算符号串集合V自身的n次（连接）积记为：
Vn=VV…V=Vn-1V=VVn-1(n个V)
规定V0={}.
V的闭包：令：V*=V0∪V1∪V2∪…
称V*是V的闭包。
V的正则包（正闭包，正则闭包）：记V+=VV*,称V+是V的正则包，即V+=V1∪V2∪V3∪…。
一个例子作业：引例由语法规则“推导”出句子的过程“推导”过程对应的语法分析树上下文无关文法的定义上下文无关文法的形式定义上下文无关文法的举例上下文无关文法的定义上下文无关文法3.开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴。
4.产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。
一个产生式的形式是A→α
其中箭头左边的A是一个非终结符，称为产生式的左部符号；
箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部，或称候选式。文法简写约定产生式实例关于产生式利用语法规则进行分析的方法推导与直接推导句型与句子句型与句子用文法定义语言的方法例2.1考虑一个文法G1:
S→bA
A→aA|a
它定义了一个什么语言呢？
解：从开始符号S出发，我们可以推出如下句子：
SbAba
SbAbaAbaa
SbAbaA…baa…a
可以写为：L(G1)={ban|n≥1}例2.2设有文法G2
S→P|aPb
P→ba|bQa
Q→ab
求语言L(G2)。
解：
L(G2)={ba,baba,abab,ababab}
例2.3设有文法G3
S→AB
A→aA|a
B→bB|b
求语言L(G3)。
解：
L(G3)={ambn|m,n≥1}
例2.8：已知语言L={anbbn|n1},写出产生L的文法。
[解]：
G[S]:SaAb
AaAb|b
如果写成
G[S]:SaSb|b
可不可以？
如果写成
G[S]:SaSb|abb
可不可以？例2.9：
试构造生成语言L={anbnci|n0,i1}的文法
解：G(Z):ZAB
AaAb|
BcB|c最左（右）推导语法分析树：简称语法树。用来表示推导过程。

语法树示例语法树的不唯一性语法树的不唯一性文法的二义性文法二义性的几