编译原理第二章(2-1).ppt

1
第二章上下文无关文法和语言
§ 文法和语言的表示
§ 文法和语言的定义
§ 句型的分析
§ 文法的化简与改造
§ 文法和语言的Chomsky分类
北京交通大学于双元
2
提要
所谓形式化方法,简单地说,就是用一整套带有严格规定的符号体系来描述问题的理论和方法,用形式化方法描述的语言(语法和语义)便是形式语言。
本章将从形式语言的角度系统地介绍什么是程序设计语言的文法,文法和语言的关系等问题,本章是本课程的理论基础。
北京交通大学于双元
3
§2·1 文法和语言的表示
语言的定义可采用下列三种方法
——把该语言的所有句子列出放
在一集合内。(有限个句子时)
——描述语言的全部句子。
(有限或无限个句子),即文法表示
——检验和识别句子。
(有限或无限个句子)即自动机
北京交通大学于双元
4
§2·2 文法和语言的定义
§2·2·1 基本概念和术语
§2·2·2 文法和语言的形式定义
§2·2·3 递归规则与递归文法
北京交通大学于双元
5
§2·2 文法和语言的定义
1、字母表:
元素的非空有穷集合,
元素称符号。
例:∑={0,1}
2、符号串:
字母表中的符号所组成的任何有穷序列.
特别:
空符号串ε
(不包含任何符号)
∑={a,b}
§2·2·1、基本概念和术语
北京交通大学于双元
6
3 、字母表∑上的符号串的递归定义。

(1)ε是∑上的符号串
(2)若x是∑上的符号串,且a∈∑,
则xa或ax是∑上的符号串
特别:ε x = x ε= x
(3)若y是∑上的符号串,
当且仅当y可由(1)和(2)产生。
北京交通大学于双元
7
例: ∑={b,c} ,
求∑上的所有符号串
根据1
ε是∑上的符号串
∑上的所有符号串ε,b , c, bb,bc,, bbb,bbc ,bcb ,bcc ,cbb ,bcb ,ccb , ccc……
根据2
ε b和εc 即b,c 是∑上的符号串
bb,bc, 是∑上的符号串
bbb,bbc ,bcb ,bcc ,cbb ,bcb ,ccb , ccc是∑上的符号串…….
北京交通大学于双元
8
5 、符号串的前缀、后缀和子串:
前缀:设x是一符号串,从x的尾部删去若干个(包括
0个)符号之后所剩余下的部分称为x的前缀;
若x的前缀不是x本身,则称为x的真前缀。
后缀:设x是一符号串,从x的头部删去若干个(包括
0个)符号之后所剩余下的部分称为x的后缀;
若x的后缀不是x本身,则称为x的真后缀。
子串:从一个符号串中删去它的一个前缀和一个后缀
之后所剩下的部分称为此符号串的子串。
若x的子串不是x本身,则称为x的真子串
北京交通大学于双元
9
例设x=abc
x= ε a ε b ε c ε
x的前缀:
abc
ab
a
ε
(ε,a,ab为真前缀)
x的后缀:
abc
c
bc
ε
( ε, c,bc 为真后缀)
x的子串:
abc
ab
bc
a
b
c
ε
(ε,a,ab,b,c,bc为真子串)
用法: z=x…….(x为z的前缀)
z=……x (x为z的后缀) 对某些感兴趣
z=…x….(x 为z的子串)
北京交通大学于双元
10
5、符号串的长度:符号串所含符号的个数
6 、符号串的连接和方幂
连接:设有符号串x,y,把y的符号写在x的符号
之后所得的符号串,叫做x与y的连接,
记xy

方幂:设有符号串x,则x的n次自身连接称为x的
n次方幂,记为xn
特别:x0 = ε
北京交通大学于双元