NLP-句法分析概述
句法分析概述
一. 句法分析概述：
定义：判断单词串是否属于某个语言(recognition)，如果是，则给出其（树）结构(parsing)
句法分析常见任务：
1). 判断输入的字符串是否属于某种语言
2). 消除输入句子中词法和结构等方面的歧义
3). 分析输入句子的内部结构，如成分构成、上下文关系等。
通常默认知道当前处理的文本的语言种类，着重的是任务2）、3）。
语言的描述：
1). 穷举法：把语言中的所有句子都枚举出来。
2). 文法描述：构造规则，定义语言，生成句子。
3). 自动机：构造自动机，用于识别针对某一语言的句子。
文法种类：
正则文法(RG)，上下文无关文法(CFG)，上下文相关文法(CSG)，无约束文法(PSG)
二. 移进规约算法：
CFG描述语言举例：
句子：老师被迟到的学生逗乐了
CFG规则：
1). S ➔ np vp 2). np ➔ n 3). np ➔ cs de 4). vp ➔ vp u
5). pp ➔ p np 6). np ➔ n 7). vp ➔ v 8). n ➔ 老师 | 学生 …
9). v ➔ 迟到 | 逗乐 … 10). p ➔ 被 … 11). u ➔ 的| 了 …
语法分析树：
主要处理策略：
1). 自底向上：从待分析字符串开头，逐步匹配CFG规则剪头的又不字符，直到S（相当于从底部向上构造语法分析树）。
2). 自顶向下：从规则S开始，需按照相应的规则，用左部替换又不，知道完全匹配为待分析字符串（相当于自上而下构造语法分析树）。
移进规约算法：
1). 数据结构：栈
2). 操作：
- 移进(Shift - sh)：从句子左端讲一个终结符移到栈顶
- 规约(Reduce - r)：根据规则，将栈顶的若干符号替换成一个符号
- 接受：句子中所有词语已移到栈中，栈中只剩下一个符号S，分析成功，算法结束
- 拒绝：句子中所有词语已移到栈中，栈中非只有一个符号S，无法继续规约，分析失败，算法结束
3). 冲突处理方式：回溯法
在算法的处理过程中，可能会出现既可以移进，也可以规约的情况：移进-规约冲突，这时有限进行规约，如果最终分析失败则返回尝试移进。
另外一种冲突是规约-规约冲突：可以用不同规则进行规约。这时有限制性排在前面的规则，分析失败则回溯顺次尝试。
4). 实例：
规则：1) S ➔ NP VP 2) NP ➔ N 3) NP ➔ CS de
4) CS ➔ NP V' 5) VP ➔ V NP 6) V' ➔ V V
句子：我 是 上帝 派 来 的
N V N V V de
分析过程：
5). 语法树：
