Atitit.词法分析的争鸣原理 part2

Atitit.词法分析的理论原理 part2   

 

 

1.
 转换图1

1.1. 转换图是出于程序流程图改进而变成的。同样,转换图也得等价地转换为程序流程图3

1.2.
2.2.3 
构造词法分析器(2)流程程序2-1虽然才发生26实行,却是词法分析器的核心4

1.3. 单词存储形式就是三元组(单词ID,单词备注,单词行号)。4

1.4. 单词流是何许传递给语法分析器的。5

1.5.
词官义5

1.6. 词法分析器主要不外乎:构造转换图与转换表、设计词法分析器算法。6

1.7. 提早寻觅几个字符与词法定义有关,有些设计不尽如人意的言语或要超前搜索三独甚至四独字符才能够科学识别单词7

 

1.  转换图

 

起图2-2遭到,不难窥见,其中只有”搜索指针后换一个字符”一种植处理动作(方框)。那么,读者不妨设想一下,词法分析器是否就只有这种拍卖动作也?仔细分析手工识别单词的过程后,就足以发现真相当真这样。既然词法分析器的流程中规范判断(菱形框)比较复杂,而拍卖动作很单纯,因此,可以用一般性流程图改造成为一种植特别用于描述条件判断的流程图。具体改造步骤如下:

1)把图2-2遇所有上、下菱形(判断)之间的箭头用完美表示。

2)把图2-2惨遭具备的菱形直接用箭头线表示,箭头上勾及本菱形的判断成立吗的规格,即可取图2-3。

 

图2-3  识别Pascal标识符的状态转换图

这里大概了失误处理,由于词法分析器的错处理好统一就,所以不必再考虑。

那,将图2-2改建成为图2-3底意思是什么啊?实际上,主要对词法分析器的流水线特点,突出了工艺流程中极复杂的一对,省略或简化相对简便易行的一些,这样的改造福利更直观地解析问题之真面目。这种分析问题之艺术在软件系统分析及统筹过程遭到较常用,读者应当善用改进一些早已部分工具,使的又利于分析问题。

图2-3
对此词法分析器设计有老重要的意向。在形式语言学着拿这种图名转换图(transition
diagrams),亦名状态转换图。

转换图是一个有向图。在转换图中,圆表示状态,状态之间为此箭弧连接。箭弧上的号子表示在箭弧始结点的状态下读入于定字符或字符集时,当前状态转至箭弧终结点所示状态。例如,图2-3当起来状态下,若输入字母,则转移到状态1。一摆放转换图只含有限个状态(即有限个结点),其中,有一个凡是开始状态(图2-3被之”开始”状态),而且要至少发生一个悬停状态(用对缠绕表示,读者可以拿停止状态理解呢而停状态,而其余状态就为不可终止状态)。那么,如何使转换图成功单词的辨别为?实际上,识别一个单词就是由开始状态经过数次变到终止状态的经过。如果有一个字符串的鉴别过程不能到达终止状态,说明输入字符串不克给该换图接收。

脚,应用转换图来分析一个犬牙交错的实例。在Pascal词法分析器中最好复杂的就是可辨实型常量的逻辑流程。Pascal的实型常量有三三两两种植形式:普通小数形式、科学记数法的小数形式,例如,2.34、23.4E32、46.1e-43、30.e12等都是官方的实型常量,而例如
.32、31.3e、32.3E13.2齐花样都是伪的实型常量。读者可以参考图2-4。

 

图2-4  识别Pascal实型常量的转换图

读者可能会见出疑惑,为什么图2-4并未设想实型常量的+/-号?实际上,在词法分析时,只能拿”-“识别成运算符,但无能为力确定该到底是作负号还是减号。这个工作以于语法分析阶段就。因此,词法分析器无法确定是不是拿”-“直接和持续常量组合。仅由分辨实型常量的角度而言,图2-4已足够完整了。但自从事实上编译器设计的角度而言,可能还索要作少量更上一层楼。这里,值得注意的是正规Pascal中的数组声明形式,例如:

 

