什么是 Lex 和 Yacc？

想象一下你如何理解一句话,"2 + 3 * 4"。

1. 第一步：识别单词，你首先会认出 "2"、"+"、"*"、"4" 这些独立的、有意义的单元，这个过程就是词法分析。
2. 第二步：理解语法结构，然后你会根据数学规则，知道乘法的优先级高于加法，所以先算 "3 * 4"，再算 "2 + 12"，这个过程就是语法分析。

Lex 和 Yacc 就是用来完成这两步工作的经典工具：

• Lex (Lexer Generator)：词法分析器生成器，它根据你定义的规则（哪些是数字，哪些是运算符等），生成一个名为 lex.yy.c 的 C 语言文件，这个文件包含一个可以识别输入文本中“单词”（称为 Token）的函数 yylex()。
• Yacc (Yet Another Compiler-Compiler)：语法分析器生成器，它根据你定义的语法规则（表达式如何组合），生成一个名为 y.tab.c 的 C 语言文件，这个文件包含一个可以解析 Token 流并检查其是否符合语法的函数 yyparse()。

工作流程：

[用户输入]  -->  [Lex]  -->  [Token流]  -->  [Yacc]  -->  [抽象语法树]  -->  [执行/输出]
   (e.g., "2+3")      (e.g., NUMBER, PLUS, NUMBER)       (e.g., 2+3的结构)

核心概念

Lex (词法分析)

Lex 的输入是一个 .l 文件，定义了模式和动作。

• 模式：通常是一个正则表达式，用来匹配输入文本中的一个“单词”。
• 动作：当某个模式被匹配到时，C 语言代码片段被执行。

基本结构：

/* 定义段 */
%{
    #include "y.tab.h"  // 包含Yacc生成的头文件，定义Token类型
    int yyerror(char *s); // 声明错误处理函数
%}
/* 规则段 */
数字  [0-9]+
运算符 [\+\-\*/\(\)]
%%
规则1  { action1; }
规则2  { action2; }
...
/* 用户代码段 */
// 主函数等

常用宏和函数：

• yylex()：由 Yacc 调用，开始词法分析。
• yytext：一个字符指针，指向当前匹配到的文本。
• yylval：一个联合体，用于将匹配到的文本（如 "123"）转换成一个有意义的值（如整数 123）传递给 Yacc。
• return NUMBER;：向 Yacc 返回一个 Token 类型。

Yacc (语法分析)

Yacc 的输入是一个 .y 文件，定义了语法规则和语义动作。

• 语法规则：定义了 Token 如何组合成更大的结构，类似 BNF (巴科斯-瑙尔范式)。
• 语义动作：当一个语法规则被成功匹配时，执行的 C 语言代码，通常用于构建抽象语法树 或直接计算结果。

基本结构：

/* 定义段 */
%{
    #include <stdio.h>
    extern int yylex();
    extern int yyparse();
    void yyerror(char *s);
%}
/* Token定义段 */
%token NUMBER
%token PLUS MINUS TIMES DIVIDE LPAREN RPAREN
/* 语法规则段 */
%%
程序: 表达式 { printf("结果: %d\n", $1); };
表达式: 表达式 PLUS 项    { $$ = $1 + $3; }
      | 表达式 MINUS 项   { $$ = $1 - $3; }
      | 项               { $$ = $1; }
      ;
项: 项 TIMES 因子   { $$ = $1 * $3; }
  | 项 DIVIDE 因子  { $$ = $1 / $3; }
  | 因子           { $$ = $1; }
  ;
因子: NUMBER        { $$ = $1; }
     | LPAREN 表达式 RPAREN { $$ = $2; }
     ;
%%
/* 用户代码段 */
// 主函数和错误处理函数

核心概念：

• %token：定义 Token 的名称。
• 规则: 规则体 { C代码 };：定义一条语法规则。
• $1, $2, $3, ...：代表规则体中各个子表达式的值（从左到右，从1开始）。
• 代表当前规则的值。
• yyparse()：启动语法分析器，它会调用 yylex() 来获取 Token。

动手实践：构建一个简单的计算器

我们的目标是解析形如 2 + 3 * 4 的表达式并计算结果。

第1步：编写 Lex 文件 (calc.l)

这个文件负责识别数字和运算符。

/* calc.l */
%{
    #include "y.tab.h"
    void yyerror(char *);
%}
/* 定义数字的正则表达式 */
DIGIT    [0-9]
NUMBER   {DIGIT}+
/* 忽略空白字符（空格、制表符、换行） */
[ \t\n]   ;
%%
/* 规则和动作 */
{NUMBER} {
    // 将匹配到的字符串转换为整数，并存入yylval
    yylval = atoi(yytext);
    return NUMBER;
}
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return DIVIDE; }
"(" { return LPAREN; }
")" { return RPAREN; }
/* 其他字符视为错误 */
.   { yyerror("非法字符"); return 0; }
%%
/* 用户代码：可以留空，也可以放lex的额外C代码 */

