当前位置：文档之家 › 编译原理课后答案——第二章 词法分析

编译原理课后答案——第二章 词法分析

  • 格式：ppt
  • 大小：951.50 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

编译原理-词法分析02-正则表达式

编译原理-词法分析02-正则表达式

编译原理-词法分析02-正则表达式0.术语rr：正则表达式，表⽰字符串的格式。

L(r)r所匹配的串的集合。

symbol符号L(r)中的元素称为符号。

alphabet字母表表⽰符号的字符的集合。

⽤ ∑ (sigma)表⽰。

元字符metacharacter，元符号metasymbol它们⾮字母表中的字符，是⼀些特殊意义的字符，⽐如,*. 如果要匹配这类符号，则需要使⽤转义符号\。

escape character转义字符⼀般使⽤\表⽰，⽤于匹配元字符。

空串empty string不包含任何字符的串，但它仍然是⼀个匹配。

⽤ε（eplsilon）表⽰空集empty set表⽰正则表达式⽆任何匹配。

regular definition正则定义即正则表达式的名字。

1.正则表达式的定义正则表达式是以下中的⼀种：1. 基本正则表达式由单个字符a(其中a在正规字符的字母表 ∑ 中)，以及元字符ε或元字符Φ。

分别表⽰为：L(a) = {a};L(ε) = {ε};L(Φ) = {}.2. r|s格式的表达式：其中r和s均是正则表达式。

在这种情况下：L(r|s) = L(r)|L(s)。

3. rs格式的表达式：其中r是正则表达式。

在这种情况下：L(rs) = L(r)L(s)。

4. r格式的表达式：其中r是正则表达式。

在这种情况下：L(r) = L(r)*。

5. (r)格式的表达式：其中r是正则表达式。

在这种情况下：L((r)) = L(r)，因此，括号并不改变语⾔，它们只调整运算的优先级。

注意到这个定义中，|,*,(,),Φ,ε均为元字符。

2.扩展r+ 正闭包，⾄少匹配⼀个. 匹配任意⼀个字符区间匹配如[a-z],[0-9],[A-Za-z]~a或^a 排除匹配r? 可选匹配3.程序语⾔记号的正则表达式numbernat = [0-9]+ #⾃然数signedNat = (+|-)?nat #有符号数number = signedNat("."nat)?(E signedNat)? #数字，包含整数，⼩数，正负数，指数reserved & identifierreserverd = if | while | then | repeat | do ...letter = [a-z]digit = [0-9]identifier = letter(letter|digit)*comment{(~})*} #匹配{ this is a Pascal comment}whitespace解决匹配的⼆义性遵循最长⼦串原理principle of longest。

清华大学编译原理第二版课后习答案

清华大学编译原理第二版课后习答案

Lw.《编译原理》课后习题答案第一章第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

盛威网（）专业的计算机学习网站1《编译原理》课后习题答案第一章目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

编译原理课后习题答案+清华大学出版社第二版

编译原理课后习题答案+清华大学出版社第二版
也称基地址。 SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，
用以引用非局部（包围它的过程）变量时，寻找该变量的地址。 DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放
数据空间时，恢复调用该过程前运行栈的状态。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地
编译程序大致有哪几种开发技术？
答案：
（1）自编译：用某一高级语言书写其本身的编译程序。 （2）交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。 （3）自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的编
译程序 T0，再把语言 L0 扩充到 L1，此时 L0⊂ L1 ,并用 L0 编写 L1 的编译程序 T1，再把语 言 L1 扩充为 L2，有 L1 ⊂ L2 ,并用 L1 编写 L2 的编译程序 T2，……，如此逐步扩展下 去， 好似滚雪球一样，直到我们所要求的编译程序。 （4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。
(main).
答案： 程序执行到赋值语句 b∶=10 时运行栈的布局示意图为：
1
《编译原理》课后习题答案第二章
第 3题 写出题 2 中当程序编译到 r 的过程体时的名字表 table 的内 容。
name
kind
level/val
adr
size
答案：
题 2 中当程序编译到 r 的过程体时的名字表 table 的内容为：
盛威网（）专业的计算机学习网站
2
《编译原理》课后习题答案第一章
合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行 中间代码程序，最后得到运行结果。

编译原理第三版课后习题答案

编译原理第三版课后习题答案

编译原理第三版课后习题答案编译原理是计算机科学中的一门重要课程，它研究的是如何将高级程序语言转换为机器语言的过程。

而《编译原理》第三版是目前被广泛采用的教材之一。

