当前位置：文档之家 › 《编译原理》第3章 词法分析与有穷自动机

《编译原理》第3章 词法分析与有穷自动机

  • 格式：ppt
  • 大小：2.23 MB
  • 文档页数：120

下载文档原格式

  / 120

合集下载

《编译原理》第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}

编译原理第三章

编译原理第三章

例3.4 Z→ A→ B→
有正规文法G： 0A 0A | 0B 1A | ε
例3.5 A→ B→ C→
有正规文法G： aB | bB aC | a | b aB
例3.6 Z→ U→ V→
有正规文法G： Z=0(0|01)*0 U0 | V1 A=(a|b)(aa)*(a|b) Z1 | 1 Z=(10|01)(10|01)* Z0 | 0
A
B
r2 ε
A C
A
B
ε
B
r1
④R为复合正规式？
例3.12 3.13 P41
教学进度
3.4.4 NFA确定化为DFA
方法（子集法） 1、改造M为M’： ①引进新的初态结点X、终态结点Y； ②对M的状态转换图实施分裂（替换）
计算机科学与工程系
2、将M’进一步变换为DFA :
①状态子集T的闭包_CLOSURE(T) ②定义状态集Ta = _CLOSURE(J) ③从DFA的初态_CLOSURE({X})开始计算状态转换矩阵；直到 不再产生新的状态子集为止。
第三章
• • • • • •
词法分析与有穷自动机
计算机科学与工程系
词法分析器的功能与输出 单词符号的两种定义方式 正规表达式与有穷自动机 正规文法与有穷自动机 词法分析器的设计 词法分析程序自动构造工具LEX简介
教学进度
3.1 词法分析器的功能

计算机科学与工程系
词法分析：对字符串表示的源程序进行从左到右的扫描和 分解，根据语言的词法规则识别出一个个具有独立意义的 单词符号。
教学进度
3.3 单词符号的两种定义方式
单词符号结构的描述方法：
计算机科学与工程系
正规文法（３型文法）(regular grammar)

西安理工大学《编译原理》编译原理作业集－第三章－修订版

西安理工大学《编译原理》编译原理作业集－第三章－修订版

第三章词法分析本章要点１．词法分析器设计，２．正规表达式与有限自动机，３．词法分析器自动生成。

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

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

6. 有限状态自动机可用五元组（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所能接受的语言可以用正则表达式表示为。

第三章 词法分析和有穷自动机

第三章 词法分析和有穷自动机

ε
ε
2
ε
6 b
ε
f
3.4.5 DFA的最小化（化简）
• 最少状态DFA 对于一个DFA M，存在一个最少状态DFA M’， 使得L(M’)=L(M)。 (a)没有多余状态 (b)没有两个状态是互相等价的 结论： 一个NFA 对应的DFA不惟一 但它对应的最小化DFA不计同构是惟一的
• 多余状态的例子 a
例
正规式 φ
ε
a a|b ab (a|b)(a|b) a* ba* (a|b)*
正规集 φ {ε } {a} L(a|b)=L(a) ∪ L(b)={a,b} L(ab)=L(a)L(b)={ab} {aa,ab,ba,bb} { ε ,a,aa,aaa,…} {b,ba,baa,baaa,…} {所有由a和b组成的字}
• 例 DFA M=({0,1,2,3},{a,b}, f ,0,{3}) 其中 f 为： f (0,a)=1 f (0,b)=2 f (1,a)=3 f (1,b)=2 f (2,a)=1 f (2,b)=3 f (3,b)=3 f (3,a)=3
3.4.1 确定有穷自动机(DFA) • DFA的表示方法 两种：矩阵和图形的方式 矩阵称为状态转换矩阵 图形称为状态转换图
• NFA M所接受字符串的集合称为NFA M所能 识别的语言，记为L(M)。 • NFA的确定化 DFA是NFA的特例
NFA M存在与之等价的DFA M’,L(M)=L(M’) 与某一NFA等价的DFA不惟一 正规式 NFA 正规文法 DFA
3.4.4 NFA 确定化
• 状态集合I的空闭包：ε -closure(I) 它是一个状态集合，包含 ： ♠ I中任何状态q ♠ I中任何状态q经任意条空弧到达的任何状态 • 状态集合I的a弧转换：Ia 定义一个状态集J，J是I中所有状态经一条a 弧到达的状态的全体 Ia＝ε -closure(J)

