编译原理试题及答案

课程测试试题（04A卷）I、命题院（部）：数学与计算机科学学院II、课程名称：编译原理III、测试学期：2006－2007学年度第1学期IV、测试对象：数计、国交学院计科专业2004级1、2、国交班V、问卷页数（A4）：3页VI、答卷页数（A4）：4页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、填空题（共30分，30个空，每空1分）1、典型高级程序设计语言编译系统的工作过程一般分为六个阶段，即词法分析、语法分析、语义分析、中间代码生成、、目标代码生成。编译阶段的两种组合方式是组合法和按遍组合法，这两种组合方式的主要参考因素都是的特征。2、Chomsky将文法按其所表示语言的表达能力，由高往低分为四类：0型，1型，2型，3型文法。其中，2型文法也称，它的所有规则α→β都满足：α∈，β∈((VN∪VT)*且，仅当β=ε时例外。3、现代编译系统多采用方法，即在语法分析过程中根据各个规则所相联的或所对应的语义子程序进行翻译的办法。该方法使用为工具来说明程序设计语言的语义。4、构造与NFAM等价的正规文法G的方法如下：（1）对转换函数f(A，a)=B或f(A，ε)=B，改成形如或的产生式；（2）对可识别终态Z，增加一个产生式：。5、代码生成要考虑的主要问题：充分利用的问题、选择的问题、选择的问题。6、设有穷自动机M=(K，，f，S，Z)，若当M为时，满足z0∈f(S，α)且z0∈Z，或当M为时，满足f(S，α)=P∈Z，则称符号串α∈*可被M所。7、符号表中每一项对应一个多元组。符号表项的组织可分为组织、组织、组织等。8、对于A∈ＶN定义A的后续符号集：FOLLOW(A)={a|S=*uAβ，a∈ＶT，且a∈，u∈ＶT*，β∈Ｖ+;若，则#∈FOLLOW(A)。也可以定义为：FOLLOW(A)={a|S=*…Aa…，a∈ＶT}。若有，则规定#∈FOLLOW(A)。9、基本块的定义：一个基本块是指程序中一个执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序或转移语句。在基本块范围内的优化称为。10、预测分析器由预测分析表、先进后出栈（用来存放分析过程的语法符号）和三部分组成。其中预测分析表是一个二维矩阵，其形式为M[A，a]，其中A∈VN，a∈VT或#。若有产生式A→α，使得a∈，则将A→α填入M[A，a]中。(书写时，通常省略规则左部，只填→α)。对所有的M[A，a]标记为出错。二、简述题（共20分，4个小题，每小题5分）1、简述将NFA转换为最小化DFA的步骤。2、简述静态存储分配、栈式存储分配和堆式存储分配的特点和主要用途。3、以表达式a:=b*(-c)+b/(-d)为例，简述常用的三种中间代码表示形式。4、简述判别文法Ｇ是否为LL(1)文法的步骤和将一个非LL(1)文法转换为LL(1)文法的方法。三、应用题（共50分）1、有文法G[S]：(12分)S→aAS|aA→SbA|SS|ba(1)证明aabbaa是文法的一个句子。(3分)(2)构造句子aabbaa的语法树。(3分)(3)指出该句子的所有短语、直接短语和句柄。(6分)2、对文法G[E']：(15分)E'→#E#E→E+T|TT→T*F|FF→P^F|PP→(E)|i(1)计算G[E']的FIRSTVT和LASTVT。(5分)(2)构造G[E']的算符优先关系表,并说明G[E']是否为算符优先文法。(5分)(3)给出输入串w=i+i#的算符优先分析过程。(5分)3、对以下基本块：（8分）A：=5B：=R+rT0：=A+BT1：=2*AT2：=B+AT3：=A+AX1：=T1+T2X2：=T0*T3（1）画出基本块的DAG图。(3分)（2）根据DAG结点原来的构造顺序重写四元式。(2分)（3）假设基本块出口后只有X1，X2还被引用，试写出优化后的四元式序列。(3分)4、对文法G[S’]：(15分)0)S’→S1)S→A2)S→B3)A→aAe4)A→a5)B→bBd6)B→b(1)试构造G[S’]的LR(0)项目集规范族DFA。(4分)(2)试构造G[S’]的SLR(1)分析表，并判断它是否为SLR(1)文法。(4分)(3)试用SLR（1）方法分析输入串aae#。(4分)(4)G[S’]是否为LR(0)、LR(1)和LALR(1)文法？为什么？(3分)课程测试试题（04B卷）I、命题院（部）：数学与计算机科学学院II、课程名称：编译原理III、测试学期：2006－2007学年度第1学期IV、测试对象：数计、国交学院计科专业2004级1、2、国交班V、问卷页数（A4）：3页VI、答卷页数（A4）：4页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、填空题（共30分，30个空，每空1分）1、典型编译过程一般分为词法分析、语法分析、语义分析、（并非所有的编译程序都包含此阶段）、代码优化、目标代码生成六个阶段，其中词法分析的任务是对构成源程序的字符串进行扫描和分解，识别出(如标识符等)符号；为代码生成阶段收集类型信息，并进行类型审查和违背语言规范的报错处理是的任务。2、文法是一些规则的有穷集合，它是以有穷规则集来刻划无穷集合的工具。文法的四元组表示G=（VN，VT，P，S）中，元素VN，VT分别是非空有限的。且二者交集为φ；P为产生式/规则集，是文法的核心部分；S∈VN，是文法的开始符号(或识别符)，它是一个非终结符，至少要在一条规则中作为出现。3、构造ＬＲ（０）项目集规范族的项目类型分为四种：形如A→α.aβ的、形如的待约项目、形如A→αBβ.的归约项目、形如S'→α.的。4、一个优先关系矩阵对应的优先函数；所表示优先关系唯一的矩阵不一定存在优先函数；当两个终结符对之间无优先关系时，可以将相应元素置出错信息，而使用却无法识别这种情况，不能准确指出出错位置。5、在编译程序中用符号表来存放语言中出现的有关的语义特征属性信息。程序设计语言中通用的标识符属性主要有如下几种：符号名、符号的、符号的存储类别、符号的、符号变量的存储分配信息及数组的内情向量等其它属性。6、如果文法G=（VN，VT，P，S）中不存在形如A→…BC…的产生式，其中B、C为非终结符，则称之为。在此基础上，如果a,b∈VT,a≡b,a≮b,a≯b至有一个成立，则称之为。7、分为三类：的机器语言代码；的机器语言代码；汇编语言（宏汇编）。8、在程序流中，一个循环必须具有以下性质：1），即序列中任意两点都可达，若只有一个结点，则有一条返回本身的回边；2），即从序列外某结点，有一条有向边指向它，或它为图中首结点。9、LR分析步骤：1）置输入指针ip指向输入串的第一个符号；令S是栈顶状态，a是ip所指向的符号;将#压入符号栈，将开始状态0压入状态栈；2）根据分析表重复执行如下过程：如果action[S，a]=Sj，则把入符号栈，把入状态栈，并使ip指向下一个输入符号；如果action[S,a]=rj，则从栈顶弹出第j条规则右部串长|β|个符号，把压入符号栈，将压入状态栈，并输出规则A→β；如果action[S,a]=acc，则分析成功，否则报错。10、过程(函数)是结构化程序设计的主要手段。调用与被调用过程两者之间的信息主要通过或参数来传递。参数分为，常用的参数传递方式有传地址、传值、传名等。二、简述题（共20分，4个小题，每小题5分）1、简述运行目标程序时所需空间的种类。2、简述算符优先分析算法的步骤和算符优先分析方法的优、缺点。3、简述代码优化的概念和分类，并列举出四种以上常用的代码优化技术。4、简述判别任意给定的一个上下文无关文法G[S]是否为LALR(1)文法的过程。三、应用题（共50分）1、有文法G[E]：(16分)E→T+E｜TT→T*F｜FF→(E)｜i(1)证明T+T*F+i是文法的一个句型。(3分)(2)构造型T+T*F+i的语法树。(3分)(3)指出该句型的所有短语、直接短语和句柄。(7分)(4)指出该句型的所有素短语和最左素短语。(3分)2、将下列条件语句翻译成四元式的中间代码形式：(6分)ifaborcdandefthens1elses23、有正规文法G[S]：(12分)S→aA|bBA→bS|bB→aS|a(1)构造对应的正规式R，使得L(R)=L(G)。(3分)(2)构造对应的NFA状态图，使得L(M)=L(R)。(3分)(3)将所得NFA确定化为DFA。(3分)(4)将所得DFA最小化。(3分)4、对表达式文法G[E]：(16分)E→E-T｜TT→T^F｜FF→(E)｜a(1)判断G[E]是否为LL(1)文法。若不是，改造为LL(1)文法。(8分)(2)构造预测分析表，并对输入串w=a-a^a#进行预测分析。(8分)课程测试试题（03A卷）----------------------以下为教师填写--------------------I、命题院（部）：数学与计算机科学学院II、课程名称：编译原理III、测试学期：2005－2006学年度第1学期IV、测试对象：数计学院计算机科学技术专业2003级1、2、3班V、问卷页数（A4）：4页VI、答卷页数（A4）：6页VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚）VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号）一、填空（30分）1、将编译过程的各阶段划分为前端或后端和将编译程序分遍的主要参考因素都是（）和（）的特征。2、（）是一种语法分析程序的自动构造工具，用它可以直接构造各种语言的语法分析器；而（）是一种词法分析程序的自动构造工具，用它可以直接构造各种语言的词法分析器。3、假设G[S]是一个文法,如有S*x,则称x是该文法G的（）；文法G产生的（）的全体称为该文法所描述的语言。4、所谓2型文法就是指（）文法，若用G=（VN，VT，P，S）表示它，则它要求G中的所有规则α→β都满足：α是（），而β属于（VNUVT）*。5、文法中形如U→U的规则称为（）规则；由不可达的非终结符或不可终止的非终结符作为左部的规则称为（）规则。在实用文法中一般不允许含有这两类规则。6、在用五元组表示的确定的有穷自动机DFAM=（K，V，F，S，Z）中，元素V表示字母表；元素S表示唯一的初态，它是状态集K的一个元素；元素F表示（）；元素Z表示终态集，它是状态集K的一个（）。7、语法分析方法分为自上而下与自下而上两类，自上而下的分析方法方要有递归子程序分析法和（）；而自下而上的分析方法主要有（）和LR分析方法。8、LR(0)项目集规范族中的项目可分为四类，它们是移进项目、（）、归约项目和接受项目。其中，接受项目是（）的一种特例。9、将非LL(1)文法转换为等价的LL(1)文法所采用的两种方法是（）和（）。但这两种方法并不能保证所有的非LL(1)文法都能转换为等价的LL(1)文法。10、通常局部优化是指基本块内的优化，所谓基本块是指程序中一顺序执行的语句序列，其中只有一个（）语句和一个（）语句。11、算符优先分析时，在句型N1a1N2…ai-1NiaiNi+1ai+1…ajNj+1aj+1Nj+2…中，寻找的最左素短语NiaiNi+1ai+1…ajNj+1中的终结符应满足下优先关系：（）、（）、（）。12、在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，这些信息集中反映了标识符的语义特征属性。符号表的功能可以归结为三个主要方面，即（）、作为上下文语义合法性检查的依据和作为（）的依据。13、根据优先关系矩阵计算优先函数可用迭代法或优先关系图法，但先关