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→ｉSｅS |ｉS | ｉ 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. 一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ ）