lex & yacc

### Lex与Yacc：构建编译器的紧凑指南 #### 引言 在1975年之前，编写编译器是一项极其耗时的工作。随着Lesk和Johnson分别于1975年发表了关于Lex与Yacc的文章后，这两款工具极大地简化了编译器的开发过程。本篇文章将详细介绍Lex与Yacc的基本理论、实践应用以及如何利用它们构建一个复杂的计算器，并最终将其转换为针对栈式机器的编译器。 #### Lex：词法分析器生成器 **理论** 1. **定义与功能**： - **Lex** 是一种词法分析器生成器，它能够根据用户提供的规则自动生成词法分析器。 - 词法分析器的主要任务是从输入流中识别出有意义的符号（例如关键字、标识符、操作符等），并把这些符号传递给解析器进行进一步处理。 - Lex的规则由正则表达式组成，这些规则定义了如何从输入文本中提取特定的符号。 2. **工作原理**： - 用户提供一系列的正则表达式和相应的动作代码。 - Lex程序读取这些规则并生成C语言源代码，该源代码实现了一个词法分析器函数。 - 当调用这个函数时，它会从输入流中读取字符，并按照定义好的规则进行匹配。 - 当找到匹配项时，相应的动作代码会被执行，通常这些动作代码会返回一个代表识别到的符号的整数值。 **实践** 1. **基本语法**： - 规则格式：`<pattern> { <action> }` - 示例规则：`"int" { return INT; }` 表示当识别到“int”字符串时，返回INT值。 - 可以使用多种正则表达式来定义模式，如 `"[a-zA-Z_][a-zA-Z_0-9]*"` 用于匹配标识符。 2. **高级特性**： - **嵌入C代码**：可以在Lex文件中嵌入C语言代码，这些代码会在生成的词法分析器中出现。 - **状态管理**：通过使用不同的状态可以更灵活地处理不同的输入模式。 #### Yacc：语法分析器生成器 **理论** 1. **定义与功能**： - **Yacc** 是一种语法分析器生成器，它可以根据用户提供的文法规则自动生成语法分析器。 - 语法分析器的作用是检查输入是否符合定义好的文法，并生成抽象语法树（AST）或执行其他相关的动作。 - Yacc基于上下文无关文法（CFG）。 2. **工作原理**： - 用户提供一系列的文法规则和相应的动作代码。 - Yacc读取这些规则并生成C语言源代码，该源代码实现了一个递归下降的语法分析器。 - 分析器读取词法分析器产生的符号，并根据文法规则判断输入是否有效。 - 当识别到有效的输入时，相应的动作代码会被执行。 **实践** 1. **基本语法**： - 规则格式：`<non-terminal> : <symbol1> <symbol2> ... { <action> }` - 示例规则：`expr : expr '+' term { $$ = $1 + $3; }` 表示两个expr和一个term之间用加号连接时，结果为第一个expr加上term的结果。 - 使用 `$<n>` 来引用规则中的各个符号。 2. **高级特性**： - **递归**：可以通过递归来定义复杂的文法结构。 - **错误处理**：可以通过特殊规则处理输入中出现的错误情况。 - **继承属性**：允许父节点将某些信息传递给子节点。 #### 构建计算器 **描述** - 在本书的后续部分，作者将逐步介绍如何使用Lex与Yacc构建一个简单的计算器。 - 计算器支持常规的算术运算以及if-else和while等控制语句。 - 最终，通过简单的修改，这个计算器可以被转化为一个栈式机器的编译器。 **包含文件** - 需要包括必要的头文件，如 `<stdio.h>` 和 `<stdlib.h>`，以支持基本的输入输出操作。 **Lex输入** - 定义了一组规则，用于识别数字、操作符和其他关键字。 **Yacc输入** - 定义了一组文法规则，用于处理计算器的操作逻辑，包括算术运算、条件语句和循环语句。 **解释器与编译器** - 解释器直接执行计算表达式，而编译器则生成中间代码或目标代码。 #### 总结 Lex与Yacc是构建编译器的强大工具，通过学习它们的基本理论和实践应用，开发者可以高效地构建出功能强大的编译器。本文档提供了从简单计算器到栈式机器编译器的完整构建过程，帮助读者深入理解这两个工具的工作原理及其应用场景。