编译原理文法类型及语法分析测试卷附答案

编译原理文法类型及语法分析相关知识测试试卷一、选择题（每题2分）1．关于程序设计语言的翻译机制，下列选项说法错误的是（）[单选题]A、汇编程序一般对源程序进行两遍扫描来完成翻译。B、编译程序将高级语言编写的源程序作为输入，产生目标程序。C、解释程序是边翻译源程序，边执行源程序的结果。D、解释程序将高级语言编写的源程序作为输入，产生目标程序。(正确答案)2、设符号串X=abcd,则X的真尾为（）。[单选题]A:ε、a、ab、abc、abcdB:abc、ab、a、εC:ε、d、cd、bcd、abcdD:ε、d、cd、bcd(正确答案)3．文法G[S]:S→aBB→cBB→bC→c是（）[单选题]A短语结构文法B上下文有关文法C上下文无关文法D正规文法(正确答案)4．文法G[S]:S→aBB→cCB→bC→𝓔是（）[单选题]A短语结构文法B上下文有关文法C上下文无关文法(正确答案)D正规文法5．文法G[S]:S→aAbaA→aBaA→aaAB→bA→a是（）[单选题]A短语结构文法B上下文有关文法(正确答案)C上下文无关文法D正规文法6．文法G[S]:S→aCdaC→BaC→aaAB→b是（）[单选题]A短语结构文法(正确答案)B上下文有关文法C上下文无关文法D正规文法7.有文法G[S]:S→aABc|bBA|cAA|dBBA→a|b|c|dB→a|b|c|d下列字符串是该文法的句子。（）[单选题]A、accaB、adcc(正确答案)C、abbdD、bcaa8.有文法G[S]:[单选题]A∷=BCc|gDBB∷=ε|bCDEC∷=DaB|caD∷=ε|dDE∷=gAf|c非终结符A的FIRST集为（B）[选择题]A、FIRST(A)={b、ε、g}B、FIRST(A)={a、b、c、d、g}(正确答案)C、FIRST(A)={B、g}D、FIRST(A)={b、g}9、自顶向下语法分析中，构造LL(1)分析表，需要先构造FIRST集和FOLLOW集，下列关于构造文法中非终结符B的FOLLOW集说法正确的是（）[单选题]A、若文法中有形如A::=αBβ的规则，且β≠ε，则将FIRST(β)加进FOLLOW(B)中。B、若文法中有形如A::=αB或A::=αBβ的规则，则FOLLOW(A)中全部终结符均属于FOLLOW(B)C、若文法中有形如A::=αBβ的规则，且β≠ε，则将FIRST(β)中一切非ε符号加进FOLLOW(B)中。(正确答案)D、以上说法都不正确10、一个文法G，如果它的分析表M不含多重定义入口，则称该文法是LL(1)文法。所谓“多重定义入口”是指分析表中某M[A，a]有两个或两个以上产生式。下列关于LL（1）文法描述正确的是（）[单选题]A、LL（1）文法中可以存在回溯但不能存在左递归B、LL（1）文法中可以存在左递归但不能存在回溯C、LL(1)文法中即可以存在回溯又可以存在左递归D、LL(1)文法中既不能存在回溯又不能存在左递归(正确答案)11、一个LR（1）文法合并同心集后若不是LALR（1）文法（）[单选题]A则可能存在移进/归约冲突B则可能存在归约/归约冲突(正确答案)C则可能存在移进/归约冲突和归约/归约冲突D则可能存在移进/移进冲突12、编译原理是对（）[单选题]A、机器语言的执行C、高级语言的翻译D、高级语言程序的解释执行B、汇编语言的翻译C、高级语言的翻译(正确答案)D、高级语言程序的解释执行13、把汇编语言程序翻译成机器可执行的目标程序的工作是由（）完成的。[单选题]A.编译器B.汇编器(正确答案)C.解释器D.预处理器14、编译程序绝大多数时间花在（）上。[单选题]A．出错处理B．词法分析C．目标代码生成D．表格管理(正确答案)15、源程序是句子的集合，（）可以较好地反映句子的结构。[单选题]A.线性表B.树(正确答案)C.完全图D.堆栈16、词法分析器的主要任务不包括（）[单选题]A.识别出数值常量B.过滤源程序中的注释和空格C.识别单词D.发现括号不匹配(正确答案)17.如果文法G是无二义的，则它的任何句子α（）[单选题]A．最左推导和最右推导对应的语法树必定相同(正确答案)B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同18．文法G产生的（）的全体是该文法描述的语言。[单选题]A．句型B.终结符集C.非终结符集D.句子(正确答案)19．若文法G定义的语言是无限集，则文法必然是（）[单选题]A．递归的(正确答案)B.上下文无关的C.二义性的D.无二义性的20．编译过程中，语法分析器的任务是（）

①分析单词的构成

②分析单词串如何构成语句

③分析语句是如何构成程序

