3.1.1 从语句中重新建立production tree是为了在production tree的结构中获得语义
二叉树只要叶子数一样，总结点数就一样，令叶子树为n，总结点数为2 * n - 1。
规则右边有且仅有两个结点：2 * n - 1
规则右边可以多过两个结点：小于 2 * n - 1（因为不需要那么多父亲结点）
规则右边有且只有一个结点：小于2 * Cu * n（因为一系列规则可能导致一个词增加常数个父亲结点（Cu-1个））
规则右边可以没有结点：小于 2 * Cn * Cu * n
3.1.2 歧义
有歧义的句子有多个production tree，有歧义的grammar会生成有歧义的句子。
但若多个production tree的语义一样，则这种歧义是spuriously ambiguous。
3.1.3 parse tree 的线性化
leftmost derivation：对parse tree先续遍历
rightmost derivation：对parse tree后续遍历
infix notation：先前n各子结点（再加括号），再父节点，再后剩余的子结点（再加括号）。如（左子节点） 父亲 （右子节点）
当n为1时为 left-corner derivation。
以上的方法线性化后，可以逆向求回 parse tree
3.2 Two Ways to Parse a Sentence
自顶向下 和 自底向上
3.3 Non-Deterministic Automata
Non-Deterministic Automata 若能产生结果，则比正确。
若不能产生结果，则死循环或者走到死路。
正确与否决定于control mechanism
构造constrol
（1）independent of the grammar,
（2）consult the grammar regularly
（3）use large tables precomputed from the grammar
（4）use tables computed from the input string
Constructing the control mechanism, including the tables, from the grammar is
almost always done by a program. Such a program is called a parser generator;
3.4 Recognition and Parsing for Type 0 to Type 4 Grammars
只要一个sentence是由0型grammar生成的，那么我们一定可以用程序将parse tree构建出来。
不能在有限的时间内判断一个sentence是否可以由0型grammar生成，但1型grammar可以。
3.5 An Overview of Context-Free Parsing Methods
3.5.1 方法可分directional和non-directional
3.5.2 方法可分为深度优先搜索和广度优先搜索
3.5.3 General directional method
3.5.4 大部分general的parsing算法需要指数时间，最好也需要3次方的时间。但有些线性时间的算法可以针对特定的grammar
限制NDA的选择到只有一个，就是deterministic automaton，它可达成线性时间。
3.5.5
There is only one deterministic top-down method; it is called LL.The first L stands for Left-to-right, the second for “identifying the Leftmost production”, as directional top-down parsers do.
There are quite a variety of deterministic bottom-up methods, the most powerful being called LR, where again the L stands for Left-to-right, and the R stands for “identifying the Rightmost production”.
3.5.6 Non-Canonical Methods
3.5.7 Generalized Linear Methods
使用广度优先搜索来处理不能造出deterministic automaton的情况
3.6 The “Strength” of a Parsing Technique
一种parsing技术是否更强，取决于他要求原有语法需要多少更改来适应这种parsing技术。
The stronger the parser is, the fewer restrictions the grammars need to obey and the “weaker” they can afford to be.
