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

2024-01-09 23:32:39

一、预测分析方法步骤

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

例子:

文法G[E]:????????????????????????????????????????????E\rightarrowE+T|T

T\rightarrowT*F|F

?????????????????????????????????????????????????????????????F\rightarrowi|(E)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 构造预测分析表。?

(1)消除左递归?

?VN排列为E,T,F

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

? ? ? ? E\rightarrowTE'? ? ? ? T\rightarrowT*F? ? ? ? F\rightarrowi

? ? ? ? E'\rightarrow+E'|ε? ? T\rightarrowF? ? ? ? ? ?F\rightarrow(E)

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

? ? ? ? E\rightarrowTE'? ? ? ? T\rightarrowFT'? ? ? ? F\rightarrowi

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

F没有左递归

文法无左公因子。

所以,提取左公因子和消除左递归后的文法为:? ? ? ?

????????E\rightarrowTE'? ? ? ? T\rightarrowFT'? ? ? ? F\rightarrowi

? ? ? ? E'\rightarrow+E'? ?? ? T^\rightarrow*FT'??? ?F\rightarrow(E)

? ? ? ? E'\rightarrowε? ? ? ? ? ?T\rightarrowε

(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')?\cap SELECT(E'→ε )= Φ

? ? ? ? SELECT(T'→*FT') \cap SELECT(T'→ε ) = Φ?

? ? ? ? SELECT(F→(E) ) \cap 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#?

未完待续......?

文章来源:https://blog.csdn.net/lerp020321/article/details/135490878
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。