《编译原理》期中及期末习题

《《编译原理》期中及期末习题》由会员分享，可在线阅读，更多相关《《编译原理》期中及期末习题（120页珍藏版）》请在装配图网上搜索。

1、编译原理期中及期末习题第一章高级语言与编译程序概述典型例题:单项选择题1.1.1将编译程序分成若干个“遍”是为了_。a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率1.1.2构造编译程序应掌握_。（陕西省2000年自考题）a.源程序b.目标语言c.编译方法d.以上三项都是1.1.3变量应当。a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值1.1.4编译程序绝大多数时间花在_上。（陕西省1998年自考题）a.出错处理b.词法分析c.目标代码生成d.管理表格1.1.5_不可能是目标代码。

2、( 陕西省1997年自考题)a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码1.1.6数组A120,110的首地址偏移量为0，按列存储，每个元素占一个字节，存储器按字节编址，则Ai,的偏移地址为_。a.(i-1)X10+（j-1）b.(i-1)X20+(j-1)c. (i-1)(j-1)X10d.(i-1)+(j-1)X201.1.7.使用_可以定义一个程序的意义。a.语义规则b.词法规则c.产生规则d.左结合规则1.1.8表达式X:=5中，变量x_。a.只有左值b.只有右值c.既有左值又有右值d.没有左值也没有右值1.1.9词法分析器的输入是_。a.单词符号b.源程序c.语法

3、单位d.目标程序1.1.10中间代码生成时所遵循的是。a.语法规则b.词法规则c.语义规则d.等价变换规则1.1.11编译程序是对_。a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译1.1.12词法分析应遵循。（陕西省2000年自考题）a.语义规则b.语法规则c.构词规则d.等价变换规则多项选择题：1.2.1 编译程序各阶段的工作都涉及到_。（陕西省1999年自考题）a.语法分析b.表格管理c.出错处理d.语义分析e.词法分析1.2.2下列各项中，_与数组元素的地址有关。（陕西省1999年自考题）a.数组第一个元素的存储地址b.数组的存储方式c.数组的维数d.内

4、存的编址方式e.编译程序1.2.3 编译程序工作时,通常有_阶段。（陕西省1998年自考题）a.词法分析b.语法分析c.中间代码生成d.语义检查e.目标代码生成1.2.4 过程调用的参数传递方式有_。a传名 b.传值 c.传参数d.传地址e.传结果1.2.5 编译过程中所遵循的规则有_。a.等价变换规则b.短语规则c.构词规则d. 语义规则e.语法规则填空题：1.3.1 解释程序和编译程序的区别在于。1.3.2 编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。（陕西省1999年自考题）1.3.3 编译程序工作过程中，第一阶段输入是，最后阶段的输出为一程序。（陕西省1997

5、年自考题）1.3.4 静态数组元素地址的计算公式由两部分确定，一部分是，它在时确定；另一部分是，它在时确定。1.3.5 把语法范畴翻译成中间代码所依据的是语言的。（陕西省2000年自考题）1.3.6 目标代码可以是指令代码或指令代码或绝对机器指令代码。（陕西省2000年自考题）1.3.7 编译程序是指能将_程序翻译成_程序的程序。1.3.8 数组元素的地址由_和_组成，其中中的a和c在翻译数组说明语句时填入到数组的中。1.3.9 过程调用时，参数传递的方式有_、_、_。1.3.10 词法分析所遵循的是语言的_，而中间代码生成所遵循的是语言的_。（陕西省1997年自考题）1.3.11 数组元素的

