第63集：基于表格的词法分析器

学习目标

• 理解基于表格的词法分析器的基本原理
• 掌握转移表和动作表的构建方法
• 了解表压缩技术的应用
• 学习如何使用生成工具创建表格驱动的词法分析器
• 能够实现一个简单的基于表格的词法分析器

核心知识点讲解

1. 基于表格的词法分析器概述

基于表格的词法分析器是一种使用预计算表格来驱动词法分析过程的方法。与手写的状态机实现相比，表格驱动的方法更加系统和易于维护，特别适合复杂的词法分析任务。

基于表格的词法分析器的组成：

1. 状态转移表：记录从一个状态到另一个状态的转移
2. 动作表：记录在每个状态下遇到结束符时应该执行的动作
3. 驱动程序：使用表格来控制词法分析过程的程序

2. 转移表的构建

转移表是一个二维数组，其中行代表当前状态，列代表输入字符，值代表下一个状态。构建转移表的过程实际上就是将DFA（确定有限自动机）的状态转移关系转换为表格形式。

转移表的构建步骤：

1. 确定DFA的所有状态
2. 确定输入字符集
3. 对每个状态和每个输入字符，确定转移后的状态
4. 将这些转移关系填充到表格中

3. 动作表的构建

动作表记录在每个状态下应该执行的动作，特别是当遇到词素结束时的动作。对于接受状态，动作通常是返回相应的Token类型。

动作表的构建步骤：

1. 确定每个状态是否为接受状态
2. 对于接受状态，确定对应的Token类型
3. 将这些动作信息填充到表格中

4. 表压缩技术

当输入字符集较大时，转移表可能会变得非常大，导致内存使用过高。因此，需要使用表压缩技术来减少内存使用。

常见的表压缩技术：

1. 默认转移：为每个状态设置一个默认转移，只存储与默认转移不同的条目
2. 状态分组：将具有相似转移行为的状态分组，共享转移表条目
3. 稀疏矩阵表示：使用稀疏矩阵数据结构来存储转移表，只存储非空条目
4. 编码优化：对状态和字符进行编码，减少表的大小

5. 生成工具

为了简化基于表格的词法分析器的构建过程，通常使用自动生成工具来从正则表达式或状态定义生成表格。

常见的词法分析器生成工具：

1. Lex/Flex：生成C语言的词法分析器
2. JFlex：生成Java语言的词法分析器
3. ANTLR：生成多种语言的词法分析器和语法分析器
4. Ply：Python的词法分析器生成工具

实用案例分析

案例1：简单表达式语言的转移表

考虑一个简单的表达式语言，包含以下Token：

• 数字（0-9）
• 标识符（字母开头，后跟字母或数字）
• 运算符（+、-、*、/）
• 括号（(、)）

对应的DFA状态转移表：

对应的动作表：

案例2：使用Lex/Flex生成词法分析器

以下是一个使用Flex生成词法分析器的示例：

%{
#include <stdio.h>
%}

%%
[0-9]+        { printf("数字: %s\n", yytext); }
[a-zA-Z][a-zA-Z0-9]* { printf("标识符: %s\n", yytext); }
[+]           { printf("加号\n"); }
[-]           { printf("减号\n"); }
[*]           { printf("乘号\n"); }
[/]           { printf("除号\n"); }
[(]           { printf("左括号\n"); }
[)]           { printf("右括号\n"); }
[ \t\n]       { /* 忽略空白字符 */ }
.             { printf("未知字符: %s\n", yytext); }
%%

int main() {
    yylex();
    return 0;
}

int yywrap() {
    return 1;
}

编译和运行：

flex lexer.l
gcc lex.yy.c -o lexer
./lexer

输入输出示例：

输入：

123 + abc * (456 - def)

输出：

数字: 123
加号
标识符: abc
乘号
左括号
数字: 456
减号
标识符: def
右括号

代码示例

基于表格的词法分析器实现

以下是一个简单的基于表格的词法分析器实现，用于识别数字、标识符和基本运算符：