在学习过程中，课后习题是巩固知识、提高能力的重要环节。

本文将为读者提供《编译原理》第三版课后习题的答案，希望能够帮助读者更好地理解和掌握这门课程。

第一章：引论习题1.1：编译器和解释器有什么区别？答案：编译器将整个源程序转换为目标代码，然后一次性执行目标代码；而解释器则逐行解释源程序，并即时执行。

习题1.2：编译器的主要任务是什么？答案：编译器的主要任务是将高级程序语言转换为目标代码，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等过程。

第二章：词法分析习题2.1：什么是词法分析？答案：词法分析是将源程序中的字符序列划分为有意义的词素（token）序列的过程。

习题2.2：请给出识别下列词素的正则表达式：（1）整数：[0-9]+（2）浮点数：[0-9]+\.[0-9]+（3）标识符：[a-zA-Z_][a-zA-Z_0-9]*第三章：语法分析习题3.1：什么是语法分析？答案：语法分析是将词法分析得到的词素序列转换为语法树的过程。

习题3.2：请给出下列文法的FIRST集和FOLLOW集：S -> aAbA -> cA | ε答案：FIRST(S) = {a}FIRST(A) = {c, ε}FOLLOW(S) = {$}FOLLOW(A) = {b}第四章：语义分析习题4.1：什么是语义分析？答案：语义分析是对源程序进行静态和动态语义检查的过程。

习题4.2：请给出下列文法的语义动作：S -> if E then S1 else S2答案：1. 计算E的值2. 如果E的值为真，则执行S1；否则执行S2。

第五章：中间代码生成习题5.1：什么是中间代码？答案：中间代码是一种介于源代码和目标代码之间的表示形式，它将源代码转换为一种更容易进行优化和转换的形式。

编译原理第二版课后习答案

编译原理第二版课后习答案

编译原理第二版课后习答案编译原理是计算机科学领域中的一门重要学科，它主要研究程序的自动翻译技术，将高级语言编写的程序转换为机器能够执行的低级语言。

编译原理的基本概念和技术是计算机专业学生必须学会的知识之一，而编译原理第二版课后习题则是帮助学生更好地理解课程内容和提高编译器开发能力的重要资源。

本篇文章将对编译原理第二版课后习题进行分析和总结，并提供一些参考答案和解决问题的思路。

一、词法分析词法分析是编译器的第一步，它主要将输入的字符流转换为有意义的词法单元，例如关键字、标识符、常量和运算符等。

在词法分析过程中，我们需要编写一个词法分析程序来处理输入的字符流。

以下是几道词法分析相关的习题：1. 如何使用正则表达式来表示浮点数？答案：[+|-]?(\d+\.\d+|\d+\.|\.\d+)([e|E][+|-]?\d+)?这个正则表达式可以匹配所有的浮点数，包括正负小数、整数和指数形式的浮点数。

2. 什么是语素？举例说明。

答案：语素是构成单词的最小承载语义的单位，例如单词“man”，它由两个语素“ma”和“n”组成。

“ma”表示男性，“n”表示名词。

3. 采用有限状态自动机(Finite State Automata)实现词法分析的优点是什么？答案：采用有限状态自动机(Finite State Automata)实现词法分析的优点是运行速度快，消耗内存小，易于编写和调试，具有可读性。

二、语法分析语法分析是编译器的第二步，它主要检查词法分析生成的词法单元是否符合语法规则。

在语法分析过程中，我们需要编写一个语法分析器来处理词法单元序列。

以下是几道语法分析相关的习题：1. 什么是上下文无关文法？答案：上下文无关文法(Context-Free Grammar, CFG)是一种形式语言，它的语法规则不依赖于上下文，只考虑规则左边的非终结符号。

EBNF是一种常见的上下文无关文法。

2. LR分析表有什么作用？答案：LR分析表是一种自动机，它的作用是给定一个输入符号串，判断其是否符合某个文法规则，并生成语法树。

编译原理课后答案2010