编译原理分知识点习题 词法分析与有穷自动机

编译原理分知识点习题 词法分析与有穷自动机

1. 将图1所示的有穷自动机转换成与其等价的正规文法，其中4、5为终止状态。

解答：本题考查有穷自动机到正规文法的转换方法。

这类题只需要书中所介绍的方法进行即可得到正规文法，本题有穷自动机对应的正规文法G[S]为：A →aB|bB|cCB →aB|bD|aE|cC|b|aC →bB|cC|cE|cD →bD|bE →aE|a图1有穷自动机的状态转换图2.给定如图2所示的有穷自动机，试用正规表达式给出它能接受的语言集合。

图2有穷自动机解：本题考查正规表达式与有穷自动机的等价性。

对于一个在输入字母表∑上的FAM ，一定可以在字母表∑上构造一个正规表达式e ，使得L(e)=L(M) .根据状态转换图，从开始状态出发，可以有任意个（包括0个）b 作为句子的开始部分；从0状态出发，每输入一个a ，不许输入两个b 才能到达终止状态后，还可以通过输入a 回到状态1，或输入b 回到状态0，然后进入递归过程，再输入相同的符号串，所以，该有穷自动机描述的语言为：startab(b*(aa*b)*b)*3. 构造下述正规表达式的DFA。

Xy*|yx*y|xyx解：本题考查由正规表达式构造有穷自动机的方法，本题可按照由正规表达式构造等价的NFA，NFA确定化，DFA最小化3步进行求解。

（1）根据题中所给的正规表达式得到相应的DFA如图3所示。

图3正规表达式Xy*|yx*y|xyx的DFA。

（2）依据该NFA采用子集法构造确定DFA其过程如表1（已换名）所示。

以所有包含NFA的终止状态Z的DFA状态作为终止状态，得到DFA相应的状态转换图如图4所示图4 DFA的状态转换图（3）对DFA进行最小化，过程如下：已知K={0,1,2,3,4,5,6}。

首先将K分成两个子集K1={0,2,3} （非终态集）K2={1,3,4,6} （终态集）在状态集合K1={0,2,3}中，因为{0}x={1}⊂K2{2,4}x={4}⊂K1所以状态0与状态2，4不等价，故K1可分割为K11={0} K12={2,4}在状态集合K12={2，4}中，因为有{2，4}x={4} {2,4}y={5}⊂K2所以，状态2和状态4等价。

第三章词法分析及有穷自动机

第三章词法分析及有穷自动机

U
④ 以识别符号为终止状态。
例：设有正规文法G[Z]： Z∷= U0|V1 U∷=Z1|1 V∷=Z0|0
（描述的语言为L(G)={01,10}＋） 则状态转换图如下：
新增加开 始状态S
1 S
0
U 1
0
V
0 Z
1
以开始符号Z 作终态
例：标识符的转换图：
字 母 或 数 字
字 母
0
1
非 字 母 和 非 数 字 2
例：一种一类的单词输出形式 设保留字、标识符、常数、运算符、分界符
的种别码分别为1，2，3，4，5；将if a>1 then b:=10表示为一种一类的单词输出形式。
if a>1 then b:=10
(字符串表示 的源程序)
＝>词法分析 器=>
(1, ’ if ’ )
(2,’ a ’ ) , (4,’ >’) (3,’1’ 的二进 制数)
2>根据状态转换图写词法分析程序 为每一个状态结点写一个过程或函数： 对N1结点： Procedure PN1
Begin
Ch:=getchar( );
If ch=”e” then PN5 Else if ch=”d” then PN2
Else if ch=” ·” then PN3 Else error
从开始状态出发到某一终止状态结点为止，所经过的路径 上的符号串，称能为该状态转换图所接收（识别）的符号 串。
如：标识符x26为上述转换图识别，识别路径为
x
2
6
0
1
1
1
非 字 母 和 非 数 字 2
2) 右线性正规文法构造状态转换图
① 右线性正规文法U ∷= a|aV构造状态转换图的步骤： ② 增加一个终止状态结点z（假定文法的词汇表中不含

