计算机编译原理c&k

《计算机编译原理c&k》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．试设计接收以a为头符号和尾符号，且中间可有任意多个符号a或b的确定的有限状态自动机M。分析：1）输入集合VT中只有2个符号a和b，即VT={a,b}。2）a为头符号和尾符号，因此输入串a是满足条件的。3）先用状态转换图的方式构造出满足条件的NFA。解答：1）状态转换图如图2.4所示。aa,b2_1aa3+a图2.4符合题意的不确定有限状态自动机M注意：δ(1,a)={3}不能少，不然输入串a不能被M接收。2）确定化M的状态转换表如表2.3所示。表2.3M的状态转换表Mab⊥1{2,3}2{2,3}{2}3{3}F确定化过程如表2.4所示。表2.4M的确定

2、化Mab⊥[1][23][23][23][2]F[2][23][2]对应的状态转换图如图2.5所示。aa[2+[23]_[1b[1]a[2[2]b图2.5M的状态转换图2．对如下的文法G[]:→uz→r

3、w→→y

4、ε→x

5、εa）指出文法G[]的所有可空非终结符，计算所有非终结符的FOLLOW集与FIRST集。该文法是LL(1)文法吗？为什么？b）改造文法G[]，给出与其等价的LL(1)文法G1[]，并给出相应的下推自动机选择表。解答：a)文法G[]的可空非终极符是

6、、、。各非终极符的FIRST集与FOLLOW集为：FIRST()={u}FOLLOW()={⊥}FIRST()={w}FOLLOW()={r,y,x,z}FIRST()={y,x,ε}FOLLOW()={z}FIRST()={y,ε}FOLLOW()={x,z}FIRST()={x,ε}FOLLOW()={z}该文法不是LL(1)文法，因为文法具有左递归的产生式：→r。b)消除左递归后得到等价文法G1[]为：→uz→w→r

7、

8、ε→→y

9、ε→x

10、ε各产生式的选择集合为：Select(→uz)=FIRST()={u}Select(→w)=FIRST()={w}Select(→r)=FIRST()={r}Select(→ε)=FOLLOW()=FIRST()∪FOLLOW()={x,y}∪{z}={x,y,z}Select(→)=FIRST()∪FOLLOW()={x,y,z}Select(→y)=FIRST()={y

11、}Select(→ε)=FOLLOW()={x,z}Select(→x)=FIRST()={x}Select(→ε)=FOLLOW()={z}∵具有相同左部的产生式的select集合不相交。∴G1[]是LL(1)文法。G1[]的下推自动机的选择表（表3.7）为：栈顶非终极苻输入符号动作uReplace(zu)wReplace(w)rReplace(r)x,y,zpopx,y,zReplace()yReplace(y)x,zpo

12、pxReplace(x)zpop表3.7G1[]的下推自动机的选择表3．考察文法G[]：（1）→b（2）→b（3）→da（4）→b（5）→ca（6）→c试判定G[]是LR(0)、SLR(1)、LALR(1)还是LR(1)文法？为什么？分析：这一类题目如果不能确定是哪一类文法，可先尝试用LR(0)项目构造状态集，以判定是LR(0)还是SLR(1)。若是SLR(1)的，则文法还是LALR(1)和LR(1)文法；若不是，则只能用LR(1)项目构造状态集，以判定是L

13、R(1)还是LALR(1)（当然只有是LALR(1)文法，才可能又是LR（1）文法）。解答：考虑引入产生式→⊥，则对增广文法G[]构造其状态集，如表4.30所示。表4.30文法G[]的状态集状态T项目集输入符号下一状态→·⊥10→·bb2→·bb21→·,⊥⊥Accept2→b·3→b·3→·dad4→·bb5→b·6→b·#23→·b

14、b2→·bb2→d·a