欢迎来到天天文库
浏览记录
ID：52209471
大小：192.50 KB
页数：7页
时间：2020-03-25
《编译原理复习题 (3).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理复习题1.设G=（VN，VT，P，）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？答：一般形式为→a，ÎVN，aÎ(VN∪VT)*。若G是正则文法，则一般形式为→a或→a，、ÎVN，aÎVT（或→a，→a）。2.何谓二义性文法？试举一例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。例子：给定文法G[]：
2、→*
3、
4、a
5、b考察句子ab*，它有两棵不同的推导树，如下所示：3.试正确消除下述传递图的e弧，使其接收的语言不变。1－e-Se11110e，100ee+ABCDEFG答：74.试将下述程序段翻译成三地址形式的中间代码表示。①5+6´（a+b）;答::100:t1:=a+b101:t2:=6*t1102:t3:=5+t2②ØAÚ（BÙ（CÚD））;答:200:ifAgoto202201:gotoT202:ifBgoto204203:gotoF204:ifCgotoT205:goto206206:ifDgo
6、toT207:gotoF③forj:=1to10doa[j+j]:=0;答:300:j:=1301:ifj10gotoNEXT302:i:=j+j303:a[i]:=0304:goto301④while(a+b7、:goto100109:a:=a+1110:b:=b+1111:goto105112:⑤ifx>ythenx:=10elsex:=x+y;答:400:ifxygoto402401:goto404402:x:=10403:goto4057404:x:=x+y405:4.试判定下述文法G［］是否是LR（1）文法？为什么？→→a→a答：1）因为对文法G[]存在的句子aaa，有两棵不同的推导树，如图4.5所示。图4.5两棵不同的推导树所以该文法是二义性文法，G[]不是LR(18、)文法。2）可构造文法G[]的状态集，考虑增广文法G[]，如表4.29所示。表4.29文法G[]的LR(1)状态集状态T项目集输入符号下一状态0[→·⊥,Ù]1[→·,⊥]2[→·a,a]2[→·a,a]a31[→·⊥,Ù]⊥Accept2[→·,⊥][→·a,a]a4[→·a,a/⊥][→·a,a/⊥]a43[→a·,a]a#34[→a·,9、a]a#2[→a·,a/⊥]a/⊥#3到此不用继续计算，因为状态T4是不适定状态，对输入符a出现了“归约—归约”冲突，因此文法G[]不是LR(1)文法。5.对给定正则表达式b*（d10、ad）（b11、ab）+构造其NFAM。答:74.证明下面文法是SLR(1)文法，并构造其SLR分析表。E®E+T12、TT®TF13、FF®F*14、a15、b答：分析表如下所示：状态T项目集输入符号下一状态0*E’→·E⊥E1E→·E+TE1E→·TT2T→·TFT2T→·FF3F→·F*F3F→·aa4F→·bb51*E’→E·⊥⊥Accept16、*E→E·+T+62*E→T·⊥/+#2*T→T·FF7F→·F*F7F→·aa4F→·bb53*T→F·⊥/+/a/b#4*F→F·**84*F→a·#65*F→b·#76*E→E+·TT9T→·TFT9T→·FF3F→·F*F3F→·aa4F→·bb57*T→TF·⊥/+/a/b#3*F→F·**88*F→F*·#59*E→E+T·⊥/+#1*T→T·FF7F→·F*F7F→·aa4F→·bb574.构造下列正则表达式的确定性的有限状态自动机。aba(a17、b)*a答：5.文法G[E]的产生式为：E®E+T18、TT®T*19、E20、FF®I21、（E）①给出（I+I）*I的最左推导、最右推导及相应的推导树；②列出句型F+T*F的所有短语、简单短语和句柄。答：a)最左推导：EÞTÞT*EÞF*EÞ(E)*EÞ(E+T)*EÞ(T+T)*EÞ(F+T)*EÞ(I+T)*EÞ(I+F)*EÞ(I+I)*EÞ(I+I)*TÞ(I+I)*FÞ(I+I)*
7、:goto100109:a:=a+1110:b:=b+1111:goto105112:⑤ifx>ythenx:=10elsex:=x+y;答:400:ifxygoto402401:goto404402:x:=10403:goto4057404:x:=x+y405:4.试判定下述文法G［］是否是LR（1）文法？为什么？→→a→a答：1）因为对文法G[]存在的句子aaa，有两棵不同的推导树，如图4.5所示。图4.5两棵不同的推导树所以该文法是二义性文法，G[]不是LR(1
8、)文法。2）可构造文法G[]的状态集，考虑增广文法G[]，如表4.29所示。表4.29文法G[]的LR(1)状态集状态T项目集输入符号下一状态0[→·⊥,Ù]1[→·,⊥]2[→·a,a]2[→·a,a]a31[→·⊥,Ù]⊥Accept2[→·,⊥][→·a,a]a4[→·a,a/⊥][→·a,a/⊥]a43[→a·,a]a#34[→a·,
9、a]a#2[→a·,a/⊥]a/⊥#3到此不用继续计算，因为状态T4是不适定状态，对输入符a出现了“归约—归约”冲突，因此文法G[]不是LR(1)文法。5.对给定正则表达式b*（d
10、ad）（b
11、ab）+构造其NFAM。答:74.证明下面文法是SLR(1)文法，并构造其SLR分析表。E®E+T
12、TT®TF
13、FF®F*
14、a
15、b答：分析表如下所示：状态T项目集输入符号下一状态0*E’→·E⊥E1E→·E+TE1E→·TT2T→·TFT2T→·FF3F→·F*F3F→·aa4F→·bb51*E’→E·⊥⊥Accept
16、*E→E·+T+62*E→T·⊥/+#2*T→T·FF7F→·F*F7F→·aa4F→·bb53*T→F·⊥/+/a/b#4*F→F·**84*F→a·#65*F→b·#76*E→E+·TT9T→·TFT9T→·FF3F→·F*F3F→·aa4F→·bb57*T→TF·⊥/+/a/b#3*F→F·**88*F→F*·#59*E→E+T·⊥/+#1*T→T·FF7F→·F*F7F→·aa4F→·bb574.构造下列正则表达式的确定性的有限状态自动机。aba(a
17、b)*a答：5.文法G[E]的产生式为：E®E+T
18、TT®T*
19、E
20、FF®I
21、（E）①给出（I+I）*I的最左推导、最右推导及相应的推导树；②列出句型F+T*F的所有短语、简单短语和句柄。答：a)最左推导：EÞTÞT*EÞF*EÞ(E)*EÞ(E+T)*EÞ(T+T)*EÞ(F+T)*EÞ(I+T)*EÞ(I+F)*EÞ(I+I)*EÞ(I+I)*TÞ(I+I)*FÞ(I+I)*
此文档下载收益归作者所有
