资源描述：
《编译原理阶段练习二》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理练习二一、填空题1、假设G是一个文法，S是文法的开始符号，如果SÞ*x则称x是句型。2、文法G产生的句子的全体是该文法描述的语言。3、文法G[S]：S®ABA®aA
2、eB®bBc
3、bc描述的语言L（G[S]）={anbmcm
4、n³0,m³1}。4、已知文法G[E]：E®T
5、E+T
6、E-TT®F
7、T*F
8、T/FF®（E）
9、i该文法的开始符号是E，终级符号集合VT是{+,-,*,/,(,),i}，非终级符号集合VN是{E,T,F}，句型T+T*F+i的短语有T+T*F+i,第一个T，T*F和i。改写该文
10、法以消除直接左递归，改写后的文法为：E®T{(+
11、-)T},T®F{(*
12、/)F},F®(E)
13、i。5、乔姆斯基定义的四种形式语言文法分别为：0型文法（又称短语文法）、1型文法（又称上下文有关文法）、2型文法（又称上下文无关文法）、3型文法（又称正规文法）。6、自顶向下语法分析方法的基本思想是：从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。7、递归下降法的主要原理是，对每个非终极符按其产生式结构产生相应语法分析子程序，其中的终极符产生匹配命令，而非终极符则产
14、生调用命令，由于文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。8、LL（K）分析法中，“K”的含义是向输入串中查看k个输入符号。9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行直接归约，试图归约到文法的开始符号。10、LR（0）分析法的名字中，“L”的含义是从左到右进行分析，“R”的含义是采用最右推导的逆过程——最左归约，“0”的含义是向貌似句柄的符号串后查看0个输入符号。二、选择题（单项或多项）1、文法G所描述的语言是d的集合。a.文法G的字汇
15、表V中所有符号组成的符号串a.文法G的字汇表V的闭包V*中的所有符号串b.由文法的开始符号推出的所有符号串c.由文法的开始符号推出的所有终极符号串2、巴科斯-诺尔范式（即BNF）是一种广泛采用的c的工具。a.描述规则b.描述语言c.描述文法d.描述句子3、描述语言L={ambn
16、n³m³1}的文法为d。a.Z®Abbb.Z®ABbA®aA
17、aA®Aa
18、aB®bB
19、bB®aBb
20、bc.Z®Abd.Z®aAbA®aAb
21、aA®Ab
22、aAb
23、e4、I®I1
24、I0
25、Ia
26、Ic
27、a
28、b
29、c下列符号串中是该文法的句子的
30、有bcd.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二义文法E®EiT
31、TT®T+F
32、iF
33、FF®E*
34、（a.是b.不是c.无法判定9
35、、编译过程中，语法分析器的任务是bcd。a.分析单词是怎样构成的b.分析单词串是如何构成语句和说明的c.分析语句和说明是如何构成程序的d.分析程序的结构10、语法分析的常用方法是ab。a.自顶向下b.自底向上c.自左向右d.自右向左11、编译程序中的语法分析器接受以c为单位的输入，并产生有关信息供以后各阶段使用。a.表达式b.产生式c.单词d.语句12、高级语言编译程序常用的语法分析方法中，递归下降分析方法属于a分析方法。a.自顶向下b.自底向上c.自左向右d.自右向左13、LL（1）文法的条件是c。a.对
36、形如Ugx1
37、x1
38、…
39、xn的规则，要求FIRST（xi）ÇFIRST（xj）=Æ,(i¹j)b.对形如Ugx1
40、x1
41、…
42、xn的规则，若xiÞ*e，要求FIRST（xj）ÇFOLLOW（U）=Æc.(a)和（b）d.都不是14、已知文法G[E]：EgTE’E’g+TE’
43、eTgFT’T’g*FT’
44、eFg(E)
45、idFOLLOW（F）={*,+,#,}}，FIRST（T’）={*,e}。a.{*，+}b.{*，e}c.{+，#，)}d.{*，+，#，)}e.{#，)}f.{*，+，#，)，id}15、LR
46、语法分析栈中存放的状态是识别b的DFA状态。a.前缀b.可归前缀c.项目d.句柄一、设有文法G[S]：SgAAgB
47、IFATHENAELSEABgC
48、B+C
49、+CCgD
50、C*D
51、*DDgx
52、（A）
53、-D(1)试问其中哪些是终极符号，哪些是非终极符号(2)对于下列符号串：j（x*-x）kIFx+xTHENx*xELSE-xlIF-xTHENxELSEIFxTHENx+xELSEx试分别构造其推导的语法分析树，并指出
