语言及其文法
# 0x1.基本概念
# 1.字母表(Alphabet)
字母表∑是一个有穷符号集合
➢符号:字母、数字、标点符号、… 字母表 (Alphabet)
例: ➢二进制字母表:{ 0,1 } ➢ASCII字符集 ➢Unicode字符集
# 2.字母表的运算
# 2-1.乘积(product)
$$ ∑_1∑_2 ={ab|a ∈ ∑_1 , b ∈ ∑_2 } $$
例: {0, 1} {a, b} ={0a, 0b, 1a, 1b}
# 2-2.幂(power)
$$ ∑_0 ={ ε }\ ∑_n =∑_{n-1} ∑ , n ≥ 1 $$
例: {0, 1}^3^ ={0, 1} {0, 1} {0, 1} ={000, 001, 010, 011, 100, 101, 110, 111}
# 2-3.正闭包(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, …}
# 2-4.克林闭包(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, …}
# 3.串(String)
设∑是一个字母表,∀x∈∑* ,x称为是∑上的一个串
串是字母表中符号的一个有穷序列。
串s的长度,通常记作|s|,是指s中符号的个数
➢例: |aab|=3
空串是长度为0的串,用 ε(epsilon)表示
➢|ε|= 0
# 4.串上的运算
# 4-1.连接
x和y的连接(concatenation) 是把y附加到x后面而形成的串,记作xy
➢空串是连接运算的单位元( identity),即,对于任 何串s都有,εs = sε = s
设x,y,z是三个字符串,如果 x=yz, 则称y是x的前缀,z是x的后缀。
# 4-2.幂
$$ s^0= ε,\ s^n = s^{n-1}s, n≥1 $$
例:如果 s =ba,那么s 1= ba,s 2=baba, s 3=bababa,…
# 0x2.文法的定义
例子:
文法的定义: $$ G = (V_T , V_N , P , S ) $$
# V~T~:终结符集合
**终结符(terminal symbol)**是文法所定义的语言的基本 符号,有时也称为token
例: VT = { apple, boy, eat, little }
# V~N~:非终结符集合
非终结符(nonterminal) 是用来表示语法成分的符号, 有时也称为“ 语法变量”
例: V~N~ = { <句子>, <名词短语>, <动词短语>, <名 词>, … }
# P :产生式集合
产生式( production)描述了将终结符和非终结符组合成串的方法产生式的一般形式: α→β
读作:α定义为β
α∈(VT∪VN) + ,且α中至少包含VN中的一个元素:称为产生式的头 (head )或左部(left side) β∈(VT∪VN) * :称为产生式的体(body)或右部(right side)
例子:
# S :开始符号
S∈V~N~。开始符号(start symbol)表示的是该文法中最大的语法成分
# 形式化定义:
# 简写:
# 符号约定:
终结符:
- 字母表中排在前面的小写字母,如 a、b、c
- 运算符,如 +、 *等
- 标点符号,如括号、逗号等
- 数字0、1、. . . 、9
- 粗体字符串,如id、if等
非终结符:
- 字母表中排在前面的大写字母,如A、B、 C
- 字母S。通常表示开始符号
- 小写、斜体的名字,如 expr、stmt等
- 代表程序构造的大写字母。如E(表达式)、T(项) 和F(因子)
# 0x3.语言的定义
例子:
# 1.推导和归纳
推导:
给定文法G=(VT , VN , P , S ),如果 α→β ∈ P,那么 可以将符号串γαδ中的α替换为β,也就是说,将γαδ **重写(rewrite)**为γβδ,记作 γαδ ⇒ γβδ。此时,称文法 中的符号串 γαδ **直接推导(directly derive)**出 γβδ
推导和归约:
# 2.句型和句子
句型:如果 S ⇒* α,α∈(V~T~∪V~N~) * ,则称α是G的一个句型 (sentential form)
一个句型中既可以包含终结符,又可以包含非终结符,也可能是空串
句子:如果 S ⇒* w,w ∈V~T~^*^ ,则称w是G的一个句子(sentence)
句子是不包含非终结符的句型
例子:
# 3.语言的形式化定义
语言的定义:由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)。
答案是无穷多个
例子:
# 4.语言上的运算
# *0x4.文法的分类
# 四种文法的关系
# 0型文法 (Type-0 Grammar)
# 1型文法 (Type-1 Grammar)
# 2型文法 (Type-2 Grammar)
# 3型文法 (Type-3 Grammar)
# 0x5.CFG的语法分析树
# 总览:
# 树的产出/边缘:
即所有根节点从左往右加起来。
从左到右读出叶子的标记而构成句型。树称为该句型的语法树。
# 短语和直接短语:
短语一般有多个!
例子:
# 句柄
一个句型的最左直接短语称为该句型的句柄(最左子串)
# 二义性文法 (Ambiguous Grammar):
如果一个文法可以为某个句子生成多棵分析树, 则称这个文法是二义性的
例子:
可以采用消歧规则来消歧:
对于任意一个上下文无关文法,不存在一个算法, 判定它是无二义性的;但能给出一组充分条件, 满足这组充分条件的文法是无二义性的
➢满足,肯定无二义性 ➢不满足,也未必就是有二义性的
# 规范推导 规范句型(最右推导)
最左(最右)推导:在推导的任何一步α=>β,其中α、β是句型,都是对α中的最左(右)非终结符进行替换
最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。
演示如下:最左推导、最右推导、不规范推导
做题时则可以根据语法树来写出: