编译原理复习题

-.z.一、填空题：〔10分，第1小题每2个1分，其余每空1分〕1、编译程序一般含有八局部，分别是、、、、、、、。2、编译程序与解释程序的根本区别是3、一个上下文无关文法G包括四个组成局部依次为：一组_____、一个_____、一组_____、一组______。4、设G是一个文法，S是文法的开场符号，如果S**，则称*是。二、选择题〔本大题共15小题，每题1分，共15分〕1、编译程序生成的目标程序是机器语言程序。A、一定B、不一定2、设有文法G[S]=〔{b},{S,B},S,{S→b|bB,B→bS}〕,该文法描述的语言是。A、bi|i≥0B、b2i|i≥0C、b2i+1|i≥0D、b2i+1|i≥13、设有文法G[S]： S→S*S|S+S|〔S〕|a该文法二义性文法A、是B、不是C、无法判断4、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。A、汇编语言程序B、机器语言程序C、高级语言程序D、汇编语言或机器语言程序5、给定文法A→bA|cc,下面符号串中，为该文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①B、①③④⑤C、①⑤D、①④⑤E、①②③④⑤6、语法分析的常用方法是。①自顶向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③7、语言L={anbbn|n≥1}，则下述文法中，可以产生语言LA、Z→aZb|aAb|bA→aAb|bB、A→aAbA→bC、Z→AbBA→aA|aB→bB|bD、Z→aAbA→aAb|b8、以下正规表达式中________与(a|b)*(c|d)等价。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)9、算符优先分析法每次都是对进展归约。A、最左短语B、直接短语C、句柄D、素短语E、最左素短语10、简单优先分析法每次都是对进展归约A、最左短语B、直接短语C、句柄D、素短语E、最左素短语11、以下文法G[S]]：S→AAA→Aa|a不是LR〔1〕文法，理由是A.、FIRST(S)∩FIRST〔A〕≠B、FIRST〔A〕∩FOLLOW〔A〕≠C、FIRST〔Aa〕∩FIRST〔a〕≠D、都不是12、设有文法G[E]：E→E*E|E+E|〔E〕|a该文法LR〔1〕文法A、是B、不是C、无法判断13、对于文法G[A]：A→aABe|BaB→dB|有人说，因为FIRST〔aABe〕∩FOLLOW〔A〕≠并且FIRST〔Ba〕∩FOLLOW〔A〕≠，所以文法G[A]不是LL〔1〕文法。这种说法A、正确B、不正确14、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：A、①④B、①⑤C、①⑥D、②④E、③⑤F、③⑦G、②⑦15、表达式A*〔B-C*〔C/D〕〕的逆波兰式为A、ABC-CD/**B、ABCCD/*-*C、ABC-*CD/*D、都不正确三、简答题〔共35分〕(10分)现有文法G[E]:E→E+T|E-T|TT→T*F|T/F|FF→(E)|i画出句型E+F*〔E+i〕的语法树,找出它的短语，直接短语，句柄和素短语(5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法承受的句子：S→aAS→BA→abSA→bBB→bB→cCC→DD→dD→bB(10分)将下面具有的NFA确定化SSABZaba(5分)求出以下文法所产生语言对应的正规式。S→aAA→bA|aB|bB→aA。(5分)构造识别下面正规式的NFA〔a|b〕*ba。选择题〔本大题共20小题，每题1分，共20分〕1、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。a、汇编语言程序b、机器语言程序c、高级语言程序d汇编语言或机器语言程序2、描述一个语言的文法是___________。a、唯一的b、不唯一的c、个数有限的3、生成非0开头的正偶数集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A4、设有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符号串中是该文法的句子的有___________________。①ab0②a0c01③aaa④bc10可选项有a、①b、②③④c、③④d、①②③④5、现有前缀表示的表达式文法G1：E::=-EEE::=-EE::=a|b|c则文法的句子—a-bc的所有可能语法树有______棵。a、1b、2c、3d、46、一个上下文无关文法G包括四个组成局部依次为：一组_____、一个_____、一组_____、一组______。a、字符串b、字母数字串c、产生式d、完毕符号e、开场符号f、文法g、非终结符号h、终结符号7、语法分析的常用方法是_________：①自顶向下②自底向上③自左向右④自右向左可选项有：a、①②③④b、①②c、③④d、①②③8、以下文法__________二义文法E::=EiT|TT::=T+F|iF|FF::=E*|(可选项有：a、是b、不是c、无法判断。9、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦10、LR〔K〕文法是_________。a、从左到右分析，共经过K步的一种编译方法。b、从左到右分析，每次向前预测K步的一种编译方法。c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。d、从左到右分析，每次走K步的一种编译方法。11、在编译中产生语法树是为了____________。a、语法分析b、语义分析c、词法分析d、产生目标代码12、文法的二义性和语言的二义性是两个____________概念。a、不同b、一样c、无法判断13、下述正规表达式中________与(a*+b)*(c+d)等价。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可选项有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存在b、不存在c、无法判定是否存在15、LL〔K〕文法________二义性的。a、都是b、都不是c、不一定都是16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可选项有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波兰表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在编译程序中安排中间代码生成的目的是_______________。①便于进展存储空间的组织②利于目标代码优化③利于编译程序的移植④利于目标代码的移植⑤利于提高目标代码的质量可选项有：a、②④b、①②③c、③④①d、②③④⑤20、代码优化的主要目标是_____________。①如何提高目标程序的运行速度②如何减少目标程序运行所需的空间。专业年级〔本、专科〕**______________姓名专业年级〔本、专科〕**______________姓名________________密封线④如何使生成的目标代码尽可能简短可选项有：a、②④b、①②③c、③④①d、②③④简答题：〔每题5分，共35分〕证明下面文法是二义性的。S::=ibtSeS|ibtS|a现有文法S::=SaA|AA::=AbB|BB::=cSd|e请证实是文法的一个句型，并写出该句型的所有短语、素短语以及句柄。求出以下文法所产生语言对应的正规式。S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列消除以下文法的左递归。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e给出与以下图的NFA等价的正规文法。S0S2S0S2S1S3bεε7、对根本块P画出DAG图B:=3D:=A+CE::=A*CF:=E+DG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L假定只有L在根本块出口之后活泼，写出优化后的四元式序列。1、文法G1：P→aPQR|abR，RQ→QR，BQ→bb，bR→bc，cR→cc，它是chomsky哪一型文法？A、0型B、1型C、2型D、3型2、编译程序必须完成的工作有①词法分析②语法分析③语义分析④代码生成⑤中间代码生成⑥代码优化①②③④B、①②③④⑤C、①②③④⑥D、①②③④⑤⑥3、LR〔K〕文法________二义性的。A、都是B、都不是C、不一定都是4、语法分析的常用方法是________。①自顶向下②自底向上③自左向右④自右向左A、①②③④B、①②C、③④D、①②③5、用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行，这种说法A、不正确B、正确6、生成非0开头的正偶数集的文法是______________。A、Z::=ABCB、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9C、Z::=ABCD、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|97、文法G所描述的语言是的集合A、文法G的字汇表V中所有符号组成的符号串B、文法G的字汇表V的闭包V*中的所有符号串C、由文法的开场符号推出的所有符号串D、由文法的开场符号推出的所有终结符号串。8、给定文法G[I]:I→I1|I0|Ia|Ic|a|b|c,下面符号串中，为该文法句子的是。①ab0②a0c01③aaa④bc10A、①B、②③④C、③④D、①②③④9、____这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：A、存在B、不存在C、无法判定是否存在10、LR〔K〕文法是_________。A、从左到右分析，共经过K步的一种编译方法。B、从左到右分析，每次向前预测K步的一种编译方法。C、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。D、从左到右分析，每次走K步的一种编译方法。11、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波兰表示是___________。A、a-bc*cd-/b-a*+-B、a-bc*/cd-b-a*+-C、abc*cd-b-a*+/--D、a-bc*cd-b-a*+/-12、设有文法G[S]=〔{b},{S,B},S,{S→b|bB,B→bS}〕,该文法描述的语言是。A、{b2i+1|i≥1}B、{b2i+1|i≥0}C、{bi|i≥0}D、{b2i|i≥013、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：A、①④B、①⑤C、①⑥D、②④E、③⑤F、③⑦G、②⑦14、算符优先分析属于分析方法。A、自顶向下B、自底向上C、自左向右D、自右向左15、简单优先分析法每次都是对进展归约A、最左短语B、直接短语C、句柄D、素短语E、最左素短语16、文法G[S]：S→aSS→WS→UU→aV→bVV→acW→aW其中的全部无用符号是A、W，V，UB、V，bC、W，V，a,b,cD、W，V，b，c17、程序根本块是指A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口18、设有文法G[Z]：Z→Z*Z|Z+Z|〔Z〕|a该文法二义性文法A、是B、不是C、无法判断19、以下正规表达式中________与(a|b)*(c|d)等价。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)20、语法分析的任务是①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的构造A、②③B、②③④C、③④D、①②③④二、〔简答题，共计20分〕1、(10分)文法G〔T)：T→T*F|FF→F↑P|PP→(T)|i(1)写出句型T*P↑〔T*F〕推导过程，画出语法树；(2)写出句型T*P↑〔T*F〕的短语、直接短语、句柄和素短语。2、(5分)构造识别下面正规式的NFAb〔aa|bb〕*ab3、〔5分〕消除文法G[S]的左递归G[S]：S→ABA→bB|AaB→Sb|a三、〔综合题，共计30分〕1、(10分)将下面具有的NFA确定化和最小化SSABZaba专业年级〔本、专科〕**______________姓名________________密封线2、(10分)〔1〕对下面的文法G[Z]Z→aBA→aBB→bBB→aAB→b构造状态转换图,并说明符号串aaaabbb是否是该文法承受的句子〔2〕写出G[Z]文法相应的正规式：3、〔10分〕设有以下文法G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|D→Se|〔1〕求出文法中每个非终结符的FOLLOW集〔2〕该文法是LL〔1〕文法吗？构造LL〔1〕分析表一、选择题〔本大题共20小题，每题1分，共20分〕1、描述一个语言的文法是___________。a、唯一的b、不是唯一的c、个数有限的2、简单优先分析法每次都是对___________进展归约。a、最左短语b、直接短语c、句柄d、素短语e、最左素短语3、设有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符号串中是该文法的句子的有___________________。①ab0②a0c01③aaa④bc10可选项有a、①b、②③④c、③④d、①②③④4、LR〔K〕文法________二义性的。a、都是b、都不是c、不一定都是5、一个上下文无关文法G包括四个组成局部依次为：一组_____、一个_____、一组_____、一组______。a、字符串b、字母数字串c、产生式d、完毕符号e、开场符号f、文法g、非终结符号h、终结符号6、文法G所描述的语言是__________的集合a、文法G的字汇表V中所有符号组成的符号串b、文法G的字汇表V的闭包V*中的所有符号串c、由文法的开场符号推出的所有符号串d、由文法的开场符号推出的所有终结符号串。7、设有文法G[Z]：Z→Z*Z|Z+Z|〔Z〕|a该文法_______二义性文法a、是b、不是c、无法判断8、语法分析的常用方法是_________：①自顶向下②自底向上③自左向右④自右向左可选项有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、从左到右分析，共经过K步的一种编译方法。b、从左到右分析，每次向前预测K步的一种编译方法。c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。d、从左到右分析，每次走K步的一种编译方法。10、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、文法的二义性和语言的二义性是两个____________概念。a、不同b、一样c、无法判断12、在编译中产生语法树是为了____________。a、语法分析b、语义分析c、词法分析d、产生目标代码13、以下正规表达式中________与(a|b)*(c|d)等价。a、〔a*|b*〕(c|d)b、〔a*|b*〕*(c|d)c、(ab)*(d|c)d、〔a*b*〕(cd)_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存在b、不存在c、无法判定是否存在文法G[S]：S→aSS→WS→UU→aV→bVV→acW→aW其中的全部无用符号是〔〕a、〔W，V，U〕b、〔V，b〕c、〔W，V，a,b,c〕d、〔W，V，b，c〕16、ab3的另一种表示方法是〔〕a、abbbb、abababc、abbaabd、aaabbb17、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波兰表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在编译程序中安排中间代码生成的目的是_______________。①便于进展存储空间的组织②利于目标代码优化③利于编译程序的移植④利于目标代码的移植⑤利于提高目标代码的质量可选项有：a、②④⑤b、①②③c、③④①d、②③④⑤20、设有文法G[S]=〔{b},{S,B},S,{S→b|bB,B→bS}〕,该文法描述的语言是〔〕。a、{b2i+1|i≥1}b、{b2i+1|i≥0}c、{bi|i≥0}d、{b2i|i≥0}二、简答题：〔每题5分，共30分〕1、证明下面文法是二义性的。P→PaP|PbP|cP|Pe|f2、设一文法E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。3、求出以下文法所产生语言对应的正规式。S→bS|aAA→aA|bBB→aA|bC|bC→bS|aA4、将表达式〔〔B*D+A〕/E+D〕*F+G分别表示为三元式、四元式、逆波兰式序列5、消除文法G[S]的左递归(G[S])G[S]：S→ABA→bB|AaB→Sb|a6、对下面的文法G[Z]Z→aBA→aBB→bBB→aAB→b构造状态转换图,并说明符号串aaaabbb是否是该文法承受的句子一、选择题〔本大题共20小题，每题1分，共20分〕1、要在*一台机器上为*种语言构造一个编译程序，必须找掌握下述三方面的内容：______。①高级语言②源语言③目标语言④程序设计方法⑤编译方法⑥测试方法⑦机器语言可选项有①②③④⑤⑥⑦a、①③⑤b、①②⑥c、②③⑤d、②④⑦2、"用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行。〞这种说法___________。a、不正确b、正确3、假设一个文法是递归的，则它所产生的句子个数___________。a、必定是无穷的b、是有限个的c、根据具体情况而定4、以下文法__________二义文法E::=EiT|TT::=T+F|iF|FF::=ET|(可选项有：a、是b、不是c、无法判断。5、编译程序的语法分析器承受以________为单位的输入，并产生有关信息供以后各阶段使用。可选项有：a、表达式b、产生式c、单词d、语句6、文法G[Z]：Z→BeA→Ae|eB→AfD→f中，________是多余产生式a、Z→Beb、A→Ae|ec、B→Afd、D→f7、算符优先文法属于________。a、自顶向下语法分析法b、LR分析法c、SLR分析法d、自底向上语法分析法8、设有文法G[S]=〔{a}，{S,B}，S，{S→a|aB,B→aS}〕,该文法描述的语言是_____a、{ai|i≥0}b、{a2i|i≥0}c、{a2i+1|i≥0}d、{a2i+1|i≥1}9、描述语言L={ambn|n≥m≥1}的文法是__________a、Z→ABbb、Z→ABbc、Z→Abd、Z→aAbA→aA|aA→Aa|aA→aAb|aA→Ab|aAb|εB→bB|bB→aBb|b10、一个句型中的最左_______称为该句型的句柄。a、短语b、直接短语c、素短语d、终结符号11、通常高级语言的词法规则可用正规式描述，词法分析器可用_________来实现a、语法树b、有限自动机c、栈d、堆12、文法G[S]：S→AAA→Aa|a不是LR〔1〕文法，理由是_________。a、FIRST(S)∩FIRST(A)≠b、FIRST(A)∩FOLLOW(A)≠c、FIRST(Aa)∩FIRST(a)≠d、都不是13、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦14、给定文法G[S]：S→ACcA→aA|SbC→DefD→hACDd|eC|E→bDe|ε该文法是____________。〔1〕右线性文法〔2〕前后文无关文法〔3〕左递归文法〔4〕LL〔1〕文法可选项有：a、②b、③c、②③d、②③④15、算符文法是指____________的文法。①没有形如U→…VW…的规则〔U、V、W为非终结符〕②终结符号集中任意两个符号对之间至多有一种优先关系成立③没有一样的规则右部④没有形如U→ε的规则可选项有a、①b、①②c、①②③d、①②③④16、以下正规表达式中________与(a|b)*(c|d)等价。a、〔a*|b*〕(c|d)b、〔a*|b*〕*(c|d)c、(ab)*(d|c)d、〔a*b*〕(cd)17、假设一个句型中出现了*一产生式的右部，则此右部_______是该句型的句柄a、一定b、不一定18、前后文无关文法和正规文法所产生的语言类相比_______a、前后文无关文法产生的语言类大b、正规文法产生的语言类大c、两者产生的语言类一样大d、无法比拟19、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤20、LL〔1〕文法的条件是_______________。a、对形如U→*1|*2|…|*n的规则，要求FIRST〔*i〕)∩FIRST(*j)=(i≠j)b、对形如U→*1|*2|…|*n的规则假设*i*ε则要求FIRST(*j)∩FOLLOW(U)=c、a和bd、都不是二、简答题：〔每题5分，共30分〕1、对于下面的文法G[S]S→Sa|Ab|b|cA→Bc|aB→Sb|b构造状态转换图,并说明符号串bcbabcba是否是该文法承受的句子2、设一文法G[T]：T→T*F|FF→F↑P|PP→(T)|i证明T*P↑(T*F)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。3、求出以下文法所产生语言对应的正规式。Z→aZ|bZ|aAA→aBB→aA|b4、将表达式〔〔A+B*D〕/E+F〕*F+G^E分别表示为三元式、四元式、逆波兰式序列。5、〔5分〕消除文法G[S]的左递归G[S]：S→SA|AA→SB|B|(S)|()B→[S]|[]专业专业年级〔本、专科〕**______________姓名________________密封线E→E+T|T|TT→T*F|FF→P↑F|PP→i(+、、*、↑、i是终结符号)构造文法的算符优先矩阵表，判断此文法是否是算符优先文法。填空题〔每空1分，共20分〕1、假设G是一个文法，S是文法的开场符号，如果S**，则称*是。2、乔姆斯基定义的四种形式语言分别为：文法、文法、文法、文法。3、设有文法G[I]：I→I1|I0|Ia|Ic|a|b|c,以下符号串中是该文法的句子的有〔1〕ab0(2)a0c01(3)aaa(4)bc104、一个上下文无关文法G包含四个组成局部依次为：一组，一组，一个，以及一组。5、确定的有穷自动机是一个，通常表示为。6、编译程序一般含有八局部，分别是、、、、、、、。简答题〔每题5分，共30分〕1、文法G[Z]：Z→U0|V1U→Z1|1V→Z0|0写出全部由此文法描述的只含有四个符号的句子。2、文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？3、设一文法G[S]S→〔AS〕S→〔b〕A→〔SaA〕A→〔a〕对于句子〔〔〔b〕a〔a〕〕〔b〕〕，写出该句子的最左推导，画出语法树，写出其全部短语，直接短语和句柄。构造下述文法G[S]的自动机：S→A0A→A0|S1|05、将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列6、消除以下文法的左递归。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e一、选择题〔本大题共20小题，每题1分，共20分〕1、描述一个语言的文法是___________。a、唯一的b、不唯一的c、个数有限的2、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。a、汇编语言程序b、机器语言程序c、高级语言程序d汇编语言或机器语言程序3、设有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符号串中是该文法的句子的有___________________。①ab0②a0c01③aaa④bc10可选项有a、①b、②③④c、③④d、①②③④4、生成非0开头的正偶数集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|95、一个上下文无关文法G包括四个组成局部依次为：一组_____、一个_____、一组_____、一组______。a、字符串b、字母数字串c、产生式d、完毕符号e、开场符号f、文法g、非终结符号h、终结符号6、现有前缀表示的表达式文法G1：E::=-EEE::=-EE::=a|b|c则文法的句子—a-bc的所有可能语法树有______棵。a、1b、2c、3d、47、以下文法__________二义文法E::=EiT|TT::=T+F|iF|FF::=E*|(可选项有：a、是b、不是c、无法判断。8、语法分析的常用方法是_________：①自顶向下②自底向上③自左向右④自右向左可选项有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、从左到右分析，共经过K步的一种编译方法。b、从左到右分析，每次向前预测K步的一种编译方法。c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。d、从左到右分析，每次走K步的一种编译方法。10、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、文法的二义性和语言的二义性是两个____________概念。a、不同b、一样c、无法判断12、在编译中产生语法树是为了____________。a、语法分析b、语义分析c、词法分析d、产生目标代码13、下述正规表达式中________与(a*+b)*(c+d)等价。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可选项有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存在b、不存在c、无法判定是否存在15、LL〔K〕文法________二义性的。a、都是b、都不是c、不一定都是16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可选项有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波兰表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在编译程序中安排中间代码生成的目的是_______________。①便于进展存储空间的组织②利于目标代码优化③利于编译程序的移植④利于目标代码的移植⑤利于提高目标代码的质量可选项有：a、②④b、①②③c、③④①d、②③④⑤20、代码优化的主要目标是_____________。①如何提高目标程序的运行速度②如何减少目标程序运行所需的空间。专业年级〔本、专科〕**______________姓名专业年级〔本、专科〕**______________姓名________________密封线④如何使生成的目标代码尽可能简短可选项有：a、②④b、①②③c、③④①d、②③④二、简答题：〔每题5分，共30分〕1、写一个文法使其语言为L(G)={anbmambn|m,n≥1}。2、对于文法G(E):ET|E+TTF|T*FF(E)|i〔1〕写出句型(T*F+i)的最右推导并画出语法树。〔2〕写出上述句型的短语，直接短语、句柄和素短语。3、求出以下文法所产生语言对应的正规式。S::=bS|aAA::=aA|bBB::=aA|bC|bC::=bS|aA4、将表达式((a*d+c)/d+e)*f+g分别表示三元式、四元式、逆波兰式序列5、消除以下文法的左递归。S::=SaP|Sf|PP::=QbP|QQ::=cSd|e6、给出与以下图的NFA等价的正规文法。S0S2S0S2S1S3bcεε选择题〔本大题共20小题，每题1分，共20分〕1、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：A、①④B、①⑤C、①⑥D、②④E、③⑤F、③⑦G、②⑦2、表达式ab+cd+*的逆波兰式表达式所表示的中缀形式的表达式是A、a+b+c*dB、(a+b)*(c+d)C、(a+b)*c+dD、a+b*c+d3、Chomsky的3型语言是这样一种语言，其产生式限制为〔、、为字符串〕。A、A→B、A→aA→aBC、→D、A→4、设有文法G[S]=〔{b},{S,B},S,{S→b|bB,B→bS}〕,该文法描述的语言是。A、bi|i≥0B、b2i|i≥0C、b2i+1|i≥0D、b2i+1|i≥15、设有文法G[S]： S→S*S|S+S|〔S〕|a该文法二义性文法A、是B、不是C、无法判断6、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。A、汇编语言程序B、机器语言程序C、高级语言程序D、汇编语言或机器语言程序7、给定文法A→bA|cc,下面符号串中，为该文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA、①B、①③④⑤C、①⑤D、①④⑤E、①②③④⑤8、递归下降分析语法分析的属于分析方法。A、自顶向下B、自底向上C、自左向右D、自右向左9、语言L={anbbn|n≥1}，则下述文法中，可以产生语言LA、Z→aZb|aAb|bA→aAb|bB、A→aAbA→bC、Z→AbBA→aA|aB→bB|bD、Z→aAbA→aAb|b10、假设一个句型中出现了*一产生式的右部，则此右部________是句柄。A、一定B、不一定11、考虑文法G[A]：A→A∨B|BC→∧DB→BC|D→〔A〕|i,该文法LL(1)文法。A、是B、不是12、简单优先分析法每次都是对进展归约A、最左短语B、直接短语C、句柄D、素短语E、最左素短语13、以下文法G[S]：S→AAA→Aa|a不是LR〔1〕文法，理由是A.、FIRST(S)∩FIRST〔A〕≠B、FIRST〔A〕∩FOLLOW〔A〕≠C、FIRST〔Aa〕∩FIRST〔a〕≠D、都不是14、设有文法G[E]：E→E*E|E+E|〔E〕|a该文法LR〔1〕文法A、是B、不是C、无法判断15、对于文法G[A]A→ABe|BaB→dB|有人说，因为FIRST〔aABe〕∩FOLLOW〔A〕≠并且FIRST〔Ba〕∩FOLLOW〔A〕≠，所以文法G[A]不是LL〔1〕文法。这种说法A、正确B、不正确16、以下正规表达式中________与(a|b)*(c|d)等价。A、〔a*|b*〕(c|d)B、〔a*|b*〕*(c|d)C、(ab)*(d|c)D、〔a*b*〕(cd)17、假设一个句型中出现了*一产生式的右部，则此右部_______是该句型的句柄A、一定B、不一定18、前后文无关文法和正规文法所产生的语言类相比_______A、前后文无关文法产生的语言类大B、正规文法产生的语言类大C、两者产生的语言类一样大D、无法比拟19、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：A、①③④B、②③④C、③④①⑤D、②③④⑤20、LL〔1〕文法的条件是_______________。A、对形如U→*1|*2|…|*n的规则，要求FIRST〔*i〕)∩FIRST(*j)=(i≠j)B、对形如U→*1|*2|…|*n的规则假设*i*ε则要求FIRST(*j)∩FOLLOW(U)=C、a和bD、都不是二、综合题：〔共35分〕1、(10分)对于文法G(S):(1)写出句型b(Ma)b的最右推导并画出语法树。(2)写出上述句型的短语，直接短语和句柄。(5分)对下面的文法G[S]构造状态转换图,并说明符号串aabca是否是该文法承受的句子：S→AaS→BA→CcA→BbB→BbB→aC→DC→BabD→d(10分)将下面具有的NFA确定化eeS0S2S3mnS1专业年级〔本、专科〕**______________姓名________________密封线4、(5分)求出以下文法所产生语言对应的正规式。S→aSS→bAS→bA→aS5、(5分)构造识别下面正规式的NFAab〔a|b〕*一、选择题〔本大题共20小题，每题1分，共20分〕1、文法的二义性和语言的二义性是两个____________概念。a、不同b、一样c、无法判断2、在编译中产生语法树是为了____________。a、语法分析b、语义分析c、词法分析d、产生目标代码3、下述正规表达式中________与(a*+b)*(c+d)等价。a*〔c+d〕+b〔c+d〕a*〔c+d〕*+b〔c+d〕*a*〔c+d〕+b*〔c+d〕〔a+b〕*c+〔a+b〕*d〔a*+b〕*c+〔a*+b〕*d可选项有:a、①b、②c、③d、④e、⑤f、④⑤g、③④⑤4、______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：a、存在b、不存在c、无法判定是否存在5、LL〔K〕文法________二义性的。a、都是b、都不是c、不一定都是6、现有前缀表示的表达式文法G1：E::=-EEE::=-EE::=a|b|c则文法的句子—a-bc的所有可能语法树有______棵。a、1b、2c、3d、47、以下文法__________二义文法E::=EiT|TT::=T+F|iF|FF::=E*|(可选项有：a、是b、不是c、无法判断。8、语法分析的常用方法是_________：①自顶向下②自底向上③自左向右④自右向左可选项有：a、①②③④b、①②c、③④d、①②③9、LR〔K〕文法是_________。a、从左到右分析，共经过K步的一种编译方法。b、从左到右分析，每次向前预测K步的一种编译方法。c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。d、从左到右分析，每次走K步的一种编译方法。10、素短语是指_______的短语。①至少包含一个符号②至少包含一个非终结符号③至少包含一个终结符号④除自身外不再包含其它终结符号⑤除自身外不再包含其它非终结符号⑥除自身外不再包含其它短语⑦除自身外不再包含其它素短语可选项有：a、①④b、①⑤c、①⑥d、②④e、③⑤f、③⑦g、②⑦11、描述一个语言的文法是___________。a、唯一的b、不唯一的c、个数有限的12、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。a、汇编语言程序b、机器语言程序c、高级语言程序d汇编语言或机器语言程序13、设有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符号串中是该文法的句子的有___________________。①ab0②a0c01③aaa④bc10可选项有a、①b、②③④c、③④d、①②③④14、生成非0开头的正偶数集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|εB::=BA|B0|0A::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|9b、Z::=ABCd、Z::=ABC|2|4|6|8C::=0|2|4|6|8C::=0|2|4|6|8B::=BA|B0|0B::=BA|B0|εA::=1|2|3|4|5|6|7|8|9A::=1|2|3|4|5|6|7|8|915、一个上下文无关文法G包括四个组成局部依次为：一组_____、一个_____、一组_____、一组______。a、字符串b、字母数字串c、产生式d、完毕符号e、开场符号f、文法g、非终结符号h、终结符号16、下面的文法是__________。S::=aAa|aBb|bAb|bBaA::=*B::=*可选项有：a、LR〔1〕文法b、LALR〔1〕文法c、都不是d、a和b17、编译过程中，比拟常见的中间语言有___________。①波兰表示②逆波兰表示③三元式④四元式⑤树形表示可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤18、-a-〔b*c/〔c-d〕+〔-b〕*a〕的逆波兰表示是___________。a、abc*cd-b-a*+/--b、a-bc*cd-b-a*+/-c、a-bc*cd-/b-a*+-d、a-bc*/cd-b-a*+-19、在编译程序中安排中间代码生成的目的是_______________。①便于进展存储空间的组织②利于目标代码优化③利于编译程序的移植④利于目标代码的移植⑤利于提高目标代码的质量可选项有：a、②④b、①②③c、③④①d、②③④⑤20、代码优化的主要目标是_____________。①如何提高目标程序的运行速度②如何减少目标程序运行所需的空间。专业年级〔本、专科〕**______________姓名专业年级〔本、专科〕**______________姓名________________密封线④如何使生成的目标代码尽可能简短可选项有：a、②④b、①②③c、③④①d、②③④二、简答题：〔共30分〕(5分)证明下面文法是二义性的。P::=PaP|PbP|cP|Pe|f(10分)对于文法G(E):ET|E+TTF|T*FF(E)|i(1)写出句型T*F+i1*i2的最右推导并画出语法树。(2)写出上述句型的短语，直接短语、句柄、素短语和最左素短语。3、(5分)求出以下文法所产生语言对应的正规式。S::=aAA::=bA|aB|bB::=aA4、(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。5、(5分)写一个文法使其语言为L(G)={anbncm|m,n≥1，n为奇数，m为偶数}。一、选择题〔本大题共20小题，每题1分，共20分〕1、描述一个语言的文法是___________。a、唯一的b、不唯一的c、个数有限的2、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。a、汇编语言程序b、机器语言程序c、高级语言程序d汇编语言或机器语言程序3、设有文法G[I]：I→I0|I1|Ia|Ic|a|b|c以下符号串中是该文法的句子的有___________________。①ab0②a0c01③aaa④bc10可选项有a、①b、②③④c、③④d、①②③④4、生成非0开头的正偶数集的文法是______________。a、Z::=ABCc、Z::=ABC|2|4|6|8C::=0|2|4|6|8