文档介绍：第三章词法分析
本章要点
,
,
。
本章目标:
,掌握词法分析器的设计;
;
。
本章重点:
,用高级语言编写词法分析器等内容,它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计,状态转换图等内容。
,它们之间转换的技巧、方法或算法。
(1)非形式描述的语言« 正规式
(2)正规式® NFA(非确定的有限自动机)
(3)NFA ® DFA(确定的有限自动机)
(4)DFA ® 最简DFA
本章难点
(1) 非形式描述的语言« 正规式
(2) 正规式® NFA(非确定的有限自动机)
(3) NFA ® DFA(确定的有限自动机)
(4) DFA ® 最简DFA
作业题
一、单项选择题
1. 程序语言下面的单词符号中, 一般不需要超前搜索
a. 关键字 b. 标识符 c. 常数 d. 算符和界符
2. 在状态转换图的实现中, 一般对应一个循环语句
a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是
3. 从左线性文法构造有限自动机时,通常自动机状态个数比文法非终结符号数多
(a)4 (b)2 (c)0 (d)1
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. 有限状态自动机可用五元组(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所对应的状态转换图为。
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. 下面四个选项中,关于编译过程中扫描器的任务的叙述,________是不正确的。
①组织源程序的输入;按词法规则分割出单词,识别其属性,并转换成属性字的形式输出;删除注释;删除空格和无用字符;行计数、列计数;发现并定位词法错误;建立符号表。
②按词法规则分割出单词,识别其属性,并转换成属性字的形式输出;发现并定位词法错误;建立符号表;输出状态转换图。
③组织源程序的输入;按词法规则分割出单词,识别其属性,并转换成属性字的形式输出。
④组织源程序的输入;按词法规则分割出单词,识别其属性,并转换成属性字的形式输出;行计数、列计数;发现并定位词法错误;建立符号表;输出状态转换图。
:1. b;2. b;3. d;4. d;5.②;6. ②,7.④;8. b;9. ①
二、多项选择题:
1.
:1. a,b,c,d,e,f,g;2. b;
三、填空题:
1. 词法分析器对扫描缓冲区进行扫描时一般用两个指示器,一个_________________________________;另一个_____________________________________。
2. 一个确