6、地址计算与数组的_数及_方式有关，也与数组的类型及机器对存储器的编址方式有关。（陕西省2000年自考题）判断题：1.4.1赋值号左边的变量只持有左值，不持有右值。（）1.4.2二维数组a315,520按行存放，并且每个元素占用一个存储单元，则数组元素ai ,j的地址为base-85+i X 16+j (base是数组a存放的起始地址）。（）1.4.3变量的名字用标识符来表示，同时名字代表一定的存储单元，有属性、值、作用域等特性。（陕西省1997年自考题）（）1.4.4指示器变量的右值只持有右值，没有左值。（陕西省2000年自考题）（）1.4.5般而言，中间代码是一种独立于具体硬件的记号系统。（

7、）综合题1.5.1 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？1.5.2 何谓“标识符”，何谓“名字”，两者的区别是什么？1.5.3 简述在过程调用中，形参和实参间常见的各种信息传递方式（即形实结合方式）的含义。1.5.4 画出编译程序的总体结构图，简述各部分的主要功能。1.5.5 对于下面的程序：PROCEDURE P(x,y,z)；BEGINPy：=y+l；Z：=Z+XEND；PBEGIN mainA：=2；B：=3；P（A+B,A,A）；Print AEND main若参数传递的办法分别为（1)传名，(2）传地址，(3）传结果，(4)传值；试问，程序执行时所输出

8、的A值分别是什么？1.5.6 对于下面的程序：PROGRAM main；a:integer；PROCEDURE test(x：:integer)；temp:integer；BEGIN testx：=a+l；Temp：=a+2x：=tempEND； testBEGINa:=2；test(a)；print(a)END分别给出参数传递为传地址、传结果、传值和传名时a的输出结果。1.5.7 三维数组a2:5,-2:2,5:7首址为100,每个数组元素占4个存储单元，求数组元素a3,1,6的地址。1.5.8 什么叫自展？什么叫交叉编译？1.5.9 试分析编译程序是否分遍应考虑的因素及多遍扫描编译程序的优

9、缺点。1.5.10 请画出编译程序的总框。如果你是一个编译程序的总设计师，应当考虑哪些问题？（国防科大2000年研究生试题）1.5.11 对于下面说明语句所定义的数组Aarray A-2:3,-5:5假定数组按行存放，存储器按字节编址，每四个字节为一机器字，令A的首地址为1000，问Ai+3,j+2的首地址是什么？（写出步骤）（同济大学1998年研究生试题）1.5.12 数组var a：array1.5,-3.6 of integer；按列存放，其首址100,每个整数占4个字节，内存按字节编址，则数组元素a4,3的地址是什么？（上海交大1997年研究生试题）1.5.13 对于下面的程序段pro

10、cedure P(x,y,z)beginy：=y*2；;z：=x+z；end；begina：=5；b：=2；p(a*b,a,a)；print(a)end若参数传递的方法分别为（1)传值、(2)传地址、(3)传名，试问程序执行所输出的结果分别是什么？1.5.14 有一段程序为：PROGRAM sample;x：integer；PROCEDURE sun(m：integer)；BEGINsunM：=11；x：=m+END；sunBEGINX：=100；sun（x）；write（x）END；请用（1）传地址；（2）传值；（3）传结果；(4)传名的参数传递方式，给出程序的运行结果。1.5.15有一程序

11、如下：PROGRAM ex；a：integer；PROCEDURE PP(x：integer)；BEGINPPa：=5；x：=a+1END；PPBEGINa：=2；PP（a）；write（a）END 用（1)传地址；(2)传值；（3)传结果；(4)传名等4种参数传递方式，；试写出程序的运行结果。第二章词法分析典型例题:单项选择题1.1.1词法分析所依据的是_。a.语义规则b.构词规则c.语法规则d.等价变换规则1.1.2词法分析器的输出结果是_。a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值1.1.3正规式MI和M2等价是指_。a. MI和M2的状态数相等b

12、.Ml和M2的有向弧条数相等。C.M1和M2所识别的语言集相等 d. Ml和M2状态数和有向弧条数相等1.1.4状态转换图（见图2.5），接收的字集为：图2.5a.以0开头的二进制数组成的集合b.以0结尾的二进制数组成的集合c.含奇数个0的二进制数组成的集合d.含偶数个0的二进制数组成的集合1.1.5词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此_。a.词法分析器应作为独立的一遍b.词法分析器作为子程序较好c.词法分析器分解为多个过程，由语法分析器选择使用d.词法分析器并不作为一个独立的阶段1.1.6词法分析器的输入是。a.单词符号串b.源程序c.语法单位d.目标程序1.1.7

