基本概念
字母表
字母表Σ是一个有穷符号集合
- 符号：字母、数字、标点符号、……
【例】字母表
- 二进制字母表：{0，1}
- ASCII 字符集
-
字母表上的运算
字母表Σ相乘：{0，1} {a，b} = {0a，0b，1a，1b}
- 字母表Σ次幂：{0，1} 3 = {0，1} {0，1} {0，1} = {000，001，010，011，100，101，110，111}
- 字母表Σ闭包：{a，b，c，d} + = {a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc，……}
- 字母表Σ克林闭包：{a，b，c，d} = {*ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc，……}(闭包基础上多了个空串)
串
- 字母表Σ克林闭包中的每一个元素都称为是字母表Σ上的一个串
-
串上的运算
连接：x 和 y 的连接就是把 y 附加到 x 后面形成的串，记作 xy
- 【例】若 x=dog，y=house，则 xy=doghouse
- 空串ε是连接运算的单位元，可看作 1。对于任意串，εs=sε=s
- 设 x，y，z 是三个字符串，如果 x=yz，则称 y 是 x 的前缀，z 是 x 的后缀
幂：串 s 的 n 次幂就是将 n 个 s 连接起来
图中第一个规则表示：一个句子应该由一个名词短语连接动词短语构成。
- 图中第二个规则表示：一个名词短语应该由一个形容词连接名词短语构成。
从上面自然语言的例子中可以提取出文法的一些组成要素。
- 尖括号括起来的部分称为语法成分
- 未用尖括号括起来的部分称为语言的基本符号
因为该文法是用来描述句子的构成规则的，所以该文法的基本符号是单词；如果一个文法是用来描述单词的构成规则的，那么该文法的基本符号就是字母。
简而言之，文法就是一套语言规则。
文法的形式化定义
文法用大写字母 G 表示，把一个文法 G 定义为一个四元组
G=(VT，VN，P，S)
- VT：终结符集合
- 终结符 (terminal symbol) 是文法所定义的语言的基本符号，有时也称为 token
- 【例】上例中文法用来描述句子的构成规则，，所以该文法的基本符号是单词。VT={apple，boy，eat，little}
- VN：非终结符集合
- 非终结符 (non terminal) 是用来表示语法成分的符号，有时也称为 “语法变量”。因为可以用由它们推导出其他语法成分，所以叫做非终结符。
- 【例】上例中文法的 VN={<句子>，< 名词短语 >，< 动词短语 >，< 名词 >，……}
- VT∩VN=Φ，即 VT 和 VN 不相交；VT∪VN= 文法符号集，即 VT 并上 VN 构成文法符号集
- P：产生式集合
- 产生式 (production) 描述了将终结符和非终结符组合成串的方法
- 产生式的一般形式：α→β，读作α定义为β
- α∈(VT∪VN)+，且α中至少包含 VN 中的一个元素：称为产生式的头或左部
- β∈(VT∪VN)：称为产生式的体或*右部
- 【例】上例中文法的每一个规则都是一个产生式
- S：开始符合
- S∈VN。开始符号 (start symbol) 表示的是该文法中最大的语法成分
- 【例】上例中文法的开始符号 S 是句子。S=<句子>
产生式的简写
- 对一组有相同左部的α产生式：α→β1，α→β2，……，α→βnα→β_1，α→β2，……，α→βn_
- 可以简记为：α→β1|β2|……|βnα→β_1∣β2∣……∣βn_
- 读作：α 定义为 β1，或者 β2，……，或者 βn
- β1，β1，……，β1 称为 α 的候选式 (Candidate)
符号约定
为了避免总是要声明哪些是终结符，哪些是非终结符的麻烦。我们对符号的使用做一些约定。
| 符号 | 约定 | 例如 |
|---|---|---|
| 终结符 | 字母表中排在前面的小写字母；运算符；标点符号；数字；粗体字符串 | a，b，c；+，*；括号、逗号；id、if |
| 非终结符 | 字母表中排在前面的大写字母；字母 S，通常表示开始符号；小写、斜体的名字；代表程序构造的大写字母 | A，B，C；expr、stmt；E(表达式)、T(项) 和 F(因子) |
| 文法符号 | 字母表中排在后面的大写字母 | X，Y，Z |
| 终结字符串 | 字母表中排在后面的小写字母 | u，v，……，z |
| 文法符号串 | 小写希腊字母 | α，β，γ |
除非特别说明，否则第一个产生式的左部就是开始符号。即文法中第一个产生式的左部是该文法最大的语法成分。
语言的定义
推导与归约
- 给定文法 G=(VT , VN , P , S )，如果 α→β ∈ P，那么可以将符号串 γαδ 中的 α 替换为 β。
- 也就是说，将 γαδ 重写 (rewrite) 为 γβδ，记作 γαδ ⇒ γβδ。
- 此时，称文法中的符号串 γαδ 直接推导 (directly derive) 出 γβδ
简而言之，就是用产生式的右部替换产生式的左部
【例】推导与归约
- 从图中可以看到，从 <句子> 可以推导出little boy eats apple，逆过程就叫归约。
- 推导就是用产生式的右部替换产生式的左部
- 规约就是用产生式的左部替换产生式的右部
有了文法（语言规则），如何判定某一词串是否是该语言的句子？
- 句子的推导——从生成语言的角度
-
语言的形式化定义
由文法 G 的开始符号 S 推导出的所有句子构成的集合称为文法 G 生成的语言，记为 L(G)。即，L(G)= {w | S ⇒ w, w∈ VT }
-
文法的分类
-
0 型文法 (无限制文法 / 短语结构文法)
α→βα→β
无限制文法 / 短语结构文法 (Phrase Structure Grammar, PSG)
- ∀α→β∈P，α中至少包含一个非终结符∀α→β∈P，α中至少包含一个非终结符
0 型语言
上下文有关文法 (Context-Sensitive Grammar , CSG)
- ∀α→β∈P，|α|≤|β|∀α→β∈P，∣α∣≤∣β∣，即产生式左部的符号个数不能多于右部的符号个数
- 产生式的一般形式：α1Aα2→α1βα2 (β≠ε)α_1_Aα_2→α1βα2(β=ε_)，即非终结符 A 只有当它的上下文是α1α2 的的时候，才能替换为β。因此是上下文有关文法。
- 可以看出，CSG 中产生式右部不能是空串。即 CSG 中不包含ε- 产生式 (空产生式)
上下文有关语言 (1 型语言)
上下文无关文法 (Context-Free Grammar, CFG)
- ∀α→β∈P，α∈VN∀α→β∈_P，α∈VN，即产生式左部必须是非终结符
- 产生式的一般形式：A→βA→β，前文提到过符号约定非终结符为 A。即将 A 替换为β不需要考虑它的上下文。
上下文无关语言 (2 型语言)
正则文法 (Regular Grammar, RG)
- 右线型文法：A→wB 或 A→w，在 2 型文法基础上，对产生式右部进行限制，要么是一个终结符号串 w，要么是一个终结符号串 w 右边有一个非终结符 B
- 左线型文法：A→Bw 或 A→w，在 2 型文法基础上，对产生式右部进行限制，要么是一个终结符号串 w，要么是一个终结符号串 w 左边有一个非终结符 B
- 可以观察出，正则文法的产生式左部只能有一个非终结符
- 正则语言 (3 型语言)
- 由正则语言 (3 型文法)G 生成的语言 L(G)
-
四种文法之间的关系
逐级限制
- 0 型文法：α中至少包含一个非终结符
- 1 型文法 (CSG)：|α|≤|β|
- 2 型文法 (CFG)：α ∈ VN
- 3 型文法 (RG)：A→wB 或 A→w (A→Bw 或 A→w)
- 逐级包含
CFG 的分析树
- 根节点的标号为文法开始符号
- 内部结点表示对一个产生式 A→β 的应用，该结点的标号是此产生式左部 A 。该结点的子结点的标号从左到右构成了产生式的右部β
- 叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出 (yield) 或边缘 (frontier)
【例】分析树是推导的图形化表示
推导过程：E ⇒ - E ⇒ - (E) ⇒ - (E+E) ⇒ -(id+E) ⇒ - (id+id)
短语
- 给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语 (phrase)
- 如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语 (immediate phrase)
【例 1】短语与直接短语
- 直接短语一定是某产生式的右部
- 但产生式的右部不一定是给定句型的直接短语
二义性文法
如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的
【例】二义性文法
二义性文法的判定
对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的
- 满足，肯定无二义性
- 不满足，也未必就是有二义性的
若有收获，就点个赞吧
0 人点赞
