第51集：Lex / Flex 工具入门

学习目标

  • 了解 Lex 和 Flex 工具的基本概念和历史
  • 掌握 Lex/Flex 源文件的基本结构
  • 学会编写简单的 Lex/Flex 规则
  • 理解 Lex/Flex 的工作原理
  • 能够使用 Flex 生成词法分析器

1. Lex 和 Flex 简介

1.1 什么是 Lex？

Lex（词法分析器生成器）是一个用于生成词法分析器的工具，由 Mike Lesk 和 Eric Schmidt 于 1975 年开发。它接受一个包含正则表达式和对应动作的规范文件，生成一个词法分析器，该分析器可以识别输入文本中的词法单元。

1.2 什么是 Flex？

Flex（Fast Lexical Analyzer Generator）是 Lex 的一个开源替代品，由 Vern Paxson 于 1987 年开发。它是 Lex 的超集，提供了更多功能和更好的性能，是目前最常用的词法分析器生成器之一。

1.3 Lex/Flex 的应用场景

  • 编译器和解释器的词法分析阶段
  • 文本处理工具
  • 配置文件解析器
  • 数据提取工具
  • 模式匹配工具

2. Lex/Flex 源文件结构

Lex/Flex 源文件通常分为三个部分，用 %% 分隔：

定义部分
%%
规则部分
%%
用户代码部分

2.1 定义部分

定义部分包含：

  • 宏定义（正则表达式的别名）
  • 包含文件
  • 全局变量和函数声明

示例：

%{
#include <stdio.h>
int line_count = 1;
%}

DIGIT [0-9]
LETTER [a-zA-Z]
ID {LETTER}({LETTER}|{DIGIT})*
NUMBER {DIGIT}+

2.2 规则部分

规则部分包含一系列的模式-动作对，格式为：

模式 { 动作 }

其中：

  • 模式是一个正则表达式
  • 动作是当匹配到该模式时执行的 C 代码

示例：

{ID} { printf("标识符: %s\n", yytext); }
{NUMBER} { printf("数字: %s\n", yytext); }
[ \t]+ { /* 跳过空白符 */ }
\n { line_count++; }

2.3 用户代码部分

用户代码部分包含：

  • 主函数
  • 辅助函数
  • 其他用户定义的代码

示例：

int main() {
    yylex();
    printf("总行数: %d\n", line_count);
    return 0;
}

int yywrap() {
    return 1;
}

3. Flex 的工作原理

Flex 的工作原理可以分为以下几个步骤：

  1. 读取源文件：Flex 读取用户编写的 .l 文件
  2. 解析规则：解析文件中的正则表达式和动作
  3. 构建 NFA：为所有正则表达式构建一个非确定有限自动机 (NFA)
  4. 转换为 DFA：使用子集构造算法将 NFA 转换为确定有限自动机 (DFA)
  5. 最小化 DFA：使用 Hopcroft 算法最小化 DFA
  6. 生成代码：生成 C 代码，实现词法分析器
  7. 编译链接：用户编译生成的代码并链接到自己的程序中

4. 编写第一个 Flex 程序

4.1 安装 Flex

在不同系统上安装 Flex：

  • Linux/Unix：sudo apt-get install flex (Debian/Ubuntu) 或 sudo yum install flex (CentOS/RHEL)
  • macOS：brew install flex
  • Windows：可以通过 MinGW 或 Cygwin 安装

4.2 编写简单的词法分析器

创建一个名为 simple.l 的文件：

%{
#include <stdio.h>
%}

%%
[0-9]+ { printf("数字: %s\n", yytext); }
[a-zA-Z]+ { printf("标识符: %s\n", yytext); }
[+\-*/] { printf("运算符: %c\n", yytext[0]); }
[ \t\n] { /* 跳过空白符 */ }
. { printf("未知字符: %c\n", yytext[0]); }
%%

int main() {
    printf("输入一些文本:\n");
    yylex();
    return 0;
}

int yywrap() {
    return 1;
}

4.3 编译和运行

  1. 使用 Flex 生成词法分析器代码：

    flex simple.l

    这将生成一个名为 lex.yy.c 的文件。

  2. 编译生成的代码：

    gcc lex.yy.c -o lexer -lfl

  3. 运行词法分析器：

    ./lexer

  4. 输入一些文本，例如：

    x = 10 + y

  5. 查看输出：

    标识符: x
运算符: =
数字: 10
运算符: +
标识符: y

5. Flex 中的特殊变量和函数

5.1 特殊变量

  • yytext：指向当前匹配的文本
  • yyleng：当前匹配的文本长度
  • yyin：输入文件指针，默认为 stdin
  • yyout：输出文件指针，默认为 stdout