13、.如果L(M)=L(M），则M与M_。（陕西省1999年自考题）a. 等价bM与M都是二义的c. M与M都是无二义的d. 他们的状态数相等1.1.8图2.56所示的状态转换图接受的字集所对应的正规式为。（陕西省1997年自考题）a. a*b*(aa|bb)a*b*b. (a|b)*(aa|bb)(a|b)c. (a*|b*)(aa|bb)(a*|b*)d. (a*|b*)aa(a*|b*)|(a*|b*)bb(a*|b*)图2.56 状态转换图多项选择题：1.2.1在词法分析中，能识别出。（陕西省1998年自考题）a.基本字b.四元式c.运算符d.逆波兰式e.常数1.2.2令=a,b，则上所有

14、以b开头，后跟若干个ab的字的全体对应的正规式为。ab(ab)* b.b(ab) c.(ba)* bd.(ba)+be. b(alb)*1.2.3设=0,1，则上字的全体可用正规式_表示。a.(1|0)*b.(1*|0*)*c.(1|0)+d.(1*0*)*e.(10)*填空题：1.3.1 确定有限自动机DFA是_的一个特例。1.3.2 若二个正规式所表示的_相同，则认为二者是等价的。（陕西省1997年自考题）1.3.3 一个字集是正规的，当且仅当它可由_所_（陕西省1997年自考题）判断题：1.4.1一个有限状态自动机中，有且仅有一个唯一的终态。（）1.4.2设r和s分别是正规式，则有L(r

15、|s)=L(r)|L(s) （）1.4.3自动机M和M的状态数不同，则二者必不等价。（）1.4.4确定的自动机以及不确定的自动机都能正确地识别正规集。（）1.4.5对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。（）1.4.6 对任意一个右线性文法G,都存在一个DFA M,满足L(G=L(M) 。（）1.4.7 对任何正则表达式e,都存在一个NFA M,满足L(G)=L(e) 。（）1.4.8 对任何正则表达式e,都存在一个DFA M,满足L(G)=L(e)。（）1.4.9 两个正规集相等的必要条件是他们对应的正规式等价。（）1.4.10 词法分析作为单独的一遍来处理较好

16、。（）1.4.11 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）综合题1.5.1 什么是扫描器？扫描器的功能是什么？1.5.2 给出字母表上的正规式及其所描述的正规集的递归定义。1.5.3 正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言能力上是否相互等价？1.5.4 已知Pascal语言的实数表示规则如下：（1)实数十进制表示(a)实型数的小数点前后必须出现数字：(b）必须出现小数点。（2）实数科学表示（指数形式）(a)字母e表示以十为底的指数；(b）字母e前必须出现实数或者整数；（c）字母e后必须出现整数，这个整数表示实型数的指数部分。试画出该实数

17、对应的状态转换图。1.5.5 设M= f(x,a)=x,yfa,b=Y)f(Y,a)=fy,bx,y试构造相应的确定有限自动机M。1.5.6 (1）对给定正规式b*(d|ad) (b|ab)，构造其NFA M；（陕西省1997年自考题）（2) 对给定正规式(a|b)*a(a|b)，构造其DFA M。（中科院计算所1997年研究生试题）1.5.7 构造一个DFA,它接收=a,b上的所有满足下述条件的字符串，即该字符串中的每个a都有至少一个b直接跟在其右边。1.5.8 有穷状态自动机M接受字母表0，1上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。（1)请给出与M等价的正规（则）式

18、。（2）将M最小化。（3）构造与M等价的正规文法。1.5.9 构造正规表达式(a|b)*|bb)*的（要求写出步骤）。1.5.10 设有L(G)=a2n+1b2m a2p+1|n0,p0,m1（1)给出描述该语言的正规表达式。(2)构造识别该语言的确定的有穷自动机（可直接用状态图形式给出）。1.5.11 请写出在(a,b)上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。1.5.12 有语言L=w|w(0,1），并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机（DFA）。1.5.13 已知正规式(1)(a|b)*|a

19、a)*b和正规式(2)(a|b)*b。(1)试用有限自动机的等价性证明正规式(1)和(2)是等价的。(2）给出相应的正规文法。1.5.14 某操作系统下合法的文件名为device:name.extension,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。1.5.15 Pascal语言无符号数的正规定义如下：Numdigit+(.digit+)?(E(+|-)?digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。1.5.

20、16 在C语言中无符号整数可用十进制（非0打头）、八进制（0打头）和十六进(0X 打头）表示，试写出其相应的文法和识别无符号数的DFA(假定位数不限)。1.5.17 下列程序段若以B表示循环体，A表示初始化，I表示增量，T表示测试。I:=1；while Ibeginsun:=sun+aI;I:=I+lEnd请用正规表达式表示这个程序段可能的执行序列。1.5.18 在操作系统的进程管理中，进程的状态转换如图2.50所示。假设现有两个进程Pi 和CPU每次只能运行一个进程。当P1、P2都处于就绪状态时为初态，当P1、P2都处于睡眠状态时为终态。请用一个有限自动机来描述这个进程管理系统。图2.50

21、进程状态转换图1.5.19 有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中投放3分的硬币，便可得到一块糖（注意：只给一块并且不找钱）。(1)写出售货机售糖的正规表达式。(2)构造识别上述正规式的最简DFA。1.5.20 证明：一不含无用状态的有限自动机M的接收集L(M)是无限集，当且仅当M相应的状态转换图中含有回路。1.5.21 假定A和B都是正规集，请用正规集与有限自动机的等价性说明AB也是正规的。1.5.22 下面的正规式等价吗？为什么？(1)(a|b)* (2) (a*|b*)* (3)(|a)b*)*1.5.23 （电子科大1996年研究生试题）构造识别下

22、列单词符号的状态转换图：begin end标识符正整数*，1.5.24 （清华大学1998年研究生试题）请将图2.57所示的有穷自动机M1最小化。图2.57 有穷自动机M11.5.25 （清华大学1998年研究生试题）将有穷自动机M2确定化M2=(U,V,W,X，10,1,f,U，W）其中：f(U,0）f(U,1）V,Xf(V,0)=V f(V,l）tvlwlf(W,0)=Xf(W,1)Wf(X,0)=X f(X,1）X1.5.26 （清华大学1998年研究生试题）将图2.58所示的DFA最小化。图2.58 DFA1.5.27 （中科院计算所1997年研究生试题）为正规式(a|b) *a(a|

23、b)构造一个确定的有限自动机。1.5.28 （南开大学1998年研究生试题）写出正规式(alb) *(aa|bb)(a|b)*的DFA。1.5.29 （复旦大学1999年研究生试题）将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。图2.59 NFA其中，X为初态，Y为终态。1.5.30 （上海交大1997年研究生试题）请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。1.5.31 （国防科大1999年研究生试题）构造一个确定的有限自动机DFA,它接受0,1上的所有不带前导0的二进制区数。1.5.32 （国防科大2000年研究生试题）已知DFA

24、 M如图2.60所示。图2.60 DFA M请给出M所识别的字的全体L(M)。1.5.33 （华中理工2001年研究生试题）构造一个确定的有穷自动机DFA M,它识别=a,b上所有满足如下条件的字符串：字符串由a, b组成，且其中b的个数为3k (k0)。1.5.34 （华中理工2001年研究生试题）正规式(ab）*a与正规式a(ba) *是否等价？请说明理由。1.5.35 DFA与NFA有何区别5第三章语法分析典型例题:单项选择题3.1.1. 文法G: S-xSxly所识别的语言是_（陕西省1997年自考题）a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*3.1.2.

25、文法G描述的语言L(G)是指_。a. L(G)=|S=，VT*b. L(G)= |SA=, VT*cL(G)= |S=，(VTVN)*d. L(G)=|S=,(VTVN)*3.1.3. 有限状态自动机能识别。a.上下文无关文法b.上下文有关文法c.正规文法d.短语文法3.1.4. 设G为算符优先文法，G的任意终结符对a, b有以下关系成立_。a.若f(a)g(b)，则abb.若f(a)c.ab都不一定成立d. ab一定成立3.1.5茹果文法G是无二义的，则它的任何句子_。（西电1999年研究生试题）a.最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c.最左推导

26、和最右推导必定相同d.可能存在两个不同的最左推导，但它们对应的语法树相同3.1. 6.由文法的开始符经。步或多步推导产生的文法符号序列是_。（陕西省2000年自考题）a短语 b.句柄 c.句型 d.句子3.1.7文法G：E-E+TITT-T*P|PP-(E)|I则句型P+T+i的句柄和最左素短语分别为_。a. P+T和ib. P和P+Tc. i和P+T+id. P和P3.1.8设文法为：S-SA|AAa|b则对句子aba，下面_是规范推导a. S=SA=SAA=AAA=aAA=abA=abab. S=SA=SAA=AAA=AAa=Aba=abac. S=SA=SAA=SAa=Sba=Aba=a

27、bad. S=SA=Sa=Sba=Aba=aba3.1.9.文法G: Sb|(T)T-T,SIS则FIRSTVT(T)=_。a.b，（b.b，）c.b,，（，,d.b, ，），3.1.10产生正规语言的文法为_。a. 0型b. 1型c. 2型d. 3型3.1.11任何算符优先文法优先函数。a.有一个b.没有c.有若干个d.可能有若干个3.1.12.采用自上而下分析，必须_。a.消除左递归b.消除右递归c.消除回溯d.提取公共左因子3.1.13设a, b, c是文法的终结符，且满足优先关系a=b和b=c，则_。a.必有a=b必有c=ac.必有b=ad. ac都不一定成立3.1.14.在规范归约中

28、，用_来刻画可归约串。（陕西省1999年自考题）a.直接短语b.句柄c.最左素短语d.素短语3.1.15.有文法：EE*T|TTT+i|i句子1+2*8+6按该文法G归约，其值为_。a.23b.42c.30d.173.1.16.规范归约是指_。（陕西省年自考题）a.最左推导的逆过程b.最右推导的逆过程c.规范推导d.最左归约的逆过程3.1.17.一文法G:SS+T|T（陕西省1998年自考题）TT*P|PP(S)|i则句型P+T+i的短语有_。a. i,P+Tb. P,P+T,i,P+T+ic. P+T+id. P,P+T,i多项选择题：3.2.1.下面哪些说法是错误的_。（陕西省1998年自

29、考题）a.有向图是一个状态转换图b.状态转换图是一个有向图c状态转换图可以用DFA表示 d. DFA可以用状态转换图表示e.有向图是一个DFA3.2.2.对无二义性文法来说，一棵语法树往往代表了_。a.多种推导过程b.多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最右推导过程3.2.3如果文法G存在一个句子，满足下列条件_之一时，则称该文法是二义文法。a.该句子的最左推导与最右推导相同b、该句子有两个不同的最左推导c.该句子有两个不同的最右推导d,该句子有两棵不同的语法树e.该句子的语法树只有一个3.2.4.语法分析时通过_操作使用符号栈。（陕西省2000年自考题）a. 移进b

30、. 归约c. 比较d. 接受e. 出错处理3.2.5.算符优先文法与算符优先函数的关系描述中，下列_正确。（陕西省1997年自考题）a、一个算符优先文法可能不存在算符优先函数与之对应b. 一个算符优先文法可能存在多对算符优先函数与之对应c.一个算符优先文法一定存在多对算符优先函数与之对应d.一个算符优先文法一定存在算符优先函数与之对应e.一个算符优先文法一定存在有限对算符优先函数与之对应3.2.6.有一文法G: S-AB （陕西省1998年自考题）A-aAb|B一cBd|它不产生下面_集合。a. anbmcndm|n,m0b. anbcmdm|n,m0c. anbmcmdn|n,m0d. an

31、bncmdm|n,m0e. anbncndn|n03.2.7文法的无二义性是指_。a.文法中不存在句子有两个不同的最左推导b.文法中不存在句子有两个不同的最右推导c.文法中不存在句子有不同的推导d.文法中不存在句子有两裸不同的语法树e.文法中不存在句子有不同的最左和最右推导3.2.8. 文法G：SaAcB|BdAAaB|cBbScA|b则句型aAcbBdcc的短语是_。a. Bdb. cc. bBdccd. aAcbBdcce. cbBd3.2.9.在自下而上的语法分析中，应从_开始分析。a.句型b.句子c.以单词为单位的程序d.文法的开始符e.句柄3.2.10.对正规文法描述的语言，以下_有

32、能力描述它。a. 0型文法b. 1型文法c.上下文无关文法d.右线性文法e.左线性文法填空题：3.3.1规范归约中的可归约串是指_;算符优先分析中的可归约串是指_。3.3.2.文法中的终结符和非终结符的交集是_。词法分析器交给语法分析器的文法符号一定是_，它一定只出现在产生式的_部。3.3.3.在自上而下的语法分析中，应先消除文法的_递归，再消除文法的_递归。3.3.4.规范归约是指在移进过程中，当发现栈顶呈现_时，就用相应产生式的_符号进行替换。3.3.5当文法非终结符的所有_两两_时，该文法对应的句子分析不含回溯。3.3.6.最左推导是指每次都对句型中的_非终结符进行扩展。（陕西省1998

33、年自考题）3.3.7.在语法分析中，最常见的两种方法一定是_分析法，另一是_分析法。（陕西省1998年自考题）3.3.8._语法分析的关键问题是精确定义可归约串的概念。（陕西省2000年自考题）3.3.9. Chomsky定义的4种形式语言文法为：_文法，又称_文法；_文法，又称_文法；_文法，又称_文法；_文法，又称_文法。（中国科技大学1999年研究生试题）3.3.10. LL(K)文法中，第一个L表示_，第二个L表示_，K表示_，通常情况下K_。（西安电子科大2000年研究生试题）3.3.11采用_语法分析时，必须消除文法的左递归。3.3.12_树代表推导过程，_树代表归约过程。3.3.

34、13.自下而上分析法采用_、归约、错误处理、_等四种操作。（陕西省1999年自考题）3.3.14设是文法G的一个句型，A是非终结符，则是句型相对于A的短语，若_；是句型相对于A的直接短语，若_；是句型的句柄，若_。（西安电子科大2000年研究生题）3.3.15Chomsky把文法分为_种类型，编译器构造中采用_和_文法，它们分别产生_和_语言，并分别用_和_自动机识别所产生的语言。（西安电子科大2000年研究生试题）判断题：3.4.1语法分析之所以采用上下文无关文法是因为它的描述能力最强。（）3.4.2欲构造行之有效的自上而下分析器，则必须消除左递归。（）3.4.3文法(有图片)描述的语言是（

35、a|bc）* ( )3.4.4 在自下而上的语法分析中，语法树与分析树一定相同。（）3.4.5 二义文法不是上下文无关文法。（陕西省1999年自考题）（）3.4.6 每一个算符优先文法，必定能找到一组优先函数与之对应。（陕西省2000年自考题）（）3.4.7 语法分析时必须先消除文法中的左递归。（）3.4.8 规范归约和规范推导是互逆的两个过程。（）3.4.9 一个文法所有句型的集合形成该文法所能接受的语言。（）3.4.10 LL(1)文法一定不含左递归和二义性。（）综合题3.5.1 简答题1句柄 2.素短语3语法树4.归约5.推导3.5.2给出上下文无关文法的定义。3.5.3 Chomsky

36、将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左线性文法、正规文法之间的主要区别。3.5.4 文法G是LL(1)文法的充分必要条件是什么？3.5.5 文法GS：SaSPQ|abQQPPQbPbbbQbecQcc（1)它是Chomsky哪一型文法？（2）它生成的语言是什么？3.5.6 指出下述文法的所有类型，并给出所描述的语言。（1）SBe （2）A|aB（3）TSabcABeC|Af BAb|a SAabcAAe|e ACCf AaSaDfDA cAcS3.5.7 按指定类型，给出语言的文法。（1）L=aidjil的上下文无关文法。(2)字母表=a,b上的同时只有奇数个a和

37、奇数个b的所有串的集合的正规文法。(3）由相同个数a和b组成句子的无二义文法。3.5.8 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。SSandS|S or S|not S|p|q|(S)3.5.9 有文法G：SaAcB|BdAAaB|cBbScA|b（1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)写出句子acabcbbdcc的最左推导过程。3.5.10对文法G：EE+T|TTT*P|PPi（1)构造该文法的优先关系表（不考虑语句括号），并指出此文法是否为算符优先文法；(2）构造文法G的优先函数3.5.11 在上一题中，如果将文法改为EE+E|E*E|i,在不

38、改动文法的情况下是否同样能构造出优先关系表？此外，针对例3.14中的文法与本例中的文法，对算符优先分析快于规范归约进行说明。3.5.12 对于文法GS：S(L)|aS|aLL,S|S（1)画出句型（s，（a）的语法树。(2)写出上述句型的所有短语、直接短语、句柄和素短语。3.5.13 构造算符文法GH的算符优先关系（含）。GH：HH;M|MMd|aHb3.5.14 设有文法GS为：Sa|b|(A)ASdA|S（1)完成下列算符优先关系表，见表3.6.并判断GS是否为算符优先文法。(2）给出句型（SdSdS)的短语、简单短语、句柄、素短语和最左素短语。（3)给出输入串(adb)#的分析过程。3.

39、5.15 下面映射if语句的文法GS是算符优先文法吗？若是，则构造其优先关系矩阵。若不是，请按照多数程序设计语言（如Pascal)的习惯，给出一个相应的算符优先文法。GS：SiBtS|iBtSeS|aBb3.5.16 文法GG3.5.17 已知文法GA为：AaAB1|aBBb|d（I）试给出与GA等价的LL(I）文法GA。（2)构造GA的预测分析表。（3）给出输入串aadl#分析过程。3.5.18 将GV改造为LL（1）文法。GV: VN|NEEV|V+ENi3.5.19 有文法GS: S-BAA-BS|dBaA|bS|c(I）证明文法G是LL(I）文法。（2）构造LL（1）分析表。(3）写出

40、句子adccd的分析过程。3.5.20 考虑文法GT：TT*F|FFFP|PP(T)|i（1)证明T*P(T*F)是该文法的一个句型，并指出其直接短语和句柄。(2)构造文法G的优先关系表（要求写出步骤）。3.5.21 给出算符优先文法的分析算法。3.5.22 文法G的产生式集为：SS+S|S*S|i|（s），对于输入串i+i*i；（1)给出一个推导；(2）画出一棵语法树；（3)文法G是否是二义性的，请证明你的结论。3.5.23 已给文法GE：EEOE|(E)|i0+|*试将其改造为可进行不带回溯的自顶向下分析的文法，并给出其相应的LL(1)分析表。3.5.24 考虑文法G(S)：S(T)|a+

41、S|aTT,S|S消除文法的左递归及提取公共左因子，然后，对每个非终结符，写出不带回溯的递归子程序。3.5.25 有映射程序设计语言if-the-else语句的文法GS: SiEtSeS|EtS|aEb其中，else遵从最近匹配原则。（1)试改造文法，并为之构造LL（1）分析表。(2）利用构造的分析表分析句子ibtibtaea,要求给出分析过程中每一步的分析栈和输入串的变化以及输出信息。3.5.26 下述文法描述了C语言整数变量的声明语句：DTLTint|long|shortLid|L,id（1)改造上述文法，使其接受相同的输入序列，但文法是右递归的。(2)分别用上述文法和改造文法，为输入序列

