没有合适的资源?快使用搜索试试~ 我知道了~
词法分析1
需积分: 0 0 下载量 174 浏览量
2022-08-03
20:20:00
上传
评论
收藏 2.19MB PDF 举报
温馨提示
试读
19页
一、问题概述 二、正则表达式 三、有穷状态自动机
资源详情
资源评论
资源推荐
构造可配置词法分析器
陈梓瀚
华南理工大学计算机软件学院软件工程 05 级本科
vczh@163.com
http://www.cppblog.com/vczh/
2007-11-8
一、问题概述
随着计算机语言的结构越来越复杂,为了开发优秀的编译器,人们已经渐渐感到将词
法分析独立出来做研究的重要性。不 过 词 法 分 析 器 的 作 用 却 不 限 于 此 。回 想 一 下我们的老师
刚刚开始向我们讲述程序设计的时候,总是会出一道题目:给出一个填入了四则运算式子的
字符串,写程序计算该式子的结果。除此之外,我们有时候建立了比较复杂的配置文件,譬
如 XML 的时候,分析器首先也要对该文件进行词法分析,把整个字符串断成了一个一个比
较短小的记号(指的是具有某种属性的字符串),之后才进行结构上的分析。再者,在实现某
种控制台应用程序的时候,程序需要分析用户打进屏幕的命令。如果该命令足够复杂的话,
我们也首先要对这个命令进行词法分析,之后得到的结果会大大方便进行接下去的工作。
当然,这些问题大部分已经得到了解决,而且历史上也有人做出了各种各样专门的或
者通用的工具(Lex、正则表达式引擎等)来解决这一类问题。我们在使用这种工具的时候,
为了更加高效地书写配置,或者我们在某种特殊情况下需要自己制作类似的工具,就需要了
解词法分析背后的原理。本文将给出一个构造通用词法分析工具所需要的原理。由于实现的
代码过长,本文将不附带实现。
究竟什么是“把一个字符串断成一些记号”呢?我们先从四则运算式子入手。一个四
则运算式子是一个字符数列,可是我们关心的对象实际上是操作符、括号和数字。于是此法
分析的作用就是把一个字符串断开成我们关心的带有属性的记号。举个例子:
(11+22)*(33+44)是一个合法的四则运算式子,如果输入是(左括号,”(“) (数字,”11”) (一级操作
符,”+”) (数字,”22”) (右括号,”)”) (二级操作符,”*”) (左括号,”(“) (数字,”33”) (一级操作符,”+”)
(数字,”44”) (右括号,”)”)的话,我们在检查结构的时候只需要关心这个记号的属性(也就是左
括号、右括号、数字、操作符等)就行了,具体计算的时候才需要关心这个记号实际上的内
容。如果式子里边有空格的话,我们也仅仅需要把空格当成是一种记号类型,在词法分析得
出结果之后,将具有空格属性的记号丢弃掉就可以了,接下去的步骤不需变化。
但需要注意的是,词法分析得到的结果是没有层次结构的,所有的记号都是等价的对
象。我们在计算表达式的时候把+和*看成了不同层次的操作符,类似的结构是具有嵌套的
层次的。词法分析不能得出嵌套层次结构的信息,最多只能得到关于重复结构的信息。
二、正则表达式
我们现在需要寻找一种可以描述记号类型的工具,在此之前我们首先研究一下常见的
记号的结构。为了表示出具有某种共性的字符串的集合,我 们 需 要 书 写 出 一些能代表字符串
集合的规则。这个集合中的所有成员都将被认为是一种特定类型的记号。
首先,规则可以把一个特定的字符或者是空字符串认为是一种类型的记号的全部。
上
文所说到的四则运算式子的例子,“左括号”这种类型的记号就仅仅对应着字符”(“,其他的
字符或者字符串都不可能是“左括号”这个类型的记号。
其次,规则可以进行串联。
串联的意思是这样的,我们可以让一个字符串的前缀符合
某一个指定的规则,剩下的部分的前缀符合第二个规则,剩下的部分的前缀符合第三个规则
等等,一直到最后一个部分的全部要符合最后一个规则。如果我们把”function”这个字符串
作为一个记号类型来处理的话,我们可以把”function”这个字符串替换成 8 个串联的规
则:”f”,”u”,”n”,”c”,”t”,”i”,”o”,”n”。首先,字符串”function”的前缀”f”符合规则”f”,剩下的部
分”unction”的前缀”u”符合规则”u”,等等,一直到最后一个部分”n”的全部符合规则”n”。
第三,规则可以进行并联。
并联的意思就是,如果一个字符串符合一系列规则中的其
中一个的话,我们就说这个字符串符合这一些规则的并联。于是这些规则的并联就构成了一
个新的规则。一个典型的例子就是判断一个字符串是否关键字。关键字可以是”if”,可以
是”else”,可以是”while”等等。当然,一个关键字是不可能同时符合这些规则的,不过只要
一个字符串符合这些规则的其中一个的话,我们就说这个字符串是关键字。于是,关键字这
个规则就是”if”、”else”、”while”等规则的并联。
第四,一个规则可以是可选的。
可选的规则实际上是属于并联的一种特殊形式。加入
我们需要规则”abc”和”abcde”并联,我们会发现这两个规则有着相同的前缀”abc”,而且 这个
前缀恰好就是其中的一个规则。于是我们可以把规则改写成”abc”与””和”de”的并联的串联。
但是规则””指定的规则是空串,因此这个规则与”de”的并联就可以看成是一个可选的规
则”de”。
第五,规则可以被重复。
有限次的重复可以使用串联表示,但是如果我们不想限制重
复的次数的话,串联就没法表示这个规则了,于是我们引入了“重复”。一个典型的例子就
是程序设计语言的标识符。标识符可以是一个变量的名字或者是其他东西。一门语言通常没
有规定变量名的最大长度。因此为了表示这个规则,就需要将 52 个字母进行并联,然后对
这个规则进行重复。
上述的 5 种构造规则的方法中,后面的 4 个方法被用于把规则组合成为更大的规则。
为了给出这种规则的形式化表示,我们引入了一种范式。这种范式有以下语法:
1:字符用双引号包围起来,空串使用ε代替。
2:两个规则头尾连接代表规则的串联。
3:两个规则使用 | 隔开代表规则的并联。
4:规则使用[]包围代表该规则是可选的,规则使用{}包围代表该规则是重复的。
5:规则使用()包围代表该规则是一个整体,通常用于改变操作符 | 的优先级。
举个例子,一个实数的规则书写如下:
{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}”.”[{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}]。
但是,我们如何表示“不是数字的其他字符呢”?字符的数量是有限的,因此我们可
以使用规则的并联来表示。但是所有的字符实在是太多(ASCII 字符集有 127 个字符,UTF-16
字符集有 65535 个字符), 因 此 后 来 人 们 想 出 了 各 种 各 样 的 简化规则书写的办法。比较著名
的有 BNF 范式。BNF 范式经常被用于理论研究,但是更加实用的是正则表达式。
正则表达式的字符不需要用双引号括起来,但是如果需要表示一些被定义了的字符(如
“|” )的话,就 使用转义字符的方法表示(如 “\|”)。其 次 ,X?代表[X],X+代表{X},X*代表[{X}]。
字符集合可以用区间来表示,[0-9]可以表示“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”,[^0-9]则
表示“除了数字以外的其他字符”。正则表达式还有各种各样的其他规则来简化我们的书写,
不过由于本文并不是“精通正则表达式”,因此我们只保留若干比较本质的操作来进行词法
分析原理的描述。
正则表达式的表达能力极强,小数的规则可以使用[0-9]+.[0-9]来表示,C 语言的注释可
以表示为/\*([^\*]|\*+[^\*/])*\*+/来表示。
三、有穷状态自动机
人阅读正则表达式会比较简单,但是机器阅读正则表达式就是一件非常困难的事情了。
而且,直接使 用 正则表 达 式进行 匹 配配的 话 ,不仅工 作 量大,而 且 速度缓 慢。因此 我 们还需
要另外一种专门为机器设计的表达方式。本文在以后的章节中会给出一种算法把正则表达式
转换为机器可以阅读的形式,就是这一章节所描述的有穷状态自动机。
有穷状态自动机这个名字听起来比较可怕,不过实际上这种自动机并没有想象中的那
么复杂。状态机的这种概念被广泛的应用在各种各样的领域中。软件工程的统一建模语言
(UML)有状态图,数字逻辑中也有状态转移图。不过这些各种各样的图在本质上都跟状态机
没有什么区别。我将会通过一个例子来讲述状态的实际意义。
假设我们现在需要检查一个字符串中 a 的数量和 b 的数量是否都是偶数。当然我们可以
用一个正则表达式来描述它。不过对于这个问题来说,用正则表达式来描述远远不如构造状
态机方便。我们可以设计出一个状态的集合,然后指定集合中的某一个元素为“起始状态”。
其实状态就是在工作还没开始的时候,分析器所处的状态。分析器在每一次进行一项新的工
作的时候,都要把状态重置为起始状态。分析器每读入一个字符就修改一次状态,修改的方
法我们也可以指定。分析器在读完所有的字符以后,必然停留在一个确定的状态中。如果这
个状态跟我们所期望的状态一致的话,我们就说这个分析器接受了这个字符串,否则我们就
说这个分析器拒绝了这个字符串。
如何通过设计状态及其转移方法来实现一个分析器呢?当然,如果一个字符串仅仅包
含 a 或者 b 的话,那么分析器的状态只有四种:“奇数 a 奇数 b”、“ 奇 数 a 偶数 b”、“ 偶 数 a
奇数 b”、“ 偶 数 a 偶数 b”。 我们把这些状态依次命名为 aa、aB、Ab、AB。大写代表偶数,
小写代表奇数。当工作还没开始的时候,分析器已经读入的字符串是空串,那 么 理 所 当 然 的
起始状态应当是 AB。当分析器读完所有字符的时候,我们期望读入的字符串的 a 和 b 的数
量都是偶数,那么结束的状态也应该是 AB。于是我们给出这样的一个状态图:
剩余18页未读,继续阅读
巧笑倩兮Evelina
- 粉丝: 25
- 资源: 336
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 论文(最终)_20240430235101.pdf
- 基于python编写的Keras深度学习框架开发,利用卷积神经网络CNN,快速识别图片并进行分类
- 最全空间计量实证方法(空间杜宾模型和检验以及结果解释文档).txt
- 5uonly.apk
- 蓝桥杯Python组的历年真题
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 2023-04-06-项目笔记 - 第一百十九阶段 - 4.4.2.117全局变量的作用域-117 -2024.04.30
- 前端开发技术实验报告:内含4四实验&实验报告
- Highlight Plus v20.0.1
- 林周瑜-论文.docx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0