5.2 特殊函数

  • yylex()：开始词法分析
  • yywrap()：当输入结束时调用，返回 1 表示结束
  • yyless(n)：将最后 n 个字符放回到输入流中
  • yymore()：将当前匹配的文本与下一次匹配的文本连接起来
  • yyinput()：读取一个字符
  • unput(c)：将一个字符放回到输入流中

6. 实战案例：简单计算器的词法分析器

6.1 需求分析

我们需要为一个简单的计算器编写词法分析器，能够识别：

  • 数字（整数和小数）
  • 运算符（+, -, *, /, ^）
  • 括号（(, )）
  • 空白符（需要跳过）

6.2 实现代码

创建 calculator.l 文件：

%{
#include <stdio.h>

// 词法单元类型
enum TokenType {
    NUMBER,    // 数字
    PLUS,      // +
    MINUS,     // -
    MULTIPLY,  // *
    DIVIDE,    // /
    POWER,     // ^
    LPAREN,    // (
    RPAREN,    // )
    EOF_TOKEN  // 结束符
};

// 当前词法单元类型
enum TokenType current_token;
// 当前数字值
double current_value;

// 函数声明
void get_token();
void error();
%}

DIGIT [0-9]
NUMBER {DIGIT}+(\.{DIGIT}+)?

%%
{NUMBER} { 
    sscanf(yytext, "%lf", &current_value); 
    current_token = NUMBER; 
}
"+" { current_token = PLUS; }
"-" { current_token = MINUS; }
"*" { current_token = MULTIPLY; }
"/" { current_token = DIVIDE; }
"^" { current_token = POWER; }
"(" { current_token = LPAREN; }
")" { current_token = RPAREN; }
[ \t\n] { /* 跳过空白符 */ }
. { error(); }
%%

void get_token() {
    yylex();
}

void error() {
    fprintf(stderr, "词法错误: 未知字符 '%s'\n", yytext);
    exit(1);
}

int yywrap() {
    current_token = EOF_TOKEN;
    return 1;
}

int main() {
    printf("简单计算器词法分析器\n");
    printf("输入表达式: ");
    
    // 测试词法分析器
    while (1) {
        get_token();
        if (current_token == EOF_TOKEN) {
            break;
        }
        
        switch (current_token) {
            case NUMBER:
                printf("Token: NUMBER, Value: %lf\n", current_value);
                break;
            case PLUS:
                printf("Token: PLUS\n");
                break;
            case MINUS:
                printf("Token: MINUS\n");
                break;
            case MULTIPLY:
                printf("Token: MULTIPLY\n");
                break;
            case DIVIDE:
                printf("Token: DIVIDE\n");
                break;
            case POWER:
                printf("Token: POWER\n");
                break;
            case LPAREN:
                printf("Token: LPAREN\n");
                break;
            case RPAREN:
                printf("Token: RPAREN\n");
                break;
        }
    }
    
    printf("词法分析完成\n");
    return 0;
}

6.3 编译和运行

  1. 生成词法分析器代码：

    flex calculator.l

  2. 编译：

    gcc lex.yy.c -o calc_lexer -lfl

  3. 运行：

    ./calc_lexer

  4. 输入表达式，例如：

    3.14 * (2 + 3) ^ 2

  5. 查看输出：

    Token: NUMBER, Value: 3.140000
Token: MULTIPLY
Token: LPAREN
Token: NUMBER, Value: 2.000000
Token: PLUS
Token: NUMBER, Value: 3.000000
Token: RPAREN
Token: POWER
Token: NUMBER, Value: 2.000000

7. 自测题

  1. Flex 工具的主要作用是什么？

  2. Flex 源文件的三个部分是什么？

  3. 解释 yytext 和 yyleng 变量的作用。

  4. 如何在 Flex 中定义正则表达式的别名？

  5. 编写一个简单的 Flex 程序，识别并统计输入文本中的单词数量。

8. 小结

在本集中，我们介绍了 Lex 和 Flex 工具的基本概念、工作原理和使用方法。Flex 是一个强大的词法分析器生成器，它可以根据用户定义的正则表达式和动作，自动生成词法分析器代码。通过 Flex，我们可以快速开发出高效、可靠的词法分析器，为编译器的前端部分打下基础。

9. 下集预告

下一集将介绍 语法分析的基本概念，包括上下文无关文法、推导、句型和句子等概念，为我们后续学习语法分析器的设计和实现做准备。

10. 参考资料

  1. Flex 官方文档：https://westes.github.io/flex/manual/
  2. 《编译原理》（龙书），Alfred V. Aho 等著
  3. 《Flex 与 Bison》，John Levine 著
  4. 正则表达式教程：https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Guide/Regular_Expressions
« 上一篇 DFA 的最小化 下一篇 » 语法分析的基本概念
↑