42、int a,b,c构造分析树。3.5.27 设有文法GW：WAOAAO|W1|0请改写文法，消除规则左递归和文法左递归。3.5.28 文法GP及相应翻译方案为：PbQb print:”1”QcR print:”2”Qa print:”3”RQad (print:”4”（1)该文法是不是算符优先文法，请构造算符优先关系表证实之。(2)输入串为bcccaadadadb时，该翻译方案的输出是什么。3.5.29 设有文法GS：SSAS|bAbSb|b试构造一个与其等价的算符文法。3.5.30 在算符优先分析法中，为什么要在找到最左素短语的尾时，才返回来确定其对应的头，能否按扫描顺序先找到头后找到对应的

43、尾，为什么？3.5.31 试证明在算符文法中，任何句型都不包含两个相邻的非终结符。3.5.32假定文法包含产生式A，V*（V是文法的词汇表，由终结符和非终结符组成的集合），证明：如果FIRST（）FOLLOW（A），则该文法不是LL（1)文法。3.5.33 给出文法G1：SaSb|PAbPc|bQcBQa|a（1)它是Chomsky哪一型文法？（2）它生成的语言是什么？（3)它是不是算符优先文法？请构造算符优先关系表证实之。(4)请证实所有左递归文法有公共左因子的文法均不是LL（1)文法。(5)文法G1消除左递归、提取公共左因子后是不是LL (1）文法？请证实。3.5.34 简答题（1)什么是

