还剩4页未读,继续阅读
文本内容:
编译原理练习二
1、填空题
1、假设G是一个文法,S是文法的开始符号,如果S*x则称x是句型
2、文法G产生的句子的全体是该文法描述的语言
3、文法G[S]SABAaA|BbBc|bc描述的语言L(G[S])={anbmcm|n0m1}
4、已知文法G[E]ET|E+T|E-TTF|T*F|T/FF(E)|i该文法的开始符号是E,终级符号集合VT是{+-*/i},非终级符号集合VN是{ETF},句型T+T*F+i的短语有T+T*F+i第一个T,T*F和i改写该文法以消除直接左递归,改写后的文法为ET{+|-T}TF{*|/F}FE|i
5、乔姆斯基定义的四种形式语言文法分别为0型文法(又称短语文法)、1型文法(又称上下文有关文法)、2型文法(又称上下文无关文法)、3型文法(又称正规文法)
6、自顶向下语法分析方法的基本思想是从识别符号出发,不断建立直接推导,试图构造一个推导序列,最终由它推导出与输入符号串相同的符号串
7、递归下降法的主要原理是,对每个非终极符按其产生式结构产生相应语法分析子程序,其中的终极符产生匹配命令,而非终极符则产生调用命令,由于文法递归相应子程序也递归,所以称这种方法为递归子程序方法或递归下降法
8、LL(K)分析法中,“K”的含义是向输入串中查看k个输入符号
9、自底向上语法分析方法的基本思想是从待输入的符号串开始,利用文法的规则步步向上进行直接归约,试图归约到文法的开始符号
10、LR
(0)分析法的名字中,“L”的含义是从左到右进行分析,“R”的含义是采用最右推导的逆过程——最左归约,“0”的含义是向貌似句柄的符号串后查看0个输入符号
2、选择题(单项或多项)
1、文法G所描述的语言是d的集合a.文法G的字汇表V中所有符号组成的符号串b.文法G的字汇表V的闭包V*中的所有符号串c.由文法的开始符号推出的所有符号串d.由文法的开始符号推出的所有终极符号串
2、巴科斯-诺尔范式(即BNF)是一种广泛采用的c的工具a.描述规则b.描述语言c.描述文法d.描述句子
3、描述语言L={ambn|nm1}的文法为da.ZAbbb.ZABbAaA|aAAa|aBbB|bBaBb|bc.ZAbd.ZaAbAaAb|aAAb|aAb|
4、II1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子的有bcd.a.ab0b.a0c01c.aaad.bc
105、若一个文法是递归的,则它所产生语言的句子个数aa.必定是无穷的b.是有限个的c.根据具体情况而定
6、一个句型中的最左b称为给句型的句柄a.短语b.简单短语c.素短语d.终极符号
7、一个上下文无关文法G包括四个组成部分依次为一组g,一组h,一个e,以及一组ca.字符串b.字母数字串c.产生式d.结束符号e.开始符号f.文法g.非终极符号h.终极符号
8、下列文法a二义文法EEiT|TTT+F|iF|FFE*|(a.是b.不是c.无法判定
9、编译过程中,语法分析器的任务是bcda.分析单词是怎样构成的b.分析单词串是如何构成语句和说明的c.分析语句和说明是如何构成程序的d.分析程序的结构
10、语法分析的常用方法是aba.自顶向下b.自底向上c.自左向右d.自右向左
11、编译程序中的语法分析器接受以c为单位的输入,并产生有关信息供以后各阶段使用a.表达式b.产生式c.单词d.语句
12、高级语言编译程序常用的语法分析方法中,递归下降分析方法属于a分析方法a.自顶向下b.自底向上c.自左向右d.自右向左
13、LL
(1)文法的条件是ca.对形如Ux1|x1|…|xn的规则,要求FIRST(xi)FIRST(xj)=ijb.对形如Ux1|x1|…|xn的规则,若xi*,要求FIRST(xj)FOLLOW(U)=c.a和(b)d.都不是
14、已知文法G[E]ETE’E’+TE’|TFT’T’*FT’|FE|idFOLLOW(F)={*+#}},FIRST(T’)={*}a.{*,+}b.{*,}c.{+,#,}d.{*,+,#,}e.{#,}f.{*,+,#,,id}
15、LR语法分析栈中存放的状态是识别b的DFA状态a.前缀b.可归前缀c.项目d.句柄
3、设有文法G[S]SAAB|IFATHENAELSEABC|B+C|+CCD|C*D|*DDx|(A)|-D1试问其中哪些是终极符号,哪些是非终极符号2对于下列符号串(x*-x)IFx+xTHENx*xELSE-xIF-xTHENxELSEIFxTHENx+xELSEx试分别构造其推导的语法分析树,并指出句柄解答
(1)非终极符号集{S,A,B,C,D}终极符号集{IF,THEN,ELSE,+,-,*,(,),x}
(2)句型推导的语法树如下图句型(x*-x)的句柄为第一个x句型IFx+xTHENx*xELSE-x的句柄为第一个x句型IF-xTHENxELSEIFxTHENx+xELSEx的句柄为-x
4、设有文法G[S]Sga||(T)TgTS|S请给出句子(aaa)的最左、最右推导解答最左推导为STTSSSaSATaTSaSSaaSaaa最右推导为STTSTTTTSTTaTSaTaaSaaaaa
5、试消除下列文法的直接左递归G1[S]SgSa|Ab|b|cAgBc|aBgSb|b解答Sgbcb|ab|b|cS’S’ga|bcbS’|AgBc|aBgSb|bG2[S]Sga||(T)TgT.S|S解答Sga||(T)TgST’T’g.ST’|
6、试构造生成语言L={anbnci|n1i0}的文法解答SgaAbBAgaAb|BgcB|
七、有文法G[N]NgSE|ESgSD|DEg0|2|4|6|8|10Dg0|1|2|3|4|5|6|7|8|9证明此文法有二义性;此文法所描述的语言是什么?证明对于文法的句子110,存在两棵不同的语法树或两种不同的最左(最右)推导,所以文法具有二义性NSEDE1E110NSESDEDDE1DE11E110此文法描述的语言是偶数集合
8、知文法G[S]SgeT|RTTgDR|RgdR|Dga|bd1FIRSTS={abde}FIRSTT={ab}FIRSTR={d}FIRSTD={ab}.2FOLLOWS={#}FOLLOWT={#}FOLLOWR={ab#}FOLLOWD={d#}.3该文法的LL
(1)分析表为abde#SgRTgRTgRTgeTgRTTgDRgDRgRgggDRgDgagbdAAELSETHENAIFSSABCBCBBC+BCD*DCxDDCxDDx-DxxA)(BC*DCDB-DxxASIFAAELSETHENDCx-DDCBELSEATHENAIFABxDCBBBxDCC+BxDxDCx。