Unit 2 文法分类

文法的形式化定义

G = (V_T, V_N, P, S)

V_T : 终结符 (Terminal symbol)：基本符号（token）
V_N：非终结符 (Non-Terminal symbol)：语法成分的符号（语法变量）

V_T ∩ V_N = Φ， 文法符号集 = V_T ∪ V_N

P：产生式集合：描述将V_T与V_N组合成"串"的规则
S：开始符号（文法中最大的语法成分：特殊的非终结符，eg：语言的文法中S=<句子>）

• L(G)：G生成的语言 -> 由S推导出的所有句子集合（文法解决了无穷语言的有穷表示）

• 语言定义
  推导（Derivations）：生成语言
  规约（Reductions）：识别语言

直接推导、n步推导

• 句型 & 句子

句子是不包括“非终结符”的句型

句型更像一个类，句子是句型生成的一个Instance

文法分类：Chomsky

根据语言的产生式不同而划分：P = α → β

0型文法 (Unrestricted Grammer / Phrase Structure Grammer)

最基本的文法

• 只要求：α 至少包含一个V_N

1型文法 (Context-Sensitive Grammer)

在0型文法的基础上 对产生式P的右部(产出) 进行限制：

• 要求左部每个V_N（语法成分）必须有产出，一个语法成分不能生成了个寂寞

定义的形式有很多种：

1. 产生式集合 P={α → β} ，|α| <= |β|
2. α₁A α₂ → α₁ β α₂ (β != ε， ε 就是 NULL)

总结来说，就是，要求文法产生式符合这样一条规则：
每一个V_N（非终结符，就是语法成分）必须产出一个非空的β，即每个语法成分必须是有意义的，比如语法成分：<动词>必须产出一个实际的动词或动词短语来：上文 <A=动词>下文 -> 上文 β=eat 下文

由于对产生式右部不限制：同0型文法一样只要求至少有一个V_N，所以α → β中的α 能识别出带有上下文的“语句”

2型文法 (CFG：Context-Free Grammer)

在1型文法的基础上 对产生式左部(输入端) 进一步限制：

• 要求左部只能有且仅有一个V_N ： P = A → β

在一段语言中，只要识别到V_N（语法成分），无论上下文是什么，立刻执行产生式P

上下文无关文法可以用来描述大多数程序设计语言中的语法构造

3型文法（RG: Regular Grammer）

在2型文法的基础上对产生式右部再进一步限制

• 要求最多只能产出一个非终结符V_N，而且必须在一侧：P = A → Bβ | βB | β

根据左侧非终结符在左边还是右边，可分为左线性和右线性文法

正则文法可用于生成标识符， 或描述程序设计语言中的大多数单词，但生成能力有限，几乎描述不了句子构造

文法关系：

• 从0型文法到3型文法：是逐级限制的关系

分析树

推导过程中每得到一个句型α，都可以构造一个以α为边缘（“叶子”）的分析树

短语（Phrase）：
分析树每棵子树的边缘，就是一个短语

直接短语（Immediate Phrase）：
子树高度为2
（直接短语一定是某个产生式的右部，但产生式的右部不一定是直接短语）

• 二义性文法 (Ambiguous Grammer)：
  可以构造出多棵分析树

• 如何消除二义性：
  通过引入一些代价来改造二义性文法：

1. 引入新的非终结符 或 空产生式
2. 引入新的规则（else只匹配最近的if …）