编译原理考试题

1、 正规文法又称 2、 对于无二义性的文法，规范归约是 3、 扫描器的任务是从 中识别出一个个 。4、 程序所需的数据空间在程序运行前就可确定，称为 管理技术。5、 编译过程中，语法分析器的任务是()。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构A、®@ B.®@®C、①②③ D、①②③④6、 文法G：EtE+T|T TtT*P|P P—(E)|i贝恂型P+T+1的句柄和最左素短语分别为 oA、P+T和iE、P和P+TC、i和P+T+i D、P和P7、 四元式之间的联系是通过 实现的8、 程序语言的单词符号一般可以分为 等等。9、下列 优化方法是针对循坏优化进行的。10、 若文法G定义的语言是无限集，则文法必然是 11、 文法G产生的 的全体是该文法描述的语言。12、 Chomsky定义的四种形式语言文法中，0型文法又称为 文法；1型文法又称为 文法。13、 语法分析最常用的两类方法是—和 分析法。14、 一个确定的有穷自动机DFA是一个 o15、 不属于乔姆斯基观点分类的文法。16、 一个文法所描述的语言是—；描述一个语言的文法是 。17、 语法分析是依据语言的_规则进行的，中间代码产生是依据语言的 规则进行的。19、过程调用时参数传递方式有 21、下列代码中 不可能是目标代码。A、汇编指令代码E、可重定位指令代码C、绝对指令代码D、中间代码22、一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。23、 有限自动机能识别 24、 汇编程序是将 程序改造成目标语言程序的翻译程序。25、 LR(k)文法 二义性的。A、都是 E、都不是 C、不一定都是26、 乔姆斯基方法的2型语言是这样一种语言，其产生式限制为 27、 局部优化是局限于一个_范围内的一种优化。TOC\o"1-5"\h\z28、 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 cA.正确E.不正确29、 乔姆斯基方法的3型语言是这样一种语言，其产生式限制为 30、 运算符与运算对彖类型不符属于 。31、 词法分析器的输入是 o32、 在下述的编译方法中，自底向上的方法有 ,自顶向下的分析方法有—°①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR(K)分析⑥SLR(k)分析⑦LL(k)分析®LALR(K)分析33、 对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 。A.正确 E.不正确34、 算符优先分析法每次都是对 进行归约。35、 编译时能进行的类型检査称为 o36、 规范推导的每一步总是用产生式右边符号串替换句型中 位置的非终结符号37、 语法分析器的输入是 ,其输出是 38、 每个文法都能改写为LL(1)文法。 39、 对于无二义性的文法，规范推导是 40、 描述语言L={ambn|n>m>l}的文法为 。41、 间接三元式表示法的优点为 42、 编译时能进行的类型检查称为 43、 文法G[S]：StxSx|y所识别的语言是 。44、 项目Atci•称为 ,其中AGVn,A不是开始符。45、 设有文法G[S]:S->S*S|S+S|（S）|a,该文法 二义性文法。A、是 E、不是 C、不一定46、 高级语言编译程序常用的语法分析方法中，LL分析法属于 分析方法。47、 有文法G：E-*E*T|TT~T+i|i句子2+5*3+3按该文法G归约，其值为_49、 形如A->a-Bp的项目为 项目。TOC\o"1-5"\h\z50、 活动记录的连接数据不包拾 。51、 高级语言编译程序常用的语法分析方法中，1ALR分析法属于 分析方法。52、 设a、b、c是文法的终结符，且满足优先关系a=・b和b=・c,贝9 。53、 词法分析器的输出是 。54、 对一个基本块来说， 是正确的。55、 词法分析所依据的是 。56、 句型是由 推导出的符号串。57、 如果文法G是无二义的，则它的任何句子a 。58、 算符优先文法与算符优先函数的关系的描述中正确的是（）。59、 一个句型中称为句柄的是该句型的最左 。60、 描述一个语言的文法是（）61、 下列 优化方法不是针对循坏优化进行的。A、强度削弱 E、删除归纳变量 C、删除多余运算 D、代码外提62、 更动一张 表很困难。63、栈式存储分配申请和释放存储空间遵守 原则。TOC\o"1-5"\h\z64、 所谓自上而下分析法是指 。65、 所谓语法制导翻译方法是 = ，66、 确定的有穷自动机是一个 ,通常表示为 。67、规范归约中的可归约串是指 ；算符优先分析中的可归约串是指 68、 编译程序在逻辑上由 、= 、语义分析、中间代码生成、代码优化和目标代码生成六部分组成。69、 不可能是目标程序。70、 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 71、 一个名字的属性包拾 和 o72、 正规式的读作 o74、 编译程序的各个阶段的工作都涉及到 和 75、 文法用来描述语言的语法结构，它由如下4个部分组成：文法终结符集合、文法非终结符集合、 和文法开始符号。77、已知文法G[E]：EtE+T|TTtT*F|FFt(E)Iid该文法终结符集合Vt= ,文法非终结符集合Vn= ,该文法在乔姆斯基(Chomsky)文法分类属于 文法。79、假设G是一个文法，S是文法开始符号，如果S=>*>x,则称x是该文法的一 。81、 优化时，节省一条指令MOVRPM,节省的指令代价为 A、0E、1 C、2D、382、 采用 语法分析时，必须消除文法的左递归。83、 在状态转换图中，结点代表 ，用圆圈表示。84、 若源程序是高级语言编写的，目标程序是 语言的程序，则相应的翻译程序称为编译程序。85、 常用的两种动态存贮分配办法是 分配和 分配。86、 翻译方案和语法制导定义不同的是它的 (而不叫语义规则)放在括号{}内，并且可以插在产生式 的任何地方88、 所谓最左推导是指： 89、 上下文无关文法的可以用 表示，其形式为 。TOC\o"1-5"\h\z90、 后缀式ab+c+d*e-所表达的式子为 >91、 常用的两种动态存贮分配办法是 分配和 分配。92、 LL（K）文法中，第一个L表示 ,第二个L表示 K表不 °93、 一个上下文无关文法所含四个组成部分是 94、 对于文法G,仅含终结符号的句型称为 。95、 设有文法G[E]：EtE+T|E-T|TTtT*FIT/FIfFt（E）|iTOC\o"1-5"\h\z该文法句型E+T*F的句柄是 。96、 后缀式ab+c+d*e-所表达的式子为 。97、 文法符号的属性有两种，一种称为 属性，另一种称为 属性，S属性定义是指仅使用 属性的语法制导定义。98、 LR（0）项目和LR（1）项目的区别在于 o99、 紧跟在条件转移语句后面的语句是基本块的 语句。100、 若二个正规式所表示的 相同，则认为二者是等价的。101、 仅含终结符的句型称为 o102、 编译方式与解析程序的根本区别在于是否生成目标代码。 （）103、 规范归约和规范推导是互逆的两个过程。 （）104、 一个上下文无关文法的开始符号可以是终结符或非终结符。 （）105、 逆波兰表示法表示表达式时无需使用括号。 （）106、 符号表由词法分析程序建立，由语法分析程序使用。 （）107、 逆波兰法表示的表达式亦称前缀式。 （）108、 代码生成器的输入包括中间代码和符号表中的信息。 （）109、 孤立地考虑一个基本块常常不能确定一个赋值是否真是无用的。 （）110、 目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 （）111、 无左递归的文法是LL（1）文法。 （）112、 一个句型的直接短语语是唯一的。 （）113、 正规文法产生的语言都可以用上下文无关文法来描述。 （）114、 对任何一个编译程序来说，产生中间代码是不可缺少的一部分。 （）115、 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）116、 一个上下文无关文法的开始符号可以是终结符或非终结符。 （）117、 ~个文法所有句子的集合构成该文法定义的语言。 （）118、 优化实质上是对代码进行等价变换，变换后的代码结构不同但运行结果相同。（）119、 算符优先分析法是一种规范归约分析法。 （）120、 非终结符可以有综合属性，但不能有继承属性。 （）121、 所有LR分析器的总控程序都是一样的，只是分析表各有不同。 （）122、 因名字都是用标识符表示的，故名字与标识符没有区别 （）123、 空符号串的集合{8}={}=0o （）124、 非终结符可以有综合属性，但不能有继承属性。 （）125、 终结符可以有综合属性，也可以有继承属性。 （）126、 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）127、 若一个句型中出现了某一产生式的右部，则此右部一定是该句型的句柄。（）129、 DAG是一个可带环路的有向图。 （）130、 设有符号串x和y,把y的符号写在x的符号之后所得的符号串，叫做x与y的连接，记为xy。 （）132、对任何正规表达式e,都存在一个DFAM,满足L（M）=L（e）° （）133、 运行时的DISPLAY表的内容是什么？它的作用是什么？134、 何谓局部优化、循坏优化和全局优化？优化工作在编译的哪个阶段进行?135、 常见的存储分配策略有几种？它们都适合于什么性质的语言？136、 下面文法是否是二义文法？试说明理由。G[S]：S^SaS|£137、 已知文法G（E）EtT|E+TTtF|T*FFt（E）|i（1） 给出句型（T*F+i）的最右推导及画出语法树；（2） 给出句型（T*F+i）的短语、素短语。138、把算术表达式—(a+b)*(b+c)翻译成:后缀表示语法树有向无环图四元式三地址代码139、 DFA与NFA的区别？140、 设已构造出文法G(S)：StS(S)S—£的LR分析表如下状态ACTIONGOTO()S0r2r211S2Acc2r2r233S4S54r2r265rlrl6S4S77ilrl假定输入串为()()，请给出LR分析过程(即状态，符号，输入串的变化过程)。步骤 状态 符号 输入串141、对符号表的基本操作有几种，分别是什么？142、给定代码段如下，求出按四种不同方式进行参数传递后，变量a的值procedureP(w,x、y,z);begmy:=y*w;z:=z+x;endbegma:=5;b:=3;P(a+b，a-b,a,a);wiite(a);end传值:传地址:得结呆:传名:143、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？144^F面的推导S ...=>rmyAbw=>m//J3bw中，最后一步用的是A->\p>分别指出LL(1)方法和LR(1)方法在扫描到此句型的什么位置决定用此产生式？(5分)145、 构造一个最简DFA,它接受正规式ab(a|b)*o给出文法G[S]：S->SaA|AoA—AbB|BB—>cSd|e证实AacAbcBaAdbed是文法G[S]的一个句型；请写出该句型的所有短语、素短语以及句柄。146、 写出表达式a+b*(c-d)对应的逆波兰表示、三元式三地址代码序列和抽彖语法树。147、 什么是活动记录？它主要由哪些内容构成？148、 对下列四元式序列生成目标代码(10分)T=A-BS=C+DW=E-FU=W/TV=U*S其中，v是基本块出「I的活跃变量，R0和R1是可用寄存器。149、 设有如下的三地址码(四元式)序列：ReadNI:=NJ:=2LI：ifI<JgotoL3L2：I:=I-JifI>JgotoL2if1=0gotoL4J:=J+1I:=NgotoLIL3：PrintTES^ReturnL4：PrintTIOrReturn、对题中代码划分基本块，并给每个基本块一个序号、画出基本块集合的控制流图，每个基本块就用(1)小题中的序号表示。、若有循坏的话，列出构成每个循坏的结点。150、 已知文法G(V)：VtNIN[E]E»IV+EN—i给出与G(V)等价的LL(1)文法G*(V)：求文法G(V)的每个非终结符的FIRST集合和FOLLOW集合；构造文法G(V)的LL(1)分析表。151、 考虑下面的三地址语句序列：b:=lb:=2ifw<=xgotoL2e:=bgotoL2LI:gotoL3L2:c:=3b:=4c:=6L3:ify<=zgotoL4gotoL5L4:g：=g+1h:=8gotoLIL5:h:=9、在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。、画出该代码的控制流图，每个基本块就用(1)小题中的序号表示。、若有循环的话，列出构成每个循坏的结点。152、 对于文法G(S)：STbMbMT(L|aLTMa)写出句型b(Ma)b的最右推导并画出分析树。写出上述句型的短语，直接短语和句柄。153、 LL(1)分析法对文法有哪些要求？154、 写出语句a:=b*(-c)+b*(-c)的后缀式、抽彖语法树、DAG图、四元式三地址代码和三元式三地址代码。155、 设有文法G[A]： A-iB*eBSB|eS〜[eC]|.1C〜eC|w判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。(20分)156、 构造一个DFA,它接受£={0,1}上能被5整除的二进制数。157、 正规式(0|1)*和((s|0)1*)*是否等价，说明理由。158、 写出字母表》={a,b}上语言L={w|w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFAo159、文法G(S)及其LR分析表如下，请给出串baba$的分析过程。(1)S-DbB (2)Dfd (3)D-*eB-*a (5)B-*Bba (6)B-*eLR分析表