④分析程序的结构[单选题]A.②③(正确答案)B.④C.①②③④D.②③④21．词法分析器的输入是（）。[单选题]A．符号串(正确答案)B．源程序C．语法单位D．目标程序22．乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（）[单选题]A.短语结构文法B.正规文法(正确答案)C.上下文有关文法D.上下文无关文法23．一个句型中的（）称为该句型的句柄。[单选题]A.最左直接短语(正确答案)B.最右直接短语C.终结符D.非终结符24．在自底向上的语法分析方法中，分析的关键是（）[单选题]A.寻找句柄(正确答案)B.寻找句型C.消除递归D.选择候选式25．在LR分析法中，分析栈中存放的状态是识别规范句型（）的DFA状态。[单选题]A.句柄B.前缀C.活前缀(正确答案)D.LR(0)项目26．编译程序是一种（）[单选题]A.汇编程序B.翻译程序(正确答案)C.解释程序D.目标程序27．按逻辑上划分，编译程序第三步工作是（）[单选题]A.语义分析(正确答案)B.词法分析C.语法分析D.代码生成28．在语法分析处理中，FIRST集合、FOLLOW集合均是（）[单选题]A.非终结符集B.终结符集(正确答案)C.字母表D.状态集29．若一个文法是递归的，则它所产生的语言的句子（）。[单选题]A.是无穷多个(正确答案)B.是有穷多个C.是可枚举的D.个数是常量30．识别上下文无关语言的自动机是（）[单选题]A.下推自动机B.NFAC.DFA(正确答案)D.图灵机31．若B为非终结符，则A→.B为（）。[单选题]A.移进项目B.归约项目C.接受项目D.待约项目(正确答案)32．若B为非终结符，则A→.a为（）。[单选题]A.移进项目(正确答案)B.归约项目C.接受项目D.待约项目33．同心集合并可能会产生新的（）冲突。[单选题]A.二义B.移进/移进C.移进/归约D.归约/归约(正确答案)34．就文法的描述能力来说，有（）[单选题]A．SLR(1)LR(0)B．LR(1)LR(0)C．SLR(1)LR(1)(正确答案)D．无二义文法LR(1)35.有限自动机能识别（）[单选题]A.上下文无关语言B.上下文有关语言C.正规语言(正确答案)D.0型文法定义的语言36．已知文法G是无二义的，则对G的任意句型α（）[单选题]A.最左推导和最右推导对应的语法树必定相同(正确答案)B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同37．（）不是DFA的成分[单选题]A.有穷字母表B.多个初始状态的集合(正确答案)C.多个终态的集合D.转换函数38．与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是（）[单选题]A.a+b+c*dB.(a+b)*c+d(正确答案)C.(a+b)*(c+d)D.a+b*c+d38．后缀式abc-+-d+可用表达式（）来表示。[单选题]A．(-(a+b)-c)+dB．-(a+(b-c))+d(正确答案)C．-(a-(b+c))+dD．(a-(-b+c))+d39．表达式A+B*(C-D)/A+B/D的后缀式为（）。[单选题]A．ABCDABD+*-/+/B．ABCD-*A/+BD/+(正确答案)C．ABCD-*ABD/++D．以上都不对40．语言是（）[单选题]A．终结符与非终结符的符号串的集合B．非终结符符号串的集合C．终结符符号串的集合(正确答案)D．产生式的集合41．编译程序分两阶段工作，前阶段完成的工作是（）[单选题]A．词法分析、语法分析和代码优化B．代码生成、代码优化和词法分析C．词法分析、语法分析、语义分析和中间代码生成(正确答案)D．词法分析、语法分析和代码优化42．常用的中间代码形式不含（）[单选题]A．三元式B．四元式C．逆波兰式D．语法树(正确答案)43．代码优化的目的是（）[单选题]A．节省时间B．节省空间C．节省时间和空间(正确答案)D．把编译程序进行等价交换二、填空题（每空1分）1、程序设计语言的翻译机制中，汇编程序、编译程序和解释程序三种翻译程序实现的难易程度，由易到难依次是（汇编程序、解释程序、编译程序）[填空题]_________________________________2、与源语言相关的部分被称为编译前端，包括（词法分析、语法分析、语义分析）及中间代码生成3个阶段;[填空题]_________________________________3、设符号串X=abcd,则|X|=（4）,|εX|=（4）。[填空题]_________________________________4、设A=______，则A2=______[填空题]空1答案：b，d空2答案：bb，bd，db，dd5、设Σ=（______，a|ba*是Σ上正规式，则它的正规集是______。[填空题]空1答案：a，b空2答案：a，b，ba，baa，…6、已知文法G[S]:S→ABe|CAb|DBaA→a|εB→b|εC→cD→d，求FIRST______=______[填空题]空1答案：ABe空2答案：a，b，e7、自动机识别的语言是（3型语言或正规语言）[填空题]_________________________________8、用高级语言编写的程序经编译后产生的程序叫（目标程序。）[填空题]_________________________________9、只有两层的简单子树末端结点形成的符号串是相对于简单子树根的（简单短语）[填空题]_________________________________10、子树末端结点的符号串是相对于子树根的（短语）[填空题]_________________________________11、词法分析的主要任务包括（消除无用字符、识别单词、建立各种表格、）对识别出来的单词进行内部编码。[填空题]_________________________________12、在左线性文法中，开始符号为状态转换图的（终态）。[填空题]____________