[Theory] Parsing Techniques 读书笔记
1. Introduction
名词定义
文法推断（grammatical inference）：给定一组句子，找出产生它们的语法结构。
内容总结
解析是根据给定的语法构造其线性表示的过程。
其反向问题（文法推断 grammatical inference）也是人们所关心的，给定一组句子，找出产生它们的语法结构。
2. Grammars as a Generating Device
名词定义
字母表（alphabet）：给定语言中，所有字符的集合
单词（word），句子（sentence）：字符串
语言（language）：字符串的集合
生成文法（generative grammar）：由 4 部分组成，非终结符（集合），终结符（集合），推导规则（集合），开始符号。
选择（alternatives选择）：文法中的“|”，表示选择。
下标 s（subscript s）：有下标 s 的终结符，表示开始符号。
句型（sentential forms）：文法生成最终字符串过程中的中间形式
产生式规则（production rules）：文法中的推导规则
产生图（production graph），语法图（syntactic graph）：描述字符串语法结构的有向图，顶点是非终结符或终结符，边表示一次推导（从非终结符指向终结符或非终结符）。
乔姆斯基谱系（Chomsky Hierarchy）：将文法的刻画能力进行分类
（0）短语结构文法（phrase structure grammar）
（1）上下文相关文法（context-sensitive grammar），等价于，单调文法（monotonic grammar）
（2）上下文无关文法（context-free grammar）
（3）正则文法（regular grammar），或称，有限状态文法（finite-state grammar）
（4）有限选择文法（finite-choice grammar）
上下文相关文法（context-sensitive grammar）：每条产生式，左边只有一个非终结符被替换为其他符号。
单调文法（monotonic grammar）：每条产生式的左边不能比右边符号多。
上下文无关文法（context-free grammar）：每条产生式，左边只能包含一个非终结符。
右递归非终结符（right-recursive non-terminal）：它可以产生以自己为结尾的字符串。
左递归非终结符（left-recursive non-terminal）：它可以产生以自己为开头的字符串。
自嵌入非终结符（self-embedding non-terminal）：它可以生成以自己为中间部分的字符串。
正则文法（(right-)regular grammar），有限状态文法（finite-state grammar）：产生式右边至多包含一个非终结符，且必须以该终结符结尾。
有限选择文法（finite-choice grammar）：产生式右边不能包含非终结符。
空串规则（ε-rules）：可以生成空串的产生式规则。
ε-free：任何一个产生式都不产生空串。
最左推导（leftmost derivation）：每次推导，将产生式最左边的非终结符替换成终结符
最右推导（rightmost derivation）：每次推导，将产生式最右边的非终结符替换成终结符
收缩（shrink）：在推导的过程中句型（sentential forms）变短。
原生符号（original symbol）：符号的推导过程中，用到的不同的产生式的不同部分。
原生句子（original sentence）：句子的推导过程中，用到了不同产生式的不同部分。
上下文无关语言的泵引理（pumping lemma for context-free languages）：如果上下文相关文法生成的句子比原生句子（original sentence）更长，则这个句子总是可以拆分为 5 个部分，u, v, w,x 和 y，且 u v^n w x^n y 仍然是符合该文法的句子（n ≥ 0）。
正则语言的泵引理（pumping lemma for regular languages）：任何足够长的正则语言中的句子，可以被拆分为 3 个部分，u, v 和 w，且 u v^n w 仍然是符合该文法的句子（n ≥ 0）。
属性文法（attribute grammars）：每条产生式根据右边计算左边非终结符的属性。
语法转换（transduction grammars）：每条产生式根据输入字符串，输出一个结果字符串。
内容总结
并不是所有的语言，都可以用文法来生成。
根据对角线法，我们总是可以找到（存在无穷多个）没有文法对应的语言。
短语结构文法（phrase structure grammar）的刻画能力是最强的，目前没有发现更强的刻画方式。
一个短语结构文法（phrase structure grammar）是否产生空语言（空字符串集），是不可判定的。
上下文相关文法，如果允许收缩（shrink），则等价于短语结构文法（无限制文法）。
包含 ε-rules 的单调文法，也等价于短语结构文法（无限制文法）。
上下文无关文法（context-free grammar）的语法图（production graph，syntactic graph）退化为了一棵语法树（production tree）。
任何上下文无关文法，都可以转换为 ε-free 的。
正则文法（regular grammar）的语法图，退化成了一条语法链（production chain）。
上下文无关文法，可能会包含几类无用（useless）产生式规则：包含未定义的非终结符，开始符号不可达到该产生式，不产生任何东西的产生式。
清理方法：
（1）自底向上从终结符开始，找到所有用得到的非终结符。
（2）自顶向下从开始符号开始，找到所有可达的产生式。
两个上下文无关语言的并集，仍然是上下文无关的。
但是，两个上下文无关语言的交集，却不一定是，至少是上下文相关的。
如果允许擦除符号（erase symbol），任何短语结构语言都可以由两个上下文无关语言交集得到。
上下文无关语言与正则语言的交集，仍然是上下文无关的。
正则语言的并集，交集，补集，仍然是正则语言。
有两种常见的语义分析技术：属性文法（attribute grammars），语法转换（transduction grammars）。
文法的能力指的是刻画能力。
威力更强的文法，可以刻画出更复杂的边界，用来断定哪些句子是否属于该语言。
所有词法正确的Java代码，可由正则文法生成。
所有语法正确的Java代码，可由上下文无关文法生成。
所有语义正确的Java代码，可由上下文相关文法生成。
所有总停机的Java代码，可由（无限制）短语结构文法生成。
所有Java代码，无法由任何文法生成。
乔姆斯基文法是一种采用有限的机制，生成无限句子集的方法。
上下文无关文法，其语法图是一棵树，因此某节点的语义总是可以由子节点归纳得出，这是它备受关注的原因之一。
（接后文）
