<数字>→0|1|2|3|4|5|6|7|8|9
2.3.3 和语言有关的几个概念
1.直接推导
如果α → β是文法G的一条产生式，而γ ，δ是(VT∪VN)*中任意 一个符号串，则将α → β作用于符号串γ α δ上得到符号串γ β δ ，称 符号串γ β δ 是符号串γ α δ的直接推导，记为 γ α δ γβδ 直接推导的逆过程称为直接归约，即由符号串γ β δ可直接归约到γ α δ 。
G4[<无符号整数>]： <无符号整数>→<数字>|<无符号整数><数字> <数字>→0|1|2|3|4|5|6|7|8|9
2.3
2型和3型 。
文法的分类
乔姆斯基（Chomsky）把文法分成四种类型 ，即0型、1型、
这四类文法的区别在于：对产生式规则的形式上施加不同 的限制。从0型到3型对产生式的要求越来越严格,而其描述语 言的能力是逐步减弱的。

符号串集合的正闭包A+ 与 闭包A* A是集合 A的正闭包 A＋＝ A1∪A2 ∪ …… ∪ An A的闭包 A*＝ A0 ∪ A1∪A2 ∪ …… ∪ An ＝ {ε} ∪ A+ A={a,b} A＋ ＝ { a, b, aa, ab, ba, bb, aaa, aab,…..} A* ＝ {ε, a , b, aa , ab, ba, bb, aaa, aab,…..} A＋表示A上元素a,b构成的所有符号串的集合。
2.3
文法的分类
0型文法（无限制文法或短语结构文法）
产生式为 ： α→β 其中：α (VN∪VT)* 且至少包含一个非终结符 β (VN∪VT)*， 0型文法没有其他任何限制条件，故称无限制文法。 0型文法所生成的语言称为无限制语言。
例如 有0型文法G=(VN,VT,P,S) ,其中 P={S→0AB 1B→0 B→SA|01 A1→SB1 A0→S0B} 其描述的0型语言为 L(G[S])={ }
8.规则左递归与规则右递归
如果文法的产生式呈 U→U… 的形式，则称其为 规则左递归。 如果文法的产生式呈 U→…U 的形式，则称其为 规则右递归。 规则左(右)递归，也称直接左(右)递归。
9.文法左递归与文法右递归
+ 如果文法中有推导 U U… ，则称其为文法左递归，也称
间接左递归。
+ 如果文法中有推导 U …U ，则称其为文法右递归，也称

符号串的方幂 设x是符号串，xn 是x自身连结n次。并且x0＝ ε 则 x1＝ x x2＝ xx xn＝ xx……x= x xn-1 n个 例如, 设 x=abc，则 x1＝ abc x2＝ abcabc ……

符号串集合的方幂 A是符号串的集合， An 是集合A自身n次相乘， 并且A0＝ {ε} 则 A 1＝ A A2＝ AA An＝ AA……A= A An-1 (n>0) n个A 例1 A={a,b} A0＝ {ε} A1 ＝ {a,b} A2＝ {aa,ab,ba,bb} A3＝ {aa,ab,ba,bb}· {a,b} ＝ { aaa,aab,aba,abb,baa,bab,bba,bbb }