编译原理第三章_有穷自动机

5
例 过河问题 分析（续）
初始状态：MWGC-φ；终止状态：φ-MWGC。 g
MWGC-φ
WC-MG
问题：
6
例 过河问题 状态转换图
起始 g
MWGC-φ g
g φ-MWGC
g
7
WC-MG
m
m MWC-G
w
w
c
C-MWG
c W-MGC
g
g
MGC-W c
MG-WC
w
m
c G-MWC
m
gg MWG-C
+dd. ddd;
输入符号串
数字 数字
SB
.
数字
+
A
H
-.
数字
.G
接收：若扫描完输入串， 且在一个终止状态上结 束。
数字 阻塞：若扫描结束但未 停止在终止状态上；或 者为能扫描完输入串 （如遇不合法符号）。
不完全描述：某些状态 对于某些输入符号不存 在转换。
练习：+34.567 .123 3.4.5
w
有穷自动机（FA）
数字系统：可以从一个状态移动到另一个状态；每次 状态转换，都上由当前状态及一组输入符号确定的；可以 输出某些离散的值集。
FA：一个状态集合；状态间的转换规则；通过读头来 扫描的一个输入符号串。
读头：从左到右扫描符号串。移动（扫描）是由状态 转换规则来决定的。
8
读头
一个FA的例子
(3)运行： 串f(，Q,且t1tt21)∈= Σf(，f(Qt1,t2t1∈), Σt2*)，其中Q∈K， t1t2为输入字符
17
例３
题：试证abba可为例1的DFA M所识别（所接受）。

编译原理 第三章 有限自动机与词法分析器

第三章有限自动机与词法分析器3.1词法分析3.1.1词法分析器的功能在第二章里我们已介绍了词法分析的基本问题。

计算机存储是二进制式的，因此，任何一种程序和数据在计算机内部均被表示为二进制表示。

实际上，当程序员每按键盘中的一个键时，自动往计算机里输入一个相应的八位二进制码，称这种码为ASCII码。

当程序员敲完程序时将它保存到自己事先起好名的文件中，因此，程序在计算机文件中的表示是ASCII码序列(末尾有文件结束码)。

编译器总是要用某种程序设计语言来写，而任何一种语言的程序其操作对象必须是该语言所规定的数据。

编译器的操作对象是程序中的各种语法单位，如<常量声明>,<类型声明>,<变量声明>,<过程声明>,<表达式>,<语句>,<变量>等等，因此，必须把它们都表示成某种数据结构形式，而它们的最小单位是所谓的单词，故首当其充的是要把每个单词转换成一种数据形式，通常称它们为TOKEN。

词法分析器的任务就是，从源程序的ASC码(用高级语言的术语来说是字符串)序列逐个地拼出单词，并将构造相应TOKEN数据表示。

词法分析器可有两种，一种是它作为语法分析的一个子程序，一种是它作为编译器的独立一遍。

前一种情形，词法分析器不断地被语法分析器所调用，每调用一次词法分析器将从源程序的字符序列拼出一个单词，并将其TOKEN值返回给语法分析器。

后一种情形则不同，即不是被别的部分不断地调用，而是完成编译器的独立一遍任务，具体说将整个源程序的字符序列转换成TOKEN序列，并将其交给语法/语义分析器。

实际的编译器一般都采用子程序方式，但是为了独立地介绍词法分析、语法分析和语义分析的概念和技术，我们将词法分析部分分离出来即作为独立一遍的词法处理器来介绍。

从实际的角度来说，这种方法有以下缺点:一是因为它要生成TOKEN列，自然多占用空间；二是因为要保存所有的TOKEN，需要耗费更多的时间。

编译原理 第3章 词法分析与有穷自动机(第5-8讲)


