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

(1)ε是∑上的符号串
(2)若x是∑上的符号串,且a∈∑,
则xa或ax是∑上的符号串
特别:ε x = x ε= x
(3)若y是∑上的符号串,
当且仅当y可由(1)和(2)产生。
5
例: ∑={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是∑上的符号串…….
6
5 、符号串的前缀、后缀和子串:
前缀:设x是一符号串,从x的尾部删去若干个(包括
0个)符号之后所剩余下的部分称为x的前缀;
若x的前缀不是x本身,则称为x的真前缀。
后缀:设x是一符号串,从x的头部删去若干个(包括
0个)符号之后所剩余下的部分称为x的后缀;
若x的后缀不是x本身,则称为x的真后缀。
子串:从一个符号串中删去它的一个前缀和一个后缀
之后所剩下的部分称为此符号串的子串。
若x的子串不是x本身,则称为x的真子串
7
例设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的子串)
8
5、符号串的长度:符号串所含符号的个数
6 、符号串的连接和方幂
连接:设有符号串x,y,把y的符号写在x的符号
之后所得的符号串,叫做x与y的连接,
记xy

方幂:设有符号串x,则x的n次自身连接称为x的
n次方幂,记为xn
特别:x0 = ε
9
7 、符号串集合A与B的和与积:
和: A+B={w|w ∈A或w ∈B}
积: AB={xy|x ∈A且y ∈B}
8 、符号串集合的方幂:
设有符号串集合A
则定义A0 = {ε}
A1=A
A2=AA
An=AA……A
n个
10