LL(1)分析法

• 构造不带回溯的自上而下分析算法
  • 消除文法的左递归性
  • 克服回溯

• 编译原理重点 LL(1)

  • L：表示从左向右扫描输入串
  • L：最左推导
  • 1：向前看1步

左递归的消除

• 直接消除在产生式中的左递归：
  • 如非终结符P的规则为：$P\to P\alpha |\beta$
    • 其中$\beta$不以$P$为开头

  • 编译原理重点 我们可以把$P$的规则等价的改写为如下的非直接左递归形式：

    • $P\to \beta P^{\prime }$
    • $P^{\prime }\to \alpha P^{\prime }|\epsilon$

      将左递归变为了右递归

• 编译原理重点 一般而言，假定$P$关于的全部产生式是：\($P\to P{\alpha }_1|P{\alpha }_2|\cdots |P{\alpha }_m|{\beta }_1|{\beta }_2|\cdots |{\beta }_n$\)

  • 消除$P$的直接左递归性即将规则改写为：\($\begin{array}{}P\to {\beta }_1{P}^{\prime }|{\beta }_2{P}^{\prime }|\cdots |{\beta }_n{P}^{\prime }\\ P^{\prime }\to {\alpha }_1{P}^{\prime }|{\alpha }_2{P}^{\prime }|\cdots |{\alpha }_m{P}^{\prime }|\epsilon \end{array}$\)
• 有的文法可能没有直接左递归，但也可能是左递归的：
• 一个文法消除左递归的条件：
  • 不含以$\epsilon$为右部的产生式
  • 不含回路：
• 消除左递归的算法：
  • 将文法$G$的所有非终结符按照某一种顺序排列，并逐个执行：
  • 
  • 化简所得到的文法，去除从开始符号出发永远无法到达的非终结符的产生规则
• 算法的注意事项：
  • 适用于：消除了$P\to P$产生式和不以$\epsilon$为右部的产生式文法
  • 第二步中所作的工作：
    • 若为直接左递归，则消除直接左递归
    • 若右部的最左符号是非终结符且序号大于左部的非终结符，则不进行替换
    • 若序号小于左部的非终结符，则将序号小的非终结符用其右部的串进行替换，然后消除新的直接左递归
    • 这样，每次替换的非终结符均为前面已经处理过的非终结符

消除回溯，提取左公因子

• 产生回溯的原因：推导时，若产生式存在多个候选式，选择哪个进行推导存在不确定性

• 编译原理重点 提取左公因子：

  

LL(1)分析条件

• 编译原理重点 如果一个文法是LL(1)文法，则满足：

  • 文法不含左递归
  • 对于文法中每个非终结符A的各个产生是的候选首符集两两不相交
    • 若$A\to {\alpha }_1|{\alpha }_2|\cdots |{\alpha }_n$
    • 则$FIRST({\alpha }_i)\cap FIRST({\alpha }_j)=\varnothing$
  • 对于文法中的每个非终结符A，存在某个候选首符集包含$\epsilon$，则$FIRST({\alpha }_i)\cap FOLLOW(A)=\varnothing$

#编译原理重点 FIRST

• $FIRST(\alpha )$：可以从$\alpha$推导得到的串的首符号的集合\($FIRST(\alpha )=\{a|a\stackrel{\ast }{\Rightarrow }a\cdots .a\in V_T\}$\)
• 算法：
  • 如果$X$是一个终结符号，那么$FIRST(X)=X$
  • 如果$X$是一个非终结符号，且$X\to Y_1{Y}_2\cdots Y_k$
    • 如果对于某个$i$，$\alpha$在$FIRST(Y_i)$中，且$\epsilon$在所有的$FIRST(Y_1)$、$FIRST(Y_2)$、$\cdots$、$FIRST(Y_{i-1})$中，则将a添加到$FIRST(X)$中
  • 如果$X\to \epsilon$是一个产生式，则将$\epsilon$添加到$FIRST(X)$中
• 主要看产生式左边
• 自下而上求

#编译原理重点 FOLLOW

• $FOLLOW(A)$：可能在某些句型中紧跟在A右边的终结符号集合\($FOLLOW(A)=\{a|S\stackrel{\ast }{\Rightarrow }\cdots Aa\cdots ,a\in V_T\}$\)
• 算法：
  • 将$\mathrm{\$}$添加到$FOLLOW(S)$中，其中$S$是开始符号，$\mathrm{\$}$是右端的结束标记
  • 如果存在产生式$A\to \alpha B\beta$，则$FIRST(\beta )$中除了$\epsilon$之外的所有符号都在$FOLLOW(B)$中
  • 如果存在$A\to \alpha B$或存在产生式$A\to \alpha B\beta$且$FIRST(\beta )$中包含了$\epsilon$（可以理解为同一种情况$A\to \alpha B$），则将$FOLLOW(A)$中的所有符号都放在$FOLLOW(B)$中
• 只看产生式右边
• 自上而下求