top-down parser

语法分析，通俗的讲其实就是给一个句子和一个语法，判断这个句子是否能够由这个语法生成出来，如果能，则给出生成的路径(或者生成树)

top-down parsing，自顶向下语法分析；在这种分析规则下最常用的语法分析算法是LL，即从左至右分析，每次分析都替换掉最左边的非终结符。

（LL：Scan input from Left to Right; Construct a Leftmost Derivation）

LL算法的基本组成

LL算法有四个组件：

输入缓冲区：待分析的句子，在进行分析前需要在句子的末尾添加一个"$"符号
栈：用于存放一些语法符号，栈底用"$"号标记，初始化将起始符S压入栈底。当栈为空时，分析完成。
分析表：表的第一行是终结符或者"$"符号，第一列是非终结符，表里的格子里存放相应的递推公式
输出流A：每次分析所使用到的推导公式

算法伪代码：

repeat
  Let X be the top stack symbol
  Let a be the symbol pointed to by ip(input pointer)
  if X is terminal or $ then
    if X = a then
      pop X from the stack and advance ip
    else error()
  else
    if M[X,a] = X -> Y_1...Y_k then begin
      pop X from the stack;
      push Y_k,...,Y_1 onto the stack, and Y_1 on top;
      output the production X -> Y_1...Y_k
    end
    else error()
until X = $ /*where the stack is empty*/

构建分析表

从上面的算法伪代码就能看出来，如果能构建出算法分析表的话，其实LL算法是比较简单的。

构建算法分析表的步骤：先计算出语法的FIRST以及FOLLOW，然后按照分析表构造算法进行构造

FIRST函数：
设 a 是语法中的一个符号，则FIRST(a)则是所有出现在 a 的最左边或者由 a 生成的字符串的最左边的非终结符的集合
注：若 $\alpha\Rightarrow\epsilon$ ，则 $\epsilon\in First(\alpha)$
FOLLOW函数：
设 A 是非终结符，则FOLLOW(A)是所有在任何形式的句子中直接出现在A的右边的非终结符的集合
注：若 $S\Rightarrow\alpha A$ ，则"$"属于FLLOW(A)

计算FIRST()的具体步骤：

如果X是终结符，则FIRST(X) = {X}
如果X是非终结符，
若X-> $\epsilon$ ，则 $\epsilon\in FIRST(X)$
若X ->Y_1...Y_k，则 $FIRST(X) = FIRST(Y_1...Y_k)$

$FIRST(X_1X_2...X_n) = FIRST(X_1)$
"+" $FIRST(X_2)$ ，if $\epsilon\in FIRST(X_1)$
"+" $FIRST(X_3)$ ，if $\epsilon\in FIRST(X_2)$
$\cdots$
"+" $FIRST(X_n)$ ，if $\epsilon\in FIRST(X_{n-1})$

计算FOLLOW()的步骤

若S是起始符号，则"$" 属于FOLLOW(S)
若 $A\to\alpha B\beta$ ，则 $FIRST(\beta)-\epsilon\subset FOLLOW(B)$
若 $A\to\alpha B$ 或者 $A\to\alpha B\beta, \epsilon\in FIRST(\beta)$ ，则 $FOLLOW(A)\subset FOLLOW(B)$

计算FOLLOW()算法的伪代码：

initialize FOLLOW(X) to empty set for all non-terminals X
place $ in FOLLOW(S), where S is the start symbol
repeat
for any production X ->X_1X_2...X_m
  for j = 1 to m
    if X-j is non-terminal then:
    FOLLOW(X_j) = FOLLOW(X_j) + (FIRST(X_{j+1},...,X_m)-{\epsilon});
      if FIRST(X_{j+1},...,X_m) contains \epsilon or X_{j+1}...X_m = \epsilon then
        FOLLOW(X_j) = FOLLOW(X_j) + FOLLOW(X)
until no modification are made to any FOLLOW-set

有了FIRST()和FOLLOW()后，就可以按照以下算法构建词法分析表：

1. Repeat Steps 2 & 3 for each production rule A -> α
2. Terminal a in FIRST(α)? Add A->α to M[A,a]
3.1 ε in FIRST(α)? Add A->α to M[A,b] for all terminals b in FOLLOW(A)
3.2 ε in FIRST(α) and $ in FOLLOW(A)? Add A->α to M[A,$]

LL(1)文法

如果一个文法的词法分析表没有冲突，即每个格子里的公式都不超过两个，那么就称这个文法是LL(1)文法。
L: Scan input from Left to Right
L: Construct a Leftmost Derivation
1: Use "1" input symbol as lookahead in conjunctino with stack to decide on the parsing action

LL(1)文法的属性：

文法不会有二义性或者左递归
一个文法是LL(1)文法当且仅当，A → α | β
其中 α 和 β 推到出的字符串不会以一个相同的终结符开始
并且 α 和 β 中有且仅有一者能够推导出ε

根据LL(1)文法的属性可以判断一个文法是否是LL(1)文法：

含有左递归递推公式的文法不是LL(1)文法，形如A → Aα | β
含有左公因式的文法不是LL(1)文法，形如A → αa | αb