语言及其文法

1. 一些基本概念
- 字母表(Alphabet)
- 字母表上的运算
- 串(String)
- 串上的运算----连接
- 串上的运算----幂
2. 文法的定义
- 文法的形式化定义
- 产生式的简写
- 符号约定
3. 语言的定义
- 自然语言的例子 (自然语言的文法)
- 推导(Derivations) 和归约(Reductions)
- 句型和句子
- 语言的形式化定义
- 语言上的运算
4. 文法的分类
- 0型文法 (Type-0 Grammar)
- 1型文法 (Type-1 Grammar)
- 2型文法 (Type-2 Grammar)
- 3型文法 (Type-3 Grammar)
- 四种文法之间的关系
5. CFG的分析树
- 分析树是推导的图形化表示
- (句型的)短语
- 二义性文法(Ambiguous Grammar)

1. 一些基本概念

字母表(Alphabet)

字母表Σ是一个有穷符号集合
- 符号: 字母, 数字, 标点符号, ......
  
  例如:
  - 二进制字母表: {0, 1}
  - ASCII字符集
  - Unicode字符集

字母表上的运算

字母表 Σ₁ 和 Σ₂ 的乘积(product)
字母表 Σ 的n次幂(power)
字母表 Σ 的正闭包(positive closure)
字母表 Σ 的正闭包(positive closure)

串(String)

串上的运算----连接

串上的运算----幂

2. 文法的定义

文法的形式化定义

V_T : 终结符集合
终结符（ terminal symbol）是文法所定义的语言的基本符号，有时也称为token

例: V_T = { apple, boy, eat, little }

V_N : 非终结符集合
非终结符(nonterminal ) 是用来表示语法成分的符号，有时也称为“ 语法变量”

例: V_N = { <句子>, <名词短语>, <动词短语>, <名词>, … }

P: 产生式集合
产生式(production)就是文法规则
产生式的一般形式：α→β
读作： α定义为β

α ∈ ( V_T∪ V_N )⁺，且α中至少包含 V_N 中的一个元素：称为产生式的头(head ) 或左部(left side)

β ∈ ( V_T∪ V_N )^* : 称为产生式的体(body)或右部(right side)

V_T∪ V_N : 文法符号集 V_T∩ V_N = ?

S : 开始符号
S ∈ V_N 开始符号(start symbol ) 表示的是该文法中最大的语法成分

例： S = <句子>

产生式的简写

符号约定

下述符号是终结符
下述符号是非终结符
字母表中排在后面的大写字母（如X、 Y、 Z）表示文法符号（即终结符或非终结符）
字母表中排在后面的小写字母（主要是u、 v、 . . . 、 z）表示终结符号串（包括空串）
小写希腊字母，如α、 β、 γ，表示文法符号串（包括空串）
除非特别说明，第一个产生式的左部就是开始符号

3. 语言的定义

自然语言的例子 (自然语言的文法)

文法：
① <句子> → <名词短语> <动词短语>
② <名词短语> → <形容词> <名词短语>
③ <名词短语> → <名词>
④ <动词短语> → <动词> <名词短语>
⑤ <形容词> → little
⑥ <名词> → boy
⑦ <名词> → apple
⑧ <动词> → eat
单词串： little boy eats apple