语法复习题.doc

一、单项选择题 1．如果文法G是无二义的，则它的任何句子α 。 　A a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 2.语法分析时所依据的是 。A a. 语法规则 b. 词法规则 c. 语义规则 d. 等价变换规则 3．文法G：S→xSx|y所识别的语言是 。C a. xyx b. (xyx)* c. xnyxn (n≥0) d. x*yx* 4.由文法的开始符号出发经过若干步（包括0步）推导产生的文法符号序列称为______B________。 A．语言 B．句型 C．句子 D．句柄 5．在自上而下的语法分析中，应从 C 开始分析。 A．句型 B．句子 C．文法开始符号 D．句柄 6..文法G：S → x xS | y 所识别的语言是（ D　）。 A．xxy* B．(xxy)* C．xx*yx D．(xx)*y 7.文法G：S → xS | y 所识别的语言是（ D　）。 A．xy* B．(xy)* C．xx*yx D．x*y 8.设有文法G[T]: T→T*F|F F→F↑P|P P→(T)|a 该文法句型T*P↑(T*F)的句柄是下列符号串（ C ） A.（T*F） B. T*F C. P D. P↑(T*F) 9.最左简单子树的叶结点，自左至右排列组成句型的________C____________。 A．短语 B．句型 C．句柄 D．间接短语 二、填空题 语法分析部分：（基本概念、递归下降子程序） 语法分析的方法通常分为两类： 自上而下分析方法 和 自下而上分析方法 。 2．文法中的终结符集和非终结符集的交集是 空集 。 3．一个句型的最左直接短语称为该句型的___句柄________________。 4．常用的自上而下语法分析方法有递归下降子程序方法和预测分析表方法（LL（1）方法）。 5．关于非终结符A的直接左递归产生式：A→Aα|β，其中α、β是任意的符号串且β不以A开头，则可以将A的产生式改写为右递归的形式为： A→βA’ , A’→αA’|ε000000000000000000000000 。 6．在消除回溯，提取公共左因子时，关于A的产生式A → δβ1 | δβ2 | … | δβi | βi+1 | …| βj，可以改写为： A → δA’ | βi+1 | …| βj ， A’ →β1 | … |βi 。 7．设G[S] 是一文法，如果符号串x是从识别符号推导出来的，即有x，则称x是文法G[S]的____句型__，若x仅由终结符号组成，即，则称x为文法G[S]的__句子 。 三、判断题（第1，2章，第三章概念，递归下降子程序） 1．设r和s分别为正规式，则有L(r|s) = L(r) | L(s).。( × ) 2．一个文法的所有句型的集合形成该文法所能接受的语言。( × ) 3．语法分析之所以采用上下文无关文法是因为它的描述能力最强。( × ) 4．自动机M和M’的状态个数不同，则二者必不等价。( × ) 5．最左推导也被称为规范推导。（× ） 6．用高级语言编写的源程序必须经过编译，产生目标程序后才能运行。（ × ） 7．对于任何一个正规式e，都存在一个DFA A，使得L（e）=L（A）。（ √ ） 8．最小化的DFA，它的状态数最小。（ √ ） 9．NFA的确定化算法具有消除ε边的功能。（ √ ） 10．每个非终结符产生的终结符号串都是该语言的子集。（ × ） 11．一个语言的文法是不唯一的。（ √ ） 12．语法错误校正的目的是为了把错误改正过来。（ × ） 13．源程序和目标程序是等价关系。（ √ ） 14．编译程序中错误处理的任务是对检查出的错误进行修改。（ × ） 15．使用有限自动机可以实现单词的识别。（ √ ） 16．一个非确定的有限自动机NFA可以通过多条路径识别同一个符号串。（ √ ）