基本概念
一. 字母表 (Alphabet)
字母表∑ 是一个有穷符号集合
符号：字母、数字 、 标点符号、…
例
- 二进制字母表：{ 0,1 }
- ASCII 字符集
- Unicode 字符集
1. 字母表上的运算
- 字母表∑ 和∑' 的 乘积 ( product)
∑ ∑' ={ ab|a ∈ ∑, b ∈ ∑' }
例
{0, 1} {a, b} ={0a, 0b, 1a, 1b}
- 字母表∑的n次幂 ( power)
∑ 的n 次幂.png
例
{0, 1}^3 = {0, 1} {0, 1} {0, 1}
= {000, 001, 010, 011, 100, 101, 110, 111}
字母表的n次幂：长度为n 的符号串构成的集合
- 字母表∑的正闭包(positive closure)
∑+ = ∑ ∪ ∑^2 ∪ ∑^3 ∪ …
例
{a, b, c, d } + =
{a, b, c, d,
aa, ab, ac, ad, ba, bb, bc, bd, …,
aaa, aab, aac, aad, aba, abb, abc, …}
字母表的正闭包：长度 正数 的符号串构成的集合
- 字母表∑的克林闭包(Kleene closure)
∑* = ∑^0 ∪ ∑^+ = ∑^0 ∪ ∑ ∪ ∑^2∪ ∑^3 ∪ …
例
{a, b, c, d }* =
{ε, a, b, c, d,
aa, ab, ac, ad, ba, bb, bc, bd, …,
aaa, aab, aac, aad, aba, abb, abc, …}
字母表的克林闭包：任意符号串（长度可以为零）构成的集合
2. 串 (String)
设∑ 是一个字母表，∀x∈∑*，x 称为是∑ 上的一个串（串是字母表中符号的一个有穷序列）串s的长度，通常记作|s|，是指s中符号的个数。
例
|aab| = 3
空串是长度为0的串，用ε（epsilon）表示 |ε| = 0。
- 串上的运算——连接
如果x和y是串，那么x和y的连接 (concatenation)是把y附加到x后面而形成的串，记作 xy。例如，如果 x=dog 且 y=house ，那么 xy=doghouse
空串是连接运算的单位元(identity)，即对于任何串s 都有，εs = sε = s
设x,y,z 是三个字符串，如果 x=yz ，则称y 是x 的 前缀 ，z 是x 的后缀。
- 串上的运算——幂
串s的幂运算
串s的幂运算.png
例： 如果s= ba，那么s^1= ba，s^2= baba ，s^3=bababa ， …
串s 的n 次幂：将n 个s 连接起来
二 文法的定义
自然语言的例子——句子的构成规则
句子的构成规则.png
文法的形式化定义 G = (VT, VN, P, S)
VT：终结符集合
终结符（terminal symbol）是文法所定义的语言的基本符号，有时也称为token。
例：VT = { apple, boy, eat, little }
VN：非终结符集合
非终结符 (nonterminal) 是用来表示语法成分的符号，有时也称为“ 语法变量”。
例：VN = { <句子>, <名词短语>, <动词短语>, <名词>, … }
VT ∩ VN = Φ
VT ∪ VN ：文法符号集
P: 产生式集合
产生式 (production) 描述了将终结符和非终结符组合成串的方法，产生式的一般形式：α→β 读作：α 定义为β。
α ∈ (VT ∪ VN)+，且α中至少包含VN中的一个元素：称为产生式的头 (head) 或左部 (left side)。
β ∈ (VT ∪ VN)* ：称为产生式的体 (body) 或右部 (right side)
例
P = {
<句子> → <名词短语><动词短语>,
<名词短语> → <形容词><名词短语>,
...
}
ps: 终结符集合与非终结符集合是不相交的，产生式是用于产生字符串的式子。
S：开始符号
S ∈VN 。 开始符号 (start symbol) 表示的是该文法中最大的语法成分，例：S = <句子>。
简化版本的用于表示算术两则运算（加乘）表达式的文法
简化版本的用于表示算术两则运算（加乘）表达式的文法.png
由于这是用于描述表达式的文法，因此表达式E是这个语法的最大成分。那么E就是此文法的开始符号而且此文法中也没有其他非终结符。因此最后只需要将产生式写出就能表示其文法。
- 产生式的简写
对一组有相同左部的α 产生式
α → β1, α → β2, … , α → βn
可以简记为：
α → β1 | β2 | … | βn
读作：α 定义为β1， 或者β2 ，… ， 或者βn 。
β1，β2，… ，βn 称为α 的候选式 (Candidate)
例.png
- 符号约定
-
下述符号是终结符
(a) 字母表中排在前面的小写字母，如 a、b、c
(b) 运算符，如 +、* 等
(c) 标点符号，如 括号、逗号等
(d) 数字0、1、 . . . 、9
(e) 粗体字符串，如id、if -
下述符号是非终结符
(a) 字母表中 排在前面的大写字母 ，如A、B、C
(b) 字母S。通常表示开始符号
(c) 小写、斜体的名字 ，如 expr 、stmt 等
(d) 代表程序构造的大写字母 。如E( 表达式)、 T( 项)和F( 因子) -
字母表中排在后面的大写字母（如X、Y、Z）表示文法符号（即终结符或非终结符）
-
字母表中排在后面的小写字母（主要是u、v、... 、z）表示终结符号串（包括空串）
-
小写希腊字母，如α、β、γ ，表示 文法符号串 （包括 空串)
-
除非特别说明，第一个产生式的左部就是开始符号
总结.png
重点概念：
文法符号：终结符或非终结符
文法符号串：包括空串
终结符号串：包括空串
三 语言的定义
自然语言的例子.png
推导(Derivations)和归约(Reductions)
- 直接推导
给定文法G = (VT, VN, P, S)，如果α→β ∈ P，那么可以将符号串γαδ中的α替换为β，也就是说，将γαδ重写(rewrite)为γβδ，记作γαδ => γβδ。此时，称文法中的符号串γαδ直接推导(directly derive)出γβδ。简而言之，就是用生产式的右部替换产生式的左部。
- 经过n步推导
经过n步推导.png
例.png
有了文法（语言规则），如何判定某一词串是否是该语言的句子？
语言规则.png
句型和句子
如果S=>*α，α∈(VT ∪VN)*，则称α是G的一个句型(sentential form)。一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串，如果S=>*w，w∈VT*，则称w是G的一个句子(sentence)。句子是不包含非终结符的句型。
例.png
语言的形式化定义
由文法G的开始符号S推导出的所有句子构成的集合称为文法G 生成的语言，记为L(G )。即
L(G)= {w | S =>* w, w ∈ VT*}
例子.png
语言上的运算
语言上的运算.png
三 文法的分类
Chomsky 文法分类体系
0型文法 (Type-0 Grammar)
1型文法 (Type-0 Grammar)
2型文法 (Type-0 Grammar)
3型文法 (Type-0 Grammar)
- 0型文法
- 无限制文法(Unrestricted Grammar) / 短语结构文法(Phrase Structure Grammar, PSG)
∀α → β ∈ P， α 中至少包含1 个非终结符。- 0型语言：由0型文法G生成的语言 L(G)
- 1型文法
- 上下文有关文法 (Context-Sensitive Grammar , CSG)
∀α → β∈ P，｜α｜≤ ｜β｜
产生式的一般形式：α1Aα2 → α1βα2 ( β ≠ ε )- 上下文有关语言（1 型语言）
由上下文有关文法 (1 型文法) G 生成的语言L(G )，CSG 中不包含ε- 产生式。
- 2型文法
- 上下文无关文法 (Context-Free Grammar, CFG )
∀α → β ∈ P ，α ∈ VN产生式的一般形式：A→β
例子：
S → L | LT
T → L | D | TL | TD
L → a | b | c | d |…| z
D → 0 | 1 | 2 | 3 |…| 9
- 上下文无关语言（2型语言）
由上下文无关文法 (2 型文法) G 生成的语言L(G )
- 3型文法
- 正则文法 (Regular Grammar, RG )
右线性(Right Linear)文法：A → wB 或 A → w
左线性(Left Linear)文法：A → Bw 或 A → w
左线性文法和右线性文法都称为正则文法
3型文法.png
- 正则语言（3型语言）
由正则文法 (3型文法) G 生成的语言L(G)，正则文法能描述程序设计语言的多数单词。
- 四种文法之间的关系
上述定义的4种语言类具有依次包含关系，即对于i=0，1，2，在不考虑空产生式时，i型语言都真包含i+1型语言。
- 逐级限制
0型文法：α 中至少包含1 个非终结符
1型文法(CSG)：｜α｜≤｜β｜
2型文法(CFG)：α ∈ VN
3型文法(RG)：A→wB 或 A→w (A→Bw 或A→w)
- 逐级包含
逐级限制.png
PS:在不考虑空产生式的基础上
四 CFG的分析树（2型文法）
正则文法可以描述程序设计语言中的大多数单词，但是它的能力有限它几乎不能描述程序设计语言中的句子构造。而上下文无关文法能描述大多数程序语言的构造，也是被讨论最多的文法。
分析树.png
根节点的标号为文法开始符号。
内部结点表示对一个产生式A→β的应用，该结点的标号是此产生式左部A。该结点的子结点的标号从左到右构成了产生式的右部β。
叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出(yield)或边缘(frontier)。
- 分析树是推导的图形化表示
给定一个推导 S => α1 => α2 =>…=> αn ，对于推导过程中得到的每一个句型αi，都可以构造出一个边缘为αi的分析树。
推导过程：E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)
分析树是推导的图形化表示.png
- (句型的）短语
给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语(phrase)。如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语 (immediate phrase)。
短语.png
例-产生式的右部不一定是给定句型的直接短语.png
- 二义性文法 (Ambiguous Grammar)
如果一个文法可以为某个句子生成多棵分析树，则称这个文法是 二义性的。
文法
文法.png
句型
句型.png
消歧规则.png
二义性文法的判定
对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的。
满足，肯定无二义性
不满足，也未必就是有二义性的
网友评论