编译原理(同名14094).docVIP

2011春课程情况 ?? （1）考试题目来自教材的例题和习题、教材的辅助程序、实验内容几个方面； ???（2）题型：填空（20%）、简单作答（10%），文法题（10%）、词法分析（20%）、语法分析（20%）、代码优化10%、Lex/yacc程序10%。 ???（3）重点在计算题上，即形式语言、词法分析、语法分析和代码优化，将占60-70%。主要有 ???????? 形式语言（根据语言描述写上下文无关文法）（10分）， ???????? 词法分析（自动机、正则式、正则文法之间相互转化，自动机应用）（20分）； ???????? 语法分析部分是给出文法和待分析的串，按照某个分析方法构建分析表列分析过程（20分）， ????????????? 可能出现的分析方法有LL（1）、算符优先分析、LR（0）分析 ????????????? 左递归的消除、公共因子提取对文法进行改造 ?????????代码优化（10分）。给定一段程序（可能是中间代码形式的），进行优化或找出循环之类的题目。 ???????? Lex或Yacc程序简单设计（10） ??? (4)共有题目7道，时间100min； ????（5）具体考试时间、地点待后通知。 ? 1、? 给出如图所示NFA(?非确定自动机)等价的DFA ? ? ? 思路：子集划分方法。参考答案（矩阵表示） a b { i,1,2} S {1,2,3} A {1,2,4} B {1,2,3} A {1,2,3,5,6,f} C {1,2,4} B {1,2,4} B {1,2,4,5,6,f} D {1,2,3,5,6,f} C* {1,2,3,5,6,f} C {1,2,4,6,f} E {1,2,4,5,6,f} D* {1,2,3,6,f} F {1,2,4,5,6,f} D {1,2,4,6,f} E* {1,2,3,6,f} F {1,2,4,5,6,f} D {1,2,3,6,f} F* {1,2,3,5,6,f} C {1,2,4,6,f} E 2、? 构造正规式1(1|0)*101相应的DFA. 3、? 为正规式（ab）*a(a|b)构造NFA、DFA。 4、? （1）考虑正规表达式1（1|0）*101，构造可以生成语言L(r)的一个正规文法。 （2）考虑如图所示的NFA N,构造可以生成语言L(N)的 一个正规文法. ? ? 5、考虑如下文法G： S--1S|0S|1A A--0B|1B B--e (空串) (1)??? 试构造语言为L(G)的一个正规表达式。 (2)??? 试构造语言为L(G)的一个有限自动机。 6、构造产生如下语言的上下文无关文法： （1）{anbn|n0} （2）{wcwR|w由a,b组成的任意串} （3）{wwR|w由a,b组成的任意串} （4）{w|w由a,b组成的任意串且w与其逆串相等} (5) {w|w由a,b组成的任意串且w中a的个数是b个数的2倍} 7、考虑下面的文法： S--aS|aSbS|e e是空串的意思 这个文法是二义的，试给出串a a b的两个不同的： （1）?????? 分析树。 （2）?????? 最左推导。 （3）?????? 最右推导。 8、? 已知文法G[S]: ???? S--MH|a ???? H--LS|e???? e是空串的意思 ???? M--K|MBL ???? K--dML ???? L--bHf ???? ? 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 9、? 已知文法G[S]: ??? S--MBf ??? M--BbS|a ??? B--dMg|e??? e是空串的意思 ? ? 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 10、????????????????????????????????????????????????? 对于文法G[V]: ???? V--N|N[E] ???? E--V|V+E ??? N--i? ? ? (1)??? 构造G[V]的优先关系表，判断G[V]是否为算符优先文法。 ???????? (2)??? 分析输入串i[i+i+i]是否是G[V]的句子。 11、某语言的文法G(E)为： ?????????? E--aTd|e?? e是空串的意思 ?????????????????? T--Eb|ac|e??? ???????? （1）?????? 请证明G（E）不是LR(0)文法而是SLR(1)文法，请给出该文法的分析表。 （2）?????? 给出输入串aabdbd#的分析过程，并说明是否是G(E)的句子。 12、????????????