编译原理习题

1、作业一1 .已知文法GA,写出它定义的语言描述如：GA:A f 0B|1CB- 1|1A|0BBC- 0|0A|1CC2. 给出生成下述语言的上下文无关文法：(1) a nbnambml n , m>=0(2) 1 n0m 1m0n| n , m>=03. 给出生成下述语言的三型文法：(1) anbmjn,m>=1 a nbmck|n,m,k>=0 4、文法 GE为：E- E+T|TTf T*F|FF-(E)|i试给出句型(E+F)*i的短语，简单(直接)短语，句柄。第3章练习题一、判断题：1、编译程序中的词法分析程序以字符形式的源程序作为输入，输出的单词符号常 采用二

2、元组的形式。2、正规式的运算符“ |”读作”或3、若两个正规式所表示的正规集相同，则认为二者是等价的。4、用l代表字母，d代表数字，2=l,d,则正规式r=dd*定义了无符号整数单词。5、一个确定的有穷自动机DFA M的转换函数f是一个从Kx 2到K的子集的映像。6、一个非确定的有穷自动机 NFA N的转换函数f是一个从KxNiJK的映像。7、一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。8、终态与非终态是可区别的。9、对任意一个右线性文法 G,都存在一个 NFA M满足L ( G) =L ( M)。10、对任意一个右线性文法 G都存在一个 DFA M满足L (M)

3、 =L (R)。二、构造正规式1(0|1) *101相应的DFA.练习题2一、判断题：1、 空符号串的集合 £ = 6。2、 设A是符号串的集合，则 A0= e。3、 设G是一个文法，S是开始符号，如果 S => x且xC W则称x是文法G网的句型。4、 在形式语言中，最右推导的逆过程也称为规范归约。5、 一个语言的文法是唯一的。6、 若一个语言是无穷集合，则定义该语言的文法一定是递归的。7、 一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。8、 每个直接短语都是某规则的右部。9、 用二义性文法定义的语言也是二义性的。10、 文法的二义性与语言的二义性是两个不同的概

