当前位置：文档之家 › 32 正规文法和状态转换图

32 正规文法和状态转换图

  • 格式：ppt
  • 大小：190.00 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

《编译原理》考试试题及答案

《编译原理》考试试题及答案

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

（√）6.2型文法一定是3型文法。

（ x ）7.一个句型一定句子。

( X )8.算符优先分析法每次都是对句柄进行归约。

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。

( x )11.一个优先表一定存在相应的优先函数。

( x )12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )13.递归下降分析法是一种自下而上分析法。

( )14.并不是每个文法都能改写成LL(1)文法。

( )15.每个基本块只有一个入口和一个出口。

( )16.一个LL(1)文法一定是无二义的。

( )17.逆波兰法表示的表达试亦称前缀式。

( )18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。

( )19.正规文法产生的语言都可以用上下文无关文法来描述。

( )20.一个优先表一定存在相应的优先函数。

( )21.3型文法一定是2型文法。

( )22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

编译原理词法分析及词法分析程序

编译原理词法分析及词法分析程序
∴M能识别出L(G)中的全部句子。
状态图=>右线性文法
文法G[0] 0->a1
d 0
S->aA A->dA A->b
a c
1 2
b
d
3
1->d1 1->b
0->c
0->c2 2->d
S->c
S->cB，2有出弧 B->d
左线性文法=>状态转换图
设G=(VN,VT,P,S)是一左线性文法,令|VN|=K， 1) 则所要构造的状态转换图共有K+1个状态. 2) VN中的每个符号分别表示K个状态 2.1) G的开始符S为终止状态 3) 起始状态,用R(VN)标记
识别符号串与归约
S





从初态R到下一状态A对应Ba，即终结 符a归约成非终结符B; U 从状态B转换到状态A对应ABa,即将 Ba归约为A; 状态A转换到状态S(终态)对应S Aa,即 U 将Aa归约为开始符S. 归约成功,恰好进入终态,即状态转换图识 U 别了(或接受)该符号串. 识别00011的例子的归约过程
f是转换函数，是在K×Σ →K上的映像，即：如果f（ki，a）=kj， （ki，kj∈K）意味着，当前状态为ki，输入字符为a时，将转换 为下一个状态kj，我们把kj称作ki的一个后继状态；
1.确定的有限自动机
通常把这五要素组成的五元式M=(K,∑,f, S0,Z)称为确定的 有限自动机(DFA)，它是相应的状态转化图的一种形式描 述，或者说，是状态转换矩阵的另一种表示。 在状态转换的每一步，据DFA当前所处状态及扫视的输入 字符，能唯一确定下一状态。

