编译原理期末大题步骤——例题
一、预测分析方法步骤
- 提取左公因子,消除左递归
- 判断文法是否为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#?
未完待续......?
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!