欢迎来到天天文库
浏览记录
ID：33587974
大小：237.16 KB
页数：9页
时间：2019-02-27
《计算机编译原理a&k》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1．考察文法G[]，其产生式为：→
2、a→if()
3、if()else→0
4、11）试证文法G[]是二义性文法。2）试给出消除二义性规则，根据此规则改造文法G[]为G1[]，使L(G[])=L(G1[])，但G1[]是非二义性文法。分析：1）本题比较简单，只需找出文法G[]的一个二义性句子即可。2）本题实际上是要求解决所谓“悬挂else问题”。按通常程序设计语言的规定，消除二义性的规则是：一个else部分总是与没有els
5、e部分的最近的if语句相配对，即所谓的“最近原则”，这可以通过增加非终结符、修改和增加产生式来解决。解答：1）考虑G[]的句子if(0)if(1)aelsea，该句子有如下2棵不同的推导树，如图1.6和图1.7所示，因此它是二义性句子，文法G[]是二义性文法。if()elsea0if()1a图1.6句子if(0)if(1)aelsea的推导树（1）if()0if()else1aa图1.7句子if(0)if(1)
6、aelsea的推导树（2）2）要想实行“最近原则”，关键是将有else子句和无else子句的if语句区分开，出现在else前面的非终结符与无else的if后面的非终结符不同（非终结符后面的非终结符），因此可将G[]改写为G1[]：→
7、→if()else
8、a→if()
9、if()else→0
10、1这样对句子if(0)if(1)aelsea就只能有惟一的推导树，如图1.8所示。if()0if
11、()else1aa图1.8句子if(0)if(1)aelsea的推导树2．设文法G[]的产生式集合为：(1)→ab(2)→ε(3)→d(4)→ε(5)→c(6)→e(7)→ε(8)→f(9)→g(10)→ε(11)→a(12)→εa)试利用布尔矩阵的方法计算每个产生式的右部符号串的头符号集合FIRST(α)；b)试利用布尔矩阵的方法计算每个可空产生式12、>→ε的可空非终结符的后继符号集合FOLLOW()；c)给出每个产生式的选择集合Select（→α）；d)文法G[]是LL(1)文法吗?解答：a)观察各个产生式，立即可知该文法的所有非终结符都是可空的。文法中各符号之间的B关系记录在下面矩阵M中(表3.10)：Mabcdefg1111111111111表3.10关系B的矩阵M+然后利用Warshall算法求出上述矩阵的传递闭包M（表3.11）:+Mabcde13、fg11111111111111111+表3.11传递闭包M由上述矩阵可以知道：FIRST()={a}FIRST()={a,d}FIRST()={a,d,c,e}FIRST()={a,f,g}FIRST()={a}∴该文法各产生式右部的头符号集合为：FIRST(ab)={a}FIRST(ε)={ε}FIRST(d)={a,d}FIRST(ε)={ε}FIRST(c)={a,d,c}FIRST(e)={e}F14、IRST(ε)={ε}FIRST(f)={a,f}FIRST(g)={a,f,g}FIRST(ε)={ε}FIRST(a)={a}FIRST(ε)={ε}b)构造E关系，其矩阵Q如表3.12所示：Q11111表3.12关系E的矩阵Q用Warshall算法计算出的Q*如表3.13所示：Q*11111111111表3.13矩阵Q*构造F关系，矩阵P如表3.14所示：P<15、B>Abcdefg⊥11111111111111表3.14关系F的矩阵PQ*·P的结果如表3.15所示：Q*·PAbcdefg⊥111111111111111111111111111111表3.15Q*·P对应的矩阵∴各可空非终结
12、>→ε的可空非终结符的后继符号集合FOLLOW()；c)给出每个产生式的选择集合Select（→α）；d)文法G[]是LL(1)文法吗?解答：a)观察各个产生式，立即可知该文法的所有非终结符都是可空的。文法中各符号之间的B关系记录在下面矩阵M中(表3.10)：Mabcdefg1111111111111表3.10关系B的矩阵M+然后利用Warshall算法求出上述矩阵的传递闭包M（表3.11）:+Mabcde
13、fg11111111111111111+表3.11传递闭包M由上述矩阵可以知道：FIRST()={a}FIRST()={a,d}FIRST()={a,d,c,e}FIRST()={a,f,g}FIRST()={a}∴该文法各产生式右部的头符号集合为：FIRST(ab)={a}FIRST(ε)={ε}FIRST(d)={a,d}FIRST(ε)={ε}FIRST(c)={a,d,c}FIRST(e)={e}F
14、IRST(ε)={ε}FIRST(f)={a,f}FIRST(g)={a,f,g}FIRST(ε)={ε}FIRST(a)={a}FIRST(ε)={ε}b)构造E关系，其矩阵Q如表3.12所示：Q11111表3.12关系E的矩阵Q用Warshall算法计算出的Q*如表3.13所示：Q*11111111111表3.13矩阵Q*构造F关系，矩阵P如表3.14所示：P<
15、B>Abcdefg⊥11111111111111表3.14关系F的矩阵PQ*·P的结果如表3.15所示：Q*·PAbcdefg⊥111111111111111111111111111111表3.15Q*·P对应的矩阵∴各可空非终结
此文档下载收益归作者所有
