西理工编译原理试题集1-7(5)

10. 关于NFA的叙述中，下面______是不正确的。

A.有一个有穷字母表 B.有多个初始状态 C.有多个终止状态 D.有多个有限状态 11. 词法分析的理论基础是 。

A.有穷自动机理论 B.图灵机理论 Ｃ.图论 Ｄ.无穷自动机理论

12. 设有两个状态S和T，如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的字而停于终态。则我们称状态S和状态T是 。

A. 可区分的；B. 等价的；C. 多余的；D. 无用的。 13. 词法分析器的输出结果是 。

A、单词自身值

B、单词在符号表中的位置 D、单词的种别编码和自身值

C、单词的种别编码

14. 编译过程中扫描器的任务包括______。

①组织源程序的输入

②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 ⑧删除注解

④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表

a．②③④⑦ b．②③④⑥⑦ c．①②③④⑥⑦ d．①②③④⑤⑥⑦

15. 下述正则表达式中______与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作x|y)

①a*(c+d)+b(c+d) ②a*(c+d)*+b(c+d)* ③a*(c+d)+b(c+d) ④(a+b)*c+(a+b)*d ⑤(a*+b)*c+(a*+b)*d

a.①③ b. ③④⑤ c.③ d.④⑤ 16、正则式的“*”读作______。

a，并且 L或者 c．连接 d．闭包

17. 在状态转换图中，结点代表 ，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串 18. 与(a|b)*(a|b)等价的正规式是 。

A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)* 19.无符号常数的识别和拼数工作通常都在 阶段完成。

Ａ．词法分析 Ｂ．语法分析 Ｃ．语义分析 Ｄ．代码生成

一．答案：1. b；2. b；3. c；4. d；5.②；6. ②，7.④；8. b；9. ①；10. B；11. A； 12. B；13. d；14. d；15.d；16.d；17.c；18. C；19. A

二、填空题：

（按照组卷方案，至少15道）

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. L(M)=L(M')；3. 单词种别，单词符号的属性值；4. 初态，终态；5. 由while和if语句构成的；6. 源程序，单词；7. 种别编码；8. 存放它的有关信息的符号表项的指针；9. 存放它的常数表项的指针；10. 单词符号的属性信息（属性值）；11. 两个正规式所表示的正规集相同；12. 这条通路上所有弧的标记符号连接起来形成的符号串等于?；13. 正规定义式，识别规则；14. 状态，输入字符，转换函数（或?(s, a)）的值；15. 将搜索器回退一个位置，并令下一个状态图开始工作。

三、判断题：

（按照组卷方案，至少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．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ ） 13. 一个正规式只能对应一个有限状态自动机；

（ ）

14. 在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。（ ） 15. 适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界所打断。 （ ） 四．答案：1. ×；2. ?；3. ?；4. ×；5. ×；6. ?；7. ?；8. ?；9. ?；10. ?；11. ?；12×；13. ×；14. ?；15. ×；

四、名词解释：

（按照组卷方案，至少5道） 1. 状态转换图；

2. 正规式（正规表达式、正则表达式）的形式化定义； 3. 给出确定性有限状态自动机的形式化定义； 4. 给出非确定性有限状态自动 …… 此处隐藏：2545字，全部文档内容请下载后查看。喜欢就下载吧 ……