编译原理课后答案2010
空串。
2.4 为下列语言写正规定义
C 语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀
（本身除外）不以 */ 结尾。
［解答］
other → a | b | …
other 指除了*以外 C 语言中的其它字符
other1 → a | b | …
other1指除了*和/以外C语言中的其它字符
=> S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10)) => S0 = ((00|11)|(01|10) (00|11)* (01|10))+
因为S0→ε所以由偶数个 0 和偶数个 1 构成的所有 0 和 1 的串的正规定义为： S0 → ((00|11)|(01|10) (00|11)* (01|10))*
标记状态S1 S3 = ε-closure(move(S1, a)) = ε-closure({5, 8, 12}) = {1, 2, 4, 5, 6, 7, 8, 9, 11,
12, 13, 14, 16} S4 = ε-closure(move(S1, b)) = ε-closure({3, 10}) = {1, 2, 4, 5, 6, 7, 10, 13, 14,
S0 = 1S1 + 0S2
S1 = 1S0 + 0S3 + 1
S2 = 1S3 + 0S0 + 0 S3 = 1S2 + 0S1
所以：
S0 = (00|11) S0 + (01|10) S3 + 11 + 00
(1)
S3 = (00|11) S3 + (01|10) S0 + 01 + 10

编译原理教程课后习题答案第二章

第二章 词法分析2.1 完成下列选择题：(1) 词法分析器的输出结果是。

a. 单词的种别编码b. 单词在符号表中的位置c. 单词的种别编码和自身值d. 单词自身值(2) 正规式M1和M2等价是指。

a. M1和M2的状态数相等b. M1和M2的有向边条数相等c. M1和M2所识别的语言集相等d. M1和M2状态数和有向边条数相等(3) DFA M(见图2-1)接受的字集为。

a. 以0开头的二进制数组成的集合b. 以0结尾的二进制数组成的集合c. 含奇数个0的二进制数组成的集合d. 含偶数个0的二进制数组成的集合【解答】(1) c (2) c (3) d图2-1 习题2.1的DFA M2.2 什么是扫描器？扫描器的功能是什么？【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。

每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。

2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下：f(x,a)={x,y} f {x,b}={y}f(y,a)=Φ f{y,b}={x,y}试构造相应的确定有限自动机M ′。

【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。

先画出NFA M 相应的状态图，如图2-2所示。

图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表表2-1 状态转换矩阵1b将转换矩阵中的所有子集重新命名，形成表2-2所示的状态转换矩阵，即得到 M ′=({0,1,2},{a,b},f,0,{1,2})，其状态转换图如图2-3所示。

表2-2 状态转换矩阵将图2-3所示的DFA M ′最小化。

编译原理(龙书)课后习题解答(详细)

编译原理(龙书)课后习题解答(详细)编译原理(龙书)课后题解答第一章1.1.1 ：翻译和编译的区别？答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。

1.1.2 ：简述编译器的工作过程？答：编译器的工作过程包括以下三个阶段：(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。

1.2.1 ：解释器和编译器的区别？答：解释器和编译器的主要区别在于执行方式。

编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。

1.2.2 ：Java语言采用的是解释执行还是编译执行？答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。

但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。

第二章2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式答：<加法表达式> ::= <加法表达式> "+" <乘法表达式> | <乘法表达式><乘法表达式> ::= <乘法表达式> "*" <单项式> | <单项式><单项式> ::= <数字> | "(" <加法表达式> ")"2.2.3 ：什么是自下而上分析？答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。

编译原理_第二章 词法分析(1)

2010-7-22 编译原理 8
第二章 词法分析
3,词法分析器输出单词的形式 ,
词法分析程序的输入是源程序字符串, 而输出是与源程序等价的单词符号序列, 词法分析器输出单词的形式 并且所输出的单词符号通常表示成如下 的二元式: 单词种别,单词自身的值) (单词种别,单词自身的值)
2010-7-22
2010-7-22
编译原理
11
第二章 词法分析
二,模式的形式化描述-正规式与正规集 模式的形式化描述-
1,字符串与语言 , 从词法分析的角度看,程序设计语言 是由记号组成的集合,每个记号又是由 若干字母按照一定规则组成的字符串.
2010-7-22
编译原理
12
第二章 词法分析
定义2.1 语言 是有限字母表 上有限长度字 语言L是有限字母表 是有限字母表∑上有限长度字 定义 符串的集合. 符串的集合. 定义2.1明确指出,语言是一个集合,集 明确指出, 定义 明确指出 语言是一个集合, 合中的元素是字符串,并且强调了两个有限: 合中的元素是字符串,并且强调了两个有限 字母表是有限的, ① 字母表是有限的,即字母表中元素是 有限多个; 有限多个; 字符串的长度是有限的, ② 字符串的长度是有限的,即字符串中 字符个数是有限多个. 字符个数是有限多个. 这是由于计算机所能表示的字符个数和 字符串的长度都是有限的. 字符串的长度都是有限的.
第二章 词Hale Waihona Puke 分析第二章词法分析
主要内容: 主要内容: 词法分析过程涉及的几个问题 模式的形式化描述模式的形式化描述-正规式与正规集 记号的识别记号的识别-有限自动机 从正规式到词法分析器 词法分析器生成器简介
2010-7-22
编译原理

编译原理第二章习题答案

第2章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}2.文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D……D3.已知文法G[S]:Sf dAB Af aA|a B|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法? [答案]正规式是daa*b* ；相应的正规文法为(由自动机化简来):G[S]:S —dA A —a|aB B —aB|a|b|bC C —bC|b也可为(观察得来):G[S]:S —dA A —a|aA|aB B —bB| &4.已知文法G[Z]:Z->aZb|ab写出L(G[Z])的全部元素。

