关于编译原理:词法分析

发布于 2022-05-23  1343 次阅读


词法分析简介和碎碎念

最近正在和Tastror做编译器,然而她超级厉害两个晚上就把语法分析写完了,我写的是词法分析。

编译器的前端分析过程大致包括这几件事:词法分析,语法分析,语义分析。

词法分析,是将代码中的每一个token提取出来的过程。给我个人的感觉类似于分类。即,判断语句中的每个标记属于什么成分。例如,对于代码:

int a=300;

"int"是关键字(Keyword),类型说明符;"a"是一个变量名,属于标识符(ID,Identifier),而"="是一个运算符(Operator),";"是终止标志,可以算作一个标点(Punctuation)。词法分析器扫描一遍源代码,按照类似这样的分类生成一个列表提供给语法分析器。同时还可以记录行列的值从而在分析出不合法token的时候停下并报出详细错误位置。而其中token间以某些符号(具体指标点或运算符)或者空格、回车、换行为界。

词法分析的简单实现

词法分析的核心是状态机。一种较为简单的方法是,列出不同首字符下的状态,然后对各个状态进行细分,每一种细分再用状态机实现。

以C语言为例。

1、如果读入token的第一个字符是一个字母或者下划线,则当前的token可能是一个关键字(当然关键字不含下划线),也可能是一个ID。读取整个token,符合正则表达式

[a-zA-Z|_][a-zA-Z0-9|_]*

的token是一个合理的ID或关键字,然后去关键字列表查找是否是关键字确定具体情况。

当然也可以在一开始就把下划线开头和字母开头分开,这样效率会高一些。但是直接在1中所述的状态机里区分开关键字和ID会使得状态机变得更复杂,比如识别"while"或者"return"这样的关键字的时候,会有比较长的识别过程,可能还不如直接在关键词列表里查一遍(其实是我懒o(TヘTo))。

2、如果读入的token第一个字符是一个数字,那么这个token只可能是数字。C语言中的整数包括十进制、八进制、十六进制,小数包括普通表示和科学计数法。这些数字满足的正则表达式如下:

十进制(Dec):

[0-9]+

八进制(Oct):

0[0-7]+

十六进制(Hex):

0[x|X][0-9a-fA-F]+

普通小数:

[0-9]+\.[0-9]+

科学计数法:

[0-9]+\.[0-9]+[e|E][+|-]?[0-9]+

使用与这些正则表达式对应的状态机去检测是哪一种数字。这些规则是有优先级的,先检查带字母和符号的格式,比如Hex和科学计数法、普通小数。在此之后再检查普通数字。

主要的情况就这些了,其他的开头是一些符号,可能会遇到一些困难,比如两个字符的运算符"&&"、"||"等等,这类符号的处理建议直接使用状态机处理效率更高。

有关token的划分的注意事项

匹配token的时候需要遵循最长匹配的原则。前面提到了,token之间以运算符或者空格等分割,但是一些代码的写法比如

float c=3+e;

float c=3.0e+3;

这两者都是合法的,但第二个语句不能直接按照"+"简单的将两边分割为两个token。这种情况下应该先按照数字规则匹配,匹配剩下的再继续分割为新的token。

一些吐槽和致谢

flex真难用TAT,玩了好久还是不会玩,最后全部自己写了。词法分析写了好久我好菜呜呜呜~

另外,谢谢 Tastror 的耐心等待和帮助。要感谢的还有 天童アリス 、 棗イロハ 和 小鳥遊ホシノ ,感谢这三位给予我精神上的支持。

参考资料:现代编译原理——第1章:词法分析 - jacksplwxy - 博客园 (cnblogs.com)

好困,想睡觉喵~
最后更新于 2022-10-19