编译原理阶段练习二

编译原理练习二一、填空题1、 假设G是一个文法，S是文法的开始符号，如果Sn*x则称x是句型。2、 文法G产生的的全体是该文法描述的语言。3、文法G[S]：StABA^aA|sB—bBc|bc描述的语言L(G[S])=4、己知文法G[E]：EtT|E十T|E-TTtF|T*F|T/FFt(E)|i该文法的开始符号是E,终级符号集合Vt是｛十「卢,/,(,),订,非终级符号集合Vn是｛E、T,£｝，句型T+T*F~H的短语有T十T*F十i,第一个T,T*F和1。改写该文法以消除直接左递归，改写后的文法为：TtF｛(*|/)F｝,Ft(E)|i。5、乔姆斯基定义的四种形式语言文法分别为：0型文法(乂称短语文法)、1型文法(乂称上下文有关文法)、2型文法(乂称上下文无关文法)、3型文法(乂称正规文法)。6、自顶向下语法分析方法的基本思想是：从识别符号出发,不断建立_直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相商的符号串。7、递归下降法的主要原理是，对每个非终极符按其产生式结构产生相应语法分析子程序，其中的终极符产生匹配命令，而非终极符则产生调用命令，由于文法递归相应子程序也递归，所以称这种方法为递归子程序方法或递归下降法。8、 LL(K)分析法中，“K”的含义是向输入串中查看k个输入符号。9、 自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行直接归约，试图归约到文法的开始符 o10、LR(0)分析法的名字中，“L”的含义是从左到右进行分析，“R”的含义是釆用最右推导的逆过程一一最左归约，“0”的含义是向貌似句柄的符号串后查看0个输入符号。二、选择题(单项或多项)1、文法G所描述的语言是 d 的集合。

文法G的字汇表V中所有符号组成的符号串文法G的字汇表V的闭包V*中的所有符号串由文法的开始符号推出的所有符号串d・由文法的开始符号推出的所有终极符号串2、巴科斯■诺尔范式（即BNF）是一种广泛采用的c 的工具。a•描述规则 b•描述语言 c・描述文法d•描述句子3、描述语言L={ambn|n>rn>l}的文法为 da.ZtAbba.ZtAbbA^aA|aB—bB|bc.Z—AbA->aAb|aZ—aAbA^Ab|aAb|e4、I^Il|IO|Ia|Ic|a|b|c下列符号串中是该文法的句子的有 bed.abOb.aOcOlc.aaad.belO5、若一个文法是递归的，则它所产生语言的句子个数 aa.必定是无穷的 b.是有限个的 c.根据具体情况而定6、 一个句型中的最左b 称为给句型的句柄。a.短语b.简单短语c.素短语d.终极符号7、 一个上下文无关文法G包拾四个组成部分依次为：一组g,一组一h,一个_以及一组 C。产生式非终极符d.结束符号号h.终极符号a.e.字符串开始符号b.字母数字串 c.f.文法 g.8、下列文法a 二义文法EtEiT|TTtT十F|iF|FFtE*|（a.是b.不是 c.无法判定9、 编译过程中，语法分析器的任务是 bed。分析单词是怎样构成的分析单词串是如何构成语句和说明的分析语句和说明是如何构成程序的分析程序的结构10、 语法分析的常用方法是 aba.自顶向下b.自底向上c.自左向右d.自右向左11、编译程序中的语法分析器接受以 c为单位的输入,并产生有关信息供以后各阶段使用。a.表达式b.产生式c.单词d.语句12、 高级语言编译程序常用的语法分析方法中，递归下降分析方法屈于a分析方法。a.自顶向下b.自底向上c.自左向右d.自右向左13、 LL(1)文法的条件是 o对形如UTxi|xi|...|xn的规则，要求FIRST(x»cFIRST(为)=0,(i#j)对形如U^xi|xi|...|xn的规则，若xi=>*8,要求FIRST(xj)nFOLLOW(U)=0(a)和(b)都不是14、已知文法G[E]：EYE'E，T+TE卞TtFT，T，t*fT“FT(E)|idFOLLOW(F)=广土#小,FIRST(D=}oa.{*,十}b.{*,8}c.{十，#,)}d・{*,+,#,)}e.{#,)}f.{*,+,#,),id}15、LR语法分析栈中存放的状态是识别b的DFA状态。a.前缀b.可归前缀 c.项目 d.句柄三、设有文法G[S]：StAA^B|IFATHENAELSEABtC|B+C|十cCtD|C*D|*DDtx|(A)|-D试问其中哪些是终极符号，哪些是非终极符号对于下列符号串：(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的句柄为・xIF ATHENA ELSEclDI+BIclDIXDIELSEIF A THENA—B——cFTHENIF ATHENA ELSEclDI+BIclDIXDIELSEIF A THENA—B——cFTHEN四、 设有文法G[S]：S^a|s|(T)TtT,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))n(T,(a,a))=>(S,(a,a))=>(a,(a,a))五、 试消除下列文法的直接左递归Gi[S]：S^Sa|Ab|b|cA->Bc|aB-Sb|b解答：ST(bcb|ab|b|c)S，S，->(a|bcb)S[wA->Bc|aB-Sb|bG2[S]：S-a囘(T)TtT・S|S解答：S-a囘(T)TtST'TfST"六、 试构造生成语言L={anbnc1|ii>l,i>0}的文法。解答：S-aAbBA->aAb|sB->cBs七、 有文法G[N]：NtSE|EStSD|DEt0|2|4|6|8|10Dt0|1|2卩|4|5|6卩|8|9证明此文法有二义性；此文法所描述的语言是什么？证明：对于文法的句子110,存在两棵不同的语法树或两种不同的最左(最右)推导，所以文法具有二义性。N=>SE=>DE=>lE=>110N=>SE=>SDEnDDEn1DE=>11E二>110此文法描述的语言是偶数集合八、知文法G[S]：S^eT|RTTtDR|eR^dR|sD^a|bdTOC\o"1-5"\h\zFIRST(S)= {a,b.d,e,w} ,FI