编译原理试题集78677

5. 已知文法G[S]: S→AB A→aA|a B→bB|b 求该文法所定义的语言。

6. 考虑下面上下文无关文法G[S]: S→SS*|SS+|a (1) 对于符号串aa+a*分别给出最左推导和最右推导过程,并为该串构造语法树。 (2)G[S]的语言是什么?

7. 令文法G为 N→ D | ND D→ 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 (1) G的语言L(G)是什么? (2) 给出句子0127、34和568的最左推导和最右推导。

8. 写一个文法,使其语言是奇数集,且每个奇数不以0开头。

9. 写一个上下文无关文法CFG,使其语言是能被5整除且不以0开头的无符号整数的集合。(

如{5,10,15,?.})

10. 证明下面的文法是二义的: S→iSeS |iS | i 11. 某程序设计语言的表达式由运算符θ1、θ2、θ3、 标识符、(、)组成,其中θ1和θ2的优先级相同,θ3

的优先级低于θ1、θ2的优先级,优先级相同的运算符从右往左 计算,可以用括号改变运算的顺序,则下述四种文法中哪一个可以描述上述的表达式文法? 设E为识别符号,终结符号集={θ1、θ2、θ3、 (、)、I},非终结符号集={E、T、F}。 a. E→T|Eθ1T|Eθ2T T→F|Tθ3F F→(E)|I b. E→T|Tθ1E|Tθ2E T→F|Fθ3T

F→(E)|I

c. E→T|Eθ3T

T→F|Tθ1F|Tθ2F F→(E)|I

d. E→T|Tθ3 E

T→F|Fθ1T|Fθ2T F→(E)|I

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

第三章 词法分析

一.填空题

1. 词法分析器对扫描缓冲区进行扫描时一般用两个指示器,一个_______________________ __________;另一个_____________________________________。 ————————————————————————————;————————— —————————————————___________________________;

2. 一个确定性有限自动机DFA M的化简是指:寻找一个状态数比M少的DFA M’,使得______

__________。

3. 词法分析器所的输出常表示成如下形式的二元式:(______________,_______________ __)。

4. 一个状态转换图只包含有限个状态,其中有一个被认为是________,而且实际上至少有 一个________。

5. 把状态转换图用程序实现时,对于含有回路的状态结点来说,可以让它对应一个_______ ______________________________程序段。

6. 词法分析阶段的任务式从左到右扫描_____________,从而逐个识别______________ 。

7. 如果一个种别只含有一个单词符号,那么,对于这个单词符号,__________就可以完全 代表它自身了。

8. 单词符号的属性值是指单词符号的特性或特征,其属性值则是反映特性或特征的值。比 如,对于某个标识符,常将_________________________________________________作为其属 性值。

9. 单词符号的属性值是指单词符号的特性或特征,其属性值则是反映特性或特征的值。比 如,对于常数,常将__________________________________________作为其属性值。

10. 如果一个种别含有多个单词符号,那么,对于它的每个单词符号,除了给出种别编码以 外,还应给出有关__________________________ 。

11. 如果_______________________________,则认为这两个正规式等价。

12. 对于?*中的任何符号串?,如果存在一条从初态结点到某一终态结点的通路,且________ ___________________________,则称?被该自动机所接受(识别)。

13. 一个Lex源程序主要包括两部分,一部分是___________________________,另一部分是_

______________________________ 。

14. 一个DFA可用一个矩阵表示,该矩阵的行表示______________,列表示_______________ ,矩阵元素表示_____________ 。这个矩阵叫状态转换矩阵。

15. 对于词法分析程序来说,当程序到达“错误处理”时,意味着现行状态i和当前所面临的

输入串不匹配。如果后面还有状态图,出现在这个地方的代码应该为: _____________________________________________________________________________

______________。

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

二.判断题

1. NFA M的非确定性表现在它有多个终态。 ( )

2. 有穷自动机接受的语言是正则语言。 ( )

3. 若r1和r2是Σ上的正规式,则r1|r2也 是。 ( )

4. 设M是一个NFA,并且L(M)={x, y, z},则M的状态数至少为4个。 ( )

5. 令Σ={a, b},则Σ上所有以b为首的字符构成的正规集的正规式为b*(a|b)*。 ( )

6. 对任何一个NFA M,都存在一个DFA M',使得L(M')=L(M)。 ( )

7. 对一个右线性文法G,必存在一个左线性文法G',使得L(G)=L(G'),反之亦然。( )

8. 对任意一个右线性文法G,都存在一个NFA M,满足L(G)=L(M)。 ( )

9. 对任意一个右线性文法G,都存在一个DFA M,满足L(G)=L(M)。 ( )

10. 对任何正则表达式r,都存在一个NFA M,满足L(M)=L(r)。 ( )

11. 对任何正则表达式r,都存在一个DFA M,满足L(M)=L(r)。 ( )

12. 一张转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态。( )

联系客服:779662525#qq.com(#替换为@)