class TableBasedLexer:
    def __init__(self):
        # 状态定义
        self.STATE_START = 0
        self.STATE_NUMBER = 1
        self.STATE_IDENTIFIER = 2
        self.STATE_PLUS = 3
        self.STATE_MINUS = 4
        self.STATE_MULTIPLY = 5
        self.STATE_DIVIDE = 6
        self.STATE_LPAREN = 7
        self.STATE_RPAREN = 8
        self.STATE_ERROR = 9
        
        # 转移表：[当前状态][字符类型] = 下一状态
        self.transition_table = {
            self.STATE_START: {
                'digit': self.STATE_NUMBER,
                'letter': self.STATE_IDENTIFIER,
                '+': self.STATE_PLUS,
                '-': self.STATE_MINUS,
                '*': self.STATE_MULTIPLY,
                '/': self.STATE_DIVIDE,
                '(': self.STATE_LPAREN,
                ')': self.STATE_RPAREN,
                'whitespace': self.STATE_START,
                'other': self.STATE_ERROR
            },
            self.STATE_NUMBER: {
                'digit': self.STATE_NUMBER,
                'letter': self.STATE_ERROR,
                '+': self.STATE_START,
                '-': self.STATE_START,
                '*': self.STATE_START,
                '/': self.STATE_START,
                '(': self.STATE_START,
                ')': self.STATE_START,
                'whitespace': self.STATE_START,
                'other': self.STATE_ERROR
            },
            self.STATE_IDENTIFIER: {
                'digit': self.STATE_IDENTIFIER,
                'letter': self.STATE_IDENTIFIER,
                '+': self.STATE_START,
                '-': self.STATE_START,
                '*': self.STATE_START,
                '/': self.STATE_START,
                '(': self.STATE_START,
                ')': self.STATE_START,
                'whitespace': self.STATE_START,
                'other': self.STATE_ERROR
            },
            # 对于运算符和括号，直接返回Token
            self.STATE_PLUS: {'default': self.STATE_START},
            self.STATE_MINUS: {'default': self.STATE_START},
            self.STATE_MULTIPLY: {'default': self.STATE_START},
            self.STATE_DIVIDE: {'default': self.STATE_START},
            self.STATE_LPAREN: {'default': self.STATE_START},
            self.STATE_RPAREN: {'default': self.STATE_START},
            # 错误状态
            self.STATE_ERROR: {'default': self.STATE_START}
        }
        
        # 动作表：状态 -> (是否接受, Token类型)
        self.action_table = {
            self.STATE_START: (False, None),
            self.STATE_NUMBER: (True, 'NUMBER'),
            self.STATE_IDENTIFIER: (True, 'IDENTIFIER'),
            self.STATE_PLUS: (True, 'PLUS'),
            self.STATE_MINUS: (True, 'MINUS'),
            self.STATE_MULTIPLY: (True, 'MULTIPLY'),
            self.STATE_DIVIDE: (True, 'DIVIDE'),
            self.STATE_LPAREN: (True, 'LPAREN'),
            self.STATE_RPAREN: (True, 'RPAREN'),
            self.STATE_ERROR: (False, 'ERROR')
        }
    
    def get_char_type(self, char):
        """获取字符类型"""
        if char.isdigit():
            return 'digit'
        elif char.isalpha():
            return 'letter'
        elif char in '+-*/()':
            return char
        elif char.isspace():
            return 'whitespace'
        else:
            return 'other'
    
    def tokenize(self, input_string):
        """将输入字符串 tokenize"""
        tokens = []
        current_state = self.STATE_START
        current_lexeme = ''
        
        for char in input_string:
            char_type = self.get_char_type(char)
            
            # 获取下一状态
            if char_type in self.transition_table[current_state]:
                next_state = self.transition_table[current_state][char_type]
            elif 'default' in self.transition_table[current_state]:
                next_state = self.transition_table[current_state]['default']
            else:
                next_state = self.STATE_ERROR
            
            # 处理状态转移
            if current_state == self.STATE_START and char_type == 'whitespace':
                # 忽略初始空白
                continue
            elif current_state != self.STATE_START and self.action_table[current_state][0]:
                # 如果当前状态是接受状态，返回Token
                tokens.append((self.action_table[current_state][1], current_lexeme))
                current_lexeme = ''
                current_state = self.STATE_START
                # 重新处理当前字符
                char_type = self.get_char_type(char)
                if char_type in self.transition_table[current_state]:
                    next_state = self.transition_table[current_state][char_type]
                elif 'default' in self.transition_table[current_state]:
                    next_state = self.transition_table[current_state]['default']
                else:
                    next_state = self.STATE_ERROR
            
            # 更新当前状态和词素
            current_state = next_state
            if char_type != 'whitespace':
                current_lexeme += char
        
        # 处理最后一个Token
        if current_state != self.STATE_START and self.action_table[current_state][0]:
            tokens.append((self.action_table[current_state][1], current_lexeme))
        
        return tokens

# 测试代码
def test_table_based_lexer():
    lexer = TableBasedLexer()
    test_input = "123 + abc * (456 - def)"
    tokens = lexer.tokenize(test_input)
    
    print("输入:", test_input)
    print("Token化结果:")
    for token_type, lexeme in tokens:
        print(f"{token_type}: {lexeme}")

if __name__ == "__main__":
    test_table_based_lexer()

运行结果：

输入: 123 + abc * (456 - def)
Token化结果:
NUMBER: 123
PLUS: +
IDENTIFIER: abc
MULTIPLY: *
LPAREN: (
NUMBER: 456
MINUS: -
IDENTIFIER: def
RPAREN: )

自测题

1. 基于表格的词法分析器由哪几部分组成？
2. 转移表和动作表的作用分别是什么？
3. 表压缩技术有哪些？它们的目的是什么？
4. 常见的词法分析器生成工具有哪些？
5. 请设计一个简单的转移表，用于识别以下Token：
   • 布尔值：true、false
   • 赋值运算符：=
   • 比较运算符：==、!=、<、>、<=、>=

小结

本集介绍了基于表格的词法分析器的设计与实现，包括：

• 基于表格的词法分析器的基本原理和组成部分
• 转移表和动作表的构建方法
• 表压缩技术的应用
• 词法分析器生成工具的使用
• 通过具体示例展示了基于表格的词法分析器的实现
• 提供了一个完整的Python实现示例

基于表格的词法分析器是一种系统、高效的词法分析方法，特别适合复杂的词法分析任务。通过使用生成工具，可以大大简化词法分析器的开发过程，提高开发效率和代码质量。

下集预告

下一集将介绍词法分析器生成器的原理，包括：

• 正则表达式解析
• NFA构造
• DFA转换
• 代码生成
• Flex/Lex的工作原理

参考资料

1. 《编译原理》（龙书），Alfred V. Aho等著
2. 《现代编译原理》，Andrew W. Appel著
3. Flex用户手册
4. 《编译器设计》，Keith D. Cooper等著
5. Ply文档：https://www.dabeaz.com/ply/