它所对应的状态表如图：
状态 0 1 2 3 a 1 3 1 3 后继 状态 b 2 2 3 3
输入字符 接受 否 否 否 是
式的转化
22
第3章 词法分析与有穷自动机
■DFA所识别的语言
给定DFA M，对于字符c1,c2,…,cn,当以下条件成立时， 称M接受由c1,c2,…,cn组成的字符串c1c2…cn： 存在状态序列s0,s1,s2,…,sn,使得s1=f(S,c1), s2=f(s1,c2),…,sn=f(sn-1,cn)，且sn∈Z。 由DFA M接受的语言L(M)是所有M接受的字符串组成的集 合。
25
第3章 词法分析与有穷自动机
判断下图是DFA还是NFA的状态转换图，并 写出其他2种表示形式
26
第3章 词法分析与有穷自动机
■由正规表达式R构造NFA
1.基本正规表达式 (a)对于正规式φ,所构造NFA: (b)对于正规式ε,所构造NFA: (c)对于正规式a,a∈Σ,则 NFA:
x ε y
练习：若S=a|bb，则L((a|bb)*)=？
5
第3章 词法分析与有穷自动机
■正规式中运算的优先级
括号优先，* 次之，•（连接）再次之，| 最后 例：a|bc* ≌ a|(b(c*)) ab|c*d ≌ (ab)|((c*)d)
■ 正规式与正规集举例
L(a|bc*)=L(a)∪L(bc*) 思考：L(ab|c*d)=？ =L(a)∪L(b)L(c*) =L(a)∪L(b)(L(c))* ={a}∪{b}{ε,c,cc,ccc……} ={a,b,bc,bcc,bccc,……}
17
第3章 词法分析与有穷自动机
■有穷自动机的状态转移图表示方法

第3章词法分析与有穷自动机20090319


单词的种类 （1）关键字：if、for、while （2）标识符： （3） 常数： （4） 运算符：+、-、* （5）分界符：, 、;、(、)
编译原理
2013年8月27日
词法分析程序的输出形式-----二元式
单词类别 单词的属性值
单词类别可以用整数编码表示:一类一种或一字一种
单词类别 关键字 标识符 常数 运算符 分界符
编译原理
2013年8月27日
【例3．9】将描述标识符的正规式R=l(l∣d)*转换 成相应的正规文法。
• 令S为文法的开始符号， 根据规则（2） 有 • S→l(l∣d)* • 根据规则（3）变换为： • S→lA • A→(l∣d)* • 根据规则（4）变换为： • S→lA • A→(l∣d)A∣ε •
有穷自动机的作用
实质上是提供了一种逻辑的探测方式,去探测一 些输入串是否属于某种语言,即: 它可以作为一种 语法检查器。
编译原理
2013年8月27日
3.4.1
确定的有穷自动机（DFA）
M=(Σ, Q, f,S, Z)
Σ：有穷字母表，它的每个元素称为一个输入符号 Q：有穷状态集，它的每个元素称为一个状态 S∈K，是唯一的初态
运算符的优先级： 先*, 后 • , 最后 | • 在正规式中可以省略.
正规式相等 这两个正规式表示的语言相等
编译原理
2013年8月27日
正规式举例
• 例：设有字母表 ∑={a,b}，根据正规式与正规集的定义，有以 下的正规式和正规集 正规式 正规集 a {a} a∣b {a,b} ab {ab} ( a∣b)( a∣b) {aa,ab,ba,bb} a* {ε,a,aa,aaa,…,任意个a的串} （a∣b）* {ε，a,b,aa,ab,ba,bb,…所有a,b组成的串} (a︱b) *(aa︱bb) (a︱b) * ∑*上所有含两个连续的a 或两 个连续的b组成的串
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

