第二章 形式语言理论

描述的1型语言为L1(G[S])={anbncn | n1}
3.2型文法(上下文无关)
若文法G=(VN,VT, P, S)中的每一条规则的形式为： A β 其中AVN , β(VN∪VT)* , 则该文法G为2型文法。相 应的语言称为2型语言。
例如：文法G=(VN,VT, P, S)，其中VN={A,B,S} VT={a,b}


1.0型文法
如果对于文法G，P中每个规则具有下列形式： α→β 其中α∈V+ ，β∈V*，则该文法G为0型文法。相应
的语言称为0型语言。
例如：文法G=(VN,VT, P, S)，其中VN={A,B,S} VT={0,1}
P={ S→0AB，1B→0，B→SA|01，A1→SB1，A0→S0B } 描述的 0 型语言为 L0(G[S])={ }
符号串及其运算
由字母表中的符号组成的任何有穷序列。
例如：0,00,10是字母表∑={0‚1}上的符号串 a,ab,aaca是∑1={a‚b,c}上的符号串

符号串中的符号是有序的，顺序不同,意义不同。
例如: ab和ba不同

不含任何符号的符号串称为空串，用ε表示。 符号串长度: 符号串中含有符号的个数。
例如：文法G： S→0S1， S→01
S0S1 00S11 03S13 … 0n-1S1n-1 0n1n L(G)={0n1n|n≥1}
文法G生成的每个终结符号串都在L(G)中，L(G)
中的每个串确实能被G生成。文法一旦确定，语言也
就唯一，语言可由不同的文法表示。
2.语法树
句子 主语 代词 They 系词 are 名词 连接词 students and 表语 名词 teachers 定语 前置词 of 冠词
则 AB = ab0,ab1,cde0,cde1
显然 {ε}A = A{ε} = A 注意:{ε}并不等于空集合{ }
4.符号串集合的方幂
设A是符号串的集合，则称An为符号串集A的方 幂，其中n是非负整数。 A0 ={ε} A1 = A A2 = A A An = AA......A(n个)
例如： X= {abc}
例如：They are students and teachers of the Physics
名词
the
Department.
名词
Physics
Department
它的结点由符号组成。根结点对应于开始符号。 只有非终结符号对应的结点有子结点。并且，一个 结点和它的子结点分别对应于文法中的一个产生式 的左部和右部。 作为识别句子的辅助工具，语法树可以表示句 子的结构。 直观地描述上下文无关文法的句型推导过程。 给定文法G=(VN,VT,P,S)，对于G的任何句型都能构 造与之关联的语法树。
的完整形式及推导。
2. 设有文法G[A1]: S → A B，A → a A | a，B → b B | b，写出该文法的完整形式及推导。
2.4．语言和语法
1.句型、句子和语言 设有文法G[S]，若符号串α是从开始符推导出来 的,即 S =>*α ，且α∈V*，则称α是文法G的句型。
若α仅由终结符组成,即 S =>*α ，且α∈VT*，则
对文法G中任何规则A，我们有A，即推导 的依据是规则。
2.3 文法的分类
对文法中的规则施加不同限制，将文法和语言
分为四大类：

0型文法（PSG）： 0型语言或短语结构语言。

1型文法（CSG）：1型语言或上下文有关语言。
2型文法（CFG）：2型语言或上下文无关语言。 3型文法（RG）：3型语言或正则（正规）语言。
VN,VT和P是非空有穷集。
VN∩VT=φ。
V=VN∪VT，V称为文法G的字母表。
VN={A} VT={0，1} P: A→ 0 | 1 | A0 | A1 S=A
例如：文法 G=(VN，VT，P，S )
2. 推导和直接推导
α→β是文法G的产生式，若有v，w满足： v=γαδ,w=γβδ, 其中γ,δ∈V* 则称v直接推导出w，或w直接归约到v，记作vw。
P={S→aB|bA, A→a|aS|bAA，B→b|bS|aBB } 描述的2型语言为L2(G[S])={x|x{a,b}+ 且x中a和b的 个数相同}
4.3型文法(右线性文法和正规文法)
若文法G=(VN,VT, P, S)中的每一条规则的形式为：
Aa或 AaB
其中A，BVN , aVT* , 则该文法G为3型文法。相应 的语言称为3型语言。
例如： a1=a a2=aa a0=ε
3.符号串集合的乘积
若集合A中所有元素都是某字母表上的符号 串，则称A为字母表上的符号串集合。

