当前位置：文档之家 › 编译原理第3章. 词法分析

编译原理第3章. 词法分析

  • 格式：ppt
  • 大小：960.50 KB
  • 文档页数：93

下载文档原格式

  / 93

合集下载

《编译原理》第3章

《编译原理》第3章

NFA到相应的DFA的构造的基本思路是： DFA的每 一个状态对应NFA的一组状态. DFA使用它的状 态去记录在NFA读入一个输入符号后可能达到的 所有状态.
NFA M所能接受的符号串的全体记为L(M)
结论：
上一个符号串集V是正规的，当且仅当存 在一个上的不确定的有穷自动机M，使得 V=L(M)。
DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之 等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这 种算法称为子集法. 与某一NFA等价的DFA不唯一.
0
1
S P
Z
{P} {}
{P}
{S,Z} {Z}
{P}
• δ为S * 到S的子集(2 S)的一种映射
• 从NFA的矩阵表示中可以看出，表项通常是一状态的集合， 而在DFA的矩阵表示中，表项是一个状态
∑*上的符号串t被NFA M接受:
• 对于Σ*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的道路，且这条道路上所有 弧的标记字依序连接成的串(不理采那些标记为ε 的弧)等于t，则称t可为NFA M所识别(读出或接 受)。 • 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为ε，那么空字ε可为M所 接受。
其中： δ(S，0)={P}
δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z} • 状态图表示
1 1 S 0 0,1 Z
P
1
• 矩阵表示
状态 输入
δ(S，0)={P} δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z}

编译原理词法分析

编译原理词法分析
❖ 数字：继续读，直到非数字字符出现或文件尾。输 出无符号整数的单词记号及数字串；
❖ =、＜、＞、！：读下一个字符，判断是否为双字 符分界符，若是，组成双字符分界符，输出类码； 若不是，输出单分界符记号；
编译原理
❖ 非=、＜、＞、/等与双分界符首字符不同的单分界 字符：输出相应单词记号及单分界符。
1.S是一个有穷集，它的每个元素称为一个状态；
2.Σ是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称Σ为输入符号表；
3.δ是在S×Σ→S上的单值映射，即，如δ (s，a)=s’， (s∈S，s’∈S)就意味着，当前状态为s，输入符为 a时，将转换为下一个状态s’，我们把s’称作s的一 个后继状态；
编译原理 在 入 准初带备整•••始的读输读有个时开入始入头穷模，始，状带：控型读位状态：可制由头置态存以器如状的所三处，处放在：果态符识部于表于输输控读正号别分输示初入入制头好组组符带状移是成成号上态动终的：向发到结字后生最状能移变后态被头每有动化一，该转向读穷个则有移后入控符输限到移一 制号入自下动个器后带动一一符控面上机个个号制，状位，状态置读态，
编译原理
词法分析 读字符
结束 Y
结束
N Y 空字
N 字母 N 数字
Y 组合标识符 Y 组合整数
查保留字Βιβλιοθήκη N 纯单分符Y 输出单分符
N
>,<,!,= Y 读字符
=
N
N
/ Y 读字符
*
N
Y
错误处理
输出保留字
Y 保留字
N 输出标识符
组合整数
读字符
Y 输出双分符
输出单分符 N 输出单分符/
注释处理
读字符

编译原理第三章练习题答案

编译原理第三章练习题答案

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

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

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

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来识别词素。

词法分析-编译原理-03-(二)

词法分析-编译原理-03-(二)

