编译原理作业集-第三章-修订版.pdf

编编译译原原理理作作业业集集-第第三三章章-修修订订版版

第三章词法分析

本章要点

１．词法分析器设计，

２．正规表达与有限⾃动机，

３．词法分析器⾃动⽣成。

本章⽬标：

１．理解对词法分析器的任务，掌握词法分析器的设计；

２．掌握正规表达与有限⾃动机；

３．掌握词法分析器的⾃动产⽣。

本章重点：

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.有限状态⾃动机可⽤五元组（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所对应的状态转换图为。

.有限状态⾃动机可⽤五元组（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.下⾯四个选项中，关于编译过程中扫描器的任务的叙述，________是较为完整且正确的。

①组织源程序的输⼊；按词法规则分割出单词，识别其属性，并转换成属性字的形输出；删除注释；删除空格和⽆⽤字符；

⾏计数、列计数；发现并定位词法错误；建⽴符号表。

②按词法规则分割出单词，识别其属性，并转换成属性字的形输出；发现并定位词法错误；建⽴符号表；输出状态转换图；

把状态转换图⾃动转换成词法扫描程序。

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

④组织源程序的输⼊；按词法规则分割出单词，识别其属性，并转换成属性字的形输出；⾏计数、列计数；发现并定位词法

错误；建⽴符号表；输出状态转换图；把状态转换图⾃动转换成词法扫描程序。

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

A.有⼀个有穷字母表

B.有多个初始状态

C.有多个终⽌状态

D.有多个有限状态

11.词法分析