第三章词法分析本章要点１．词法分析器设计，２．正规表达式与有限自动机，３．词法分析器自动生成。

本章目标：１．理解对词法分析器的任务，掌握词法分析器的设计；２．掌握正规表达式与有限自动机；３．掌握词法分析器的自动产生。

本章重点：1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。

应重点掌握词法分析器的任务与设计，状态转换图等内容。

2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。

（1）非形式描述的语言↔正规式（2）正规式→ NFA（非确定的有限自动机）（3）NFA → DFA（确定的有限自动机）（4）DFA →最简DFA本章难点（1）非形式描述的语言↔正规式（2）正规式→ NFA（非确定的有限自动机）（3）NFA → DFA（确定的有限自动机）（4）DFA →最简DFA作业题一、单项选择题（按照组卷方案，至少15道）1. 程序语言下面的单词符号中，一般不需要超前搜索a. 关键字b. 标识符c. 常数d. 算符和界符2. 在状态转换图的实现中，一般对应一个循环语句a. 不含回路的分叉结点b. 含回路的状态结点c. 终态结点d. 都不是3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。

(a)ld*(b)ll*(c)l(l | d)*(d)ll* | d*4. 正规表达式(ε|a|b)2表示的集合是(a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb}(c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba}5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所对应的状态转换图为。

6. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所能接受的语言可以用正则表达式表示为。

①(0|1)*②00(0|1)*③(0|1)*00④0(0|1)*07 . 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下：V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为：δ（q0，0）=q1δ（q1，0）=q2δ（q2，1）=q2δ（q2，0）=q2M所能接受的语言为。

①由0和1所组成的符号串的集合②以0为头符号和尾符号、由0和1所组成的符号串的集合③以两个0结束的，由0和1所组成的符号串的集合④以两个0开始的，由0和1所组成的符号串的集合8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。

a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机；b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机；c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法；d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是较为完整且正确的。

①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表。

②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。

③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。

④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。

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、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值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)*da.①③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. 给出非确定性有限状态自动机的形式化定义；5. DFA状态最小化。