编译原理2005期末考试试卷A

天津大学试卷专用纸学院专业班年级学号姓名共5页第1页2005～2006学年第1学期期末考试试卷《编译原理》（A卷共5页）（考试时间：2005年12月28日）题号一二三四五六七八成绩核分人签字得分一、单项选择题（共10分，每小题1分。）1．文法G所描述的语言是的集合。（）(a)文法G的字母表V中所有符号组成的符号串(b)文法G的字母表V的闭包V*中的所有符号串(c)由文法的开始符号推出的所有符号串(d)由文法的开始符号推出的所有终结符串2．有文法G[I]：I→I1|I0|Ia|Ib|Ic|a|b|c下列符号串中是该文法的句子的有（）①ab0②a0c01③aaa④bc10可选项有：(a)②③④(b)①(c)③(d)①②③④3．词法分析所依据的是（）(a)语义规则(b)构词规则(c)语法规则(d)等价变换规则4．如果L(M)=L(M’)，则M与M’（）(a)等价(b)M与M’都是二义的(c)M与M’都是无二义的(d)他们的状态数相等5．下面状态转换图接受的字集为（）XY0011(a)以0开头的二进制数组成的集合(b)以0结尾的二进制数组成的集合(c)含奇数个0的二进制数组成的集合(d)含偶数个0的二进制数组成的集合6．文法G[E]：E→T|E+TT→F|T*FF→a|(E)该文法句型E+F*(E+T)的直接短语是下列符号串的（）①(E+T)②E+T③F④F*(E+T)可选项有：(a)①③(b)②③(c)③④(d)③7.有限状态自动机能识别（）(a)上下文无关文法(b)上下文有关文法(c)正规文法(d)短语文法8.如果文法G是无二义的，则它的任何句子（）(a)最左推导和最右推导对应的语法树必定相同(b)最左推导和最右推导对应的语法树可能不同(c)最左推导和最右推导必定相同(d)可能存在两个不同的最左推导，但他们对应的语法树相同9．产生正规语言的文法为（）文法(a)0型(b)1型(c)2型(d)3型10．任何算符优先文法（）优先函数(a)有一个(b).没有(c)有若干个(d)可能有若干个天津大学试卷专用纸学院专业班年级学号姓名共5页第2页二、简答题（共30分，每题15分）1．试简单描述LL(1)，LR(1)，SLR(1)和LALR(1)的定义。并说明它们是怎么解决分析表中的冲突的。2．简要叙述词法分析的基本功能是什么？如果让你实现一个词法分析程序（独立的词法分析程序，不是语法分析的子程序），你将如何考虑？请简述你的设计方案（简述要点即可）三、推导证明题（共60分）1．试给出语言L(G)={anbmambn|n,m≥0}的上下文无关文法。（10分）2．构造正规式(a|b)*(aa|bb)(a|b)*的DFA。（写出步骤）（10分）天津大学试卷专用纸学院专业班年级学号姓名共5页第3页3．文法G[S]SaSb|PPbPc|bQcQQa|a①它是Chomsky哪一型文法？②它生成的语言是什么？③它是不是算符优先文法？请构造算符优先关系表证明之④文法G消除左递归，提取公共左因子后是不是LL(1)文法？请证明之。（20分）天津大学试卷专用纸学院专业班年级学号姓名共5页第4页4．二义性文法G[S]的终结符的优先级和结合性说明如下：(e)ELSE与最近的IF结合(f)；的优先级大于IF；(g)；的优先级大于ELSE；(h)优先级相同的符号符合左结合。请使用LR分析的基本思想，凭借上述条件，构造G[S]的LR分析表。请写出详细的构造过程。（20分）G[S]：SIFSELSESSIFSSS；SSa天津大学试卷专用纸学院专业班年级学号姓名共5页第5页四、附加题（10分）简单语言的文法G(VN,VT,P,)其中：VT={黑体小写字母表，标点符号，赋值号，运算符}VN={P,D,L,S,E,T,B}=PbeginD;SendDid:LLinteger|booleanSid:=E|ifBthenSEE+T|TTidBid|true|false1）试写出该文法的一个句子；2）该文法属于以下哪几种文法，不属于哪几种文法，请说明理由。a.上下文无关文法b.LL(1)文法c.SLR(1)文法