编程语言编译中的词法分析与解析技术

# 编程语言编译中的词法分析与解析技术 ## 1. 词法分析概述 词法分析器在编译过程中扮演着重要角色，它读取源文本并生成词法单元（tokens），这些词法单元是语言的基本词法单位。例如，表达式 `*ptr = 56;` 包含 10 个字符，但可划分为 5 个词法单元：`*`、`ptr`、`=`、`56` 和 `;`。对于每个词法单元，词法分析器会返回其词法单元代码和零个或多个关联值。单字符词法单元（如运算符和分隔符）的代码就是字符本身，而由一个或多个字符组成的词法单元（如标识符和常量）则使用定义的常量作为代码。 词法分析器还会跟踪每个词法单元的源坐标，这些坐标包括文件名、行号和行内字符索引，用于定位错误和记录符号定义位置。由于词法分析可能占据编译器执行时间的一半，因此速度至关重要。为了提高速度，词法分析器通常被分为两个紧密耦合的模块：输入模块和识别模块。 ## 2. 输入模块 输入模块（`input.c`）负责将输入以大块形式读入缓冲区，而识别模块（`lex.c`）则检查字符以识别词法单元。在大多数编程语言中，输入按行组织，尽管理论上行长没有限制，但实际中通常会有限制。并且，在大多数语言中，词法单元不能跨越多行，因此确保在检查时完整的行都在内存中可以简化词法分析。 输入模块导出了几个指针，允许直接访问输入缓冲区： ```c extern unsigned char *cp; extern unsigned char *limit; ``` `cp` 指向当前输入字符，`limit` 指向输入缓冲区中字符末尾的下一个字符，且 `*limit` 总是换行符，作为哨兵。这种设计使得大多数输入字符通过 `*cp` 访问，减少了字符移动，只有标识符（不包括关键字）和字符串字面量会被复制到永久存储中。 输入模块还导出了其他全局变量： ```c extern int infd; extern char *firstfile; extern char *file; extern char *line; extern int lineno; ``` `infd` 是输入文件描述符，`file` 是当前输入文件名，`line` 是当前行的起始位置，`lineno` 是当前行号。 输入缓冲区的大小由 `BUFSIZE` 定义，未消费行尾的最大字符数由 `MAXLINE` 定义： ```c #define MAXLINE 512 #define BUFSIZE 4096 ``` `bsize` 变量用于编码三种不同的输入状态：小于 0 表示未读取输入或发生读取错误，等于 0 表示到达输入末尾，大于 0 表示刚刚读取了 `bsize` 个字符。 输入模块的初始化函数 `inputinit` 会初始化输入变量并填充缓冲区： ```c void inputinit() { limit = cp = &buffer[MAXLINE + 1]; bsize = -1; lineno = 0; file = NULL; fillbuf(); nextline(); } ``` `nextline` 函数在读取到换行符时被调用，它会将 `cp` 推进到行中的第一个非空白字符。如果在填充缓冲区后 `cp` 仍然等于 `limit`，则表示到达文件末尾。 `fillbuf` 函数负责缓冲区管理和实际输入操作： ```c void fillbuf() { if (bsize == 0) return; if (cp >= limit) cp = &buffer[MAXLINE + 1]; else move the tail portion; bsize = read(infd, &buffer[MAXLINE + 1], BUFSIZE); if (bsize < 0) { error("read error\n"); exit(1); } limit = &buffer[MAXLINE + 1 + bsize]; *limit = '\n'; } ``` 如果输入缓冲区为空，`cp` 会被重置指向第一个新字符；否则，未消费的尾字符会被移动到缓冲区前面，以便与后续读取的字符连接。 ## 3. 识别词法单元 识别词法单元有两种主要技术：构建有限自动机或手动编写临时识别器。大多数编程语言的词法结构可以用正则表达式描述，这些表达式可用于构建确定性有限自动机来识别和返回词法单元。例如，LEX 程序可以根据正则表达式生成自动机和相应的解释程序。然而，对于大多数语言，手动构建词法分析器通常更简单、更高效。 在 C 语言中，词法单元可分为六类，由以下 EBNF 语法定义： - 关键字 - 标识符 - 常量 - 字符串字面量 - 运算符 - 标点符号 词法分析器导出了两个函数和四个变量： ```c extern int getchr ARGS((void)); extern int gettok ARGS((void)); extern int t; extern char *token; extern Symbol tsym; extern Coordinate src; ``` `gettok` 函数返回下一个词法单元，`getchr` 函数返回但不消费下一个非空白字符。`gettok` 返回的值包括字符本身（对于单字符词法单元）、枚举常量（对于关键字）和其他定义的常量。 `gettok` 函数通过检查词法单元的第一个字符来识别词法单元，并消费组成词法单元的后续字符。对于某些词法单元，这些字符由 `map` 定义的集合确定。`map[c]` 是一个掩码，将字符 `c` 分类为六个集合之一： ```c enum { BLANK = 01, NEWLINE = 02, LETTER = 04, DIGIT = 010, HEX = 020, OTHER = 040 }; static unsigned char map[256] { (map initializer) }; ``` `gettok` 函数是一个较大的函数，通过 `switch` 语句根据词法单元的第一个字符进行分类处理： ```c int gettok() { for (; ;) { register unsigned char *rep; skip white space; if (limit - rep < MAXTOKEN) { cp = rep; fillbuf(); rep = cp; } src.file = file; src.x = (char *)rep - line; src.y = lineno; cp = rep + 1; switch (*rep++) { gettok cases; default: if ((map[cp[-1]] & BLANK) == 0) illegal character; } } } ``` `gettok` 函数在识别词法单元时会跳过空白字符，并检查输入缓冲区中是否至少有一个词法单元。如果不足，会调用 `fillbuf` 函数填充缓冲区。 ### 3.1 识别关键字 C 语言中有 28 个关键字，如 `auto`、`double`、`int` 等。关键字的识别通过硬编码的决策树进行，比查表法更快且几乎同样简单。例如，对于以 `i` 开头的关键字： ```c case 'i': if (rcp[0] == 'f' && !(map[rcp[1]] & (DIGIT | LETTER))) { cp = rep + 1; return IF; } if (rcp[0] == 'n' && rcp[1] == 't' && !(map[rcp[2]] & (DIGIT | LETTER))) { cp = rep + 2; tsym = inttype->u.sym; return INT; } goto id; ``` 如果是 `if` 或 `int`，会更新 `cp` 并返回相应的词法单元代码；否则，该词法单元是标识符。 ### 3.2 识别标识符 标识符的语法为 `nondigit { nondigit | digit }`。代码在识别标识符时，需要处理可能跨多个输入缓冲区的长标识符。例如： ```c case 'h': case 'j': case 'k': case 'm': case 'n': case 'p': case 'q': case 'x': case 'y': case 'z': case 'A': case 'B': case '(': case 'D': case 'E': case 'G': case 'H': case 'I': case 'J': case 'K': case 'M': case 'N': case 'O': case 'P': cas ```