下面,再来探哪些运用图2-4认识别字符串”92.3E1″。这是一个合法的实数常量表示形式。首先,从开箭头进入状态1。在状态1时,读取到数字就转入状态2。在状态2经常,读取第二单字符”2″,根据圆弧箭头指示,状态2碰到数字时仍然停留在状态2。在状态2时时,读取第三单字符”.”,状态2即转入状态3。在状态3时,读取第四只字符”3″,状态3遇上数字时还留于状态3。在状态3时,读取第五单字符”E”,状态3即使转入状态4。在状态4时,读取第六独字符”1″,状态4换为状态6。根据超前搜识别原则,词法分析器继续读博下一个字符,且下一个字符必定不是数字。在状态6时,读取一个非数字字符即转入状态7。至此,状态转换停留于状态7齐,状态7凡是停状态(即双圈状态),故判定输入字符串合法有效。表2-3被来几乎单实例分析,请读者仔细了解。

发明2-3 
识别实型常量的实例分析

输入字符串

状 态 转 换

识 别 结 果

1234

1 , 2 , 2 , 2 , 2 , 7

有效(到达终止态7)

192.32

1 , 2 , 2 , 2 , 3 , 3 , 7

有效(到达终止态7)

192a2

1 , 2 , 2 , 2

无效(到达非终止态2)

A12s

1

无效(到达非终止态1)

1.104E19

1 , 2 , 3 , 3 , 3 , 3 , 4 , 6 , 6 , 7

有效(到达终止态7)

12E12.98

 

 

-12.12

 

 

+32.E23

 

 

43.1E3.9

 

 

伸手读者自行补充表2-3丁空白区域,以深化对转换图使用办法的晓。只有知道了转换图与平常流程图之间的联络,才能够展开词法分析器的筹划。Neo
Pascal语言的完好转换图将在2.3节详细分析。

 

作者::  ★(attilax)>>>   绰号:老哇的爪子 ( 全名::Attilax Akbar Al Rapanui 阿提拉克斯 阿克巴 阿尔 拉帕努伊 ) 汉字名:艾龙,  EMAIL:1466519819@qq.com

转载请注明来源: http://blog.csdn.net/attilax

 

1.1. 转换图是由程序流程图改进而成为的。同样,转换图也得等价地转换为程序流程图

完整的易图就是是词法分析器的程序流程图,是贯彻词法分析器的因。早期的编译器都是使这种方式手工编码实现之。这种实现方式对编译器设计者的编程技巧要求十分强。如果不行机械地净本转换图的讲述编码,所抱的词法分析器的执行效率可能比没有,必须用编程技巧使词法分析器尽可能精悍高效。因此,这种编码实现方式有一个重的贫乏:程序的耦合度高。当词法定义有转移时,词法分析器的改观将大坏,甚至是颠覆性的。然而,为什么早期的编译器大多以这种办法编码实现吗?最要害的原由就是是这种艺术贯彻之词法分析器运行时所待的积存空间的代价相对较小

 

明白,转换图的款型是免便利输入计算机的,众所周知,最利于程序处理的数据结构就是表格。如果会拿转换图转化为表或者类似之数据结构,那么,词法分析器就好辨别并拍卖转换图了。事实上,将转换图等价转换为二维表格的进程得参照以下四个步骤:

 

1.2. 2.2.3  构造词法分析器(2)流程程序2-1尽管光发生26实行,却是词法分析器的中心

第11履行:查询时状态下读取当前字符时底转移状态,这是程序的核心部分。

第12履:如果查询得到的换状态吧-1,表示目前状态下非同意读取当前字符。

第13行:置出错标志bTag为true。

第15实行:调用IsTerminal函数判断转换状态是不是也平息状态。

第16履行:将目前状态设为查询得到的换状态。

第17实践:当前状态下读取当前字符时,转换状态也平息状态,即获得一个单词。

第19行:由于提前搜索识别,必须以目前读取位置回退一个字符。

第20推行:将单词缓存区回退一个字符。

第21履行:调用ProcessToken处理单词。

第22行:将单词缓存区清空。

第23实施:当前状态置为0。

 

1.3. 单词存储形式就是三元组(单词ID,单词备注,单词行号)。

词法分析器识别得到的单词流是语法分析器的输入,那么,词法分析器需要提供什么消息为语法分析器呢?以什么方法传送给语法分析器呢?这些问题是亟需设计者回答的。