例：文法G=({S,U},{0,1},{SS1 |U1,

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

编译原理第三章_有穷自动机
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所识别（所接受）。

编译原理试题库

编译原理试题库

一填空题1．编译程序首先要识别出源程序中每个，然后再分析每个并翻译其意义。

单词，句子2．编译器常用的语法分析方法有和两种。

自底向上，自顶向下2．通常把编译过程分为分析与综合两大阶段。

词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。

前端，后端4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即方案和分配方案。

静态存储分配，动态存储5．对编译程序而言，输入数据是，输出结果是。

源程序，目标程序6．文法G包括四个组成部分：一组终结符号，一组非终结符号，一组，以及一个开始符号。

产生式7．文法按产生式的形式分为四种类型，它们是：0型文法，又称短语文法；1型文法，又称上下文有关文法；2型文法，又称；3型文法，又称。

上下文无关文法，正规文法8．最右推导称为，由规范推导产生的句型称为规范句型。

规范推导9．设G是一个文法，S是它的开始符号，如果S=>*α，则称α是一个。

仅由终结符号组成的句型是一个。

句型，句子10 对于一个文法G而言，如果L(G)中存在某个句子对应两棵不同，那么该文法就称为是二义的。

语法树11．通常程序设计语言的单词符号分为五种：基本字、、常数、算符、界限符。

标识符12．在自底向上分析法中，LR分析法把“可归约串”定义为。

句柄13．编译中常用的中间代码形式有逆波兰式、三元式、和四元式等。

树代码14．对中间代码优化按涉及的范围分为，和全局优化。

局部优化，循环优化15．局部优化主要包括、利用公共子表达式和删除无用赋值等内容。

合并已知量16．为了构造不带回溯的递归下降分析程序，我们通常要消除和提取左递归，左公共因子17.计算机执行用高级语言编写的程序主要有两种途径：和。

解释执行，编译执行18.扫描器是词法分析，它接收输入的，对源程序进行词法分析并识别出一个个，供语法分析器使用。

源程序，单词符号19.自下而上分析法采用，，和等四种操作。

编译原理 3.2正规文法和状态转换图

编译原理 3.2正规文法和状态转换图

2020/6/18
第30页/共24页
一个简单的词法分析器示例
1 C语言子集的单词符号表示 2 C语言子集对应的状态转换图的设计 3 状态转换图的实现
2020/6/18
第31页/共24页
1 C语言子集的单词符号表示
大多数程序语言的单词符号都可用 状态转换图予以识别。下面构造一个C 语言子集的简单词法分析器，该C语言 子集的所有单词符号及其种别编码和内 码值如下表所示。
开始符号S作为初始状态； S 设一符号F不属于V作为终止状态； F
2020/6/18
第7页/共24页
形如A→aB的规则：从结点A引一条矢线到结
点B，并用符号a标记这条矢线；
a
A
B
形如A→a的规则：从结点A引一条矢线到终态
结点F，并用符号a标记这条矢线；
a
A
F
2020/6/18
第8页/共24页
则有：S=> a1A1=> a1 a2A2=> a1 a2 a3A3=> … => a1 a2 a3 … an-1An-1=> a1a2a3…an
事实上，在利用状态转换图M对符号串ω进行识别的 过程中，M中的每一次状态转换都模拟了G中的一步 直接推导，所以，上述方法是一个自顶向下的分析
方法。
2020/6/18
a
R
A
2020/6/18
第16页/共24页
例如：G[Z]：Z→U0∣V1 U →Z1∣1 V →Z0∣0
1
2020/6/18
1
U
初态 R
0
V
0
Z
1
0
第17页/共24页
二、状态图的使用——识别句子

词法分析程序的设计与实现

词法分析程序的设计与实现

词法分析程序的设计与实现方法1：采用C作为实现语言，手工编制一．文法及状态转换图1．语言说明：C语言有以下记号及单词：（1）标识符：以字母开头的、后跟字母或数字组成的符号串。

（2）关键字：标识符集合的子集，该语言定义的关键字有32个，即auto,break,case,char,const,continue,default,do,double,else,enum, extern,float,for,goto,if,int,long,register,return,short,signed,static, sizeof,struct,switch，typedef ,union,unsigned ,void, volatile和while。

（3）无符号数：即常数。

（4）关系运算符：<,<=,==,>,>=,！=。

（5）逻辑运算符：&&、||、！。

（6）赋值号：=。

（7）标点符号：+、++、-、--、*、：、；、（、）、？、/、%、#、&、|、“”、，、.、{}、[]、_、^等（8）注释标记：以“/*”开始，以“*/”结束。

（9）单词符号间的分隔符：空格。

2．记号的正规文法：仅给出各种单词符号的文法产生式（1）标识符的文法id->letter ridrid->ε|letter rid|digit rid（2）无符号整数的文法digits->digit remainderremainder->ε|digit remainder（3）无符号数的文法num->digit num1num1->digit num1|. num2|E num4|εnum2->digit num3num3->digit num3|E num4|εnum4->+digits|-digits|digit num5digits->digit num5num5->digit num5|ε（4）关系运算符的文法relop-> <|<=|==|>|>=|!=（5）赋值号的文法assign_op->=（6）标点符号的文法special_symbol->+|-|*|%|#|^|(|)|{|}|[|]|:|;|”|?|/|,|.& （7）逻辑运算符的文法logic->&&| || | !（8）注释头符号的文法note->/starstar->*3.状态转换图其中，状态0是初始状态，若此时读入的符号是字母，则转换到状态1，进入标识符识别过程；如果读入的是数字，则转换到状态2，进入无符号数识别过程；……；若读入的符号是/，转换到状态11，再读入下一个符号，如果读入的符号是*，则转换到状态12，进入注释处理状态；如果在状态0读入的符号不是语言所定义的单词符号的开始字符，则转换到状态13，进入错误处理状态。

第三章名词解释

第三章名词解释1.最小化（minimize）指DFA M状态数的最小化，是指构造一个等价的DFA M'，而后者有最小的状态。

2.标示符（IDentifier）是指用来标识某个实体的一个符号。

在不同的应用环境下有不同的含义。

3.正规表达式（regular expression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的工具。

4.正规式（Normal form）正规式也称正则表达式，也是表示正规集的数学工具。

5.正规集（Normal set）如果把每类单词视作一种语言，那么每一类单词的全体单词组成了相应的正规集。

6. 有限状态自动机（finite state automaton）有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。

有限状态自动机可以表示为一个有向图。

有限状态自动机是自动机理论的研究对象。

7.词法分析器（Lexical analyzer）词法分析是指将我们编写的文本代码流解析为一个一个的记号，分析得到的记号以供后续语法分析使用。

8.确定的有限自动机（DFA: Deterministic Finite Automata）自动机的每个状态都有对字母表中所有符号的转移。

9.五元式（Five element type）由五个要素组成的式子K：由有限个状态组成的集合∑：由有限个输入字符组成的字母表f：从K到∑的单值映射，q),(，指明当前态为p，输入字符a，下一个状态为qf=pas：一个属于K的特定状态，称之为初始状态Z：若干个属于K的特定状态，它们组成的集合称之为终态集，记为Z。

10.非确定的有限自动机(NFA：Non deterministic finite automaton)自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。

自动机接受一个字，如果存在至少一个从q0 到 F 中标记(label)著这个输入字的一个状态的路径。

编译原理 第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<无符号数>的状态图

编译原理 3.3有限自动机

且定义 f（ {Sk1，Sk2，…，Skm}，w）= U f（Ski，w） i 1
则有 f（S，aw）= f（ f （S，a），w ）
m
=
U
i 1
f（Ski，w）
2020/6/18
第13页/共42页
讨论问题3：
NFA M所能识别的语言：对于Σ*中的符号串x，
若集合 f（S0，x）中含有属于终态集Z中的状态 （即 至少存在一条从S0到某一终态的通路，把此通路中所 有矢线上的标记连接起来就是符号串x），我们就说x 为M所接受，所有这样的x所组成的集合称为NFA M 的接受集，记作 L（M）。
f’(q0,a) =q0 f’(q0,b) =q1
{q0, q1 , q2}
第二步
2020/6/18
{q0, q1 , q2}
对于c，T=f(q0,c)= f({S0, S1, S2,S3},ca) ，
ε_closure(T) = ε_closure({S2})= {S2,
S3} = q2
S0 ε
f’(bq0,c) =q2
且{R1,R2,…,Rj}∩Z≠Ø}
2020/6/18
第21页/共42页
例：NFA M =({S0,S1}，{a，b}，f，S0，{S1} )
a
b
a,b
S0
S1
b
a
b
S0 {S0,S1} {S1}
S1
Ø
{S0,S1}
DFA M ′ =(K′，{a，b}，,f ′, S0 ′, Z′)
2020/6/18
第9页/共42页
正规文法 L（G）
必定存在 反之亦然
DFA M
=
L（M）
2020/6/18

复习：程序语言的语法描述

编译原理
else if (ch =‘*’)
begin
GetChar();
if (ch =‘*’) return ($POWER, -);
Retract(); return ($STAR, -);
end
else if (ch =‘;’) return ($SEMICOLON, -);
else if (ch =‘(’) return ($LPAR, -);
5)Concat 子程序，把ch中的字符连接到 strToken
编译原理
6)IsLetter和 IsDisgital 布尔函数， 判断ch中字符是否为字母和数字
7) Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它实保留字 则给出它的编码，否则回送0
8) Retract 子程序，把搜索指针回调一 个字符位置
return ($ID, value);
end
else
return (code, -);
end
编译原理
else if (IsDigit()) begin
while (IsDigit()) begin
Concat( ); GetChar( ); end Retract(); value := InsertConst(strToken); return($INT, value); end else if (ch =‘=’) return ($ASSIGN, -); else if (ch =‘+’) return ($PLUS, -);
… WhatALong…Wo rd
rd
… WhatALong…Wo
编译原理
二、单词符号的识别:超前搜索
1 基本字识别: 例如: DO99K=1，10
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

