LEX 和 YACC 教程.pdf

### LEX 和 YACC 教程 #### 概览 本教程主要介绍如何利用 LEX 和 YACC 这两种工具来构建编译器的前端部分。LEX 被用于生成词法分析器（扫描器），而 YACC 则用于生成解析器。这两种工具在编译原理领域具有重要的地位，广泛应用于各种语言的编译器开发。 #### LEX 与 YACC 的基本概念 - **LEX**: LEX 是一个词法分析器生成器，它的主要作用是从源代码中识别出一个个有意义的词汇单元（例如关键字、标识符等），并将其传递给解析器。LEX 可以生成 C 语言中的词法分析器。 - **YACC**: YACC（又称为 Yet Another Compiler-Compiler）是一个语法分析器生成器，它基于给定的上下文无关文法生成解析器。该解析器负责识别语法结构，并执行相应的操作，如生成中间代码等。 - **Flex** 和 **Bison**: Flex 是一个免费的 LEX 替代品，而 Bison 是一个为 GNU 项目编写的免费解析器生成程序，可以替代 YACC。 #### Scanner 和 Parser 的工作原理 - **Scanner（扫描器）**: 它负责读取源代码，根据定义的规则识别出一个个词汇单元，并将其转换为符号表中的 token。 - **Parser（解析器）**: 解析器接收来自扫描器的 token，根据预定义的文法规则进行语法分析，确定源代码是否符合语法规则，同时执行相应的语义动作。 #### Lex 规格说明 - **LEX 规格文件**：LEX 规格文件通常扩展名为 .l，其结构包含三个主要部分： - **定义部分**：定义全局变量、原型和注释。 - **规则部分**：定义如何扫描以及对每个 token 应采取的动作。 - **辅助子程序**：这部分是 C 语言的用户自定义代码，将会被嵌入到生成的词法分析器中。 - **定义部分示例**： ```c %{ #include "zcalc.tab.h" #include "zcalc.h" #include <math.h> // 用户自定义的头文件 %} ``` 此部分将包含所需的头文件和其他必要的定义。 - **规则部分示例**： ```c %% // 规则部分 [1-9][0-9]* { yylval.dval = atoi (yytext); return NUMBER; } ``` 这里的规则定义了一个非零数字后跟任意数量的数字，这样的字符串被视为一个整数（`NUMBER` 类型的 token）。 - **注意事项**： - LEX 匹配最长匹配原则：对于输入 `abc`，如果规则定义了 `[a-z]+`，那么整个 `abc` 将被视为一个 token。 - 使用第一条适用的规则：对于输入 `post`，如果存在两条规则，一条是 `"post"`，另一条是 `[a-zA-Z]+`，那么只有第一条规则会被应用，即输出 `Hello,`。 #### Yacc 规格说明 - **Yacc 规格文件**：Yacc 规格文件通常扩展名为 .y，其结构包含文法定义和动作定义。 - **文法定义**：用于描述语言的结构，如函数调用、表达式等。 - **动作定义**：定义当文法匹配成功时应执行的操作。 #### 构建流程 1. **编写 LEX 规格文件**：定义词法分析器的行为。 2. **运行 LEX**：生成词法分析器源码 `lex.yy.c`。 3. **编写 YACC 规格文件**：定义语法分析器的行为。 4. **运行 YACC**：生成语法分析器源码 `name.tab.c`。 5. **编译词法分析器和语法分析器**：生成可执行文件。 6. **测试**：运行编译器前端，检查其功能是否正确。 通过上述步骤，我们可以有效地利用 LEX 和 YACC 来构建一个功能强大的编译器前端。这两种工具不仅能够帮助我们理解编译原理，还能在实际项目中发挥重要作用。