编译原理——用Python实现简易词法分析器

近来，国产自主秀又走一波，木兰稳稳地跪了。码哥我也准备小蹭一波热度，聊聊编译原理。

其实国人自主从0开始开发的编译器非常很多，但是由于基本都是个人单打独斗的（如码哥这样的），因此一直也无人问津。开源圈其实和开公司卖产品很相似，在众多竞品中，如何让人看到你很是重要，这也是一些人傍大厂走红的缘由。

言归正传，做软件的不论是否是软件专业出身，多少都会听过编译原理。这是一门关于如何打造和优化编程语言的学科，学习后对编程人员理解和学习编程语言有很大帮助。然而实际中，很少有人能融会贯通，都只是在心中默默膜拜。

今天，码哥就给大家奉上一个简单的用python实现的词法分析器，让诸君见证编译原理也很简单。由于编译原理涉及内容很多，碍于篇幅，因此本文仅讨论词法分析器相关内容。

首先，先来说明一下词法分析器的功能。词法分析器最主要的用途是提取词素，也就是文本中符合一定规则的片段，例如下面这段ini配置：

#姑且叫它a.ini
name = 'Mr. Robot'
age = 99
Job = 'Hacker'

在我们的理解中，文本中的词素为：

name
=
'Mr. Robot'
age
=
99
Job
=
'Hacker'

每一行即为一个词素。当然，词素也有一些附加内容，例如词素类型，词素所在行数。

在编译器中，这些词素将作为上层语法解析器所使用的基础元素。

接着，我们以解析ini为例，来进一步讨论。

遥想码哥当年，工作刚有了，拿起fgets，解析ini，谈笑间获取配置信息。

代码重游，看左去空格，右删空行，一口老血，忍得菊花轻颤。

下面，给大家提供一种更好的解决方案——用Python实现的词法分析器。其实码哥更愿意用C，但是C中会包含很多内存分配、释放、出错判断，碍于篇幅，就选择脚本语言实现。

#!/usr/bin/env python3
'''
    Author: 码哥
    本人Python比较水，诸君理解大意就好，好砖请留自用...
'''
def parse(content, line=1):
    if not isinstance(content, str):
        return ('content must be string', 'error', line, content)
    token = []
    while 1:
        if not len(content):
            return ('', 'eof', line, '')
        if content[0].isalpha():
            for i in range(len(content)):
                if not content[i].isalpha():
                    return (''.join(token), 'var', line, content[i:])
                token.append(content[i])
            if i >= len(content):
                return (''.join(token), 'var', line, content[i:])
        elif content[0].isdigit():
            for i in range(len(content)):
                if not content[i].isdigit():
                    return (''.join(token), 'int', line, content[i:])
                token.append(content[i])
            if i >= len(content):
                return (''.join(token), 'int', line, content[i:])
        else:
            if content[0] in [' ', '\t', '\n']:
                if content[0] == '\n':
                    line += 1
                content = content[1:]
                continue
            else:
                c = content[0]
                if c == "'" or c == '"':
                    i = 1
                    while i < len(content) and content[i] != c:
                        token.append(content[i])
                        i += 1
                    if i < len(content):
                        return (''.join(token), 'str', line, content[i+1:])
                    else:
                        return ('String must be ended by {}'.format(c), 'error', line, content[i+1:])
                else:
                    token = content[0]
                    return (token, 'operator', line, content[1:])

if __name__ == '__main__':
    with open('a.ini', 'r') as f:
        content = f.read()
    line = 1
    while 1:
        token, type, line, content = parse(content, line)
        print('Token:[{}] Type:{} line:{}'.format(token, type, line))
        if type == 'eof' or type == 'error':
            break

从这段代码中，我们可以看到，parse函数主要是解析了以下几种词素：

• 全英文的变量名，例如a.ini中的name
• 整数
• 以’或"包裹的字符串（未支持换行）
• 其他操作符，如，=等

用这段代码解析我们之前的a.ini，结果如下：

% python3 lex.py
Token:[name] Type:var line:1
Token:[=] Type:operator line:1
Token:[Mr. Robot] Type:str line:1
Token:[age] Type:var line:2
Token:[=] Type:operator line:2
Token:[99] Type:int line:2
Token:[Job] Type:var line:3
Token:[=] Type:operator line:3
Token:[Hacker] Type:str line:3
Token:[] Type:eof line:4

所有文字处理完后，会返回一个type为eof的词素，用来标识文本结束。

现在，我们再去解析ini配置是不是就很轻松了？

其实，在词法分析阶段，还可以增加很多其他功能，例如增加预编译命令（宏等等），引入其他文件等操作。读者们可以尽情发挥自己想象力来加入各种功能。

喜欢的朋友可以关注码哥，也可以在下方评论区留言交流。

感谢诸君支持，码哥也将继续发布优质内容给你们，谢谢观看！