语言及其文法
# 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)：
如果一个文法可以为某个句子生成多棵分析树， 则称这个文法是二义性的
例子：
可以采用消歧规则来消歧：
对于任意一个上下文无关文法，不存在一个算法， 判定它是无二义性的；但能给出一组充分条件， 满足这组充分条件的文法是无二义性的
➢满足，肯定无二义性 ➢不满足，也未必就是有二义性的
# 规范推导 规范句型（最右推导）
最左（最右）推导：在推导的任何一步α=>β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换
最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。
演示如下：最左推导、最右推导、不规范推导
做题时则可以根据语法树来写出：
# 0x6.作业
# 作业1
# 作业2
