Syntax Analysis
CFG
一个图样：
CFL（语言）:可以用cfg描述的（字符串的集合）-->本质歧义性、语句是否符合文法。
|
| 一个语言可以对应多种语法
V
CFG（语法）：
production（构成语法的核心）--->可以对于每条prod定义语义（semantic）
对于给定语句（字符串），可以用语法进行解析，最终结果为parse-tree
LR(k)是语法的性质。（大部分性质都是语法的，后面会解释）
解析过程--->left-most/right-most
PDA?
其实没有讲PDA，但可以看出后面的那个算法大致就是DPDA。
消除left-recursion
自动消除left-recursion可能会出现不合理的东西。（因为解析是语法相关的）
歧义性
语法歧义性：有串存在不同的parse-tree
语言歧义性：一般称为本质歧义性（inherent ambiguous）。该语言的任何语法均有歧义.
编译器要CFG做什么？
需要通过CFG定义的语义（semantic）来解析语句。
语义：一般是指对于CFG中某个production，我实际应该做些什么。
如后缀表达式就是输出后缀，三段码就是输出三段码。
通过这个目的可以看出，编译器使用CFG是语法相关的（grammer-independent)。
如果只给你语言，只能判断一个语句（字符串）是否合法。
而不能用之构建parse-tree，以及之后的解释（semantic）
因此大部分编译器的讨论均涉及具体的语法。而不谈语言。
（这个区别是很重要的，计算理论中比较喜欢谈语言而不是语法）
Top-down
递归遍历的方法
涉及回溯。非确定（如果考虑pda即为nondeterministic)
LL(k)
通过后面的k个input，对当前行动作出判断。
LL(1)
First/Follow函数
parse-table
实现算法事实上是一个PDA。
bottom-up
shift-reduce
涉及猜（nondeterminsitic).或者说回溯亦可。
LR(0)
这个是真正的"0"。构造出的GOTO甚至无法运行。
但collection和GOTO在后面会有用。
LR(1)
范式：
state
parse-table
ACTION：terminal怎么办？决定reduce还是shift
GOTO：nonterminal怎么办？决定reduce之后是什么
remark（非核心内容）:LR(1)的GOTO和LR(0)的GOTO不一样。
LR(0):terminal/nonterminal item-set
LR(1):nonterminal state
主要是概念上的区别吧。LR(1)中GOTO的部分职能交给了ACTION
SLR(1)
一种parse-table的求法。
（事实也包含了state的意义）
remark：关于LL和LR
(left->right)读 +
top-down--->决定left-most
(right->left)读 +
bottom-up--->决定right-most
这两种方法均是为了将原语法直接生成的PDA。优化成类似DPDA。
DPDA才是真正可预期的算法。但很多优秀的算法也是“非确定的“。如单纯形法。
原文：http://www.cnblogs.com/airsplay/p/3619885.html