欢迎来到天天文库
浏览记录
ID：33591709
大小：164.85 KB
页数：8页
时间：2019-02-27
《计算机编译原理b&k》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1．考察如下的文法G[]：→abcd→a试将其转换成等价的正则文法。分析：正则文法又称3型文法，其产生形式如：→y→r其中,∈VN，y,r∈VT。文法G[]是右线性文法，可以采用逐层分解的方法将其转化为3型文法。解答：逐层分解过程如图1.14所示。→abcd→a,→bcd→b,→cd→c,→d图1.14将右线性文法文法转化为3型文法的逐层分解过程其中带下划线的
2、产生式不符合正则文法的要求，所以进入下一步的转化。转化得到的等价的正则文法G1[]的产生式为：→a→b→c→d→a2．设文法G[]的产生式为：→a→b→a
3、→d→e→ε→f→ga)试证文法G是LL(1)文法b)用递归子程序的方法，构造文法G的自顶向下的句法分析程序。构造过程中可使用如下过程。Scan:调用词法分析程序读入下一个单词到token中。Erro
4、r:报错。解答：a)文法G[]各产生式的选择集合为：Select(→a)=FIRST(a)={a,f,g}Select(→b)=FIRST(d)={d,e,b}Select(→a→)=FIRST()={f,g}Select(→d)={d}Select(→e)={e}Select(→ε)=FOLLOW()={b,⊥}Select(→f)={f}Select(
5、→g)={g}∵各具有相同左部的产生式的选择集合交集为空。∴G[]是LL(1)文法。b)文法G[]可改写为：→a
6、b→a
7、→d
8、e
9、ε→f
10、g因此G[]的递归子程序方法的句法分程序所涉及的各程序为：主程序：Scan；call过程Siftoken=’⊥’thenAcceptelseError;过程S：iftokenin{a,f,g}thenbegincall过程A;matchacall过程B;endelseiftokenin{
11、d,e,b}thenbegincall过程B;matchb;end;elseError;过程A：iftoken=athenbeginmatch(a);call过程D;endelseiftokenin{f,g}thencall过程D;elseError;过程B：iftoken=dthenmatch(d);elseiftoken=ethenmatch(e);elseiftokenin{b,⊥}thenreturn;elseError;过程D：iftoken=fthenbeginmathch(f);call
12、过程D;endelseiftoken=gthenmatch(g);elseError;注意：这儿仅给出程序框架，具体实现可根据所使用的程序设计语言编程即可。3．对文法G[]→ab→a→c1）构造G[]的LR(0)项目集规范族及识别活前缀的DFA。2）G[]是LR(0)文法吗？若是，给出LR(0)句法分析控制表。分析：本题产生式的个数虽不多，但产生式右部有连续几个，为了正确区别某状态（项目集）是否已出现在规范族（状态集）中，将显式地
13、指出该项目集的核心项目，用‘*’标记。解答：1）G[]的LR(0)状态集如表4.20所示。表4.20G[]的LR(0)状态集状态T项目集输入符号下一状态*→·⊥1→·aba20→·aa2→·cc31*→·⊥⊥Accept*→a·b4*→a·42→·aba2→·aa2→·cc33*→c·R#3*
14、→a·b5*→a·54→·aba2→·aa2→·cc3*→a·bb6*→a·75→·aba2→·aa2→·cc36*→ab·R#17*→a·R#22）因为G[]的状态集中无不适定状态，所以G[]是LR(0)文法
此文档下载收益归作者所有
