编译原理-求文法G的预测分析表

前言

为什么求预测分析表：为了消除回溯，前面做了许多准备。其中关键是FIRST集合和FOLLOW集合，它们两个组合，达到了预测候选式的目的。为了使计算机比较好处理，把它们的预测结果统计成一张二维表，这就是求预测分析表的原因 定义：M[A][a] 是一个二维数组，其中行A表示的是栈顶符号，a表示的读头下的符号（A为非终结符，a为终结符），它们存放的是当前状态下所使用的候选式（或存放出错标志，指出A不该面临a的输入）

预测分析程序的算法（栈顶为X，读入头下为a）

1）X = a = ‘#’：识别成功，推出分析程序（X为终结符） 2）X = a ≠ ‘#’：进行匹配，弹出X，读头后移（X为终结符） 3）X ≠ a：进行error处理（X是终结符） 4）若X是非终结符，则查询预测分析表M，若M[X,a]中有关于X的产生式，则弹出X，将产生式入栈；如果M[X,a]中是出错标志，则error处理

预测分析表求法

步骤 1）求出所有非终结符的FIRST集合，FOLLOW集合 2）求出所有产生式的SELECT集合 3）按规则填预测分析表 填表规则 根据FIRST集合，看该位置是填候选式还是出错标志（输入符号不存在于FIRST集合中，就是出错标志） 若要填候选式，根据SELECT集合的元素对应填写候选式

例子

题目：表达式文法为，E是开始符

E  →  E+T | T
T  →  T*F | F
F  →  i | (E)

解：

前期准备 1）消除P → P，ε 2）消除左递归，得到文法(点击查看如何)

1.E  →  TE
2.E  →  +TE | ε
3.T  →  FT
4.T  →  *FT | ε
5.F  →  i | (E)

正式开始求预测分析表 1）求出所有非终结符的FIRST集合，FOLLOW集合

非终结符：E、T、F、T、E

---------------FIRST(E)、FIRST(T)、FIRST(F)---------------
FIRST(E) = FIRST(T) = FIRST(F) = {i,(};     //  1. 3. 5.

---------------FIRST(T)---------------
FIRST(T) = {*, ε} ;      // 4.

---------------FIRST(E)---------------
FIRST(E) = {+, ε} ;      // 2.

非终结符：E、T、F、T、E
---------------FOLLOW(E)---------------
FOLLOW(E) = {
         
  #, )};    // 5.

---------------FOLLOW(T)---------------
A = FIRST(E) - {ε} = {+};    // 1.
B = FOLLOW(E) = {#, )};    // 1.
C = FOLLOW(E) = {
         
  #, )};

∴ FOLLOW(T) = A ∪ B ∪ C = {
         
  #, ), +};

---------------FOLLOW(F)---------------
A = FIRST(T) - {ε} = {*}
B = FOLLOW(T) = {
         
  #, ), +};
C = FOLLOW(T) = {
         
  #, ), +};

∴ FOLLOW(F) = A ∪ B ∪ C = {
         
  #, ), +, *};

---------------FOLLOW(T)---------------
FOLLOW(T) = FOLLOW(T) =  {
         
  #, ), +};

---------------FOLLOW(E)---------------
FOLLOW(E) = FOLLOW(E) = {
         
  #, )};

2）求出所有产生式的SELECT集合

SELECT(E  →  TE) = FIRST(T) = {i,(};
SELECT(E  →  +TE) = { + };
SELECT(E  →  ε) = FOLLOW(E) = {#, )};    // | 连接的，分开出来
SELECT(T  →  FT) = FIRST(F) = {i,(};
SELECT(T  →  *FT) = {*}
SELECT(T  →  ε) = FOLLOW(T) =  {#, ), +};
SELECT(F  →  i) = {i}
SELECT(F  →  (E) ) = {(}

3）按规则填预测分析表

其它

课件下载：

更多信息：