预测分析程序

预测分析程序的工作原理

• 预测分析程序或LL(1)分析法
  • 总控程序
  • 分析表矩阵M[A,a]
    • \(A\in V_N\)
    • \(a\in V_T\)，终结符或结束符#
  • 分析栈STACK
    • 用于存放文法符号
• 预测分析程序的工作图：
• 总控程序根据栈顶符号X和当前输入符号a，执行下列三种动作之一：
  • 若\(X=a=\#\)：分析成功，停止分析
  • 若\(X=a\neq \#\)：匹配成功，让\(a\)指向下一个输入符号
  • 若\(X\)是一个非终结符，则根据分析表\(M\)
    • 推导：若M[X,a]中存放这关于\(X\)的一个产生式，将其对应的产生式右部符号串按照反序一一进栈
    • 出错：

分析表M[A,a]的构造

• 编译原理重点 构造的算法：

  1. 对于文法\(G\)的每个产生式\(A\rightarrow\alpha\)执行2或3
  2. 对于每个终结符\(a\in FIRST(\alpha)\)，将\(A\rightarrow \alpha\)添加至M[A,a]
  3. 若\(\varepsilon\in FIRST(\alpha)\)，则对于任何\(b\in FOLLOW(A)\)，将\(A\)添加至M[A, b]中
  4. 其他设置为Error