填空选择题

1．表达式A*(B-C*(C/D))的逆波兰式是( B )

A．ABC-CD/* B．ABCCD/*-* C．ABC-*CD/* D．a,b,c均不正确2．chomsky 的2型语言可由下面哪个识别( C )

A．图灵机 B．有穷自动机 C．下推自动机 D．线性界限自动机

3型：有穷自动机 2型：下推自动机 1型：线性界限自动机 0型：图灵机

3．最左简单子树的末端结点构成的符号串称为( A )

A．句柄 B．最左素短语 C．素短语 D．简单短语

4．在使用高级语言编程时，首先可通过编译程序发现源程序的什么错误( A )

A．语法 B. 语义 C. 语用 D. 运行

5．用高级语言书写的源程序都必须通过编译，产生目标代码后才能投入运行。这种说法正确的是( C )

A. 正确

B. 不正确

C. 不一定

D. 都不对

6．若文法 G 定义的语言是无限集，则文法必然是( A )

A．递归的 B．无二义性的 C．二义性的 D．上下文无关的

7．一个文法所描述的语言是( C/D )

A．唯一的 B．不唯一的 C．可能唯一 D．可能不唯一

8 Chomsky 的3型语言可由下面哪个识别( B )

A．图灵机 B．有穷自动机 C．下推自动机 D．线性界限自动机9．Chomsky 定义的四种形式语言文法中，1型文法又称为(哪种文法( C )

A．短语结构文法 B．正规文法 C．上下文有关文法 D．上下文无关文法10．算符优先分析是一种自底向上的分析方法，它是以什么作为每一步归约的对象( D ) A．最右直接短语 B．最左直接短语 C．句柄 D．最左素短语

11．下面哪种不是自底向上的语法分析文法( B )

A．LR(1) B．LL(R) C．算符优先法 D．SLR(1)

12．赋值语句x=a+b*((a+c)*d+e)的逆波兰式是( )

A．xab+ac+d*e+= B．xabac+de+**+= C．xabac+d*e+*+= D．abc均不对

4．下面( B )是词法分析的理论基础。

A．正规式 B．有穷自动机 C．下推自动机 D．正规文法

下推自动机是语法分析的基础

13．由“非终结符符号串”这种产生式形式构成的文法是( C )

A．正则文法 B．1 型方法 C．2型方法 D．3型方法

14．若一个文法是递归的，则它产生的句子个数是( A )

A．无穷个 B．可能有限个 C．有限个 D．以上均不对

15．给定文法, A Aa|b, 下面的符号串可由其推导出的是( C )

A．aab B．aaab C．baa D．

16．LR(K)分析是一种自底向上的分析法，它是以下面哪个作为每一步归约的对象( C ) A．最右直接短语 B．最左直接短语 C．句柄 D．最左素短语

17．文法G[E]为：E E+E|E*E|a，它是( B )。

A．LL(1)文法 B．算符文法 C．算符优先法 D．非二义文法

18．下述正规式中哪个与(a*b) * (c d)等价( D )

A．a* (c d)b(c d) B．a* (c d) *b(c d) *

C．a* (c d)b* (c d) D．(a b) *c(a b) *d

19．文法G所描述的语言是( D )

A．文法G的字汇表V中所有符号组成的符号串的集合

B．文法G的字汇表V的闭包V*中的所有符号串的集合

C．由文法的识别符号推出的所有符号串的集合

D．由文法的识别符号推出的所有终结符号串

20．给定文法, A bA | cc, 下面符号串可由其推导出的是( D )

①cc ② b*cc ③ b*cbcc ④ bccbcc ⑤ bbbcc

A. ①

B. ①③④⑤

C. ①⑤

D. ①②⑤

21．某个语言，它能用正规表达式表示，但是它不能使用任何正规文法表示，这个语言必然是( D )

A．1型文法所对应的语言 B．含有二义的语言

C．既含有左递归又含有右递归 D．不存在的语言

正规式等价于正规文法

22．下面哪个不是单词的描述工具( C )

A．正规式 B．有穷自动机 C．下推自动机 D．正规文法

5．LL(1)文法的条件是( C )

A．对形如U x1 | x2 | … | xn 的规则，要求First(xi)∩ First(xj)=Φ,(i≠j);

B．对形如U x1 | x2 | …| xn 的规则，若xi=>*ε, 则要求First(xj)∩Follow(U)=,(i≠j)

C．a 和 b

D．都不是

23．词法分析的另外一个名称是(B )

A．分析器 B．扫描器 C．划分处理器 D．词法探索器

24．关于短语和句柄，正确的叙述是( B )

A．短语就是句柄 B．直接短语才可能是句柄

C．最左短语一定是句柄 D．最右短语一定是句柄

25．给定文法, A bAa | cc, 下面符号串可由其推导出的是( B )

A．bbcc B．bbccaa C．aaccbb D．acb

26．文法 G 产生的( D )的全体是该文法描述的语言。

A．句型 B. 终结符集 C. 非终结符集 D. 句子

27．Chomsky 定义的四种形式语言文法中， 0型文法又称为什么文法( A )

A．短语结构文法 B．正规文法 C．上下文有关文法 D．上下文无关文法28．Chomsky 的2 型语言可由下列哪一个识别( C )

A．图灵机 B．有穷自动机 C．下推自动机 D．线性界限自动机29．字母表{a,b}上以aa打头任何符号串的集合，可用正规式表示为( B )

A．(a|b)* aa B．aa(a|b)* C．aa(a* |b*) D．a,b,c均不正确30．chomsky 的1型语言可由下面哪个识别( D )

A．图灵机 B．有穷自动机 C．下推自动机 D．线性界限自动机31．表达式A/(B-C*(C+D))的逆波兰式是( )

A．ABC-CD/* B．ABCCD+*-/ C．ABC-*CD/* D．a,b,c均不正确32．在编译过程中，组织的符号表是( C )

A．必须是唯一的

B．应当按符号的不同属性分为几个

C．可以唯一的也可按符号表不同属性分为几个

D．以上均不对

33．BNF范式是一种广泛采用的什么工具( C )