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

一、预测分析方法步骤

• 提取左公因子，消除左递归
• 判断文法是否为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#?

未完待续......?