语法分析方法综述

每一种语法分析方法都有相应的局限性，只有对于特定的文法才可以使用相应的语法分析方法。

• 自顶向下：推导 ANTLR4（成功案例）
  • 确定的自顶向下分析方法：LL(1)分析法
    • 递归下降LL(1)
    • 表驱动LL(1)分析-预测分析法
• 自底向上：归约 BISON（成功案例）
  • 优先分析法
    • 简单优先
    • 算符优先
  • LR分析法
    • LR(0) → SLR(1) → LR(1)
    • LALR(1) Bison

自顶向下的语法分析思想

确定的自顶向下语法分析思想：

• 从分析树的 顶部（根节点）向底部（叶节点） 方向构造分析树。
• 为文法开始符号S推导出词串w的过程
• 每一步推导中：
  • 替换当前句型中的哪个非终结符
  • 使用该非终结符的哪个候选产生式

策略：

• 非终结符的选择：最左推导
• 候选产生式
  • 根据输入流的下一个终结符，选择最左非终结符的某一个候选产生式
  • 不确定的自顶向下：穷举产生式
  • 确定的自顶向下：选择唯一可能推导出输入串w的规则进行推导

First()-串首（终结）符号集

同一非终结符的多个产生式，若右部的FIRST集无交集，则推导是确定的。

• 如果X是一个终结符号，那么$FIRST(X)=X$
• 如果X是一个非终结符号，且$X$ →$Y_1{Y}_2...Y_k$是一个产生式，其中$k\ge 1$；
  那么如果对于某个$i$，$a$在$FIRST(Y_i$)中且$\epsilon$ 在所有的$FIRST(Y_1)$, $FIRST(Y_2)$, …, $FIRST(Y_{i-1})$中，就把$a$加入到$FIRST(X)$中。
  （a理解为某个终结符）
• 如果$X\to \epsilon$是一个产生式，那么将$\epsilon$加入到$FIRST(X)$中。

Follow()-非终结符的后继（终结）符号集

任意句型中紧邻非终结符号X之后出现的中介符号a组成的集合。

• 将$放到$FOLLOW(S)$中，其中$S$是开始符号，而$是输入右端的结束标记。
• 如果存在一个产生式$A\to \alpha B\beta$，那么$FIRST(\beta )$中除 $\epsilon$之外的所有符号都在$FOLLOW(B)$中。
• 如果存在一个产生式$A\to \alpha B$，或存在产生式$A\to \alpha B\beta$且$FIRST(\beta )$中包含$\epsilon$，那么$FOLLOW(A)$中的所有符号都在$FOLLOW(B)$中。

SELECT（A →α）-产生式的可选集

（也就是对于这个产生式能不能填入M[A->α,α]的预测分析表单元格中）

LL(1)文法的判定与构造

定义：文法G是LL(1)的，当且仅当对每个$V_N$，A的两个不同产生式A → $\alpha$, A→$\beta$，满足$SELECT(A\to \alpha )\cap SELECT(A\to \beta )=\varnothing$
其中，$\alpha$, $\beta$不能同时推导出$\epsilon$
性质：确定的，无二义性的。

判定的步骤

• 对于左边部分有相同的非终结符，求出其SELECT集合根据定义判断

某些非LL(1)文法到LL(1)文法的等价变换

非LL(1)文法

• 若文法中含有左公共因子，则一定不是LL(1)文法
• 若文法中含有直接或间接左递归，一定不是LL(1)文法

非LL(1)文法→LL(1)文法的等价变换

• 提取左公共因子
• 消除左递归
  • 消除直接左递归法
  • 消除间接左递归法
    

LL(1)文法的分析-表驱动分析法

• 输入栈I：以串末端为底，栈内为未匹配的部分；初始状态为w#，w为要识别的串
• 分析栈S：推导过程中产生的句型未匹配部分；初始状态为#S
• 分析表M：若a$\in$SELECT(A→α)，则M[A,α]=(A→α)
• 输出：w的最左推导，或者报告语法错误

LL(1)分析中的错误处理

错误处理的两个任务

• 报错
  • 栈顶的终结符和输入符号不匹配
  • 非终结符A位于栈顶，面临的输入符号位a，但分析表的表项M[A,a]为空
• 错误恢复
  • 应急恢复
    
  • 短语层恢复