【编译原理01】词法分析

编译里最先开始的一步就是要进行词法分析,它的主要目的是为了分词,并且检测一定的词法错误。

词法分析分为“扫描”和“分析”两个阶段,扫描用于去除一些不需要的字符,例如去除注释和压缩空白字符。

在聊分析之前,首先需要理解“词法单元”、“模式”和“词素”。

模式很好理解,就是说一个单词的组成方法,比如“由偶数个a和偶数个b组成的字符串”就是一个模式,但在计算机里,通常我们用正则表达式来表示这样的模式语言。关于正则表达式,我曾经找到一个简单的手册,可以参考一下。

词素就是一个字符序列,匹配模式的一个字符序列,例如aaaabbbb就可以是上诉模式的一个词素。用面向对象的方式来说,模式就是一种类,而词素就是一个实例。

词法单元则是“词法单元名”和“属性值”的一个组合体,词法单元名是“词法单位的抽象符号”,比如说“1111”,“2222”,“23422”这些我们可以统称他们为数字,也就是说他们的词法单元名为“number”,再比如“val1”,“val2”,“value3”这些我们可以统称他们为标识符,他们的词法单元名就可以为“id”。但是还有一类特殊的,就是关键字,一般关键字的词法单元名就是其本身。属性值则是可选的,词法单元名是语法分析阶段语法分析器所要用的东西,但在实际计算阶段我们依然需要知道词法单元的其他信息,这些信息就包含在属性里。比如,标识符的属性可以有:词素、类型、第一次出现的位置等,这些通常保存在符号表里,而词法单元的属性值则是一个指向符号表的指针。

词法单元一般长这样:<Name, Pointer>


在分析过程中,词法分析器逐个扫描字符,并且通过正则表达式进行匹配,如果某个词法组成符合某个特定的正则表达式,则被判定为是这个词法,并且返回词法单元。关键问题在于正则表达式是如何工作的?

一般来说,我们只需要三种基本的正则表达式,就可以拼凑出各种各样的模式。这三种分别是:

r=st //s后紧跟着t

r=s|t //s或者t

r=s* //0个或多个s

例如上述的偶数个a和偶数个b的正则表达式为:

(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*

正则表达式的运作关键是有穷状态机,有穷状态机分为NFA(不确定的有穷状态机)和DFA(确定的有穷状态机)。上面的三种基本的正则表达式分别可以对应以下三种基本的NFA状态机

ε代表空字符,即不需要干啥就能到达那个状态。

根据这三条基本规则的叠加,我们可以很容易得出一个正则表达式的NFA,但是NFA有一个问题,即会出现同一个状态在同一个输入的情况下到达不同的下一个状态,这会大大增大分析的成本,为了解决这个问题,就引入了DFA,DFA可以由NFA转换而来,转换的方法也不难,可以通过以下博客学习:

https://blog.csdn.net/u012359618/article/details/42456771


其他:

1)为了加速读入速度,通常我们可以一次性读取内存一页(page)的大小那么多的字符到缓冲区,以加快遍历的速度。这还会涉及到哨兵标记的问题,因为要防止走到最后有一个字符却仍然在当前页遍历的情况,所以需要在每一页末尾或者程序的末尾添加一个哨兵标记以防止溢出访问的问题。

2)有时候可能会因为没有匹配的正则表达式而产生词法错误的问题,这时候应当进行错误恢复使其可以继续的进行遍历分析,同时还应当向客户端报告该错误并且在词法分析结束后停止编译。最简单的错误恢复方法是“恐慌模式”恢复,即在剩余的输入里不断删除字符,直到发现一个正确的词法单元为止。

3)目前我们不再需要完全去手写一个词法分析器,可以使用Lex/Flex等词法分析器生成工具生成一个词法分析器,通过这些工具我们只需要编写较为简单的正则表达式而无需过多关心其他的细节内容即可快速生成和使用一个词法分析器。

-- 热度:78 ℃
-- 于 共写了1568个字
-- 文内使用到的标签:

一条回应:“【编译原理01】词法分析”

发表评论

电子邮件地址不会被公开。