编译原理作业集-第三章-修订版
第三章词法分析
本章要点
１．词法分析器设计，
２．正规表达式与有限⾃动机，
３．词法分析器⾃动⽣成。
本章⽬标：
１．理解对词法分析器的任务，掌握词法分析器的设计；
２．掌握正规表达式与有限⾃动机；
３．掌握词法分析器的⾃动产⽣。
本章重点：
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）=q2
M所对应的状态转换图为。
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）=q2
M所能接受的语⾔可以⽤正则表达式表⽰为。
①(0|1)*②00(0|1)*③(0|1)*00④0(0|1)*0
7 . 有限状态⾃动机可⽤五元组（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）=q2
M所能接受的语⾔为。
①由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)*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个字符）可以保证单词符号不会被它的边界所打断。（）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。