（接上文）
3. Introduction to Parsing
名词定义
有歧义的句子（ambiguous sentence）：一个句子对应有多个解析树。
本质歧义性（essential ambiguity）：一个句子对应多个解析树的语义是不同的。
虚假歧义性（spurious ambiguity）：一个句子对应多个解析树，语义都是相同的。
自顶向下（top-down）：从开始符号，逐步构建出整个语法树。
自底向上（bottom-up）：从终结符开始，逐步构建出整个语法树。
非确定性自动机（non-deterministic automaton，NDA）：可以同时执行多条备选方案的自动机。
不定向的（non-directional）解析：可以按任意顺序访问输入字符串，要求输入字符串一开始就在内存中。
定向（directional）解析：解析器逐个处理字符，从左到右，或从右到左。
解析森林文法（parse-forest grammars）：每个非终结符的名称中包含了匹配字符串的开始位置和长度，它与具体的解析树是一一对应的。
布尔值矩阵（boolean matrix）：元素值为1或0的矩阵。
内容总结
（下文无关语言）如果不包含循环解析，解析树的高度，与输入字符串的长度之间，是具有线性复杂度的。
如果包含循环，则可以是任意复杂度的。
短语结构文法的识别问题（recognition problem），是不可解的（unsolvable）。
但上下文无关文法的识别问题，是可解的。
上下文无关文法有一个性质，任何非终结符的推导过程，与其他的非终结符之间都是独立的，我们可以安全的合并两个不同的解析树。
上下文无关解析技术：
（1）自顶向下（top-down），自底向上（bottom-up）
（2）定向的（directional），不定向的（non-directional）
搜索技术：
（1）广度优先搜索（breadth-first search）
（2）深度优先搜索（depth-first search）
线性时间优化：
大部分搜索方法算法的时间复杂度是指数级的。
（1）对文法预分析，得到更多的信息，排除不合理的选择
（2）前瞻字符
字符串的解析过程，可以看成一个函数，它将给定的文法映射到了一个更确切的文法（parse-forest grammars）（或得到一个错误）。
上下文无法文法的解析问题，可以被转换成一个布尔值矩阵的相乘问题。
所以，要想有一个快速解析算法，必先有一个快速布尔值矩阵相乘算法。
4. General Non-Directional Parsing
名词定义
单位规则（unit rules）：形如 A -> B 的产生式规则。其中A，B为非终结符
乔姆斯基标准形式（Chomsky Normal Form，CNF）：产生式只能有两种形式，A -> a，或 A -> BC。其中A，B，C为非终结符，a为终结符。
内容总结
两种不定向（non-directional）解析算法：Unger’s method，CYK method。
Unger’s method 是自顶向下的，采用深度优先搜索，穷举输入字符的所有划分进行匹配。
对于包含 ε-rules 的文法，为了避免无效递归，记录下某个解析过程是否进行中。
CYK method（Cocke-Younger-Kasami method）是自底向上的。
它先构造一个表格，用来记录哪些非终结符，能产生哪些子串。
任何上下文无关文法，都可以转换成乔姆斯基标准形式（Chomsky Normal Form，CNF）。
（1）不包含单位规则（unit rules）
（2）不包含空串规则（ε-rules）
（3）限制了产生式右边的长度
转换方法：
（1）消除空串规则（ε-rules）
（2）消除单位规则（unit rules）
（3）对文法进行清理（clean up）
（4）把右边有多个非终结符的情况，通过引入新的非终结符，拆分成多条产生式。
转换成乔姆斯基标准形式（Chomsky Normal Form，CNF）之后，会减少一些原文法中的标识符，可以通过新的非终结符再添加回来。
表驱动解析（Tabular Parsing）方法，通过查表对结果进行了缓存，可以将算法从指数复杂度降为多项式复杂度。
5. Regular Grammars and Finite-State Automata
名词定义
识别器（recognizer）：根据（正则）文法来判断，输入字符串的哪一部分符合文法。
状态转移图（transition diagram）：节点表示状态（非终结符），边表示触发转移的终结符。
非确定性有限自动机（non-deterministic finite automaton，NFA），非确定性有限状态机（finite-state automaton, FSA）：包含有限个状态的自动机，接受同一个字符从某个状态有两条不同的转移。
确定性有限自动机（deterministic finite-state automaton，DFA）：包含有限个状态的自动机，对于相同字符，每个状态只有至多一个转移。
完全自动机（complete automaton）：所有转移（包括导致失败的）都被定义了的自动机。
内容总结
正则文法可以表示选择，重复，以及和子串合并，但是不能表示嵌套。
根据正则文法，生成一个状态转移图（transition diagram）。
与上下文无关文法不同的是，正则文法和有限自动机，是可以最小化的。
使用非确定性有限自动机来识别字符串，类似于迷宫的路径搜索，具有指数复杂度。
可以使用子集构造法（subset construction）将非确定性有限自动机转换成确定性有限自动机。
正则文法可以转换成正则表达式，反之亦然。
通常的转换路径：
（1）正则表达式
（2）正则文法
（3）非确定性有限自动机
（4）确定性有限自动机
（5）最小化的确定性有限自动机
正则语言的并集，交集，补集操作，结果仍然是正则语言。
左正则文法（left-regular grammar）与右正则文法（right-regular grammar）处理起来很不一样，
我们可以将左正则文法转换成右正则文法。
可以利用自动机，借助识别前缀的方式，实现快速文本查找。
（接后文）
网友评论