[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}5.给出语言｛a n b n c1 n>=1,m>=0｝的上下文无关文法。

［分析］本题难度不大，主要是考上下文无关文法的基本概念。

上下文无关文法的基本定义是：A-> B ,A € Vn ,B€( VnU Vt) *,注意关键问题是保证a n b n的成立，即“ a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。

［答案］构造上下文无关文法如下：S->AB|AA->aAb|abB->Bc|c［扩展］凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。

基本思路是这样的：要求符合a n b n c m，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而c m做为另一个单位，初步产生式就应写为S->AB,其中A推出a n b n，B推出c m。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第二章 词法分析
I {X}
Ia {1}
Ib {3}
S
a
b
0
1
2
{1}
{2,3,Y} {3,Y}
1
3
4
{3}
—
{3,4}
重新命名
2
—
5
{2,3,Y} {2,3,Y} {2,3,4,Y}
3
3
6
{3,Y} {2,3,Y] {3,4}
4
3
5
{3,4}
{3,4} {3,4,Y}
5
5
7
{2,3,4,Y} {2,3,4,Y} {2,3,4,Y}
{0}, {1}, {2}, {5}, {4}, {3,6,7} 按顺序重新命名为0、1、2、3、4、5，得到最简DFA 如图2-22所示。
第二章 词法分析
2.10 有一台自动售货机，接收1分和2分硬币， 出售3分钱一块的硬糖。顾客每次向机器中投放≥3分 的硬币，便可得到一块糖(注意：只给一块并且不找 钱)。
3
4
4
4
4
4
—
—
图2-24 习题2.10的状态转换矩阵
第二章 词法分析
【解答】 用正规表达式表示程序段可能的执行 序列为A(TBI)*。
2.9 将图2-19所示的非确定有限自动机(NFA)变 换成等价的确定有限自动机(DFA)。
第二章 词法分析
b
a
2
1 a
X
a
b
b b
3
4
a
a
Y b

图2-19 习题2.9的NFA
第二章 词法分析 其中，X为初态，Y为终态。 【解答】 用子集法将NFA确定化，如图2-20所示。
a
b
b
a
0
1
2
3
4
图2-10 习题2.5的最简DFA
第二章 词法分析
2.6 有语言L={w|w∈(0,1)+，并且w中至少有两个 1，又在任何两个1之间有偶数个0}，试构造接受该语 言的确定有限状态自动机(DFA)。
【解答】 对于语言L，w中至少有两个1，且任意 两个1之间必须有偶数个0；也即在第一个1之前和最后 一个1之后，对0的个数没有要求。据此我们求出L的正 规式为0*1(00(00)*1)*00(00)*10*，画出与正规式对应的 NFA，如图2-11所示。
第二章 词法分析
2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确 定的有限自动机，其中f定义如下：
f(x,a)={x,y}
f{x,b}={y}
f(y,a)=Φ
f{y,b}={x,y}
试构造相应的确定有限自动机M′。
【解答】 对照自动机的定义M=(S,Σ,f,So,Z)， 由f的定义可知f(x,a)、f(y,b)均为多值函数，因此M
第二章 词法分析
a
0
2
a, b
b b
1
图2-3 习题2.3的DFA M′
第二章 词法分析
a
0
1
a, b
b
图2-4 图2-3化简后的DFA M′
第二章 词法分析
2.4 正规式(ab)*a与正规式a(ba)*是否等价？请 说明理由。
【解答】 正规式(ab)*a对应的NFA如图2-5所示， 正规式a(ba)*对应的NFA如图2-6所示。
是一非确定有限自动机。
先画出NFA M相应的状态图，如图2-2所示。
第二章 词法分析
a
a b X b
Y
b
图2-2 习题2.3的NFA M
第二章 词法分析 用子集法构造状态转换矩阵，如表2-1所示。
表2-1 状态转换矩阵
I {x} {y} {x,y }
Ia {x,y }
— {x,y }
Ib {y} {x,y } {x,y }
第二章 词法分析
比较图2-18与图2-15，重新命名后的转换矩阵是 完全一样的，也即正规式(a|b)*b可以同样得到化简后 的DFA如图2-16所示。因此，两个自动机完全一样，即 两个正规文法等价。
(2) 对图2-16，令A对应状态1，B对应状态2，则 相应的正规文法G[A]为 G[A]：A→aA|bB|b
第二章 词法分析
第二章 词法分析
2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等
(1) 写出售货机售糖的正规表达式； (2) 构造识别上述正规式的最简DFA。 【解答】 (1) 设a=1，b=2，则售货机售糖的正 规表达式为a (b|a(a|b))|b(a|b)。 (2) 画出与正规表达式a(b|a(a|b))|b(a|b)对应 的NFA，如图2-23所示。
第二章 词法分析
a
第二章 词法分析
2
a
b