符号串集合A和B的乘积定义为: AB ={xy|x∈A且y∈B}，即AB是由A中的串x 和B中的串y连接而成的串xy组成的集合。
例如：集合A = ab,cde B = 0,1
是组成语言的基本符 号，是一个语言的不 可再分的基本符号， 通常用小写字母表示。
P(Production)：产生式（规则）集合。
S：开始符号或识别符号。
是一个非终结符，且 至少要在一条产生式 的左部出现。
P中产生式（重写规则）形如： A→α|β
其中A∈VN且至少含一个非终结符，α,β∈V*。

X0 ＝{ } ，X1 ＝{abc} ，X2 ＝ {abcabc}
5.符号串集合的正闭包
Σ+ = Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。
+ 表示上的除ε外的所有有穷长串的集合。
例如：设A={ a, b }，则： A+={ a, b, aa, ab, ba, bb, aaa, aab, …}
6.符号串集合的自反闭包
语法树的相关概念
结点：每个树的结点对应于一个符号。结点的名 字就是该符号。

边：两个结点之间的连线。 根结点：没有边进入的结点。 分支：某个结点向下射出的边和其结点称为分支。
末端结点：没有向下射出的边的结点成为末端结 点。在相对于句型的语法树中，末端结点可能是非 终结符号。
语法树的特征
例如: |abc|=3 | ε|=0
1.符号串的连接
设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy。
例如： x=ST，y=abu ，则 xy=STabu 显然εx = xε=x
2.符号串的方幂
把 符 号 串 a 自 身 连 接 n 次 得 到 的 符 号 串 an = aa…aa。
无需考虑A 在上下文中 的出现情况 产生式全部 是规定形式
3型文法
(右线性文法)
如何判断4种文法
1型文法：|β|≥|α|≥1，规则左部至少有一个非
终结符； 2型文法：规则左部是单个非终结符； 3型文法：看格式。
例3：试分析书中P22的例2.6、2.7、2.8、2.9、
2.10的文法。
练习： 1. 设有文法G[A]: A→yB，B→xB|x，写出该文法
语法：赋值语句由一个变量，后随一个赋值号
“＝”，其后面再跟一个表达式构成；
语义：首先计算语句右部表达式的值，然后把所得
结果送给左部变量中；
语用：赋值语句可用来计算和保存表达式的值。
形式语言
用一组数学符号和规则来描述语言的方式称为形
式描述，而把所用的数学符号和规则称为形式语言。

形式语言：只是从语法上研究语言。它是抽象的
将A替换成b 时，必须考 虑A的上下 文
(上下文有关文法)
α=r1Ar2，β=r1br2
A∈VN, α,β∈V* b∈V+
1型语言（上下 文有关语言）
2型文法
(上下文无关文法)
A→β，A∈VN ， β∈V* A→aB 或 A→a，
A,3型语言
a∈VT，正规文法
或 *
+ 若有v w 或 v=w， * 则记为v w，v广义推导出w，w广义规约到v（可
以包含0步推导）。
三种推导的比较

直接推导（）的长度为1。 直接推导序列（ +）的长度n≥1。 广义推导（ *）的长度≥0。
推导和规则的区别


形式上的区别：推导用“”，规则用“”。
称α是文法G的句子。
所有的句子一定是句型，句型不一定是句子。
例如：文法G[S]： S→0S1， S→01
S 0S1 00S11 000S111 00001111 句型：S，0S1，00S11，000S111，00001111 句子：00001111
语言：由文法G生成的语言记为L(G),它是文法G的一 切句子的集合,即 L(G)={x|S =>+ x，且 x∈VT* }
第二章

形式语言概论
语言成分


语言和文法
文法的分类 语言和语法 文法和语言的一些特性 分析方法简介
2.1 语言成分
对程序设计语言的描述是从语法、语义和语用
三个因素来考虑。
语法：是对语言结构的定义。
语义：是描述了语言的含义。
语用：则是从使用的角度去描述语言。
例1： 写出赋值语句 s＝2*3.1416*r*(r+h)的非 形式化的描述。
数学系统，用于模拟程序设计语言的语法，或者是 并不很成功地模拟自然语言（如英语的语法）。

形式语言理论是编译理论的重要基础，它主要研
究组成符号语言的符号串的集合及它们的表示法、 结构与特性。
字母表和符号

字母表:元素的非空有穷集合，记为∑。
例如：∑={0‚1} ∑1={a‚b,c}

字母表中至少包含一个元素。 字母表中的元素，可以是字母、数字或其他符号。 不同的语言有不同的字母表。 符号:字母表中的元素称为符号或字符。