编译原理 第三章

编译原理_第3章课件第三章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的⾃动构造原理。

教学要求１.掌握：正规式，DFA的概念，NFA的概念２.理解：将NFA转换为DFA ,正规式、正规⽂法与有穷⾃动机间的转换⽬录3.1 词法分析程序的设计3.2 单词的描述⼯具3.3 有穷⾃动机3.4 正规式与有穷⾃动机的等价性3.5 正规⽂法和有穷⾃动机的等价性3.6 词法分析程序的⾃动构造⼯具⼩结3.1.词法分析（lexical analysis）程序的设计回顾：1、词法分析的任务：逐个读⼊源程序字符并按照构词规则切分成⼀系列单词。

2、词法分析程序：实现词法分析的程序。

⼀.词法与语法分析程序的接⼝⽅式1、作为独⽴的⼀遍词法分析是编译过程中的⼀个阶段，在语法分析前进⾏，把字符流的源程序变为单词序列，输出在⼀个中间⽂件上。

2、与语法分析结合在⼀起作为⼀遍⼀般、把词法分析程序设计成⼀个⼦程序，由语法分析程序调⽤词法分析程序来获得当前单词，供语法分析使⽤。

….词法分析程序的主要任务：读源程序，产⽣单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换⾏符追踪换⾏标志，复制出错源程序，宏展开，……⼆、词法分析程序的输出输出是单词符号。

单词是语⾔中具有独⽴意义的最⼩单位。

单词包括：保留字标识符常量运算符界符（标点符号）词法分析程序所输出的单词符号常常采⽤以下⼆元式表⽰：(单词种别，单词⾃⾝的值)。

单词的种别是语法分析需要的信息，⽽单词⾃⾝的值则是编译其它阶段需要的信息。

(标识符，指向该标识符所在符号表中位置的指针) 单词的种别可以⽤整数编码表⽰，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5例如：程序段if i=5 then x∶=y；在经词法分析器扫描后输出的单词符号和它们的表⽰如下：- 保留字if(3，'if')- 标识符i(1，指向i的符号表⼊⼝)- 等号=(4，'=')- 常数5(2，'5')- 保留字then(3，'then')- 标识符x(1，指向x的符号表⼊⼝)- 赋值号∶=(4，'∶=')- 标识符y(1，指向y的符号表⼊⼝)- 分号；(5，'；')三、词法分析⼯作从语法分析⼯作独⽴出来的原因：简化设计改进编译效率增加编译系统的可移植性3.2 单词的描述⼯具程序设计语⾔中的单词是基本语法成分.单词符号的语法可以⽤有效的⼯具加以描述，并且基于这类描述⼯具，实现词法分析程序的⾃动构造.描述⼯具：正规⽂法和正规式识别⼯具：有穷⾃动机⼀．正规⽂法多数程序设计语⾔的单词的语法能⽤正规⽂法来描述。

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

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

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

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.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9,3.6.3, 3.6.4, 3.6.53.7.1, 3.7.2, 3.7.33.8.1, 3.8.23.9.3《编译原理》（龙书）第三章答案3.3.2 描述下列正则表达式代表的语言。

a) a(a|b)*ab) ((ε|a)b*)*c) (a|b)*a(a|b)(a|b)d) a*ba*ba*ba*e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*答案(a)由a开头并结尾的由a和b构成的字符串(b)由a和b构成的字符串(c)倒数第三位为a的由a和b构成的字符串(d)仅含3个b的由a和b构成的字符串(e)含有偶数个a和偶数个b的由a和b构成的字符串注意：请准确描述语言的性质而不是列举满足正则表达式的串3.3.6 写出满足下列定义的字符a) The first ten letters in either upper or lower caseb) The lowercase consonantsc) The “digits” in a hexadecimal numberd) The characters that can appear at the end of a legitimate English sentence答案(a)a-jA-J(b)a-j(c)0-9a-f(d).?!3.3.7 写出匹配字符串“\ 的正则表达式答案：\”\\3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。

这个NFA能否接受aabb? 答案：aabb的所有路径01223 00111 012000 00000 01222 00011 00123存在路径1223和0123所以能接受aabb3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。

这个NFA能否接受aabb? 答案：01012301012120301230301212030303232030303212303030321212由于存在03210这样的环,所以这里有无数种路径存在路径终止于3,所以能接受aabb3.6.5 给出以下NFA的Transition Table(a) 图3.29(b) 图3.30(c) 图3.26答案:3.7.1 把下列NFA转化为DFA(a)图3.26(b)图3.29(c)图3.30答案:(a)(b)注意:以上答案并不唯一,等价即可3.7.2 用算法3.22模拟NFA(输入为aabb)(a)图3.29(b)图3.30答案:F={3} 所以返回yesF={3},所以返回yes3.7.3 用算法3.23和3.20把下列正则表达式转换为DFAa) (alb)*b) (a*lb* )*c) ((ela)b*)*d) (alb)*abb(alb)*答案：a) NFAb) NFAc) NFAd) NFA注意：这道题要求大家按照算法构造NFA和DFA，有些同学的NFA没有完全按照算法构造。

编译原理第3章内容简介学习目标第3章有穷自动机3.1 有穷自动机的形式定义3.1 有穷自动机的形式定义DFA的表示举例——状态转换表DFA的表示举例——状态转换图 3.13.1 FA的形式定义有穷自动机识别的符号串举例DFA A3.1 有穷自动机的形式定义 3.1 有穷自动机的形式定义NFA举例 3.13.1用NFA识别符号串yFA的构造FA的构造举例—1FA的构造举例—2FA的构造举例—3请构造一个有穷自动机FA的构造举例—4 3.1请构造一个有穷自动机FA的等价性举例3.2 NFA到DFA的转换 3.2 NFA到DFA的转换—NFA确定化3.2 NFA到DFA的转换3.2 NFA到DFA的转换—NFA确定化——ε闭包状态子集I的ε闭包——举例状态子集I的状态子集I的ε闭包——举例状态子集I的——Ia 子集3.2 NFA到DFA的转换Ia子集——举例Ia子集——举例 3.2 NFA到DFA的转换NFA到DFA的转换——子集法NFA=（Q NFA到DFA的转换——举例1aNFA到DFA的转换——举例2NFA DFA DFA NFA DFA DFADFA化简举例1DFA化简——注意NFA到最小化DFA的转换——举例33.3 正规文法与FA3.3 正规文法与FAFA⇒右线性正规文法FA⇒右线性正规文法——举例1y3.4 正规表达式RE与FA 正规表达式与有穷自动机3.4 RE与FA——RE的性质 3.4 RE与FA—RE⇒FARE⇒FA举例1RE⇒FA举例23.4 RE与FA——FA⇒RE FA⇒REFA⇒RE FA⇒RE举例FA⇒RE举例正规文法到正规表达式正规文法到正规表达式DFA的程序实现DFADFA的程序实现DFA DFA的程序实现lDFA的程序实现l第3章内容小结第3章内容小结参考文献。