【习题】第03章 词法分析

编译原理第三章练习题答案编译原理第三章练习题答案编译原理是计算机科学中的重要课程之一，它研究的是将高级语言程序转化为机器语言的过程。

在编译原理的学习过程中，练习题是提高理解和应用能力的重要途径。

本文将为大家提供编译原理第三章的练习题答案，希望能够对大家的学习有所帮助。

1. 什么是词法分析？请简要描述词法分析的过程。

词法分析是编译过程中的第一个阶段，它的主要任务是将源程序中的字符序列划分为有意义的词素（token）序列。

词法分析的过程包括以下几个步骤：1）扫描：从源程序中读取字符序列，并将其转化为内部表示形式。

2）识别：根据预先定义的词法规则，将字符序列划分为不同的词素。

3）分类：将识别出的词素进行分类，如关键字、标识符、常量等。

4）输出：将分类后的词素输出给语法分析器进行进一步处理。

2. 什么是正则表达式？请给出一个简单的正则表达式示例。

正则表达式是一种用于描述字符串模式的工具，它由一系列字符和操作符组成。

正则表达式可以用于词法分析中的词法规则定义。

以下是一个简单的正则表达式示例：[a-z]+该正则表达式表示匹配一个或多个小写字母。

3. 请简要描述DFA和NFA的区别。

DFA（Deterministic Finite Automaton）和NFA（Nondeterministic Finite Automaton）是有限状态自动机的两种形式。

它们在词法分析中常用于构建词法分析器。

DFA是一种确定性有限状态自动机，它的状态转换是确定的，每个输入符号只能对应一个状态转换。

相比之下，NFA是一种非确定性有限状态自动机，它的状态转换是非确定的，每个输入符号可以对应多个状态转换。

4. 请简要描述词法分析器的实现过程。

词法分析器的实现过程包括以下几个步骤：1）定义词法规则：根据编程语言的语法规范，定义词法规则，如关键字、标识符、常量等。

2）构建正则表达式：根据词法规则，使用正则表达式描述不同类型的词素。

3）构建有限状态自动机：根据正则表达式，构建DFA或NFA来识别词素。

第三章词法分析练习3.1给出一个正则表达式和自动机，使之表示满足下面条件的0、1序列：1）只包含两个1。

2）不包含连续的1。

3）包含偶数个1。

3.2写出下面符号串集的正则表达式：1）{a,b,c}a偶数出现2）{a,b,c}不包含子串baa3）二进制数，大于1010014)二进制数，4的倍数5)偶数个0奇数个1的0/1串3.3构造识别下列正则表达式定义的NFA：1)(a|(b)+2)(a*|(b*)*3)(a|(bc)*d*4)((0|1)*(2|3)*)|00115)(a|b)*abb(a|b)*3.4为下列正则表达式构造极化的DFA:1)(a|b)*a(a|b)2)(a|b)*a(a|b)(a|b)3.5利用自动机原理构造模式匹配程序，即构造一个程序，使它能识别给定a/b串是不是a i b j a k b m类串：，其中i和j是大于等于0的整数，而k和m是大于0的整数。

3.5将下面不确定自动机NFA转换为确定自动机DFA:3.6将下面不确定自动机NFA转换为确定自动机DFA:3.7试将下面不确定自动机NFA转换为确定自动机DFA:3.8试写出下面确定自动机DFA的正则表达式：3.9设置一个名字表NameL和整数表ConstL，当遇到标识符时，将其字符串送入名字表NameL，并把其名字表地址作为标识符的Value值。

整常数情形也一样，不要求翻译成二进制数。

要求在NameL表和ConstL表中没有相同元素。

试用C语言写一个针对上述单词集的词法分析器。

单词class valuebegin BeginSymbend EndSymbvar VarSymbinteger IntSymbif IfSymbthen ThenSymbelse ElseSymb;SemiSymb:ColonSymb:=AssigSymb<LittleSymb<=LittEquiSymb标识符IdentSymb名字表地址整常数ConstSymb常数表地址3.10实数的语法定义如下面所述：<实数>::=<整数部分><小数部分><指数部分><整数部分>::=<数字>|<整数部分><数字><小数部分>::=ε|.<整数部分><指数部分>::=ε|e<指数符号><整数部分><指数符号>::=ε|+|-试写出实数的非确定自动机。

第一章1、将编译程序分成若干个“遍”是为了。

b．使程序的结构更加清晰2、构造编译程序应掌握。

a．源程序b．目标语言c．编译方法3、变量应当。

c．既持有左值又持有右值4、编译程序绝大多数时间花在上。

d．管理表格5、不可能是目标代码。

d．中间代码6、使用可以定义一个程序的意义。

a．语义规则7、词法分析器的输入是。

b．源程序8、中间代码生成时所遵循的是- 。

c．语义规则9、编译程序是对。

d．高级语言的翻译10、语法分析应遵循。

c．构词规则二、多项选择题1、编译程序各阶段的工作都涉及到。

b．表格管理c．出错处理2、编译程序工作时，通常有阶段。

a．词法分析b．语法分析c．中间代码生成e．目标代码生成三、填空题1、解释程序和编译程序的区别在于是否生成目标程序。

2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。

3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。

4、编译程序是指将源程序程序翻译成目标语言程序的程序。

一、单项选择题1、文法G：S→xSx|y所识别的语言是。

a. xyxb. (xyx)*c.x n yx n(n≥0) d. x*yx*2、文法G描述的语言L(G)是指。

a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)} d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。

a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G 的任意终结符对a、b有以下关系成立。

a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。

a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。

编译原理作业集-第三章-修订版第三章词法分析本章要点１．词法分析器设计，２．正规表达式与有限⾃动机，３．词法分析器⾃动⽣成。

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

本章重点：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所对应的状态转换图为。