S ⇒a1A1 ⇒a1a2A2 ⇒…… ⇒a1a2…an-1An-1 ⇒ a 1 a 2 … an
右线性文法与状态转换图
是一右线性文法 是相应的状态转换图 右线性文法,M 状态转换图,则从前面的 设G是一右线性文法 M是相应的状态转换图 则从前面的 讨论可以看出如下事实： 讨论可以看出如下事实：
(1)在利用M对符号串w进行识别时 M中每次状态的转换都模拟了 在利用M 进行识别时,M 在利用 一步直接推导,即识别方法 或称分析方法) 即识别方法(或称分析方法 一步直接推导 即识别方法 或称分析方法 是“↓”的; (2)因右线性文法只有形如A→aB、A →a的产生式，所以推导的每 因右线性文法只有形如 aB、 的产生式， 一步所得句型只含一个非终结符，所以推导的规范的，每步所 一步所得句型只含一个非终结符，所以推导的规范的 规范 得的句型也必为规范句型 规范句型； 得的句型也必为规范句型； 必存在G中的一个推导 (3)对于M所识别的任一符号串x,必存在 中的一个推导S ⇒* x 对于M 必存在 对于 (即有x∈L(G);反之 对于L(G)中任一句子y,必存在一条从初态S 反之,对于 即有 必存在一条从初态 到终态F的路径,此路径上各矢线的标记依次拼接起来所组成的符 到终态F的路径 此路径上各矢线的标记依次拼接起来所组成的符 号串恰为y
由左线性文法构造状态转换图的例子
已给文法G=({S,U},{0,1},{S→S1 |U1, U→U0 | 0},S) 已给文法
U→0 U →U0 S →U1 S →S1 0 1 1
用左线性文法构造出的状态转 换图来识别文法的句子,其过 换图来识别文法的句子, 程与前面右线性文法构造的状 态转换图用法一样,这里不再 态转换图用法一样, 赘述. 赘述.
由左线性文法构造状态转换图
设G=(VN,VT,P,S) G=(V ,P,S)是一左线性文法,构造相应的 状态转换图的方法是: 首先用G的VN符标记M的结点,其中,开始符S对应 G V S 的结点为终态结点.另外,再引入一个新结点 R(∉VN)作为初态.矢线的连接规则为: R(∉ (1)对于G中形如A→a 的产生式,引矢线:R→A, G R 且标记为a; (2)对于G中形如A→Ba 的产生式,引矢线 B→A, 线 且标记为a.
程序3-2 状态矩阵驱动程序
CurStat=0; FlagOfFS=NoneSeen; /*将终态标志置为“未经历”*/ /*将终态标志置为 未经历” 将终态标志置为“ if(CurStat==EOF) return 0; while (CurStat != EOF){ if(Stat=TransMat[CurStat][Cur Char]!=NULL) { CurStat=Stat; advance( ); if( CurStat 是终态 是终态){ FlagOfFS=HasSeen; /*已经历过终态*/ /*已经历过终态 已经历过终态* 记下输入串中当前位置及该状态 相关的动作; 相关的动作 }/*end if CurStat 是终态*/ /*end 是终态* } else{ if(FlagOfFS==NoneSeen) { /*未经历过终态*/ /*未经历过终态*/ 未经历过终态 报告词法错误;略过当前词文及 报告词法错误 略过当前词文及 输入字符; 输入字符 CurStat=0; } else { 回退到最近经历的那个终态的 输入字符位置;执行所记录的该 输入字符位置 执行所记录的该 终态的相关动作; 终态的相关动作 } /*end if FlagOfFS==NoneSeen */ } /*end if Stat !=NULL*/ }/*end while*/ /*end
识别无符号数的状态矩阵
当前状 态 0 扫描字符 d . th e r d . E o th e r d E o th e r d o th e r d + o th e r d o th e r d o th e r 语义处理操作或接受动作 { w = 0 ;n = 0 ;p = 0 ;e = 1 ;w = w * 1 0 + d } { w = 0 ;n = 0 ;p = 0 ;e = 1 ;} e rro r { w = w * 1 0 + d ;} 后继状 态 1 3 1 2 4 end 2 4 end 2 6 5 5 6 6 end
识别符号串与归约
由构造状态转换图的方法可知,从初 从初 到下一状态A的转换, 态R到下一状态A的转换,对应了形如 B→a 的产生式 的产生式,即将终结符a归约成 非终结符B; 类似地,从状态B转换到状态A,对应 对应 的产生式,即将Ba归约 了形如A→Ba的产生式 为A ; 如此下去,直到从某状态A转换到状 U 态S(终态),对应了形如S →Aa的产 对应了形如 生式,即将Aa归约为开始符S.此时归 生式 约成功,也恰好进入了终态,即状态转 U 换图识别了(或接受)该符号串. 前面识别00011 00011的例子对应的归约 00011 过程见右图 0 0
<标识符>→<标识符>字母 标识符> 标识符> 标识符> 标识符> <标识符>→<标识符>数字 标识符> <标识符> →字母
若把字母、数字视为终结 符，则上述产生式为（左 线性）正规文法 若我们用d表示0-9间的 数字，则C语言的<无符 号数>的文法也是（右线 性）正规文法（见P48）
一般说来，凡能用正规文法描 述的语言，均可由某种有限状 状态转换图进行分 态算法——状态转换图 状态转换图 析。 状态转换图 由有限个结点所 组成的有向图。 每个结点代表在识别分析过程 中扫描器所处的状态，其中 含 有一个初始状态和若干个终态。 在图中，状态用圆圈表示，终 态用双层圆圈表示。 状态之间可用有向边连接，其 上标记一字符a∈Σ，表示从有 向边的射出状态出发，识别一 字符a后，将进入箭头所指状 态（结点）
不过,就识别的方法而言, 不过,就识别的方法而言,它却 属于“ 分析. 属于“↑”分析. 我们以句子00011为例, 我们以句子00011为例,给出其 00011为例 识别的的步骤.见右表. 识别的的步骤.见右表.
R
0
U
S
步骤 当前状态 余留的符号串 1 2 3 4 5 6 R U U U S S 00011 0011 011 11 1 (识别结束) 识别结束)
3.2 正规文法和状态转换图
正规文法定义了3型语言，常见的单词可由正 正规文法定义了3型语言，常见的单词可由正 规文法定义。 状态转换图可用于识别3型语言；它是设计和 状态转换图可用于识别3型语言；它是设计和 实现扫描器的一种有效工具，是有限自动机的 直观图示
3.2.1 由正规文法构造状态转换图
程序设计语言的单词都能 用正规文法描述； 例如，标识符可定义为
1
{ r e tu rn ( IC O N = w ) ; { n + + ; w = w * 1 0 + d ;} { r e tu rn ( F C O N = w * p o w ( 1 0 ,e * p -n ) ) ;} { n + + ;w = w * 1 0 + d ;} e rro r { p = p * 1 0 + d ;} e = -1 ; e rro r { p = p * 1 0 + d ;} e rro r { p = p * 1 0 + d ;} { r e tu rn ( F C O N = w * p o w ( 1 0 ,e * p -n ) ) ;
2
3
4
5 6
关于状态无符号数识别矩阵
语义 动作中的返回值ICON、FCON分别为整型数、浮点型 ICON、 数的值； 一般说来，无符号数具有形式dmdm-1…d0.d-1…d-nE±dd 即 dmdm-1…d0d-1…d-n*10^(±dd-n); *10^(±dd矩阵中w,p,n,e分别用于计录尾数、指数、小数位及指数的 符号。因此数值为： N=w*10^(e*p-n) N=w*10^(e*p处理整数部分时，对于每个di ,令w=w*10+di ; 处理小数部分时，对于每个di ,令w=w*10+di ;及n++; 处理指数时，E后若有‘-’号，令e=-1；计算指数值 E e=p=p*10+d; p=p*10+d; 在出口处，令ICON=w或FCON=w*10^(e*p-n). ICON=w或FCON=w*10^(e*p识别程序见P55 P55程序3-3。 3
S S U
0
1
1
状态转换图的实现3.2.2 状态转换图的实现-状态矩阵法
我们已看到,状态转换图 状态转换图可方便地用于识别单词.但是,如何让 状态转换图 计算机利用状态转换图来进行词法分析呢? 一个简单实用的方法就是将图以矩阵的形式保存在内存中. 这就是所谓的状态矩阵法 状态矩阵法. 状态矩阵法 状态矩阵 以图中各个状态S1,S2,…,Sn为行,以各个输入符号 a1,a2, …,am为列,组成一个n×m矩阵B,其元素Bij=B[Si,aj]指 B 明下一状态Sk和扫描器此时应完成的语义动作.其含义是,在 Si状态下,扫描到aj符时,按序偶(Si,aj)查矩阵B,扫描器根据Bij 的指示,先执行相应的语义动作,再转换到下个状态Sk. 若Bij为“出错 出错”,则说明输入符号串有误,拒绝接受.扫描器 将调用出错处理程序进行处理.
d d d d E E d d d
0ቤተ መጻሕፍቲ ባይዱ
.
d
1
2
3
4
+|-
5
6
利用状态转换图识别符号串的方法
利用~对 对于已给的字符串w=a1a2…an,ai∈VT,利用 对w 识别的 利用 步骤如下: 步骤如下 (1)从初始状态S出发,自左至右逐个扫描w的各个字符 从初始状态 出发 自左至右逐个扫描 (当前为a1),此时在结点S所射出的诸矢线中 寻找标记 当前为 此时在结点 所射出的诸矢线中,寻找标记 的矢线(若不存在 若不存在,则表明 有语法错误),读入 为a1的矢线 若不存在 则表明w有语法错误 读入a1并 沿矢线所指方向前进,过渡到下一状态 过渡到下一状态(设为 沿矢线所指方向前进 过渡到下一状态 设为A1). (2)设当前处在Ai状态 所扫描的字符为ai+1,在结点Ai所射 设当前处在 状态,所扫描的字符为 在结点 出的诸矢线中,寻找标记为 的矢线(若不存在 若不存在,则表明 出的诸矢线中 寻找标记为ai+1的矢线 若不存在 则表明 w有语法错误 读入ai+1,并进入状态Ai+1; 有语法错误),读入 并进入状态 (3)重复 重复(2),直到w中所有字符被读完且恰好进入终态F 重复 直到 宣告整个识别结束, 时,宣告整个识别结束 w可被接受 宣告整个识别结束 可被接受. 显然,若我们从初态出发 分别沿一切可能 路径到达 若我们从初态出发,分别沿一切可能的 到达终态 显然 若我们从初态出发 分别沿一切可能的路径到达终态 并将中径中矢线上所标记的字符依次连接起来,便 结点,并将中径中矢线上所标记的字符依次连接起来 结点 并将中径中矢线上所标记的字符依次连接起来 便 得到状态转换图所能识别的全部符号串 状态转换图所能识别的全部符号串,这些符号串组 得到状态转换图所能识别的全部符号串 这些符号串组 成的集合构成了该~识别的语言 成的集合构成了该 识别的语言