a
X
1
Y
图2-5 正规式(ab)*a对应的NFA
第二章 词法分析
2
b
a
a

X
1
Y
图2-6 正规式a(ba)*对应的DFA
第二章 词法分析
这两个正规式最终都可得到最简DFA，如图2-7所 示。因此，这两个正规式等价。
第二章 词法分析
a
0
1
b
图2-7 最简NFA
第二章 词法分析
6
6
6
{3,4,Y} {2,3,4,Y} {3,4,Y}
7
6
7
图2-20 习题2.9的状态转换矩阵
第二章 词法分析
图2-20所对应的DFA如图2-21所示。
a
a
3
b
a1ba
0
4
a
6 b
b2
b
a
b
5
7
b
a b
图2-21 习题2.9的DFA
第二章 词法分析
1 a
0 b
2
a
a
b a
4
b
b
3
5
b b
a
图2-22 习题2.9的最简DFA
第二章 词法分析
用子集法将图2-17所示的NFA确定化为如图2-18所 示的状态转换矩阵。
第二章 词法分析
I
Ia
Ib
S
a
b
{X,1,2} {1,2} {1,2,Y} 重 新 命 名
1
2
3
{1,2}
{1,2} {1,2,Y}
2
2
3
{1,2,Y} {1,2} {1,2,Y}
3
2
3
图2-18 图2-17确定化后的状态转换矩阵
第二章 词法分析
I {X} {1} {2} {3} {4} {5} {Y} {6}
Ia {1} {2} {1} — {Y} — {6} {Y}
Ib
S
—
0
{3}
1
—
重新命名
2
{4}
3
{5}
4
{4}
5
—
7
—
6
a
b
1
—
2
3
1
—
—
4
7
5
—
4
6
—
7
—
图2-9 习题2.5的状态转换矩阵
第二章 词法分析
a
b
a
—
4
{1,Y} {2,5,Y}
—
5
{2,5,Y} {3,6,Y}
—
6
{3,6,Y} {4,7,Y} {1,Y}
7
{4,7,Y} {3,6,Y}
—
8
0
1
0
1
2
—
3
—
4
5
3
—
6
—
7
—
8
5
7
—
图2-12 习题2.6的状态转换矩阵
第二章 词法分析
由图2-12可看出非终态2和4的下一状态相同，终 态6和8的下一状态相同，即得到最简状态为 {0}、{1}、{2,4}、{3}、{5}、{6,8}、{7}
1 a
X b 2
3 b
b
a
Y a
b
图2-23 习题2.10的NFA
第二章 词法分析 用子集法将图2-21的NFA确定化，如图2-24所示。
I {X} {1} {2} {3} {Y}
Ia {1} {3} {Y} {Y} —
Ib {2} {Y} {Y} {Y} —
S 重新命名
0 1 2 3 4
a
b
1
2
B→aA|bB|b G[A]可进一步化简为G[S]：S→aS|bS|b(非终结符 B对应的产生式与A对应的产生式相同，故两非终结符 等价，即可合并为一个产生式)。
第二章 词法分析
2.8 下列程序段以B表示循环体，A表示初始化， I表示增量，T表示测试：
I=1; while (I<=n)
{ sun=sun+a[I]; I=I+1; } 请用正规表达式表示这个程序段可能的执行序列。
I
Ia
Ib
S
a
b
{X,1,2,4} {1,2,3,4} {1,2,4,Y} 重 新 命 名
1
2
3
{1,2,3,4} {1,2,3,4} {1,2,4,Y}
2
2