课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第9讲：语法分析——自上而下分析3。

第9讲 语法分析——自上而下分析3(预测分析程序)

预测分析程序的工作原理

预测分析程序构成
  • 总控程序，根据现行栈顶符号和当前输入符号，执行动作
  • 分析表$M[A,a]$矩阵，$A ∈ V_N,a ∈ V_T$是终结符或$’\sharp’$
  • 分析栈STACK，用于存放文法符号
预测分析过程

具体如下：

总控程序根据当前栈顶符号$X$和输入符号$a$，执行下列三动作之一：

  1. 若$X＝a＝’\sharp’$，则宣布分析成功，停止分析。
  2. 若$X=a \neq’\sharp’$，则把$X$从STACK栈顶逐出，让$a$指向下一个输入符号。
  3. 若$X$是一个非终结符，则查看分析表$M$。
    1. 若$M[X,a]$中存放着关于$X$的一个产生式，把$X$逐出STACK栈顶，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为$\varepsilon$，则意味不推什么东西进栈)。
    2. 若$M[X,a]$中存放着“出错标志”，则调用出错诊察程序ERROR。
总控程序实现
  • BEGIN
    • 首先把$’\sharp’$推进STACK栈，然后把文法开始符号推进STACK栈；
    • 把第一个输入符号读进$a$；
    • FLAG:=TRUE;
    • WHILE FLAG DO
    • BEGIN
      • 把STACK栈顶符号上弹出并存放在$X$中；
      • IF $X\in V_T$ THEN
        • IF $X= a$ THEN 把下一输入符号读进$a$
        • ELSE ERROR
      • ELSE IF $X=’\sharp’$ THEN
        • IF $X=a$ THEN FLAG:=FALSE
        • ELSE ERROR
      • ELSE IF $M[X,a]={X→X_1X_2…X_k}$ THEN把$X_k,X_{k-1},…,X_1$依次推进STACK栈
        • 若$X_1X_2…X_k=\varepsilon$，则不进行该操作
      • ELSE ERROR
    • END OF WHILE;
    • STOP/分析成功，过程完毕/
  • END

预测分析示例

依然考虑文法考虑文法$G(E)$

假设输入串$i_1\star i_2+ i_3$，利用分析表进行预测分析：

分析过程如下：

构造预测分析表

分析表$M[A,a]$的构造
  • 构造$\text{FIRST}(α)$和$\text{FOLLOW}(A)$
  • 构造分析表$M[A,a]$
分析表$M[A,a]$的构造算法

要构造$G$的分析表$M[A,a]$， 即确定每个产生式$A→α$在表中的位置

  1. 对文法$G$的每个产生式$A→α$执行第2步和第3步；
  2. 对每个终结符$a\in \text{FIRST}(α)$，把$A→α$加至$M[A,a]$中；
  3. 若$ε\in \text{FIRST}(α)$，则对任何$b\in \text{FOLLOW}(A)$把$A→α$加至$M[A,b]$中。
  4. 把所有无定义的$M[A,a]$标上“出错标志”。

具体例子：

FIRST：

FOLLOW：

预测分析表：

$LL(1)$文法与二义性
  • 如果$G$是左递归或二义的，那么，$M$至少含有一个多重定义入口。因此，消除左递归和提取左因子将有助于获得无多重定义的分析表$M$。
  • 可以证明，一个文法$G$的预测分析表$M$不含多重定义入口，当且仅当该文法为$LL(1)$的。
  • $LL(1)$文法不是二义的。

考虑如下文法$G(S)$:

提取左因子之后，改写成：

预测分析表为：