编译原理阶段练习二

1、编译原理练习二一、填空题1、 假设G是一个文法，S是文法的开始符号，如果 S *x那么称x是句型。2、文法G产生的 句子 的全体是该文法描述的语言。3、文法 GS: S AB A aA| B bBc|bc 描述的语言 L GS = anbmcm | n 0,m 1。4、文法GE:E T|E+T|E-TT F|T*F|T/FF E |i该文法的开始符号是E，终级符号集合 V是+，- ,*，/ , ,i ，非终级符号 集合Vn是E, T, F，句型T+T*F+i的短语有T+T*F+i,第一个T，T*F和i。改 写该文法以消除直接左递归，改写后的文法为：E T +卜T, T F *|/ F , FE

2、|i。5、 乔姆斯基定义的四种形式语言文法分别为：0型文法又称短语文法、 1型文法又称上下文有关文法、2型文法又称上下文无关 文法、 3型文法又称正规文法。6、 自顶向下语法分析方法的根本思想是：从识别符号 出发，不断建 立 直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的 符号串。7、递归下降法的主要原理是，对每个非终极符按其产生式结构产生相应语法分析子程序，其中的终极符产生 匹配命令，而非终极符那么产生 调用命令， 由于文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。8、 LLK分析法中，“ K的含义是 向输入串中查看k个输入符号。9、自底向上语法分析

3、方法的根本思想是：从待输入的符号串开始，利用文法的 规那么步 步 向上进行 直 接归 约，试图 归约 到文法 的 开 始符 号从左到右进行分析，“ R，“ 0 的含义是向貌似句10、LR0分析法的名字中，“ L的含义是 的含义 是 采用最右推导的逆过程一一最左归约 柄的符号串 后查看0个输入符号。二、选择题单项或多项1、文法G所描述的语言是 d的集合a. 文法G的字汇表V中所有符号组成的符号串b. 文法G的字汇表V的闭包V*中的所有符号串c. 由文法的开始符号推出的所有符号串d. 由文法的开始符号推出的所有终极符号串2、 巴科斯-诺尔范式即BNF是一种广泛采用的c的工具a. 描述规那么b.描述

4、语言c.描述文法d.描述句子3、描述语言L=a mbn|n m 1的文法为d。a.ZAbbb.Z ABbAaA|aAAa|aBbB|bBaBb|bc.ZAbd. ZaAbAaAb|aAAb|aAb|4、Il1|IO|la|lc|a|b|c列符号串中是该文法的句子的有 b c da. ab0 b. a0c01 c. aaa d. bc105、假设一个文法是递归的，那么它所产生语言的句子个数a.必定是无穷的b.a.短语b.简单短语c.素短语d.终极符号7、一个上下文无关文G包括四个组成局部依次为：一法组g，一组h，一个 e，以及一组c。a.字符串b.字母数字串c.产生式d.结束符口号e.开始符号f

5、.文法g.非终极符h.终极符-口号8、列文法E T EiT|T F T+F|iF|F a. E*|是b.不是c.无法判定是有限个的c.根据具体情况而定6、一个句型中的最左b称为给句型的句柄。二义文 编译过程中，语法分析器的任务是9、 分析单词是怎样构成的 分析单词 a串是如何构成语句和说明的分析b. 语句和说明是如何构成程序的分 c析程序的结构d.10、 语法分析的常用方法自底向c.自左向右d.自右向左是11、 编译下序中的语法分析器接受以c为单位的输入，并产生有关信息供以后各阶段使用。a.表达式b.产生式c.单词d.语句12、 高级语言编译程序常用的语法分析方法中，递归下降分析方法属于a 分

6、析方法。a.自顶向下b.自底向上c.自左向右d.自右向左13、 LL 1文法的条件是c。a. 对形如 U X1| X1|? | Xn 的规那么，要求 FIRSTXiFIRSTxj = , i jb. 对形如 U X1| X1|? | xn 的规那么，假设 Xi *，要求 FIRST xjFOLLOW Uc. a和bd. 都不是14、文法GE:E TE 'E' +TE' |T FT 'T' *FT ' |F E |idFOLLOW F = *,+,#,，FIRST T' = *, oa. * , + b.* ,c. +, #,d. * ,

7、+, #, e.#,f. * , +, #, , id15、LR语法分析栈中存放的状态是识别 b的DFA状态。a.前缀b.可归前缀c.工程d.句柄三、设有文法GS:SAA B|IF A THEN A ELSE AB C|B+C|+CC D|C*D|*DD x| A |-D1 试问其中哪些是终极符号，哪些是非终极符号2 对于以下符号串： x*-x IF x+x THEN x*x ELSE -xIF -x THEN x ELSE IF x THEN x+x ELSE x 试分别构造其推导的语法分 析树，并指出句柄。解答：(1)非终极符号集S , A, B, C, D终极符号集IF , THEN ,

8、 ELSE , +，-，*,(,), x (2)句型推 导的语法树如以下列图句型(x*-x )的句柄为第一个X句型IF x+x THEN x*x ELSE -x 的句柄为 第一个 xABCELSEABCD+BCDxCD的句柄为-x句型 IF -x THEN x ELSE IF x THEN x+x ELSE xABAHENBTHENATHENABCDxCD四、设有文法GS:S a|( T )T T,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,

9、a)最右推导为:S (T) (T,S)仃,(T) (T, (T ,S) (T, (T ,a) (T,(S,a)仃,(a,a) (S,(a,a) (a,(a,a)五、试消除以下文法的直接左递归GiSS Sa|Ab|b|cA Bc|a B Sb|b解答：S (bcb|ab|b|c)S S' ' (a|bcb)S' | A Bc|aG2S解答:B Sb|bS a| |( T)T T.S|SS a| |( T)T ST' T' .ST' |六、 试构造生成语言L=a nbnci|n 1,i 0的文法。解答：S aAbBA aAb|B cB|七、有文法GN:N SE|ES SD|DE 0|2|4|6|8|10D | 1|2|3|4|5|6|7|8|9证明此文法有二义性；此文法所描述的语言是什 么？证明：对于文法的句子110，存在两棵不同的语法树或两种不同的最左 (最右)推导，所以文法具有二义性。N SE DE 1E 110N SE SDE DDE 1DE 11E 110 此文法描述的语言是偶数集合八、知文法GS:S eT|RTT DR|R dR|D a|bd(1) FIRST