4、念。11、 任何正规文法都是上下文无关文法。12、 正规文法对规则的限制比上下文无关文法对规则的限制要多一些。二、选择题(从各题的 4个答案中选出一个或多个正确的答案写在横线上)(1) 一般程序设计语言的描述都涉及()3个方面。A 语法B 语用C 语义D 基本符号的确定(2)为了使编译程序能对程序设计语言进行正确的翻译，必须采用()方法定义程序设计语言。A 非形式化B 自然语言描述问题号体系相结合(3)设x是符号串的哥运算 x0=(A 1 B x C£ D *(4)设A是符号串的集合，则 A=(A A IA2U, U AnU,B A 0U Al A2U, U AnU, _+C S U

5、 AD A 0U A+(5)字母表中的元素可以是(A字母B字母和数字 C 数字D字母、数字和其他符号(6)文法用来描述语言的语法结构，它由如下 开始符号。A文法终结符集合B文法规则的集合C文法非终结符集合D字母数字串(7)在规则中，符号T (:二)表示(A 恒等于 B 等于 C 取决于 DC 形式化 D自然语言和符4个部分组成：()和文法)° 定义为)°(8)在规则中，符号“ | ”表示(A与 B 或C 非D 定引导开关参数(9)设文法GE的规则如下：ZA1|A0|Aa|Ac|a|b|c ,该文法的句子是下列符号串()A ab0 B a0c01 C aaa D bc10(1

6、0)如果在推导过程中的任何一步a=>3,都是对口中的最右非终结符进行替换，则称这种推导为()。A.直接推导 B.最右推导C.最左推导D.规范推导(11)描述语百L=ambn|n 噎mm> 1的文法为(A. Sf ABbB.SfABbZ aA|aAfaA|aBf bB|bBfaBb|bC. S fSb |AD.SfaAbZ aAb |ab Af Ab|aAb| e(12)设有文法 GS= (S, B b, SfbB|b ,BfbS, S),该文法描述的语言是 ()。A. L(GS)=bn|n > 0B. L(GS)=b2n |n > 0C. L(GS)=b2n+1|n &

7、gt;0D. L(GS)= b 2n+1|n > 1(13) 一个句型最左边的()称为该句型的句柄。A.短语B.素短语C.直接短语D.规范短语(14)设有文法GS:E f E+T | E-T |TT f T*F |T/F|FF - (E) |i该文法白句型E+T*F的句柄是下列符号串()。A E B E+T C T*F D E+T*F （15）设有文法GT:T f T*F |FFf FAP | PP - （T） |a该文法白句型T*PA（T*F）的直接短语是下列符号串（）。A. P B. （T*F） C. T*F D. PA（T*F）（16）若一个文法满足（），则称该文法是二义文法。A.

8、文法的某一个句子存在两棵（包括两棵）以上的语法树。B.文法的某一个句子，它有两个（包括两个）以上的最右（最左）推导。C.文法的某一个句子，它有两个（包括两个）以上的最右（最左）归约。D.文法的某一个句子存在一棵（包括一棵）以上的语法树。（17）在下列描述含+, *算术表达式的文法中，属于二义性文法的是（）。A.E- E+E|E*E|(E)|iB.E fEAE|(E)|iAf+ |*C. E - E+T |TD.Ef EAE|TT f T*F | FTf TBF|FF-(E)|IF-(E)|iAf +B- *（18）乔姆斯基把文法分成 4种类型，即0型、1型、2型和3型。2型文法也称为（3型文法

9、也称为（）。A.上下文无关文法B. 正规文法C.上下文有关文法 B.无限制文法1、如下程序流图（图11.18）中，B3中的i ： =2是循环不变量，可以将其提到前置结点吗 你还能举出一些例子说明循环不变量外移的条件吗？图 11.182、2、对图11.19的流图：(1)求出流图中各结点 n的必经结点集(2)求出流图中的回边；(3)求出流图中的循环。图 11.19L ®-D(n)；B8语法分析部分一、判断题：1、LL (1)文法是无左递归、无二义性文法。2、无左递归的文法是 LL (1)文法。3、在高级语言编译程序常用的语法分析方法中，预测分析法属于自上而下的语法分析方 法。4、在高级语

10、言编译程序常用的语法分析方法中，算符优先分析法属于自上而下的语法分析方法。5、算符优先分析法是一种规范规约分析法。6、算符优先分析法是最适合于分析算术表达式。7、设有一个LR (0)项目集I=X-> a .B 3 ,A-> ” .,该项目集含有“移进一归约"冲突。8、LR分析法是一种规范规约分析法。9、设有一个LR (1)项目集I=X-> a .b 3 , " ,A-> " . , a ,该项目集含有“移进一归约"冲突。10、 SLR (1)文法是二义性文法。二、选择题(从四个答案中选择一个或多个正确答案写在横线上)1、编译程序中

11、语法分析常用的方法 .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:E - >TE'E ' - > +TE' | £

12、T - > FT 'T? -> *FT? |£F >(E)|idFIRST(T?)=, FOLLOW(F)=.A. (, id ) B. *,e C. *,+,# D. +,),#6、自下而上语法分析法的原理是 .A.移进-推导法” B. 移进-归约法” C .最左推导法” D.推导-归约法”7、设有文法 G如果文法G中没有形如A->BC 的规则，其中A, B, C为非终结符，则称 文法G为.A.算符优先文法B. LL (1)文法C. LR (1)文法 D. 算符文法9、设有文法GE:E->E+T|TT->T*F|FF->(E)|a句

13、型T+T*F+a的素短语是.A. a B. T*F C.T D.T+T*F10、设有文法GS:S->a| A |(T)T->T,S|S其中 FIRSTVT(T)=, LASTVT(T)=.A. a ,(,) B. a ,(,A )C. a ,(,?,?) D. a ,(,?,?, A)E. $, F. $,aG.a, ?.? H. ,?, ) ,a, A11、 LR (0)项目集规范族的项目类型可分为 .A.移进项目B.归约项目C待约项目D.接受项目12、 LR0)分析器的核心部分是一张分析表，这张分析表包括两部分，它们是A. LL(1)分析表B.分析动作表C状态转换表D.移进分析

14、表13、 设有LR (0)项目集I=X-> a. b 3 , A-> ” .,B-> a .,该项目集含有冲突项目，它们是 .A、“移进一归约”冲突 B. “移进一接受”冲突C “移进一待约”冲突D. “归约一归约”冲突第五章自测练习题判断题：1、对任何一个编译程序来说，产生中间代码是不可缺少的一部分。2、目前多数编译程序进行语义分析的方法采用语法制导翻译法，这是因为语法制导翻译法是一种形式化系统。3、一个属性文法包括一个上下文无关文法和一系列规则。4、文法符号的属性有两种，一种称为继承属性，另一种称为综合属性。5、自下而上语法制导翻译法的特点是语法分析栈与语义分析栈不需同时

15、操作。6、自下而上语法制导翻译法的特点是在栈顶形成句柄，在归约之前执行相应的语义动作。7、逆波兰表达式ab+cd+*所代表的中缀形式的表达式是a+b*c+d.8、赋值语句A=A+B*CA(D/E)/F的逆波兰表示是 AABCDE/A*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)(T7=T4-T6)选择题：(1)编译程序的语义处理有两个任务：一个是()，另一个是()。A.静态语义审查B。审查语法结构C.执行真

16、正的翻译D。审查语义结构(2)在编译程序中安排中间代码生成的目的是()。A .便于进行存储空间的组织B. 利于目标代码优化C. 利于提高目标代码的质量D. 利于编译程序的移植(3)编译过程中比较常见的中间语言有()。A .逆波兰式 B。三元式C.四元式 D。树形表示(4)中缀表达式-a+b*(-c+d)的逆波兰表式是()。A . abcd+* +Bo abcd+8+C. abcd+*+D。abcd+*+(5)后缀式iiii-/A的中缀表达式是A. IA(i/(I-I)Bo (I-I)/IAiC. |A(|-|)/iDo (I-I)Ai/i自测练习题4选择题：(1)在编译过程中符号表的主要作用是

17、()。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)在编译程