44、文法的二义性？二义性问题的不可判定指的是什么？(2)在规范句型中，句柄以右的符号有什么特征？为什么？3.5.35 写正规文法G,它产生的语言是L(G)= anibncp|m,n,p03.5.36 语言L是所有由偶数个0和偶数个1组成的句子的集合，给出定义L的正规文法。3.5.37 已知文法GS：SABS|ABABBAA0B1该文法是几型的？该文法所产生的语言是什么？（用自然语言描述）写出与该文法等价的CFG文法。3.5.8 写一个上下文无关文法G，使得L(G)=anbmcmdn|n0,m1。3.5.39 写一个文法G，使其语言为L(G)= anbm|nm1。3.5.40 生成语言1=albmc

45、lanbn|1=O,m=1，n=2的文法是什么？它是Chomsky那一型文法？3.5.41文法GP：PaPQR|abRRQQRbQbbbRbecRcc它是Chomsky哪一型文法？请证aaabbbccc是GP的一个句子。3.5.42文法GS：SaSPQ|abQQPPQbPbbbQbecQcc（1)它是Chomsky哪一型文法？（2）它生成的语言是什么？3.5.43 给定文法GS：S(S)S|，给出句子（）（）（）（）的规范推导，并指出每步推导所得句型的句柄，画出该句子的语法推导树，指出所有的短语和直接短语。3.5.44 设文法GS：S(A)|aAA+S|S（1）构造各非终结符的FIRSTVT和