解释：

• NUMBER 规则匹配一个或多个数字。atoi(yytext) 将字符串（如 "123"）转换为整数（123），并存入 yylval。
• 每个运算符都返回一个对应的 Token 常量（如 PLUS）。
• [ \t\n]+ ; 告诉 Lex 忽略所有空白字符，不进行任何操作。
• 匹配任何其他字符，我们调用 yyerror 报告错误。

第2步：编写 Yacc 文件 (calc.y)

这个文件定义了表达式的语法和计算逻辑。

/* calc.y */
%{
    #include <stdio.h>
    int yylex();
    void yyerror(char *s);
%}
/* Token定义 */
%token NUMBER
%token PLUS MINUS TIMES DIVIDE
%token LPAREN RPAREN
/* 运算符优先级和结合性（从低到高） */
%left PLUS MINUS
%left TIMES DIVIDE
%%
/* 语法规则 */
计算器程序: 表达式 { printf("计算结果: %d\n", $1); }
          ;
表达式: 表达式 PLUS 项    { $$ = $1 + $3; }
      | 表达式 MINUS 项   { $$ = $1 - $3; }
      | 项               { $$ = $1; }
      ;
项: 项 TIMES 因子   { $$ = $1 * $3; }
  | 项 DIVIDE 因子  { $$ = $1 / $3; }
  | 因子           { $$ = $1; }
  ;
因子: NUMBER        { $$ = $1; }
     | LPAREN 表达式 RPAREN { $$ = $2; }
     ;
%%
/* 错误处理函数 */
void yyerror(char *s) {
    fprintf(stderr, "错误: %s\n", s);
}
/* 主函数 */
int main(void) {
    printf("请输入表达式 ( 2+3*4), 按 Ctrl+D 结束:\n");
    yyparse();
    return 0;
}

解释：

• %left 定义了运算符的优先级和结合性。PLUS MINUS 在同一行，优先级相同，且是左结合。TIMES DIVIDE 在下一行，优先级更高。
• 表达式: 表达式 PLUS 项 { $$ = $1 + $3; }; 这条规则处理加法。$1 是左边的 表达式 的值，$3 是右边的 项 的值。 是整个规则的值，即它们的和。
• 因子: LPAREN 表达式 RPAREN 处理括号，将括号内的表达式值直接作为因子的值。
• yyerror 是 Yacc 在遇到语法错误时调用的函数。
• main 函数启动 yyparse()，开始整个解析过程。

第3步：编译和运行

1. 安装工具 (如果未安装):

   • Linux (Debian/Ubuntu): sudo apt-get install flex bison (Flex 是 Lex 的现代替代品，Bison 是 Yacc 的现代替代品，用法兼容)。
   • macOS (Homebrew): brew install flex bison

2. 生成 C 代码: 使用以下命令，Yacc 会生成 y.tab.c 和 y.tab.h，Lex 会生成 lex.yy.c。

   yacc -d calc.y   # -d 生成头文件 y.tab.h
   lex calc.l       # 生成 lex.yy.c

3. 编译和链接: 将生成的 C 文件和你的用户代码（如果有）一起编译成可执行文件。

   gcc y.tab.c lex.yy.c -o mycalc

4. 运行:

   ./mycalc

   交互示例:

   请输入表达式 ( 2+3*4), 按 Ctrl+D 结束:
   2+3*4
   计算结果: 14
   10 / 2 + 3
   计算结果: 8
   (2+3)*4
   计算结果: 20

总结与进阶

• Lex 负责“认字”（词法分析），Yacc 负责“造句”（语法分析），它们配合默契，是构建编译器、解释器、配置文件解析器等复杂文本处理任务的利器。
• 进阶：
  • Flex/Bison：现代的替代品，功能更强大，错误处理更好，推荐使用它们。
  • 错误恢复：Yacc 提供了简单的错误恢复机制（如 error Token），但更复杂的错误恢复需要手动编写。
  • 抽象语法树：在更复杂的编译器中，Yacc 的语义动作通常不直接计算值，而是构建一个 AST，后续再对 AST 进行遍历和处理。
  • 调试：使用 yacc -v 可以生成一个 y.output 文件，里面包含了详细的语法分析过程，对于调试语法规则非常有用。

这份简明教程希望能帮助你快速入门 Lex 和 Yacc，多动手实践，尝试扩展这个计算器，比如增加幂运算(^)、支持浮点数等，你会很快掌握它们的精髓。