第86集：Yacc / Bison 入门

核心知识点讲解

什么是 Yacc？

Yacc（Yet Another Compiler Compiler）是一个经典的语法分析器生成工具，由Stephen C. Johnson在1975年为Unix系统开发。它的主要功能是根据用户定义的文法规则，自动生成对应的LALR(1)语法分析器。

Yacc的工作原理：

  1. 读取用户编写的文法规则文件（.y文件）
  2. 分析文法规则，构建LR分析表
  3. 生成C语言代码形式的语法分析器
  4. 编译生成的代码，得到最终的语法分析器

Yacc 文件结构

一个标准的Yacc文件通常分为三个部分，用%%分隔：

/* 第一部分：声明部分 */
%{
// C语言代码，会被直接复制到生成的文件中
// 通常包含头文件、全局变量、函数声明等
%}

// Yacc声明
// 包括token声明、优先级声明、结合性声明等

%%
/* 第二部分：文法规则部分 */
// 定义文法规则和对应的语义动作

%%
/* 第三部分：用户代码部分 */
// 额外的C语言代码，会被复制到生成的文件末尾
// 通常包含主函数、错误处理函数等

第一个 Yacc 程序

让我们创建一个简单的计算器例子，演示Yacc的基本使用：

/* 简单计算器的Yacc文件 */
%{
#include <stdio.h>
int yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token ADD SUB MUL DIV
%token EOL

%%

calc: /* 空规则 */
    | calc exp EOL { printf("结果: %d\n", $2); }
    ;

exp: NUMBER
    | exp ADD exp { $$ = $1 + $3; }
    | exp SUB exp { $$ = $1 - $3; }
    | exp MUL exp { $$ = $1 * $3; }
    | exp DIV exp { $$ = $1 / $3; }
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("简单计算器，输入表达式后按回车\n");
    return yyparse();
}

与 Lex 配合

Yacc通常与Lex（词法分析器生成工具）配合使用，形成完整的词法分析和语法分析系统：

  1. Lex负责将输入文本转换为token流
  2. Yacc负责分析token流，构建语法树，并执行语义动作

配合使用的步骤：

  1. 创建Lex文件（.l文件），定义词法规则
  2. 创建Yacc文件（.y文件），定义文法规则
  3. 编译步骤：
    lex calculator.l       # 生成 lex.yy.c
yacc -d calculator.y   # 生成 y.tab.c 和 y.tab.h
gcc -o calculator lex.yy.c y.tab.c

Lex文件示例：

/* 计算器的Lex文件 */
%{
#include "y.tab.h"
%}

%%

