第2章 文法和语言的基本知识 2.1-2.4

例子：考虑一个文法
G＝({a, b}, {S}, S，P） 其中 P：SaSb ab。试推导其语言。 SaSb aaSbb a3Sb3 …… an-1Sbn-1 anbn 其语言为：L(G)={anbn |n>=1}
说明：
★ 只用一个产生式并不足以定义一个语法范 畴,在绝大部分情况下都需要用好几个产生式, 特别是需要含有递归的产生式(产生式左部的 符号直接在右部出现). ★ VN∩VT=Φ:即文法中的任意一个符号要么 为非终结符号,要么为终结符号.
A A1 A 2 A 3 ......

定理2.1 若A是符号串集合，则A*=(A*)* 。
证明 显然 A* (A*)* , 现证 (A*)* A* 任给符号串 x∈(A*)*，则存在n，使得 x∈(A*)n， x 必存在n个子串x1 ,…,xn ， 使得x= x1…xn ，且 xi∈A* (i=1,…,n)。 由xi∈A* ，必存在整数pi ,使得xi∈Api ， 令 n
句型、句子和语言
* ，其中 S 是开始符号， ∈ V* ，则称 若S 为文法G的句型。 * 特别地，若 S ，且 ∈ VT* ，则称 为 G 的 句子。 文法G所定义的语言，记作：
L(G)={|∈VT*，且S}
*
同一句型有不同的推导序列
设有文法G[N1]: N1→N N →ND|D D→0|1|2 则句子12可由三种不同的推导序列推导出来： (1) N1 N ND N2 D2 12 (2) N1 N ND DD 1D 12 可见，同一句型（句子）可以通过不同的推导 序列推导出来。

|x|= 2 |y|= 3 |z|= 5
|xy|=|x|+|y|

规范推导


定义2.5-句型、句子
x，则称x是文法G的句型； 设有文法G。若S
*
若S x，且x∈VT*，则称x是文法G的句子。

*
规范句型

由规范推导所得的句型称为规范句型。

定义2.6- 语言
由文法G生成的语言记为L(G),它是文法G的一切 句子的集合。

定义2.7-文法等价




每个结点都有一个标记，此标记是V的一个符号。 根的标记是S。 若一结点n至少有一个它自己除外的子孙，并且有 标记A，则肯定A∈VN。 如果结点n有标记A,其直接子孙结点从左到右的次 序是n1，n2，…，nk，其标记分别为A1，A2，…， Ak，那么A→A1A2…Ak一定是P中的一个产生式。


符号串的方幂


符号串集合及其运算




若集合A中的一切元素都是字母表上的符号串，则 称A为该字母表上的符号串集合。 合并：字符串集合A和B的合并A∪B={α|α∈A或 α∈B}。 乘积：字符串集合A和B的乘积AB={αβ|α∈A且 β∈B}。 显然{ε}A=A{ε}=A。 幂：An=An-1A=AAn-1（n>0），并规定A0={ε}。 正闭包：A+ =A1∪A2∪…∪An∪…。 闭包：A*=A0∪A+。 显然Σ*=Σ0∪Σ1∪Σ2∪…∪Σn ∪… 。 Σ*表示Σ上的所有有穷长的串的集合
第2章
文法和语言

一个程序设计语言是一个记号系统，它的完整 定义应包括两个方面:


语法 指一组规则，用它可以形成和产生一个合适的程序。 语义 静态语义 是一系列限定规则，并确定哪些合乎语法的程序是合 适的； 动态语义 也称作运行语义或执行语义，表明程序要做些什么， 要计算什么。

0型(无限制)：G=(VT,VN,S,P) 规则形式 ： , (VTVN)*, 并且至少含有一个非终结符号； 1型（上下文有关） ： A u u (V V )+, A u ，S 除外； 2型（上下文无关）：规则形式 ： A A VN， (VTVN)* ； 3型（右线性）： A B或 A （左线性） A B 或 A ， VT*， A,B VN
S a
A
b b A a
S
a
S
a
关于分析树的几点说明
1. 一个句型推导或分析用一棵树结构图示 出来，它反应了一个句型语法结构的层次。
2. 对于一个句子的多种推导（若文法是无二义 性的），采用各种推导过程，画出的分析树是 一样的。分析树并未描述推导过程，它是不同 推导过程的抽象共性。 3. 在书中，用画分析树的过程解释语法分析过 程，用分析树图解语法结构。
1. 2. 3. 4. 5. • • • • 符号串的连接 εy=yε=y 集合的乘积 {ε}A=A{ε}=A 符号串的幂运算 y0=ε y1=y y2=yy 集合的幂运算 A0={ε} A1=A A2=AA 集合A的闭包A*与正闭包A+ ∑的闭包∑*： ∑上所有符号串的全体 例如，若 ∑={a,b}， 则∑+={a,b,aa,ab,ba,bb,aaa,…} 则∑*={ε，a,b,aa,ab,ba,bb,aaa,…}= ∑0 U ∑+
+
文法对应的语言示例：
见课本p16，例2.7—2.9 S → 01 | 0S1 S → 0S | 1S | ε
A → yB
例
B → xB | x
S → aB | bA A → a | aS B → b | bS | | bAA aBB

2.1 文法和语言的定义
文法分类
2型文法(上下文无关文法)：如果对1型文法施加以下的限制，就得到2 型文法： G的任何产生式为Aβ, A∈VN,β∈(VN∪VT)*
这种文法意味着，每一规则左部只有一个非终结符，无需考虑该非终结 符在上下文中的出现情况。
总结3型：文法(正则文法)：如果对2型文法施加以下的限制，就得到3型文法： 右α,β其部G3称2∈中型的正、形文任A规V法3,何式文TB型称产∈）法仅为生V。文则N右式为, 法线为α为A,性Aβ规3∈文型αV法则αBT或|文B左β左|,法或β线部,者性或，仅A文者否法为B；Aα则非3|β型为,终文B2法结α型等|符β价文（于，法正A若规,式B规，∈则所V以N又,
VVVNN=,VV∪NT,∪PV三T=VФ个T表集VVP示=NT合==文{均{{N法为0NG,}非10的;}空N字;,有N母穷表集1或N合词,N汇表0, N1};
S=N。
2.1 文法和语言的定义
文法
文法产生式的其它表示法：
规则1：{a}表示a的0次或多次重复出现，即{a}表示ε或a或aa或aaa或 a…a；{a}mn 表示a的m到n次出现。
要求： （1）能根据文法分析其所产生的语言； （2）能根据语言构造其文法。
2.1 文法和语言的定义
根据文法抽象语言
文法 G={VN,VT,P,S}，其中： VN={<数>，<数字串>，<数字>}； VT={0,1,2,3,4,5,6,7,8,9}； P: <数><数字串> <数字串><数字串><数字>|<数字> <数字>0|1|2|3|4|5|6|7|8|9 S=<数>