教学内容
3.1 3.2 3.3 3.4 3.5 3.6 词法分析的任务 词法分析程序的输出形式 词法分析程序的设计与实现 正规式与有穷自动机 词法分析程序的自动生成工具LEX PL/0编译程序的词法分析
3.1
词法分析的任务 （1）分析和识别单词及属性， 包括识别语言的关键字、标识符、常数、
运算符等；
3
其他字符 非=
4
= 出错
5
其他字符
返回S
出口
双界符
（3）将状态图转换成流程图，如图3.5
写出词法分析程序
a
0 1
a
2 1 b
其他
3 2
如：aba# 如：bba#
﹣c=nextchar(); ﹣if (c==‗a‘) ﹣{ ﹣ c=nextchar(); ﹣ while(c==‗a‘ 或者 c==‗b‘) ﹣ c=nextchar(); ﹣ 接受； ﹣} ﹣else 出错或其他情况；
字母表Σ含有n个 输入字符，那末 任何一个状态结 点最多有n条弧 射出，而且每条 弧以一个不同的 输入字符标记。
0 1 2 3
1
a
b b
2
a
b
3
a,b
换言之：若存在一条初始状态到某一终止状态的路径，且 这条路径上所有弧的标记符号连接成符号串α，则称α为 DFA M（接受）识别。 若M的初态结点同时为终态，或者存在一条从初态到某个终态 结点的ε通路，则ε为M所识别。 DFA M所接受的语言为：L(M)={α |f(S, α )=Sn, Sn ∈Z} DFA M所能接受的符号串的全体记为L(M)
0型文法（图灵机）
1型文法（不确定 的界限自动机） 2型文法（不确定 的下推自动机）
3型文法（有限 自动机）
1.确定的有穷自动机（DFA） M=(Σ, Q, f,S, Z)
Σ：有穷字母表，它的每个元素称为一个输入符号
Q：有穷集，它的每个元素称为一个状态
S∈K，是唯一的初态 Z K是一个终态集，终态也称可接受状态或结束状态 f是转换函数，是Q×Σ→Q上的单值映射： f（q1，a）=q2
M=(Σ, Q, f,S, Z) 例如: M:（{0,1,2,3},{a,b},f，0，{3}） f（0，a）=1 f（0，b）=2 f（1，a）=3 f（1，b）=2 f（2，a）=1 f（2，b）=3 f（3，a）=3 f（3，b）=3
输入 字符
状态
所谓确定的状 态机，其确定 性表现在状态 转移函数是单 值函数！
3.4.3 有穷自动机
读字符
状态图的形式化描述
查保留字表
字母、数字
S
字母
1
非字母数字
标识符
数字
数字 2 非数字
无符号整数
单界符
+ * ， （ ） < 其他
3
其他字符 非=
4
= 出错
5
其他字符
返回S
出口
双界符
• 有穷自动机是一种数学模型，具有离散的输入与输出， 系统可处于有穷状态中的任何一个 • 它能准确地识别正规集，即识别正规文法所定义的语言 和正规式所表示的集合 • 引入有穷自动机这个理论，正是为词法分析程序的自动 构造寻找特殊的方法和工具 有穷自动机分为两类： 确定的有穷自动机（DFA） (Deterministic Finite Automata) 不确定的有穷自动机（NFA） (Nondeterministic Finite Automata)
<
3
其他字符 非=
出口
双字符分界符
S
4
=
5
其他字符
出口
合并 ① 将初始状态合并为一个唯一的初态； ② 化简调整状态冲突并对冲突状态重新编号； ③ 如有必要，增加出错状态。
合并后的状态图
查保留字表 读字符
字母、数字
S
字母
1
非字母数字
标识符
数字
数字 2 非数字
无符号整数
单界符
+ * ， （ ） < 其他
3.4.2 正规文法与正规式
1.正规文法正规式 步骤1 将每条产生式改写为正规式； 步骤2 用代入法解正规式方程组，最后只剩下一个 开始符号定义的正规式，其中不含非终结符。
文法产生式
规则1 A→xB,B→y
正规式
A=xy
规则2
规则3
A→xA|y
A→x,A→y
A=x*y
A=x|y
文法产生式 规则1 规则2 A→xB,B→y A→xA|y
实现方案：基本上有两种
1.词法分析单独作为一遍
第一遍 S.P.(字符串) 词法分析 单词串 S.P.(符号串) 第二遍 语法分析
2.词) 词法分 析程序 单词
优点: 结构清晰、各遍功能单一 缺点：效率低
语法分 析程序
3.2
词法分析程序的输出形式
单词的种类 （1）关键字：if、for、while （2）标识符： （3） 常数： （4） 运算符：+、-、* （5）分界符：, 、;、(、)
词法规则
状态图
词法分析程序
（1）根据词法规则写出正规文法； （2）将正规文法转换成状态图； （3）将状态图转换成流程图。
【例3.2】假设某种语言的单词符号的子集有：
标识符 关键字(标识符的子集）
常数
运算符
分界符
+
,
*
;
＝ <
<=
试构造此语言子集的词法分析程序。
（1）根据词法规则写出正规文法
<标识符>→字母 | <标识符>字母 | <标识符>数字） <无符号整数>→数字 | <无符号整数>数字 <单界符>→+ | * |< |, | ; <双界符>→<=
【例3.6】求正规式(a|b)(a|b|0|1)*对应的正规文法 S→(a|b)Ａ
S→(a|b)(a|b|0|1)*
A→(a|b|0|1)*
A→aA|bA|0A|1A|ε
G[S]： S→aA|bA A→aA|bA|0A|1A|ε
下面是用正规式表示的变量声明： ( int | float ) id (, id )* 请改用上下文无关文法表示，也就是写一个上下文无关 文法，它和该正规式等价。 ( int | float ) id (, id )* D→( int | float )L L→ id (, id )* D→ int L | float L L→ L, id | id G[D]： D→ int L | float L L→ L, id | id
词法分析程序的输出形式-----二元式
单词类别 单词的属性值
单词类别可以用整数编码表示:一类一种或一字一种
单词类别 关键字 标识符 常数 运算符 分界符 编码
1 2 3 4 5
3.3
词法分析程序的设计与实现
词法规则
状态图
词法分析程序
3.3.1 正规文法及其状态图
1.状态图：为识别单词而专门设计的有向图， 是设计词法分析程序的一种好途径。 结点代表状态，用圆圈表示，为非终结符 有向弧表示状态转移 弧上的标记表示在射出弧的结点状态下可能出现的输入字 符，为终结符 1 S U 一张状态图包含有穷个状 态，只能有一个初态，至 少要有一个终态（用双圈 表示） 0 V 1
0
1 Z
0
【例3.1】某语言的标识符可使用以下正规文法G[S]来定义：
S→lA A→ε|lA|dA l∈{a,b,…z}， d∈{1,2,…,9} 试构造此文法的状态图。
l|d
l S A
状态图可识别单词
2.由正规文法构造状态图
（1）对于右线性文法
步骤1 增加结点Z为终态； 步骤2 将每个非终结符号设置为一个对应的状态； 步骤3 对于A→a，引一条从A到Z的弧，弧上标记为a； 而 对于A→aB，引一条从A到B的弧，弧上标记为a。 l|d S→lA S l A ε Z
状态转移函数f可用一矩阵来表示： a 1 3 1 3 b 2 2 3 3
0 1 2 3
字母表Σ含有n个 输入字符，那末 任何一个状态结 点最多有n条弧 射出，而且每条 弧以一个不同的 输入字符标记。
一个DFA也可以用一状态转换图表示：
输入 字符 状态
DFA的状态图表示： a 1 3 1 3 b 2 2 3 3 a 0
A→ε|lA|dA
l|d
A
l
Z
（2）对于左线性文法
步骤1 增加结点S为初态； 步骤2 将每个非终结符号设置为一个对应的状态； 步骤3 对于A→a，引一条从S到A的弧，弧上标记为a；而对 于A→Ba，引一条从B到A的弧，弧上标记为a。
A→l|Al|Ad
l|d
S→lA A→ε|lA|dA
S l
A
3.3.2 词法分析程序的实现
正规式 A=xy A=x*y
规则3
【例3.5】G[S]: S→aA|a A→dA|d S=aA|a A= d*d
A→x,A→y
A=x|y
代入:S=ad*d|a＝ ad*
2.正规式正规文法 步骤1 构造 S→r 步骤2 不断利用表3.4的规则做变换,直到每个产生式 最多含有一个终结符为止 文法产生式 规则1 规则2 规则3 A→xB,B→y A→xA|y A→x,A→y 正规式 A=xy A=x*y A=x|y
<标识符>→字母 | <标识符>字母 | <标识符>数字） <无符号整数>→数字 | <无符号整数>数字 <单界符>→+ | * |< |, | ; <双界符>→<=