5. 5.1 5.2 5.3 5.4 5.5 5.6 5.7 6 6.1 6.2
isalpha(ch) : ch→buf; 下一字符→ch WHILE isalpha(ch) OR isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch; key = isKeyword(buf) IF key >= 0 THEN 返回 key Lookup( buf ) → attr 返回 IDN ':' : 下一字符→ch; IF ch等于'=' THEN 返回 ASG 出错处理
第三章 词法分析 3.1 词法分析的任务
输入源程序，输出单词符号
把构成源程序的字符串转换成语义
上关联的单词符号的序列
单词符号
token
按照最小的语义单位设计， 通常表示为二元组
（单词种别，属性值）
1) 单词符号的表示
单词种别
通常按照语法分析的需要设置． 常用： 各关键字，标识符，常数，各
例3-3 状态图的实现算法
1. 2. 3.1 3. 4. 4.1 4.2 4.3 4.4 4.5 读入当前字符 ch //跳过空格 WHILE ch 是空格 DO 下一字符 → ch CASE ch OF isdigit(ch) : ch→buf; 下一字符→ch WHILE isdigit(ch) DO ch→buf; 下一字符→ch 回送 ch 将缓冲区的数字字符串变成数字→attr 返回 NUM
7 8 9 10 11 12 13 14 15 16 17 18
'+' : 返回 ADD '-' : 返回 SUB '*' : 返回 MUL '/' : 返回 DIV '=' : 返回 EQ '>' : 返回 GT '<' : 返回 LT '(' : 返回 LP ')' : 返回 RP ';' : 返回 SEMI 其它 : 出错处理 END OF CASE

编译原理第3章. 词法分析

编译原理第3章. 词法分析

§3.1 词法分析程序的输入输出
一.输入：字符串表示的源程序 二.输出：单词符号或单词符号表示的源程序 1.语言的单词符号：是指语言中具有独立意义的最 小语法单位。共分五类： 保留字、标识符、常数、运算符、和界符 2.单词符号的内部表示： 二元组（单词种别码，单词自身值） 继续
2019/2/25 3
6
§3.2 词法分析程序的设计 一.输入、预处理
源程序 输入缓冲区
预处理 子程序
扫描缓冲区
词法分析的预处理程序：从源 程序中处理出一串确定长度的 输入字符，并将其装进词法分 析程序的扫描缓冲区。 处理： ①删除注解、空格、回车符、 换行符之类非必要信息。 ②把标识符登录入符号表以及 某些预加工处理等。
2019/2/25 11
2.由正规文法构造状态转换图
(1).右线性文法 => 状态转换图
已知: G=(VN , VT , P , S ) P : A→aB | a A , B∈VN , a∈VT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法: ①初态=S , 增设终态结点F ②对G中形如A→aB 的产生式, 从结点A引一条矢 线到结点B , 并用 a 标记。 ③对G中形如A→a 的产生式, 从结点A引一条矢 线到终态结点F , 并用 a 标记。 ④对G中形如A→ε 的产生式, 从结点A引一条矢 线到终态结点F , 并标记为 ε , 或令A为接受状态。
第三章. 词法分析§3.0 词法分析程序的功能
回忆：词法分析程序的功能：对构成源程序的字符 串从左到右进行扫描和分解，并根据语言的词法 规则识别出一个个具有独立意义的单词符号。 具体： ①设计成单独一遍扫描。
源程序 词 法 分 析 单词符号序列 语 法 分 析

编译原理第3篇

编译原理第3篇