例如：1）<句子> → <主语> <谓语> 2）<主语> → <冠词> <名词> 3）<谓语> → <动词> <宾语> 4）<宾语> → <冠词> <名词> 5）<名词> → man | car 6）<冠词> → the 7）<名词> → drive The man drive the car The car drive the man 一组规则规定一个语言 The car drive the car 的语法结构 The man drive the man
【例1】设有文法G[S]： S→01∣0S1
S => 01 S => 0S1 => 00S11 => 000111
S,01，0S1，00S11,000111 都是句型。 01和000111 又是句型。
【例2】设有文法G[E]： E→E+T∣E-T∣T T→T*F∣T/F∣F F→（E）∣I
·
文法的实用限制
形式语言理论
由Chomsky于1956年首先提出。
是指由数学方法——形式化方法研究自然语言（如英
语）和人工语言（如程序设计语言）的语法的理论。
目前在自然语言的翻译、计算机语言的描述和转换、
编译程序的构造、模式识别等方面有广泛的应用。
2.1 语言成分的基本概念
一个语言的成分包括字母表（Alphabet）,文法（Ｇ
间接右递归。
递归举例
G1[S]： S→Sa|Ab|b|c A→Bc|a B→Sb|b G2[S]： S→a|ε|aTb
T→S, T |S 直接右递归
直接左递归 G3[S]： S→Aa|c
A→Bc|a B→Sb|b
间接左递归
2.3.3 和语言有关的几个概念 文法递归的作用：
用较少的产生式产生无穷多个句子，实现“用有穷表示无穷”。
直接推导举例
例1 文法G[E]： E →E+T|T T →T*F|F F →（E）|i
* T F * T*F F
例2 见P14
2.3.3 和语言有关的几个概念
2. 推导
设α0、α1、…αn均为(VT∪VN)*中的符号串，且有 α0α1α2…αn-1αn 则称以上序列是长度为n的推导，即α0可经过n步推导得到αn。
2.3 文法和语言的形式定义
2.3.1 文法的有关概念
1．终结符号 终结符号是组成语言的基本符号，如保留字、标识符、常数、 运算符、界限符等。终结符号是语言的不可再分的基本符号。终 结符号形成的集合记为VT。一般用小写字母表示。 2．非终结符号 非终结符号用来表示语言的语法成分（或语法范畴、语法单 位），例如“赋值语句”。非终结符号所形成的集合记为VN。一 般用大写字母来表示。 VT∩VN=
2.3.3 和语言有关的几个概念 P15
4.
句型
* * 设有文法G[S]，如果 S u ，且 u∈ (VT∪VN)
则称符号串u
为文法G[S]的句型。由规范推导(最右推导)得到的句型称为规范句型.
5.
句子
，且 uVT* ，则称符号串u为
* 设有文法G[S]，如果 S u
文法G[S]的句子。
由此可看出： 句型包含句子
前述内容回顾
· 编译程序 · 编译方式与解释方式的根本区别
· 编译程序的工作过程
· 编译程序的结构
· 编译程序的组织方式
· 编译程序的构造
第二章 文法和语言的基本知识
本章主要介绍形式语言理论中的一些最 基本的概念和基础知识，它是学习以后各章
节的基石。
本章内容简介
· 文法的形式定义 · 语言的形式定义 · 为语言构造文法与由文法推出语言 · 语法树及文法的二义性 · 文法和语言的分类
rammar)以及它的语义。 字母表是符号的有穷集，而符号构成了语言中的句子。 语法是结构规则的有穷集，这些规则定义了句子中符号 的合法上下文。 语义通常是操作规则的有穷集，这些规则定义了用该语 言编写的任何程序在某个计算机上执行的操作性效果。
2.2.1 字母表与符号串
1. 字母表
字母表是元素的有穷非空的集合。 字母表中的元素称为符号。 例如{a，b，……，y，z}，{0，1}等。 常用∑ 来表示 。 注意： 字母表中至少包含一个元素。元素可以是字母、数字 或其他符号。
【例1】设有文法G[N1]： N1→N N→ND∣D D→0∣1∣2
N1 =>N =>ND =>N2 =>D2 =>12 N1 =>N =>ND =>DD =>1D =>12 最右推导 最左推导 不是最左推导 也不是最右推导
N1 =>N =>ND =>DD =>D2 =>12
【例2】设有文法G[E]： E→E+T∣E-T∣T T→T*F∣T/F∣F F→（E）∣i
*
2.3.3 和语言有关的几个概念
P17
7
直接递归与间接递归
如果文法的产生式呈U→…U…形式，则称其为规则递归，也
称直接递归。（U为非终结符）
* 如果文法中有推导 U …U… ，则称其为文法递归，也称
间接递归。
所谓递归即，规则的左部或右部具有相同的非终结符。
*
2.3.3 和语言有关的几个概念
2.2.2符号串运算
符号串的连接 设x和y是符号串，则称xy是他们的连接。 例如：x=abc , y=1a 则 xy=abc1a , yx=1aabc 即 |x|=3, |y|=2, |xy|=3+2=5 注意：对任意一个符号串x 我们有εx = x ε= x
符号串集合的乘积 设A和B是符号串的集合，则A和B的乘积定义为 AB={xy | x∈A,y ∈B} 例如： A={a,b} B={c,d} 则AB={ac,ad,bc,bd} 集合的乘积是满足于x∈A , y ∈B 的所有符号串xy 所构成的集合。 注意： 1、对于任何集合A , 有{ε}A = A {ε}= A 2、 {ε}= Ø Ø≠ { }
=>(T+i)*i-F =>(F+i)*i-F =>(i+i)*i-i
2.3.3 和语言有关的几个概念 6. 语言
文法G[S]产生的所有句子的集合称为G所定义的语言，记为L（G[S]） L（G[S]）={u |