编译原理期末大题步骤——例题

一、预测分析方法步骤

• 提取左公因子，消除左递归
• 判断文法是否为LL(1)文法
• 若是，构造预测分析表；否则，不能进行分析。
• 根据预测分析表对输入串进行分析

例子：

文法G[E]：                                            EE+T|T

TT*F|F

                                                             Fi|(E)                                  构造预测分析表。 

（1）消除左递归 

 VN排列为E,T,F

消除E的一切直接左递归：

        ETE'        TT*F        Fi

        E'+E'|ε    TF           F(E)

消除T的一切直接左递归：

        ETE'        TFT'        Fi

        E'+E'|ε    T^*FT'|ε   F(E)

F没有左递归

文法无左公因子。

所以，提取左公因子和消除左递归后的文法为：       

        ETE'        TFT'        Fi

        E'+E'       T^*FT'     F(E)

        E'ε           Tε

（2）判断改写后的文法是否为LL(1)文法：

1、求First集：

        First（E）={ i，( }

        First（E'）={ +，ε }

        First（T）={ i，( }

        First（T'）={ *，ε }

        First（F）={ i，（ }

2、求Follow集：

        Follow（E）={ i，( }

        Follow（E'）={ +，ε }
        Follow（T）={ i，（ }

        Follow（T'）={ *，ε }

        Follow（F）={ i，（ }

3、求Select集：      

        SELECT (E→TE') = First(TE') = { i, ( }

        SELECT(E'→+iE') = First (+TE') = { + }

        SELECT(E'→ε) = Follow(E') ={ #, ) } 

        SELECT (T→FT') = First(FT') = { i, ( } 

        SELECT(T'→*FT')= First(*FT') = { * }

        SELECT(T'→ε )=Follow(T')={ +, #, ) } 

        SELECT(F→(E)) = First((E)) = { ( } 

        SELECT(F→i) = First(i) = { i }

4、判定：

        SELECT(E'→+TE')  SELECT(E'→ε )= Φ

        SELECT(T'→*FT') SELECT(T'→ε ) = Φ 

        SELECT(F→(E) ) SELECT(F→i) =Φ

（3）构造预测分析表

构造预测分析表M的方法：

M是二维数组，元素是M［A，a］

其中A是非终结符，a是终结符或“＃”。

若aESELECT（A→a），则把A→a放入M［A，a］中。 （所有空白的M［A，a］表示出错。）

（4）预测分析输入串

  #i+i*I#

二、构造算符优先表步骤 

• 计算每个V的FirstVt，集和LastVt集
• 求优先关系​​​​​​​​​​​​​​

  • 求=关系

  • 求<关系：找……aB……， a<FirstVT（B）

  • 求>关系：找……Bc……， LastVT（B）>c

• 3、构造优先关系表
• 4、根据优先关系分析句子 

例子：

文法G[E]：

E`→#E#

E→E+T

E→T

T→T*F

T→F

F→P^F

F→P

P→(E)

P→i        

构造算符优先关系表

（1）计算FirstVt集和LastVt集：

（2）计算优先关系 

 （3）构造优先关系表

（4）分析句子 

#i+i# 

未完待续......