第三章 词法分析
本章要点
１．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。
本章目标：
１．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。
本章重点：
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)表示的集合是
(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. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：
VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所对应的状态转换图为 。
2
*
*
*
*
*
6. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：
VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2
M所能接受的语言可以用正则表达式表示为 。
①(0|1) ②00(0|1) ③(0|1)00 ④0(0|1)0
7 . 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：
VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言为 。
①由0和1所组成的符号串的集合
②以0为头符号和尾符号、由0和1所组成的符号串的集合 ③以两个0结束的，由0和1所组成的符号串的集合 ④以两个0开始的，由0和1所组成的符号串的集合
8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。
a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机；
b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机； c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法； d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；
9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是较为完整且正确的。 ①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表。 ②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。
③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。
④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。
*
*
*
*
编译原理作业集-第三章-修订版
