编译原理习题.doc

作业一1.已知文法GA，写出它定义的语言描述 如：GA: A 0B|1C B 1|1A|0BB C 0|0A|1CC2. 给出生成下述语言的上下文无关文法： （1） anbnambm| n，m=0 (2) 1n0m 1m0n| n，m=03. 给出生成下述语言的三型文法： (1) anbm|n,m=1 (2)anbmck|n,m,k=0 4、 文法GE为： EE+T|T TT*F|F F(E)|i 试给出句型(E+F)*i的短语，简单(直接)短语,句柄。第3章练习题一、判断题:1、 编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常采用二元组的形式。2、 正规式的运算符“|”读作“或“。3、 若两个正规式所表示的正规集相同，则认为二者是等价的。4、 用l代表字母，d代表数字，=l，d，则正规式r=dd*定义了无符号整数单词。5、 一个确定的有穷自动机DFA M的转换函数f是一个从K到K 的子集的映像。6、 一个非确定的有穷自动机NFA N 的转换函数f是一个从K*到K 的映像。7、 一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。8、 终态与非终态是可区别的。9、 对任意一个右线性文法G，都存在一个NFA M，满足L（G）=L（M）。10、 对任意一个右线性文法G，都存在一个DFA M，满足L（M）=L（R）。二、构造正规式1(0|1)*101相应的DFA.练习题2一、判断题：1、 空符号串的集合=。2、 设A是符号串的集合，则A0=。3、 设G是一个文法，S是开始符号，如果S = x且xVT*,则称x是文法GS的句型。4、 在形式语言中，最右推导的逆过程也称为规范归约。5、 一个语言的文法是唯一的。6、 若一个语言是无穷集合，则定义该语言的文法一定是递归的。7、 一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。8、 每个直接短语都是某规则的右部。9、 用二义性文法定义的语言也是二义性的。10、 文法的二义性与语言的二义性是两个不同的概念。11、 任何正规文法都是上下文无关文法。12、 正规文法对规则的限制比上下文无关文法对规则的限制要多一些。二、选择题（从各题的4个答案中选出一个或多个正确的答案写在横线上）（1） 一般程序设计语言的描述都涉及（ ）3个方面。 A 语法 B 语用 C 语义 D 基本符号的确定（2）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（）方法定义程序设计语言。非形式化 自然语言描述问题形式化 D自然语言和符号体系相结合（3） 设x是符号串的幂运算 x0=（ ）。A 1 B x C D （4）设A是符号串的集合，则A*=（ ）。A A1A2AN B A0A1A2ANC A+ D A0A+（5）字母表中的元素可以是（ ） A 字母 B字母和数字 C 数字 D字母、数字和其他符号（6） 文法用来描述语言的语法结构，它由如下4个部分组成：（ ）和文法开始符号。 A文法终结符集合 B 文法规则的集合 C 文法非终结符集合 D字母数字串（7）在规则中，符号“”（：=）表示（ ）。 A 恒等于 B 等于 C 取决于 D 定义为 （8）在规则中，符号“|”表示（ ）。A 与 B 或 C 非 D 定引导开关参数（9）设文法GE的规则如下：AA1|A0|Aa|Ac|a|b|c ,该文法的句子是下列符号串（ ）A ab0 B a0c01 C aaa D bc10 (10) 如果在推导过程中的任何一步=,都是对中的最右非终结符进行替换，则称这种推导为（ ）。A直接推导 B.最右推导 C. 最左推导 D.规范推导（11）描述语言L=ambn|nm1的文法为（ ）。A. SABb B.SABb AaA|a AaA|a BbB|b BaBb | b C. SSb |A D.SaAbAaAb |ab AAb|aAb|(12) 设有文法GS=（S，B b, SbB |b ,BbS, S）,该文法描述的语言是（ ）。A. L(GS)=bn|n 0 B. L(GS)=b2n |n 0 C. L(GS)=b2n+1|n 0 D. L(GS)= b2n+1|n 1 (13) 一个句型最左边的（ ）称为该句型的句柄。A短语 B.素短语 C. 直接短语 D.规范短语(14)设有文法GS： EE+T | E-T |T TT*F |T/F|F F(E) |i该文法的句型E+T*F的句柄是下列符号串（ ）。A E B E+T C T*F D E+T*F(15) 设有文法GT： TT*F |F FFP | P P(T) |a该文法的句型T*P(T*F)的直接短语是下列符号串（ ）。A. P B. (T*F) C. T*F D. P(T*F)(16) 若一个文法满足（ ），则称该文法是二义文法。A. 文法的某一个句子存在两棵（包括两棵）以上的语法树。B. 文法的某一个句子，它有两个（包括两个）以上的最右（最左）推导。C. 文法的某一个句子，它有两个（包括两个）以上的最右（最左）归约。D. 文法的某一个句子存在一棵（包括一棵）以上的语法树。(17) 在下列描述含+，*算术表达式的文法中，属于二义性文法的是（ ）。A EE+E|E*E|(E)|i B.EEAE|(E)|i A+|*C. EE+T |T D.EEAE|T TT*F | F TTBF|F F(E) |I F(E)|i A+ B*(18)乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。2型文法也称为（ ）、3型文法也称为（ ）。 A.上下文无关文法 B.正规文法 C. 上下文有关文法 B.无限制文法1、 如下程序流图(图11.18)中，B3中的i=2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗? 图11.18 2、 2、对图11.19的流图：(1) 求出流图中各结点n的必经结点集D(n)； (2) 求出流图中的回边；(3) 求出流图中的循环。图11.19 语法分析部分 一、判断题：1、 LL（1）文法是无左递归、无二义性文法。2、 无左递归的文法是LL（1）文法。3、 在高级语言编译程序常用的语法分析方法中，预测分析法属于自上而下的语法分析方法。4、 在高级语言编译程序常用的语法分析方法中，算符优先分析法属于自上而下的语法分析方法。5、 算符优先分析法是一种规范规约分析法。6、 算符优先分析法是最适合于分析算术表达式。7、 设有一个LR（0）项目集I=X-.B,A-.,该项目集含有“移进归约”冲突。8、 LR分析法是一种规范规约分析法。9、 设有一个LR（1）项目集I=X-.b, ,A-. ，,该项目集含有“移进归约”冲突。10、 SLR（1）文法是二义性文法。二、选择题（从四个答案中选择一个或多个正确答案写在横线上）1、 编译程序中语法分析常用的方法_.A. 自上而下分析法 B.自下而上分析法C自左向右分析法 D.自右向左分析法2、 编译程序的语法分析器接受以_为单位的输入，并产生有关信息供以后各阶段使用。A. 表达式 B.字符串 C单词 D.语句3、在高级语言编译程序常用的语法分析方法中，递归下降分析法属于_分析法。A. 自左向右分析法 B.自上而下分析法C自下而上分析法 D.自右向左分析法4、递归分析法和预测分析法要求描述的文法是_。A. 正规文法 B. LR（1）文法 C. LL（1）文法 D. 右线性文法5、设有文法GE： ETE E +TE| T FT T *FT | F (E)|idFIRST(T)=_, FOLLOW(F)=_.A. (, id ) B. *, C. *,+,# D. +,),#6、自下而上语法分析法的原理是_.A. “移进-推导法” B. “移进-归约法” C“最左推导法” D. “推导-归约法”7、设有文法G，如果文法G中没有形如A-BC的规则，其中A，B，C为非终结符，则称文法G为_.A. 算符优先文法 B. LL（1）文法 C. LR（1）文法 D. 算符文法8、 算符优先分析法从左到右扫描输入串，当栈顶出现_时进行归约。9、设有文法GE: E-E+T|TT-T*F|FF-(E)|a句型T+T*F+a的素短语是_.A. a B. T*F C.T D.T+T*F10、设有文法GS：S-a|(T)T-T,S|S其中FIRSTVT(T)=_, LASTVT(T)=_.A. a ,(,) B. a ,(, )C. a ,(,) D. a ,(, ) E. $, F. $,a G.a, H. ,）,a, 11、 LR（0）项目集规范族的项目类型可分为_.A. 移进项目 B. 归约项目 C 待约项目 D. 接受项目12、 LR（0）分析器的核心部分是一张分析表，这张分析表包括两部分，它们是_.A. LL(1)分析表 B. 分析动作表 C 状态转换表 D. 移进分析表13、 设有LR（0）项目集I=X-. b, A-.,B-.,该项目集含有冲突项目，它们是_.A、“移进归约”冲突 B.“移进接受”冲突C “移进待约”冲突D. “归约归约”冲突第五章 自测练习题判断题：1、 对任何一个编译程序来说，产生中间代码是不可缺少的一部分。2、 目前多数编译程序进行语义分析的方法采用语法制导翻译法，这是因为语法制导翻译法是一种形式化系统。3、 一个属性文法包括一个上下文无关文法和一系列规则。4、 文法符号的属性有两种，一种称为继承属性，另一种称为综合属性。5、 自下而上语法制导翻译法的特点是语法分析栈与语义分析栈不需同时操作。6、 自下而上语法制导翻译法的特点是在栈顶形成句柄，在归约之前执行相应的语义动作。7、 逆波兰表达式ab+cd+*所代表的中缀形式的表达式是a+b*c+d.8、 赋值语句A=A+B*C(D/E)/F的逆波兰表示是AABCDE/*F/+=9、 表达式-(a+b)*(c+d)-(a+b+c)的四元式表示是：（1） (T1=a+b)（2） (T2=-T1)（3） (T3=c+d)（4） (T4=T2*T3)（5） (T5=a+b)（6） (T6=T5+c)（7） (T7=T4-T6)选择题：（1） 编译程序的语义处理有两个任务：一个是（ ），另一个是（ ）。A静态语义审查 B。审查语法结构C执行真正的翻译 D。审查语义结构（2）在编译程序中安排中间代码生成的目的是（ ）。A 便于进行存储空间的组织 B 利于目标代码优化C 利于提高目标代码的质量 D 利于编译程序的移植（3）编译过程中比较常见的中间语言有（ ）。A逆波兰式 B。三元式 C四元式 D。树形表示（4）中缀表达式-a+b*(-c+d)的逆波兰表式是（ ）。Aabcd+*+ B。abcd+8+Cabcd+*+ D。abcd+*+(5) 后缀式iiii-/的中缀表达式是AI(i/(I-I) B。(I-I)/IiCI(I-I)/i D。(I-I)i/i自测练习题4选择题：（1）在编译过程中符号表的主要作用是（ ）。A帮助错误处理 B. 辅助语法错误检查 C. 辅助上下文语义正确性检查 D. 辅助目标代码生成 (2) 符号表的查找一般可以使用（ ）A顺序查找 B.折半查找 C. 杂凑查找 D. 排序查找(3)编译程序中安排优化的目的是为得到（ ）的目标代码。A结构清晰 B. 较短 C. 高效率 D.使用存储空间最小 (4）根据所涉及程序的范围，优化可分为（ ）。A 局部优化 B.函数优化 C. 全局优化D. 循环优化（5）局部优化是局限与一个（）范围内的优化。 A循环 B. 函数 C.基本块 D.整个程序（6）所谓基本块是指程序中一个顺序执行的语句序列，其中只有（ ）。A 一个子程序 B.一个入口语句和多个出口语句C. 一个出口语句和多个入口语句 D. 一个入口语句和一个出口语句(7) 在编译程序采用优化的方法中，（ ）是在基本块范围内进行的。A