6 词法分析器的实现

在我们前面的讨论中，我们深入探讨了“词法分析之正则表达式与有限自动机”，并了解了如何使用正则表达式来定义编程语言中的词法单元以及怎样将其转换为有限自动机。接下来，我们将着眼于具体实现一个简单的词法分析器，这个分析器能够将源代码转换为“词法单元（tokens）”。

词法分析器的概述

词法分析的主要任务是将输入的源代码分解为一系列的“词法单元”。每个词法单元代表了程序中的一个基本元素，如关键字、标识符、常量、运算符等。在实际实现中，词法分析器通常会使用一种形式的有限自动机来识别这些词法单元。

设计思路

本节中，我们将通过一个简化的示例来实现一个基本的词法分析器，识别以下几种词法单元：

• 关键字：if, else, while, return
• 标识符：以字母开头，可以包含字母和数字
• 整数常量：只包含数字
• 运算符：+, -, *, /
• 分隔符：;, ,, (, )

实现步骤

1. 定义词法单元的结构
2. 实现正则表达式对应的模式匹配
3. 构建词法分析器，读取输入并生成词法单元

1. 定义词法单元的结构

首先，我们需要定义一个表示词法单元的结构。在 Python 中，这可以表示为一个类：

class Token:
    def __init__(self, type, value):
        self.type = type
        self.value = value

    def __repr__(self):
        return f"Token({self.type}, {self.value})"

Token 类包含两个属性，type 表示该词法单元的类型，value 则是词法单元的具体值。

2. 实现正则表达式对应的模式匹配

接下来，我们将使用 Python 的 re 模块来定义识别不同类型词法单元的正则表达式。

import re

# 定义词法单元类型及其正则表达式
token_specification = [
    ('NUMBER',   r'\d+'),            # 整数常量
    ('IDENT',    r'[A-Za-z_][A-Za-z0-9_]*'),  # 标识符
    ('IF',       r'if'),             # 关键字
    ('ELSE',     r'else'),           # 关键字
    ('WHILE',    r'while'),          # 关键字
    ('RETURN',   r'return'),         # 关键字
    ('OP',       r'[+\-*/]'),        # 运算符
    ('SEMI',     r';'),              # 分隔符
    ('COMMA',    r','),              # 分隔符
    ('LPAREN',   r'\('),             # 左括号
    ('RPAREN',   r'\)'),             # 右括号
    ('SKIP',     r'[ \t]+'),         # 跳过空白字符
    ('NEWLINE',  r'\n'),             # 换行符
]

# 将模式合并为一个大的正则表达式
tokens_regex = '|'.join(f'(?P<{pair[0]}>{pair[1]})' for pair in token_specification)

在上述代码中，我们为每种词法单元定义了一个模式，并使用 (?P<name>...) 构造命名组，这样我们可以跟踪每个模式匹配的类型。

3. 构建词法分析器

下面，我们将组合所有的部分，构建一个词法分析器的核心实现。

def lexer(code):
    tokens = []
    for mo in re.finditer(tokens_regex, code):
        kind = mo.lastgroup
        value = mo.group()
        
        if kind == 'NUMBER':
            tokens.append(Token('NUMBER', int(value)))
        elif kind == 'IDENT':
            tokens.append(Token('IDENTIFIER', value))
        elif kind in {'IF', 'ELSE', 'WHILE', 'RETURN'}:
            tokens.append(Token(kind, value))
        elif kind in {'OP', 'SEMI', 'COMMA', 'LPAREN', 'RPAREN'}:
            tokens.append(Token(kind, value))
        elif kind == 'NEWLINE':
            continue
        elif kind == 'SKIP':
            continue
        else:
            raise RuntimeError(f'Unexpected input: {value}')
    return tokens

这个 lexer 函数接受源代码作为字符串，并返回一个词法单元列表。它在输入字符串中查找所有匹配的模式，并将其转换为 Token 实例。

代码示例

现在我们可以用以下代码测试我们的词法分析器。假设我们的输入代码如下所示：

source_code = '''
if (x > 10) {
    return x + 1;
} else {
    return x - 1;
}
'''

tokens = lexer(source_code)
for token in tokens:
    print(token)

输出结果应为：

Token(IF, if)
Token(LPAREN, ()
Token(IDENTIFIER, x)
Token(OP, >)
Token(NUMBER, 10)
Token(RPAREN, )
Token(SEMI, ;)
Token(RETURN, return)
Token(IDENTIFIER, x)
Token(OP, +)
Token(NUMBER, 1)
Token(SEMI, ;)
Token(ELSE, else)
Token(RETURN, return)
Token(IDENTIFIER, x)
Token(OP, -)
Token(NUMBER, 1)
Token(SEMI, ;)

小结

在本节中，我们实现了一个简单的词法分析器，能够将源代码分解成不同类型的词法单元。通过结合正则表达式和 Python 的 re 模块，我们成功地为每种词法单元构建了模式，并将源代码解析为可供后续处理的数据形式。

接下来，我们将进入“语法分析之上下文无关文法”的部分，在那里，我们将进一步探索如何使用这些词法单元构建更复杂的语法结构，并进行语法分析。