[0-9]+      { yylval = atoi(yytext); return NUMBER; }
"+"         { return ADD; }
"-"         { return SUB; }
"*"         { return MUL; }
"/"         { return DIV; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

实用案例分析

案例：简单表达式解析器

让我们扩展上面的计算器例子，添加更多功能：

  1. 支持括号
  2. 支持浮点数
  3. 更好的错误处理

改进后的Yacc文件：

/* 改进的计算器Yacc文件 */
%{
#include <stdio.h>
#include <stdlib.h>
double yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token ADD SUB MUL DIV
%token LPAREN RPAREN
%token EOL

%left ADD SUB
%left MUL DIV
%nonassoc UMINUS

%%

calc: /* 空规则 */
    | calc exp EOL { printf("结果: %g\n", $2); }
    | calc EOL     { /* 空行，忽略 */ }
    ;

exp: NUMBER
    | exp ADD exp { $$ = $1 + $3; }
    | exp SUB exp { $$ = $1 - $3; }
    | exp MUL exp { $$ = $1 * $3; }
    | exp DIV exp { $$ = $1 / $3; }
    | SUB exp %prec UMINUS { $$ = -$2; }
    | LPAREN exp RPAREN { $$ = $2; }
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("科学计算器，输入表达式后按回车\n");
    return yyparse();
}

改进后的Lex文件：

/* 改进的计算器Lex文件 */
%{
#include "y.tab.h"
%}

%%

[0-9]+(\.[0-9]+)?  { yylval = atof(yytext); return NUMBER; }
"+"         { return ADD; }
"-"         { return SUB; }
"*"         { return MUL; }
"/"         { return DIV; }
"("         { return LPAREN; }
")"         { return RPAREN; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

案例：简单语言解析器

让我们创建一个更复杂的例子，解析一种简单的编程语言，支持变量声明和赋值：

Yacc文件：

/* 简单语言的Yacc文件 */
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VARS 100

struct var {
    char name[32];
    int value;
} variables[MAX_VARS];

int var_count = 0;

int find_var(const char* name) {
    for (int i = 0; i < var_count; i++) {
        if (strcmp(variables[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

int get_var(const char* name) {
    int idx = find_var(name);
    if (idx == -1) {
        fprintf(stderr, "变量未定义: %s\n", name);
        return 0;
    }
    return variables[idx].value;
}

void set_var(const char* name, int value) {
    int idx = find_var(name);
    if (idx == -1) {
        if (var_count >= MAX_VARS) {
            fprintf(stderr, "变量数量超过限制\n");
            return;
        }
        strcpy(variables[var_count].name, name);
        variables[var_count].value = value;
        var_count++;
    } else {
        variables[idx].value = value;
    }
}

int yylex();
void yyerror(const char* s);
%}

%token NUMBER
%token IDENTIFIER
%token ASSIGN
%token SEMI
%token EOL

%%

program: /* 空规则 */
       | program statement EOL
       | program EOL
       ;

statement: declaration
         | assignment
         ;

declaration: IDENTIFIER SEMI { set_var($1, 0); printf("声明变量: %s\n", $1); }
           ;

assignment: IDENTIFIER ASSIGN expr SEMI { set_var($1, $3); printf("赋值: %s = %d\n", $1, $3); }
          ;

expr: NUMBER
    | IDENTIFIER { $$ = get_var($1); }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | '(' expr ')' { $$ = $2; }
    ;

%%

void yyerror(const char* s) {
    fprintf(stderr, "错误: %s\n", s);
}

int main() {
    printf("简单语言解析器\n");
    printf("支持变量声明和赋值，例如: x; x = 5 + 3;\n");
    return yyparse();
}

Lex文件：

/* 简单语言的Lex文件 */
%{
#include "y.tab.h"
#include <string.h>
%}

%%

[0-9]+      { yylval = atoi(yytext); return NUMBER; }
[a-zA-Z_][a-zA-Z0-9_]* { yylval = strdup(yytext); return IDENTIFIER; }
"="         { return ASSIGN; }
";"         { return SEMI; }
"+"         { return '+'; }
"-"         { return '-'; }
"*"         { return '*'; }
"/"         { return '/'; }
"("         { return '('; }
")"         { return ')'; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

代码优化建议

  1. 错误处理优化：

    • 提供更具体的错误信息，包括错误位置和预期的token
    • 实现错误恢复机制，使解析器在遇到错误后能够继续工作

  2. 性能优化：

    • 对于大型文法，可以使用Yacc的-v选项生成详细的分析报告，帮助识别和解决冲突
    • 合理设计文法规则，避免左递归和二义性

  3. 可维护性优化：

    • 将复杂的语义动作分离到单独的函数中
    • 使用注释清晰地说明文法规则的含义
    • 模块化设计，将不同功能的语法规则分组

总结

Yacc/Bison是强大的语法分析器生成工具，它们通过自动化生成语法分析器，大大简化了编译器前端的开发工作。本集我们学习了：

  1. Yacc/Bison的基本概念和工作原理
  2. Yacc文件的结构和语法
  3. 如何创建简单的计算器和语言解析器
  4. 如何与Lex配合使用，形成完整的词法分析和语法分析系统

通过这些知识，你已经可以开始构建自己的简单语言解析器了。在后续的课程中，我们将学习更多关于语法分析器生成器的高级特性，以及如何将它们应用到实际的编译器开发中。

« 上一篇 LALR(1)分析法 下一篇 » Yacc 语法规则
↑