编译原理 第2章 文法和语言.pptx

第2章 文法和语言(P12)
字母表和符号串
文法
推导
句型和句子
语言
递归规则与递归文法
短语、简单短语和句柄
语法树
子树与短语
由树构造推导过程
文法的二义性
有关文法的实用限制
文法和语言分类
学****重点
1 文法的定义、分类和二义性
2 最左推导、规范推导(或最右推导)
3 语言、句型和句子
4 短语、简单短语(或直接短语)和句柄
5 语法树
形式语言(P12)
如果不考虑语义和语用,只从语法这一侧面来看语言,它是由符合某种语法(用规则定义)的句子构成的集合,这种意义下的语言称作形式语言。
例
汉语:所有符合汉语语法的句子的全体
英语:所有符合英语语法的句子的全体
程序设计语言:所有符合该语言语法的程序的
全体
形式语言
形式语言抽象地定义为一个数学系统,即能用数学符号和规则描述的语言。形式语言理论是对符号串集合的表示法、结构及其特性的研究。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。
字母表和符号串(P12)
字母表(或符号集) :元素的非空有穷集合。
例
二进制数语言的字母表={0,1}
汉语的字母表中包括汉字、数字及标点符号等
PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成
C语言的字母表由字母、数字、若干专用符号以及if、else、while等关键字组成
字母表和符号串
符号:字母表中的元素。
例={a,b,for,1},则a,b,for,1都是的符号。
不要把符号理解成字符。
典型的符号有字母、数字、各种标点符号和各种运算符。
字母表和符号串
符号串:由字母表上0个或多个符号所组成的任何有穷序列。空符号串ε也是字母表上的符号串,它由0个符号组成。
例={0,1},则ε, 0,1,01,10,00,11,100,0110,111110000等二进制数都是上的符号串
={a,b,c,+,*},则ε, a , b , c , + , *,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等都是上的符号串
一个字母表上的全部符号串所组成的集合是无穷的。
字母表和符号串
符号串的长度:指符号串x中所含符号的个数,记为|x|。特别地, |ε|=0。
例
={a,b,c,+,*}, |abc|=3,|abc+*abc|=8
符号串相等:若x、y是字母表∑上的两个符号串,那么当且仅当组成x的各符号与组成y的各符号依次相等时,则符号串x与符号串y相等,记作x=y。
例
当x=abbc,y=abbc 时,则x=y
当x=ab,y=ba 时,则x≠y
字母表和符号串
符号串的前缀:指从符号串x的末尾删除0或多个符号后得到的符号串。
例
u、uni、university都是university的前缀
符号串的后缀:指从符号串x的开头删除0或多个符号后得到的符号串。
例
ty、sity、university都是university的后缀
符号串的子串:指从符号串x的开头和末尾删除0或多个符号后得到的符号串,
例
ver是university的子串, 符号串的前缀、后缀都是它的子串。
字母表和符号串
符号串的连接:若x、y是两个符号串,则xy是将符号串y连接在符号串x的后面。
例
x=ab,y=ba,则 xy=abba
若x、y是字母表∑上的两个符号串,则xy也是字母表∑上的符号串。
除εx=xε=x外,连接没有交换率,
即 xy ≠ yx 。