在编译器设计中,最广大的单词存储形式就是三元组(单词ID,单词备注,单词行号)。

单词行号一般含两有信息:单词所于的源程序文件称、单词在源程序文件中之行号。这些信息要用来出错处理,可以供错误的职位信息,便于用户定位修改源程序。行号信息

 

 

1.4. 单词流是怎么传递给语法分析器的。

即时关键取决于词法分析是用作一个独阶段还是用她计划也独立的平全勤。词法分析作为一个独门阶段便是借助以词法分析器作为一个函数,由语法分析器调用。每次调用词法分析器只辨认一个单词,然后将单词直接传送让语法分析器处理。整个过程由于语法分析器控制,在语法分析过程遭到,进行单词识别。词法分析作为独立的一律一体就是是恃词法分析器将针对普源程序文件扫描一不良,识别出富有的单词,然后将源程序为单词流的方式传送给语法分析器处理。这半种植方法各有利弊,且每起成之下案例

 

1.5. 词法定义

计划词法分析器之前,必须明白程序设计语言的词法定义。词法定义是一样门程序设计语言的必不可少组成部分。同时,词法定义也一直关系在词法分析器的复杂程度,甚至毫无所有的词法定义都可以实现。例如,假要C语言的词法定义规定标识符中可以出现”*”,则如此的词法定义是蛮麻烦实现的。

 

表明2-5详细描述了Neo
Pascal的词法定义。

申2-5 
Neo Pascal词法定义

标识符

以字母开头,后跟字母与数字的任意组合的字符串

ID:001

运算符

Neo Pascal一共包含13个运算符,分别是:

ID

单词

ID

单词

ID

单词

ID

单词

ID

单词

016

=

017

:=

018

019

<> 

020

<=

021

022

>=

023

+

024

025

*

026

/

027

^

028

@

 

 

 

 

 

(续)

界符

Neo Pascal一共包含9个界符,分别是:

ID

单词

ID

单词

ID

单词

ID

单词

ID

单词

007

.

008

(

009

)

010

;

011

,

012

:

013

..

014

[

015

]

 

 

 

关键字

关键字是特殊的标识符,必须符合标识符的定义。Neo Pascal一共包含54个关键字,分别是:

ID

单词

ID

单词

ID

单词

ID

单词

ID

单词

040

ASM

041

AND

042

ARRAY

043

BEGIN

044

BOOLEAN

045

BYTE

046

BREAK

047

CARDINAL

048

CASE

049

CHAR

050

CONST

051

CONTINUE

052

DIV

053

DO

054

DOWNTO

055

ELSE

056

END

057

FILE

058

FOR

059

FORWARD

060

FUNCTION

061

GOTO

062

IF

063

IN

064

INTEGER

065

LABEL

066

LONGWORD

067

MOD

068

NIL

069

NOT

070

OF

071

OR

072

PROCEDURE

073

PROGRAM

074

REAL

075

RECORD

076

REPEAT

077

SET

078

SHL

079

SHORTINT

080

SHR

081

SINGLE

082

SMALLINT

083

STRING

084

THEN

085

TO

086

TYPE

087

UNTIL

088

USES

089

VAR

090

WITH

091

WHILE

092

WORD

093

XOR

 

 

 

字符串常量,                     ID:002。 例:’I am a boy.’

整数常量,                       ID:003。 例:324、32

普通形式实型常量,               ID:004。 例:43.53、62.034

带+/-号的科学记数形式实型常量,  ID:005。 例:43.12E-23

不带+/-号的科学记数形式实型常量,ID:006。 例:41.09E12

1.6. 词法分析器主要不外乎:构造转换图与转换表、设计词法分析器算法。

词法分析器的核心就是根据转换图识别单词。不过,事实并非全盘如此。由于一些程序设计语言的词法定义缘故,仅仅根据程序2-1之算法是不足以完成词法分析的

 

 

1.7. 提前寻找几个字符与词法定义有关,有些设计不帅的言语或要超前搜索三只甚至四独字符才能够是识别单词

。反复回忆搜索会大大降低词法分析器的履效率,故在统筹相同门程序设计语言时,应尽量做到就需要提前搜索一个字符就可以就所有单词的识别。

 

参考

 

2.2.2
转换图 – 51CTO.COM.html