1．SLR(1)分析法是一种规范归约分析法。（ ） 2．算符优先文法可以是二义性文法。（ ） 3．每个短语都是某规则的右部。（ ） 4．语法分析时必须先消除文法中的左递归。（ ）
5．如果两个正规式是等价的，则它们所表示的正规集相同。（ ） （ ）1. 编译程序的输入是高级语言程序，输出是机器语言程序。 （ ）2. 文法G[S]：S→iSeS|iS|i是二义文法。
（ ）3. 若一个语言的句子有无穷多个，则对应的文法必定是递归的。 （ ）4. 上下文无关文法可以产生语言L={anbnambm | n,m≥0}。
（ ）5. 设文法G[N]：N→ND|D，D→0|1|2|3|4|5|6|7，则句子3247的最右推
导为：N=>ND=>N4=>ND4=>N74=>ND74=>N274=>D274=>3274。
（ ）6. 每一个NFA都对应有唯一的一个最小化的DFA。 （ ）7. 文法G[S]：S→(S)S|ε不是LL(1)文法。
（ ）8. 若文法任一产生式的右部不含两个相继的非终结符（„QR„），则
称该文法为算符文法。
（ ）9. 优先函数是唯一的，有的优先关系矩阵不存在对应的优先函数。 （ ）10. 在LR(1)分析法中，搜索符仅对规约项目才有意义。 1、文法规则的左部就是非终结符号。
2、乔姆斯基定义1型文法对规则的限制比2型文法对规则的限制要多一些。3、LR（K）分析法能彻底解决冲突。
4、一个程序是正确的是指该程序的语法是完全正确的。
5、每一个编译程序都由完成词法分析、语法分析、语义分析、代码优化和代码生成工作的五部分程序组成。
6、多遍扫描的编译程序优于单遍扫描的编译程序。 7、每个句子都有规范推导；每个句型都有规范推导。
8、存在这样一些语言，它们能被确定有限自动机（DFA）识别，但不能用正规表达式表示。
9、每一个NFA都对应有唯一的一个最小化的DFA。
10、若给定文法G和某个固定的k，则G是否是LR（k）文法是可判定的。
二、选择题
1. 设某程序设计语言ON语句的语法规则为：
问：在下面的语句中，_______不符合语法？ ①ON A GOTO L1 ②ON B L1，L2，L3 ③ON Z GOTO L1 L2 ④ON C L2，L3 2. 文法G所描述的语言是 的集合。 ①文法G的字汇表V中所有符号组成的符号串 ②文法G的字汇表V的闭包V*中的所有符号串 ③由文法的识别符号推出的所有符号串 ④由文法的识别符号推出的所有终结符号串 3. 设有文法G[T]：T→T*F|F，F→F↑P|P，P→(T)|a ，该文法句型T*P↑(T*F)的句柄是_________ 。 ①(T*F) ②T*F ③P ④P↑(T*F) 4. 已知文法G[Z]：E→E+E|E*E|(E)|a|b|c，以下______是该文法的句子。①a*(b+c) ②(a-b)*c ③a/b ④a+4b 5. 下述正规表达式中 与（0*|1）* （c|d）等价。 ①0*（c|d）|1（c|d） ② 0*（c|d）*|1（c|d）* ③0*（c|d）|1*（c|d） ④（0|1）*c|（0|1）*d 6. 设有文法G[S]=（{b}，{S，B}，S，{S→b|bB，B→bS}），试问该文法所描述的语言是 。 ①L（G[S]）={bi|i≥0} ②L（G[S]）={b2i+1|i≥0} ③L（G[S]）={b2i|i≥0} ④L（G[S]）={b2i+1|i7. 设文法G定义为：G=({S,W,X,Y,Z},{x,y,z},P,S) 0 ≥1} P为： S→WZ 1 W→X|Y 0 S X→x|xX B Z Y→y|yY Z→z|zZ0 与该文法描述相同语言的正规表达式有 。 ①xx*|yy*|zz* ②(xx|yy)＊zz* ③xx*yy*zz* ④(xx*|yy*)zz* 8. 赋值语句X：=-（a+b）/（c-d）-（a+b*c）的逆波兰表示是______。 ①Xab+cd-/-bc*a+-:= ②Xab+/cd-bc*a+--:= ③Xab+-cd-/abc*+-:= ④Xab+cd-/abc*+--:= 9. 有下列文法G[S]：S→Pa|Pb|c，P→Pd|Se|f ，该文法是_____。 ①LL(1)文法 ②SLR(1)文法 ③都不是 ④是①和② 10. 编译程序使用 区别标识符的作用域。 ①说明标识符的过程或函数的静态层次 ②说明标识符的过程或函数的动态层次 ③说明标识符的过程或函数名 ④标识符的行号 1、一个语言的文法是 。（① 唯一的；② 不唯一的；③ 个数有限的；④ 说不清楚） 2、若一个文法是递归的，则它所产生的语言句子的个数 。（① 必定是无穷的；② 必定是有限个的；③ 可能是无穷的；④ 可能是有限个的） 3、给定文法A→bA|cc，下面的符号串中，为该文法句子的是 。（① cc；② bcbc；③ bcbcc；④ bccbcc） 4、乔姆斯基（Chomsky）把文法分成四种类型，即0型、1型、2型和3型。其中，2型文法是 。（① 上下文无关文法；② 上下文有关文法；③ 正则文法；④ 短语文法） 5、编译过程中，语法分析器的任务不包括 。（① 分析单词是如何构成的；② 分析单词串是如何构成语句和说明的；③ 分析程序的结构；④ 分析语句和说明是如何构成程序的） 6、高级语言常用的语法分析过程中，递归下降分析法属于 分析方法。（① 自左至右；② 自上而下；③ 自下而上；④ 自右至左） 7、编译方法中，自底向上的语法分析方法有 。（① 递归子程序法；② LL（K）分析方法；③ SLR方法；④ 预测分析方法） 8、算符优先分析法每次都是对 进行归约。（① 最左短语；② 简单短语；③ 素短语；④ 最左素短语） 9、-a-（b*c/（c-d）+b*a）的逆波兰表示是 （@代表单目运算-）。（① abc*cd-ba*+/-@；② a@bc*cd-ba*+/-；③ a@bc*cd-/ba*+-；④a-bc*/cd-ba*+-） 10、 LR语法分析栈中存放的状态是识别 的DFA状态。（① 前缀；② 句柄；③ 项目；④ 可归前缀） 1.属于自上而下分析方法的语法分析法有 分析法。 A．算法优先 B．递归下降 C．LR（0） D．SLR（1） 2.算符优先分析法从左到右扫描输入串，当堆栈顶部出现 时进行归约。 A．素短语 B．直接短语 C．最左素短语 D．句柄 3.已知文法G[E]：E→E+E|E*E|(E)|k|l|m，以下 是该文法的句子。 A．k*(2l+m) B．(k-l)*m C．k+4l D．k*(l+m) 4．词法分析器的输出结果是_____。 A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和自身值 D．单词自身值 5．文法G：S→xSx|y所识别的语言是_____。 A．xyx B． (xyx)* C．xnyxn(n≥0) D．x*yx* 6. 在编译过程中，符号表的主要作用是 。 A．帮助错误处理和辅助语法错误检查 B．辅助语法错误检查和辅助上下文语义正确性检查 C．帮助错误处理和辅助上下文语义正确性检查 D．辅助目标代码生成和辅助上下文语义正确性检查 7. 以下不属于对符号表进行的操作有 。 A．填入 B．查找 C．更新 D．排序 8. 在编译过程中，安排优化的目的是为了得到 的目标代码。 A．高效率 B．较短 C．结构清晰 D．使用存储空间最小 9. 不是DFA的成分。 A．有穷输入字母表 B．有限状态集合 C．终止状态集合 D．文法符号集合 10.一个句型最左边的 称为该句型的句柄。 A．直接短语 B．素短语 C．短语 D．规范短语 三、 填空题 1．编译程序的工作过程一般可划分为： 、 、 和 、 和目标代码生成。 2．短语是句型的某个 ，它对应的是 末端结点形成的符号串。 3．词法分析阶段的任务是对构成源程序的字符串 进行扫描和分解，根据语言的 ，识别出一个一个具有独立意义的 。 1.高级程序设计语言的翻译主要有___________________两种方式。 2.文法G[S]：S→(S)|ε所描述的语言是___________________。 3.文法G[S]：S→S*S|S+S|(S)|a的终结符号集合VT =___________。 4.文法G[Z]：Z→Z1|1在chomsky文法分类中属于_____型文法。 M → M*N|N 5.词法分析器的输出通常是二元组，（_______，单词自身值）。 N → (S)|id 6.符号串w的终结首符集合定义为：First(w)={a|________，a∈VT}。 (1) 求每个非终结符的FIRSTVT集;(3分) 7.___________分析法中的可规约串是最左素短语。 (2) 求每个非终结符的LASTVT集;(3分) 8.表达式（A∨B）∧（C∨﹃D∧E）的逆波兰表示（后缀式）为 。 (3) 构造此文法的优先关系表；（4分） 9.已知文法G[S]： S→xxW， {print “1” } S→y， {print “2” } W→Sz {print “3” } 若输入“xxxxyzz”，文法将输出__________________。 10.C语言允许递归调用，在编译时无法确定哪些函数在运行时激活，所以采用____________存储分配策略。 1、文法G产生的 全体是该文法描述的语言。 2、乔姆斯基定义的四种形式语言文法分别为：0型文法（又称 文法）、 文法（又称上下文有关文法）、2型文法（又称 文法）和3型文法（又称 文法）。 3、在编译过程中，扫描器（词法分析器）所完成的任务是从 中识别出一个个具有独立语法意义的 。 4、自顶向下语法分析方法的基本思想是：从 出发，不断建立 ，试图构造一个推导序列，最终由它推导出与输入符号相同的 。 5、LR（0）分析法中，“L”的含义是 ，“R”的含义是 ，“0”的含义是 。 6、编译过程中，常见的中间语言形式有 、三元式、 、树形表示和伪代码。 7、一个文法符号的继承属性是通过语法树中它的 结点的相应文法符号的属性来计算的，而综合属性是通过语法树中它的 结点的属性之值来计算的。 8、语法制导的编译程序能同时进行 分析和 分析。 9、假设G是一个文法，S是文法的开始符号，如果S*x，则称x是 。 10、C语言允许递归调用，在编译时无法确定哪些函数在运行时激活，所以采用____________存储分配策略。 四、应用题 4.已知文法G[S]：S → S+M|M 5.已知文法G(S)： S→BA A→BS| d B→aA| bS | c 的预测分析表如下 a b c d # S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c 给出句子 adccd 的分析过程。（6分） 1.设有以下文法：G[S]： S→aAbDe|d A→BSD|e B→SAc|cD|ε D→Se|ε 求：FOLLOW(S)和FOLLOW(D)。 2.给定文法G[E]： E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 求：FIRSTVT(E)和LASTVT(E)。 3.给定如下文法和语义规则，请构造（22+15）*12+13的带注释的语法树。 产生式 语义规则 L→En Print（E.val） E→E1+T E.val:=E1.val+T.vE→T al T→T1*F E.val:=T.val T→F F→（E） F→digit T.val:=T1.val*F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval 4. 请将如下图所示的转换系统（NFA）确定化（DFA），并最小化。 0 5. 设有文法G[S]:S→SaA|bB A→aB|c B→Bb|d (1) 消去文法左递归，改写文法G[S]为G’[S] (2) 计算文法G’[S]每个非终结符的FIRST集和FOLLOW集。 (3) 判断文法G’[S] 是否LL(1)文法 五、（10分）构造文法G[Z]的自动机，指明该自动机是不是确定的，并写 出相应语言。 G[Z]: Z→A0 A→A0|Z1|0 1 0 S B Z 0 1.设有文法G[S]：S→a|（T）|， T→T,S | S 请给出句子 （a,（a,a））的最左、最右推导。 2.已知语言L={anbbn|n≥1}，写出产生L的文法。 3.已知正则式0（0|1）*1，请构造相应的转换系统（NFA）。 4.已知某文法的LL（1）分析表如下，请分析baabbb是否是该文法的句子，要求写出分析过程。 a b c # S S→aBc S→bAB A A→aAb A→b B B→b B→ B→ 5.已知文法G[S]：S→SaF|F，F→FbP|P，P→c|d。求该文法的各非终结符的FIRSTVT集和LASTVT集。 6.写出语句if（A＞C）z=x+y else z=x-y+0.5的四元式表示。 4.设有一个LL(1)文法G[S]: S→(a)|aAb A→eA’|dSA’ A’→dA’|ε 试用C语言编写一个识别该文法句子的递归下降分析程序。 （函数scaner()的功能是读进源程序的下一个单词符号并将它放在全程变量sym中；函数error()是出错处理程序） 因篇幅问题不能全部显示，请点此查看更多更全内容