46、LASTVT集合。（2）构造优先关系表。3.5.45已知文法GS：SdABAaA|aBBb|（1)试问GS是否为正规文法，为什么？(2）GS所产生的语言是什么？（3) GS能否改写为等价的正规文法?3.5.46 选择题有文法GS：SaA|a|bC，AaS|bB，BaC|bA|b，CaB|bS，则_为L(G) 中句子。a. aloob5oabloob. alooob5ooabac. a500b60aab2ad. a l00 b4oab10 aa3.5.47 对文法GS：S#S#SfstSSi=EEE+T|TTPT|PP(E)|i（1）求各非终结符的FIRSTVT和LASTVT集合。(2）构造该文

47、法的优先关系表。（请将终结符以、（、i, f, t,）、的顺序构造优先关系表）3.5.48 有文法R:=i|(T)，T:=T，R|R，完成表3.21所示的算符优先关系表（填写第一、第二行）。3.5.49 文法GM是否LL(1)的，说明理由。GM：MTBTBa|BDb|eT|Dd|3.5.50 将文法GE改写为等价的LL(I)文法，并给出相应的预测分析表。GE：ETTF|TEFi|Fi3.5.51 已知文法GS: SS*aP|aP|*aPP+aP|+a（1）将文法GS改写为LL(1）文法GS。(2)写出文法G S的预测分析表。5第四章语法分析器的自动构造典型例题:单项选择题4.1.1.若a为终结

48、符，则Aaa为_项目。a.归约b.移进c.接受d.待约4.1.2.两个LR(1)项目集如果除去_后是相同的，则称这两个LR(1)项目同心。a.项目b.活前缀c.搜索符d.前缀4.1.3同心集合并不会产生冲突。a.二义b.移进移进c.移进归约d.归约归约4.1.4左结合意味着_。a.打断联系实行移进b.打断联系实行归约c.建立联系实行移进d.建立联系实行归约4.1.5.若项目集Ik含有Aa，则在状态k时，仅当面临的输入符号aFOLLOW(A)时，才采取“Aa”动作的一定是_。a. LALR文法b. LR(0)文法c. LR(1)文法d. SLR(1)文法4.1.6就文法的描述能力来说，有_。a.

49、 SLR(1）cLR(0)b. LR(1）cLR(0)c. SLR(1）cLR(1）d.无二义文法cLR(1）4.1. 7.在LR(0)的ACTION子表中，如果某一行中存在标记为ri”的栏，则_。a.该行必定填满rib.该行未填满ric.其他行也有rid. goto子表中也有ri4.1.8.一个_指明了在分析过程中的某时刻所能看到产生式多大一部分。a.活前缀b.前缀c.项目d.项目集4.1.9.若B为非终结符，则AaB为_项目。a.接受b.归约c.移进d.待约4.1.10同心集合并有可能产生新的冲突。a.归约b.移进移进c.移进归约d.归约归约4.1.11右结合意味着。a.打断联系实行归约b

50、.建立联系实行归约c.建立联系实行移进d.打断联系实行移进4.1.12.若项目集Ik含有Aa，则在状态K时，无论面临什么输入符号都采取“A归约”的动作一定是。a. LR(1）文法b. LALR(1)文法c. LR(0)文法d. SLR(1）文法4.1.13就文法的描述能力来说，有。a.无二义文法cSLR(1）b. LR(0) cLR(1)c.无二义文法cLR(0)d. LR(1) cLR(0)多项选择题：4.2.1一个LR分析器包括_。a.一个总控程序b.一个项目集。c.一个活前缀d.一张分析表e.一个分析栈4.2.2 LR分析器核心部分是一张分析表，该表包括_等子表。a. LL(1）分析b.

51、优先关系c. GOTOd. LRe. ACTION4.2.3每一项ACTIONS,a所规定的动作包括_。a.移进b.比较c.接受d.归约e.报错4.2.4.对LR分析表的构造，有可能存在_动作冲突。a.移进b.归约c.移进归约d.移进移进e .归约归约4.2.5就文法的描述能力来说，有_。a. SLR(1）c LR(1）b. LR(0) c SLR(1）c. LR(0) c LR(1）d. LR(1）c无二义文法e. SLR(1）c无二义文法4.2.6对LR分析器来说，存在_等分析表的构造方法。a. LALRb. LR(0)c. SLR(1)d. SLR(0)e. LR(1)4.2.7.自上而

52、下的语法分析方法有_。a.算符优先分析法b. LL(1)分析法c. SLR(1)分析法d. LR(0)分析法e. LALR(1)分析法填空题：4.3.1对于一个文法，如果能够构造_，使得它的_均是唯一确定的，则称该文法为LR文法。4.3.2.字的前缀是指该字的_。4.3.3活前缀是指_的一个前缀，这种前缀不含_之后的任何符号。4.3.4.在LR分析过程中，只要的已扫描部分保持可归约成一个_，则扫描过的部分正确。4.3.5.将识别_的NFA确定化，使其成为以_为状态的DFA,这个DFA就是建立的基础。4.3.6. Aa称为_项目；对文法开始符S，称Sa为_项目；若a为终结符，则称Aaa为_项目；

53、若B为非终结符，则称AaB为_项目。4.3.7. LR(0)分析法的名字中“L”表示，“R”表示，0”表示_。4.3.8一个LR分析器包括两部分：_和_.4.3.9.两个LR(1)项目集如果除去_后是相同的，则称这两个LR(1)项目集_。4.3.10.构成识别一个文法_的DFA的项目集全体，称为这个文法的LR(0) _.4.3.11.一个活前缀的_，就是从识别文法活前缀DFA的初态出发，经读出后所到达的那个4.3.12左结合意味着打断联系实行_，右结合意味着打断联系实行_。4.3.13.同心集合并不会产生冲突，但可能产生_冲突。判断题：4.4.1. LR分析法在自左至右扫描输入串时就能发现错误

54、，但不能准确地指出出错地点。（）4.4.2.构造LR分析器的任务就是产生LR分析表。（）4.4.3 .LR文法肯定是无二义的，一个无二义文法决不会是LR文法。（）4.4.4.在任何时候，分析栈的活前缀X1X2.Xm的有效项目集就是栈顶状态Sm所在的那个项目集。（）4.4.5同心集的合并有可能产生新的“移进”“归约”冲突。（）4.4.6.由于LR(0)分析表构造简单，所以它的描述能力强、适用面宽；LR(1)分析表因构造复杂而描述能力弱、适用面窄。（）4.4.7所有LR分析器的总控程序都是一样的，只是分析表各有不同。（）4.4.8. LR分析技术无法适用二义文法。（）4.4.9.项目A12对活前缀

55、1是有效的，其条件是存在规范推导S*=aAW= a 2。（）14.4.10. SLR(1)文法的特点是：当符号栈中的符号串为，而面临的输入符号为则存在把归约为A的规范句型的前缀A时，方可把a归约为A。（）综合题4.5.1请指出图4.2中的LR分析表（a）、（b）、（c）分属LR（0）、SLR和LR（1）中的那一种，并说明理由。4.5.2文法G的产生式如下：SBBBaB|b请分别构造该文法的（1) LR (0）分析表；(2）SLR分析表；(3）规范LR分析表（即LR（1）分析表）；（4）LALR分析表。4.5.3什么是规范句型的活前缀？引进它的意义何在？4.5.4对于文法GS：SAS|bASA|

56、a(1)列出所有LR (0)项目。(2)根据列出的项目构造识别文法活前缀的NFA并确定化为DFAo（3)证明DFA的所有状态全体构成文法LR（0)规范族。4.5.5 LR分析器与优先关系分析器在识别句柄时的主要异同是什么？4.5.6 LR（0）、SLR(1), LR（1)及LALR有何共同特征？它们的本质区别是什么？试论述之。4.5.7 为二义文法G构造一个LR分析表（详细说明构造方法）。其中终结符“，”满足右结合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。文法GT：TTAT|bTeaA，|；4.5.8 二义文法GS,符的优先性和结合性说明如下：（a）else与最近的if结合(b）“；”优先性大于if(c）“；”优先性大于else(d)“；”服从左结合请使用LR分析法的基本思想，凭借上述条件，为GS构造LR分析表，要求