《自然语言计算机形式分析的理论与方法》读书笔记（3-1）
第三章 基于短语结构语法的形式模型（一）
最为广泛的是短语结构语法PSG
大佬合影！（http://blog.sina.com.cn/s/blog_72d083c70100o8m8.html）
（左：冯志伟；右：乔姆斯基；图源冯志伟文化博客）
3.1 语法的Chomsky层级
形式语法：
根据重写规则，可以将形式语法分为4类：
- 0型语法type 0 G：重写规则
ϕ→ψ ，其中ϕ 不能是空串 - 1型语法，即上下文有关语法CSG：
ϕ1Aϕ2→ϕ1ωϕ2 ，A为单个的非终结符 - 2型语法，即上下文无关语法CFG：
A→ω - 3型语法，即有限状态语法FSG：
A→aQ 或A→a ，其中A和Q为非终结符，a为终结符。可见由状态A转到状态Q，输出一个终结符a
语法的乔姆斯基层级：从0型语法到3型语法依次包含，即
形式语言理论是计算机科学的基础之一
3.2 有限状态语法和它的局限性
本节原文见冯志伟的文化博客http://blog.sina.com.cn/s/blog_72d083c70100pp86.html
分析英语词汇形态的状态图，图源见博客原文
适合分析黏着语（如日语）和屈折语（如英语词根的各种派生）
缺陷：
- 一些由非常简单的符号串构成的形式语言不能用FSG生成，如
{ab,aabb,aaabbb,...} - 镜像结构的句子如
if...then...等不能生成 - 不适合刻画自然语言的句法结构
- 只能说明语言中各个符号的前后顺序，不能说明层次，因此不能解释歧义
3.3 短语结构语法
3.3.1 上下文无关语法CFG
上下文无关语法的推导树：
-
节点∈Vn∩Vt -
根节点=S - 有子节点的节点一定是非终结符
- 从左向右排列的节点
A1，A2，A3…是节点A的子节点，则必有A→A1A2A3...是P中的规则
推导树，图源冯志伟文化博客http://blog.sina.com.cn/s/blog_72d083c70102e1ka.html
支配关系——层次：父子节点
前于关系——词序：两个节点之间没有支配关系，能在从左到右的方向上排序，左边前于右边节点
乔姆斯基范式
任何由上下文无关语法生成的语言，均可有以下两条规则生成： A→BC； A→a A,B,C为非终结符，a为终结符。此类句法都有二元结构，推导树都可以简化为二叉树
层次分析法：一个复杂的语言形式不能一下就分析为若干个单词，而要按照层次逐层分析，而且是二分的
我对图案构造的层次表达模型和语言的层次分析结果极为相似。不过我的模型缺点在于高层节点没有抽象性，只是子节点图案的简单集合，分布规律在模型中仍然是内隐的
3.3.2 上下文有关语法CSG
重写规则
上下文无关语法CSG的生成能力更强。
上下文无关语法CFG能够用乔姆斯基范式实现层次分析，因此更常用，被称为短语结构语法
0型语法的重写规则几乎没有什么限制，生成能力太强，会生成大量不合格的句子
语法和自动机的联系：
- 能被图灵机识别的语言——能用0型语法生成，反之亦然；
- 能被线性有界自动机识别——能用CSG生成，反之亦然；
- 能被后进先出自动机识别——能用CFG生成，反之亦然；
- 能被有限自动机识别——能用FSG生成，反之亦然
3.4 递归转移网络和扩充转移网络
有限状态转移图FSTD（节点为始、末、中间状态，边为终结符，如词或词类符号<N>等）能够识别有限状态语言，将之进行扩充，加入递归机制，得到递归转移网络RTN（边不仅为终结符，也可以为非终结符，如词组类型符号PP等，同时也表示相应词组的子网络名称，每个子网络都可以用一个单独FSTD表示），这样类似出入栈过程。
可是RTN对无法歧义无法处理。进一步扩充，如增加寄存器实现试探和回溯机制、增加转移前的状态检查机制、增加转移后动作执行等，得到扩充转移网络ATN。
ATN重度依赖句法分析、是过程性的而非描述性的、静态数据与动态数据常常混淆，不完全符合计算意义下知识组织的一般原则。
3.5 自顶向下分析法和自底向上分析法
自顶向下：从S开始选择合适的规则替换，并用规则的右边部分同句子单词 匹配，匹配到了就抹去该单词，记下规则，继续分析剩下的内容。如果分析不下去就回溯。
自底向上：读取语句移进栈，寻找合适的规则归约，直到栈中只有S，句子遗留部分为空，才算分析成功。过程中可能会有“归归冲突”和“移归冲突”，处理这类冲突是移进-归约算法的核心问题。
移进-归约算法本质上以自左向右的LR算法，标准LR算法是处理程序设计语言的，所以难以处理自然语言的歧义问题。