Σ上的“数”的全体。
第23页
编译原理
词法分析
若两个正规式所表示的正规集相同，则认为二者等价。两个 等价的正规式U和V记为
U =V。 例如，b（ab）*=（ba）*b，
（a|b）*=（a*b*）*。 令U、V和W均为正规式，显而易见，下列关系普遍成立： （1）U|V=V|U（交换律）； (2） U|（V | W）=（U | V） | W（结合律） (3) U（VW）=（UV）W（结合律）； (4） U（V | W）＝UV | UW（分配律）
转换图是一张有限方向图。在状态转换图中，结点 代表状态，用圆圈表示。状态之间用箭弧连结。箭 弧上的标记（字符）代表在射出结点（即箭弧始结 点）状态下可能出现的输入字符或字符类。
一张转换图只包含有限个状态（即有限个结点）， 其中有一个被认为是初态，而且实际上至少要有一 个终态（用双圈表示）。一个状态转换图可用于识 别（或接受）一定的字符串。
(1)假定NFA M＝＜S,∑,δ,s0,F＞，对M的状态转换图进行以下 改造：
①引进新的初态结点X和终态结点Y， X，Y∈S, 从X到s0中任意状态结点连一条ε箭弧，从F中
任意状态结点连一条ε箭弧到Y。
②对M的状态转换图进一步施行图3.7所示的替换．其中k是 新引入的状态。重复这种分裂过程直至状态转换图中的每条 箭弧上的标记或为ε，或为∑中的单个字母。将最终得到的 NFA记为M ' ，
即δ: S × ∑*→2的s次方 (4) S0⊆S，是一个非空初态集； (5) F⊆S，是一个终态集（可空）。
第31页
编译原理
词法分析
一个含有m个状态和n个输入字符的NFA可表示成 如下的状态转换图：
该图含有m个状态结点，每个结点可射出若干条箭 弧与别的结点相连接，每条弧用∑*中的一个字（不 一定要不同的字而且可以是空字ε）作标记（称为 输入字），整张图至少含有一个初态结点以及若干 个（可以是0个）终态结点。某些结点既可以是初 态结点也可以是终态结点。

编译原理第三版 第三章 词法分析


超前搜索
例：FORTRAN语言中关键字的识别: DO99K=1,10 识别DO为关键字要搜 DO99K=1.10 索到“，” FORTRAN语言中常数的识别：
5.EQ.M, 5.E08
识别5为常数要搜索到Q
2、状态转换图
大多数程序设计语言中单词符号的词法规则可 以用正规文法描述。如： <标识符>→ 字母|<标识符>字母|<标识符>数字 <整数>→数字|<整数>数字 <运算符>→+|－|×|÷„ <界符>→; |, |( | )|„
#
3.3 正规表达式与有限自动机


目的： 形式化地描述词法规则和词法分析程序 词法分析程序的自动生成 主要内容 正规式与正规集 确定有限自动机 (DFA) 非确定有限自动机(NFA) 正规式与有限自动机的等价性 确定有限自动机的化简
正规文法

多数程序设计语言单词的语法都能用正规文法 (3型文法)描述 正规文法回顾 文法的任一产生式α→β的形式都为
单词符号的种类
(3) 常数 常数的类型一般有整型、实型、布 尔型、字符型等。
(4) 运算符 如 +，-，*，/等，对具体语言个 数是确定的。 (5) 界符 如 , ；（）等，对具体语言个数是 确定的。
单词符号的表示形式
词法分析器所输出的单词符号常常表示成如下的 二元式：<单词种别，单词符号的属性值> 单词种别:由语法分析阶段使用的抽象符号。如： 用整数编码。 最简单的编码方案为一类一码，种别编码可设为： 1,2,3,4,5。 另一种编码方案（如本教材中）： 标识符:列为一种，用一个整数编码表示； 常数:按类型分种编码； 关键字、运算符、界符:采用一字一种编码。

编译原理 第3章

编译原理 6
3.1.3 识别标识符的若干约定和策略
定义标识符的语法规则为 <标识符>→<字母>∣<标识符><字母>∣<标识符><数字> 从语法上来说,标识符的长度似乎可以任意。 然而,考虑实现技术,许多语言都对标识符的最大允许长度作 了限制。
编译原理
7
设计扫描器时,按如下原则行事: 1. 如果一个标识符中的字符个数超过最大允许长度,则把尾部 多出的字符截去; 2. 对于字符个数不超过最大允许长度的标识符,则按“尽可能 长”的策略来识别标识符。
图3.5 状态图
首先，在开始状态R下扫描的第一个符号是0，转到状态 V，表示0是句柄，归约到V。接下来，在状态V扫描1， 转到状态S，此时句柄为V1，归约成S。再往下扫描1，由 状态S转到状态U，表示句柄为S1归约为U。最后，扫描0， 转到状态S，此时句柄为U0，归约为S，
编译原理 27
图3.6（a）列出分析的每一步。形成图3.6（b）所示的语法 树。 自底向上的分析。
读入a1，沿矢线方向到下一状态，在此状态时扫 描a2，……， 直至W中全部字符读完且进入终态F，则W已被接受。
编译原理 19
例：下面的状态图对于串baabba的识别 S→aA|bB，A→bB|aD|a，B→aA|bD|b，D→aD|bD|a|b
a
A a a
a

S b
b
B
a
D b a,b b Z
编译原理
16
E d
d 0
d
d
d 5 d 6
1
.
d
2
E
4
±
. 图3.4文法G<无符号数>的状态图

编译原理-词法分析

单词：标识符，保留字，常数，算符，界符 词法分析阶段的工作所依循的是语言的词法规
则。描述词法规则的有效工具是正规式和有限 自动机。
2
3.1 对词法分析器的要求
3.1.1 词法分析器的功能和输出形式
输入源程序，扫描识别, 输出单词符号 程序语言的单词符号一般分为五种：
关 键 字 ( 保 留 字 或 基 本 字 ) ： 如 begin,end,if,then,else,while,do等
正规式
正规集
1. ba*
Σ上所有以b为首后跟着
任意多个a的字。
2. a(a|b)*
Σ上所有以a为首的字。
3. (a|b)*(aa|bb)(a|b)* Σ上所有含有两
个相继的a或两个相继的b 的字。
28
正规式与正规集: 例3.2
例3.2: 令Σ={A,B,0,1} , 则：
正规式
正规集
1. (A|B)(A|B|0|1)* 体
字母或数字 0 字母 1 其他 2 *
16
状态转换图识别字符串: 例
识别标识符的状态转换图。其中0为初态，2 为终态。
状态2是终态，它意味着到此已经识别出一个 标识符。终态上打个*号，表示多读进了一个 不属于标识符部分的字符，应把它退还给输入 串。如果在状态0时输入字符不为“字母”， 则意味着这个转换图不工作。
24
正规式定义
正规表达式
正规表达式对应的正规集
1. ，
{}，
2. a
{a}
3. 若 r, s
L( r ) , L(s)
则 选择 rs
L( r ) L(s)
连接 r ∙ s
L( r ) ∙ L(s)
闭包 r *

《编译原理》第三章 词法分析器


有限自动机模型
Finite Automata (FA):
一个有限自动机的模型如下所示：
... ... head finite control input tape
输入带被分成一个个的小单元来装输入符号， 其右边是无限延伸的。 有限状态控制器由有限个状态组成，并根据读 入字符将当前状态转换成下一个状态
有限自动机与正规式的等价性证明
• 证明一： 对于∑上的NFA M，我们来构造∑上的正规式r， 使得L(r)=L(M)。 首先，我们将状态图的概念拓广，令每条弧可 用正规式作标记。并在M的转换图上加进两个 结点，一个为X,一个为Y。从X用ε弧连接到Y, 从而形成一个新的NFA,记为M’，它只有一个初 态X和一个终态Y。显然L(M)=L(M’)。即，这 两个NFA是等价的。 现在来逐步消去M’中的所有结点，直至只剩下 X和Y为止。
有限自动机接受的语言
The language accepted by FA
一个FA 能够接受的语言定义如下：
• 对于一个 DFA M, 可接受的语言表示为： L(M)={ x | x∈Σ* and f(s0 , x)∈Z} • 对于一个 NFA M, 其接受的语言为： L(M)={x | x∈Σ*and f(s0, x)∩Z≠Φ} • 两个 FA M and M’ 是等价的当且仅当 L(M) = L(M’)
M
M
a
M
假设对于任意 正规式 r1 and r2, 如果 |r1| < k 而 且 |r2| < k, 那么就于一个NFA M1 and M2 对应 于r1 和 r2. 所以对于任意 RE r, |r| = k, 我们有:
• 这个自动机所接受的语言是所有被3整除 以后余数为2的二0, q1, q2, q3}, {0, 1}, f1, q0 {q3} ) . 其中f1如下所示 :
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2010-12-23
扫描缓冲区的设计： 扫描缓冲区的设计： 两个指针：起点指针,搜索指针 两个指针：起点指针 搜索指针 两个半区： 两个半区：左右半区互补使用
↑
↑
起点指针 搜索指针
7
二.单词符号的识别以及超前搜索
词法分析程序在识别单词时,对有些单词需 要向源程序中多看若干个字符才能被识别,称为 超前搜索。
2010-12-23 3
单词种别码
保留字： ①一字一种：1－begin 2－end 3－if 4－then 保留字： ②全体为一种：0 或者 k 标识符： 标识符： 全体为一种 常数： 常数： ①数据类型：整型、实型、字符型、布尔型 ②全体为一种 运算符： 运算符： ①一符一种 ②全体为一种 界符： ①一符一种 界符： ②全体为一种 返回
6
§3.2 词法分析程序的设计 一.输入、预处理
源程序 输入缓冲区 预处理 子程序 扫描缓冲区
词法分析的预处理程序： 词法分析的预处理程序：从源 程序中处理出一串确定长度的 输入字符， 输入字符，并将其装进词法分 析程序的扫描缓冲区。 析程序的扫描缓冲区。 处理： 处理： 删除注解、空格、回车符、 ①删除注解、空格、回车符、 换行符之类非必要信息。 换行符之类非必要信息。 ②把标识符登录入符号表以及 某些预加工处理等。 某些预加工处理等。
2010-12-23 8
三.状态转换图
状态转换图: 状态转换图: 是由一组矢线连接的有限个结点所组 成的有向图。其作用是识别相应的字符串。 例如: 标识符: I→ l | I l | I d 初态
l
=>①
②
l/d
非l 非d
③
终态
例如: <整数>→数字 | <整数>数字
d
=>①
2010-12-23
④
(1).右线性文法 (1).右线性文法 => 状态转换图
已知: G=(VN , VT , P , S ) P : A→aB | a A , B∈VN , a∈VT* 求: 状态转换图M 设: | VN |=k , 则状态转换图M共有k+1个结点 方法: ①初态=S , 增设终态结点F ②对G中形如A→aB 的产生式, 从结点A引一条矢 线到结点B , 并用 a 标记。 ③对G中形如A→a 的产生式, 从结点A引一条矢 线到终态结点F , 并用 a 标记。 ④对G中形如A→ε 的产生式, 从结点A引一条矢 线到终态结点F , 并标记为 ε , 或令A为接受状态。
已知: 已知 G=(VN , VT , P , S ) P : A→Ba | a A , B∈VN , a∈VT* ∈ ∈ 状态转换图M 求: 状态转换图 则状态转换图M共有 共有k+1个结点 设: | VN |=k , 则状态转换图 共有 个结点 方法:①新增初态=R , S=终态结点 方法 ①新增初态 终态结点 ②对G中形如 中形如A→Ba 的产生式, 从结点B引一条 的产生式 从结点 引一条 中形如 矢线到结点A 矢线到结点 , 并标记为 a 。 中形如A→B 的产生式 从结点 引一条矢 的产生式, 从结点B引一条矢 ③对G中形如 中形如 线到结点A 线到结点 , 并标记为 ε 。 中形如A→a 的产生式 从初态 引一条矢 的产生式, 从初态R引一条矢 ④对G中形如 中形如 线到结点A 线到结点 , 并 标记为 a 。
第三章. 第三章. 词法分析§3.0 词法分析程序的功能
回忆： 回忆：词法分析程序的功能：对构成源程序的字符 串从左到右进行扫描和分解，并根据语言的词法 规则识别出 识别出一个个具有独立意义的单词符号。 识别出 具体： 具体： ①设计成单独一遍扫描。
源程序 词 法 分 析 单词符号序列 语 法 分 析
2010-12-23 14
例如: 文法G[S] :
S → S1 | U1 U → U0 | 0
0 R 0 U 1
1 S
2010-12-23
15
四.状态转换图 => 程序
词法分析程序的设计步骤: 词法分析程序的设计步骤:
1.画出状态转换图(正规文法、正规式) 2.对于状态转换图中的每一个状态构造一段程序代码。 功能为: 从输入串中读一个字符。 功能为:①从输入串中读一个字符。 从输入串中读一个字符 转到匹配弧状态。 ②判断所读字符与该状态哪条弧相匹配 , 转到匹配弧状态。 都不匹配时便失败(不能到达正常出口 不能到达正常出口) ③都不匹配时便失败 不能到达正常出口 。 具体: 对应一个switch 或 if…then…else语 具体: ①不含回路的分支结点 , 对应一个 语 句构成的程序段。 句构成的程序段。(P44--45) 对应一个while 和 if 语句构成的程序 ②含回路的分支结点 , 对应一个 段。(P45) 终态结点,对应一个形如 的语句。 ③终态结点 对应一个形如 return ( code , value )的语句。 的语句 例如: 简单语言的词法分析程序。 例如 P42—46 简单语言的词法分析程序。
2010-12-23 12
例如: 文法G[Z] :
Z → 0A A → 0A | 0B B → 1A | ε 语言为 : L(G)=0 ( 0 | 01 )* 0 求 : 状态转换图。
=> Z
0 0
B
1
ε
F
=> Z
1 0
B
0
A
2010-12-23
A Z
00
13
0
(2).左线性文法 (2).左线性文法 => 状态转换图
2010-12-23 16
int code value; strToken=""; GetChar();GetBC(); if (IsLetter()) { while(IsLetter() || IsDidit() ) { Concat(); GetChar(); } Retrace(); code=Reserve(); if (code==0) { value=InsertId(strToken); return($ID,Value); } else return(code,-); } else if ( Isdigit() ) { while(IsDigit()) { Concat(); GetChar(); } Retrace(); value=InserConst(strToken); return($INT,Value); }20Fra bibliotek0-12-23
18
§3.3 单词符号的两种定义方式
正规文法 以标识符为例:
I→l|Il|Id 或 I→l|lT T→l|d|lT|dT 以标识符为例: l ( l | d )*
19
正规式
2010-12-23
一.正规式与正规集的递归定义: 正规式与正规集的递归定义: 设有字母表∑={a1 , a2 , a3 , …, an } , 定义 : 设有字母表 上的正规式， ①ε，Φ，ai 都是 上的正规式，它们所描述 ， ， 都是∑上的正规式 的正规集分别为｛ ｝， ，｛a ｝，Φ，｛ 的正规集分别为｛ ε｝， ，｛ i｝。 如果e 上的正规式， ②如果 1和e２是∑上的正规式，它们所描述的 上的正规式 正规集分别为L(e 正规集分别为 1) , L(e2)，则 ，
2010-12-23
17
else if(ch=='=') return($ASSIGN,-); else if(ch=='+') return($PLUS,-); else if(ch=='*') { GetChar(); if(ch=='*') return($POWER,-); Retract(); return($STAR,-); } else if(ch==';') return($SEMICOLON,-); else if(ch=='(') return($LPAR,-); else if(ch==')') return($RPAR,-); else if(ch=='{') return($LBRACE,-); else if(ch=='}') return($RBRACE,-); else ProcError();
(e1)也是正规式，相应的正规集 (e1) )=L(e1) 也是正规式， 也是正规式 相应的正规集L( e1 | e2也是正规式，相应的正规集 1|e2)=L(e1) 也是正规式，相应的正规集L(e ∪L(e2) e1e2也是正规式，相应的正规集 1e2)=L(e1) L(e2) 也是正规式，相应的正规集L(e e1*也是正规式，相应的正规集 e1* )=( L(e1) )* 也是正规式，相应的正规集L(
d
非d
⑤
9
利用状态转换图识别(或接受)字符串的过程: 利用状态转换图识别(或接受)字符串的过程:
从初态出发, 按照与符号串余留部分中最左字 符相匹配的原则, 游历状态图, 直至符号串的末端 为止。如果这时恰好到达终态, 则符号串为该文 法的句子；否则不是。例如：识别 num1、1001 num1、
1.关键字的识别: 有些语言中关键字的识别需要超前搜 索。例如:FORTRAN语言中: 1 DO99K=1, 10 2 DO99K=1.10 2.标识符的识别: 以运算符、界符、空格等结束。 3.常数的识别: 需要超前搜索。例如: 5.EQ.M 和 5.E08。 4.运算符和界符的识别: 需要超前搜索。例如: <=
2010-12-23 20
＝｛a 例①：令∑＝｛ , b }， ＝｛ ， 下面是∑上的正规式和相应的正规集 上的正规式和相应的正规集． 下面是 上的正规式和相应的正规集． 正规式 正规集 ba* ∑上b开头任意个 开头任意个a 上 开头任意个 a(a|b)* ∑上所有以 为首的字 上所有以a为首的字 上所有以 a +b + ∑上ambn , m,n≥1的字 上 的字 ＝｛A， ， 例②：令∑＝｛ ，B，０，1 }，则 ＝｛ ， 正规式 正规集 ∑上的标识符的全体 （A|B)(A|B|0|1)* 上的标识符的全体 ∑上数的全体 （0|1)(0|1)* 上数的全体 结论：正规式是正规语言的另一种表示方法． 结论：正规式是正规语言的另一种表示方法． 定义：若正规式R 所描述的正规集相同， 定义：若正规式 1和R2所描述的正规集相同，则称正 等价，并记为： 规式R1和R2等价，并记为： R1＝R2 。 规式 (a|b)*=(a* b*)* 。 例如： 例如：b(ab)*=(ba)*b