编译原理阶段练习二.doc

编译原理练习二一、 填空题1、假设G是一个文法，S是文法的开始符号，如果S*x则称x是句型。2、文法G产生的 句子 的全体是该文法描述的语言。3、文法GS：SAB AaA|e BbBc|bc描述的语言L（GS）= anbmcm | n0,m1 。4、已知文法GE：ET|E+T|E-TTF|T*F|T/FF（E）|i该文法的开始符号是 E ，终级符号集合VT是 + ,- ,* ,/ ,( ,) ,i ，非终级符号集合VN是E, T, F，句型T+T*F+i的短语有T+T*F+i, 第一个T，T*F和i。改写该文法以消除直接左递归，改写后的文法为：ET(+|-)T, TF(*|/)F , F (E)|i 。5、乔姆斯基定义的四种形式语言文法分别为： 0型文法（又称 短语文法）、1型文法（又称 上下文有关 文法）、 2型 文法（又称上下文无关 文法）、3型文法（又称 正规 文法）。6、自顶向下语法分析方法的基本思想是：从 识别符号 出发，不断建立 直接推导 ，试图构造一个推导序列，最终由它推导出与输入符号串相同的 符号串 。7、递归下降法的主要原理是，对每个非终极符按其产生式结构产生相应语法分析子程序，其中的终极符产生 匹配命令 ，而非终极符则产生 调用命令 ，由于文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。8、LL（K）分析法中，“K”的含义是 向输入串中查看k个输入符号 。9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行 直接归约 ，试图 归约 到文法的 开始符号 。10、LR（0）分析法的名字中，“L”的含义是 从左到右进行分析 ，“R”的含义是 采用最右推导的逆过程最左归约 ，“0”的含义是 向貌似句柄的符号串后查看0个输入符号 。二、 选择题（单项或多项）1、文法G所描述的语言是 d 的集合。a. 文法G的字汇表V中所有符号组成的符号串b. 文法G的字汇表V的闭包V*中的所有符号串c. 由文法的开始符号推出的所有符号串d. 由文法的开始符号推出的所有终极符号串2、巴科斯-诺尔范式（即BNF）是一种广泛采用的 c 的工具。a.描述规则b.描述语言c.描述文法d.描述句子3、描述语言L=ambn|nm1的文法为 d 。a. ZAbb b. ZABbAaA|aAAa|aBbB|bBaBb|bc.ZAbd.ZaAbAaAb|aAAb|aAb|e4、II1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子的有 b c d .a.ab0b.a0c01c.aaad.bc105、 若一个文法是递归的，则它所产生语言的句子个数 a 。a.必定是无穷的b.是有限个的c.根据具体情况而定6、一个句型中的最左 b 称为给句型的句柄。a.短语b.简单短语c.素短语d.终极符号7、一个上下文无关文法G包括四个组成部分依次为：一组 g ，一组 h ，一个 e ，以及一组 c 。a.字符串b.字母数字串c.产生式d.结束符号e.开始符号f.文法g.非终极符号h.终极符号8、下列文法 a 二义文法EEiT|TTT+F|iF|FFE*|（a.是b.不是c.无法判定9、编译过程中，语法分析器的任务是 b c d 。a. 分析单词是怎样构成的b. 分析单词串是如何构成语句和说明的c. 分析语句和说明是如何构成程序的d. 分析程序的结构10、语法分析的常用方法是 a b 。a.自顶向下b.自底向上c.自左向右d.自右向左11、编译程序中的语法分析器接受以 c 为单位的输入，并产生有关信息供以后各阶段使用。a.表达式b.产生式c.单词d.语句12、高级语言编译程序常用的语法分析方法中，递归下降分析方法属于 a 分析方法。a.自顶向下b.自底向上c.自左向右d.自右向左13、LL（1）文法的条件是 c 。a.对形如Ugx1| x1| | xn的规则，要求FIRST（xi） FIRST（xj）=, (ij)b.对形如Ugx1| x1| | xn的规则，若xi *e ，要求FIRST（xj） FOLLOW（U）=c.(a)和（b）d.都不是14、已知文法GE：EgTEEg+TE|eTgFTT g*FT|eFg(E)|idFOLLOW（F）= *,+,#,，FIRST（T）= *,e 。a.*，+b.*，ec.+，#，)d.*，+，#，)e.#，)f.*，+，#，)，id15、LR语法分析栈中存放的状态是识别 b 的DFA状态。a.前缀b.可归前缀c.项目d.句柄三、 设有文法GS：SgAAgB|IF A THEN A ELSE ABgC|B+C|+CCgD|C*D|*DDgx|（A）|-D(1) 试问其中哪些是终极符号，哪些是非终极符号(2) 对于下列符号串：j（x*-x）kIF x+x THEN x*x ELSE -xlIF -x THEN x ELSE IF x THEN x+x ELSE x试分别构造其推导的语法分析树，并指出句柄。解答：（1）非终极符号集S，A，B，C，D 终极符号集IF，THEN，ELSE，+，-，*，（，），x （2）句型推导的语法树如下图句型（x*-x）的句柄为 第一个x句型IF x+x THEN x*x ELSE -x的句柄为 第一个x句型IF -x THEN x ELSE IF x THEN x+x ELSE x的句柄为-xAAELSETHENAIFSSABCBCBBC+BCD*DCxDDCxDDx-DxxA）（BC*DCDB-DxxASIFAAELSETHENDCx-DDCBELSEATHENAIFABxDCBBBxDCC+BxDxDCx四、 设有文法GS：Sga|e|（T）TgT,S|S请给出句子（a,(a,a)）的最左、最右推导。解答：最左推导为：S(T)(T,S)(S,S) (a,S) (A,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a)最右推导为：S(T) (T,S) (T,(T) (T,(T,S) (T,(T,a) (T,(S,a) (T,(a,a) (S,(a,a) (a,(a,a)五、 试消除下列文法的直接左递归G1S：SgSa|Ab|b|cAgBc|aBgSb|b解答：Sg(bcb|ab|b|c)SSg(a|bcb)S|eAgBc|aBgSb|bG2S：Sga|e|（T）TgT.S|S解答：Sga|e|（T）TgSTTg.ST|e六、 试构造生成语言L=anbnci|n1,i0的文法。解答：SgaAbBAgaAb|eBgcB|e七、有文法GN：NgSE|ESgSD|DEg0|2|4|6|8|10Dg0|1|2|3|4|5|6|7|8|9证明此文法有二义性；此文法所描述的语言是什么？证明：对于文法的句子110，存在两棵不同的语法树或两种不同的最左（最右）推导，所以文法具有二义性。NSEDE1E110NSESDEDDE1DE11E110此文法描述的语言是偶数集合八、 知文法GS：SgeT|RTTgDR|eRgdR|eDga|bd(1)FIRST(S)= a,b,d,e, e ,FIRST(T)= a,b, e ,FIRS