语法分析器 Parser

词法分析器-->output: 记号 --> 语法分析器 -->output: AST 抽象语法树

context-free 上下文无关

Top-down 自顶向下:

意思就是从production rules的开始符号开始出发，所以叫Top--down.

如果可以推导出input String 那么就算成功。底下的例子就是从E 先 尝试第一个Production

E - > T+E 然后再第二个Production。。。

Recursive Descent由于算法用到了Backtrack 效率有点差，所以需要线性时间的算法，引出了 LL(1)

Recursively Descent: 递归下降  也叫预测分析  Easy to implement.

Idea: 每个Non-Terminal 构造一个 分析函数， 失败的就backtrack。 

上面情况前看一个符号会发现有好几种情况。[上述没有使用前看符号的Recursive descent]

如果对上述使用LL(1)的话 我们需要使用Left-factor  因为上面情况前看一个符号会发现有好几种情况

某种意义说recursive descent = LL(0)

所以我们需要使用Left-factor before LL(1) 

递归下降 无限循环问题：  S---> Sa

一直进入S，需要使用Elimination left recursive.

Bottom-up parsing:  也叫LR parsing, 不需要Left Factorized.自底向上。First/Follow set

Shift-Reduce:

w is a string of terminals 因为 bottom-up parse 的right-most derivation in reverse性质。

左边是被parsed后的结果，右边是要parse的input。从右往左是parsing，从左往右是reverse order  derivation? 那么rightmost derivation的话 X->beta 却没有改变w，只能证明w是一个terminals.

Predictive Parsing:

deterministic

LL(1)分析算法： 从左向右读， 最左推导，用一个前看符合。 分析高效，Linear Time, Debug信息准确。Main: idea   Table Driven Algorithm. 

这里只前看一个符号，比如T看到哦 是个Int，然后就会很confusing。有2种possible情况

这样的话又要需要试错然后backtrack。。

需要Left-factorization:

用表把不同场景应该怎么parse记录一下

First/Follow sets

First: 如果能够从这个non-terminal x derive 出一个Production such that 第一个字母是a.

那么a就在x的firstset。

Follow: A不能够Derive出t, 但是t是A的production后的第一个字母。t in followset of(A)

这里还有一个重点： A --> e 表示A可以通过一系列move变成e=消失了。

Follow：

Look at where the symbol is used! Also: Follow(x) is subset of FollowB 炒鸡重要

For each non-terminal and token, there's only 1 procedure that could lead to success.

总结：

所以其实Parser的任务就是判断input的这个东西符不符合这个语言的production rules

要么我能够从production rules开始推导出你这个语句，可以你就是valid。[top down].

要么你从这个语句能够推导回我的production rule的起点：E. 那么你就是valid [bottom up]

然后中间各种predictive， 那些都是为了加速parsing的过程。

当然，最后要output出一个AST 语法树！！！