第87集：Yacc 语法规则

核心知识点讲解

产生式写法

在Yacc中，产生式是定义文法规则的基本单位。产生式的基本语法如下：

非终结符: 产生式体1 { 语义动作1 }
         | 产生式体2 { 语义动作2 }
         | ...
         ;

其中：

  • 非终结符：文法中的非终结符号，通常用小写字母表示
  • 产生式体：由终结符和非终结符组成的序列
  • 语义动作：当该产生式被匹配时执行的C语言代码
  • **$$**：表示当前产生式的结果值
  • **$1, $2, ...**：表示产生式体中各个符号的值

语义值

Yacc使用一个特殊的变量yylval来传递词法单元的值，同时在语法规则中使用$$、$1等变量来传递语义值。

默认情况下，yylval是一个整型变量，但可以通过%union声明来自定义其类型：

%union {
    int int_val;
    double double_val;
    char* string_val;
    struct ast_node* ast_val;
}

%token <int_val> NUMBER
%token <string_val> IDENTIFIER
%type <double_val> expr
%type <ast_val> stmt

优先级和结合性

Yacc提供了声明运算符优先级和结合性的机制，以解决文法的二义性问题：

%left '+' '-'
%left '*' '/'
%right '^'
%nonassoc UMINUS

其中：

  • %left：左结合，如a + b + c解析为(a + b) + c
  • %right：右结合，如a ^ b ^ c解析为a ^ (b ^ c)
  • %nonassoc：不可结合，如a &lt; b &lt; c是不合法的
  • 优先级：声明的顺序决定优先级，后面的声明优先级更高

%prec 声明

%prec声明用于为产生式指定优先级，通常用于处理一元运算符：

expr: '-' expr %prec UMINUS { $$ = -$2; }

这里，一元减号的优先级被指定为与UMINUS相同。

实用案例分析

案例：表达式解析器（带优先级）

让我们创建一个支持运算符优先级和结合性的表达式解析器：

/* 带优先级的表达式解析器 */
%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

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

%union {
    double val;
}

%token <val> NUMBER
%token ADD SUB MUL DIV POW
%token LPAREN RPAREN
%token EOL

%left ADD SUB
%left MUL DIV
%right POW
%nonassoc UMINUS

%type <val> expr

%%

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

expr: NUMBER
    | expr ADD expr { $$ = $1 + $3; }
    | expr SUB expr { $$ = $1 - $3; }
    | expr MUL expr { $$ = $1 * $3; }
    | expr DIV expr { $$ = $1 / $3; }
    | expr POW expr { $$ = pow($1, $3); }
    | SUB expr %prec UMINUS { $$ = -$2; }
    | LPAREN expr RPAREN { $$ = $2; }
    ;

%%

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

int main() {
    printf("科学计算器，支持 +, -, *, /, ^ (幂运算)\n");
    return yyparse();
}

对应的Lex文件：

/* 词法分析器 */
%{
#include "y.tab.h"
%}

%%

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

%%

int yywrap() {
    return 1;
}

案例：抽象语法树构建

让我们创建一个构建抽象语法树（AST）的例子：

/* 构建抽象语法树的Yacc文件 */
%{
#include <stdio.h>
#include <stdlib.h>

typedef struct ast_node {
    char type; // '+' '-' '*' '/' 'n' (数字)
    double value; // 仅用于数字节点
    struct ast_node *left;
    struct ast_node *right;
} ASTNode;

ASTNode* new_node(char type, double value, ASTNode* left, ASTNode* right) {
    ASTNode* node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = type;
    node->value = value;
    node->left = left;
    node->right = right;
    return node;
}

void free_ast(ASTNode* node) {
    if (node) {
        free_ast(node->left);
        free_ast(node->right);
        free(node);
    }
}

double evaluate(ASTNode* node) {
    switch (node->type) {
        case '+': return evaluate(node->left) + evaluate(node->right);
        case '-': return evaluate(node->left) - evaluate(node->right);
        case '*': return evaluate(node->left) * evaluate(node->right);
        case '/': return evaluate(node->left) / evaluate(node->right);
        case 'n': return node->value;
        default: return 0;
    }
}

void print_ast(ASTNode* node, int indent) {
    if (!node) return;
    for (int i = 0; i < indent; i++) printf("  ");
    if (node->type == 'n') {
        printf("数字: %g\n", node->value);
    } else {
        printf("运算符: %c\n", node->type);
        print_ast(node->left, indent + 1);
        print_ast(node->right, indent + 1);
    }
}

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

%union {
    double val;
    ASTNode* node;
}

%token <val> NUMBER
%token ADD SUB MUL DIV
%token LPAREN RPAREN
%token EOL

%left ADD SUB
%left MUL DIV
%nonassoc UMINUS

%type <node> expr

%%

calc: /* 空规则 */
    | calc expr EOL {
        printf("结果: %g\n", evaluate($2));
        printf("抽象语法树:\n");
        print_ast($2, 0);
        free_ast($2);
    }
    | calc EOL     { /* 空行，忽略 */ }
    ;

expr: NUMBER { $$ = new_node('n', $1, NULL, NULL); }
    | expr ADD expr { $$ = new_node('+', 0, $1, $3); }
    | expr SUB expr { $$ = new_node('-', 0, $1, $3); }
    | expr MUL expr { $$ = new_node('*', 0, $1, $3); }
    | expr DIV expr { $$ = new_node('/', 0, $1, $3); }
    | SUB expr %prec UMINUS { $$ = new_node('-', 0, new_node('n', 0, NULL, NULL), $2); }
    | LPAREN expr RPAREN { $$ = $2; }
    ;

%%

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

int main() {
    printf("带抽象语法树的计算器\n");
    return yyparse();
}

对应的Lex文件：

/* 词法分析器 */
%{
#include "y.tab.h"
%}

%%

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

%%

int yywrap() {
    return 1;
}

案例：控制结构解析

让我们创建一个支持if-else语句和while循环的简单控制结构解析器：

/* 控制结构解析器 */
%{
#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);
%}

%union {
    int val;
    char* str;
}

%token <val> NUMBER
%token <str> IDENTIFIER
%token ASSIGN
%token SEMI
%token EOL
%token IF
%token ELSE
%token WHILE
%token LPAREN RPAREN
%token LBRACE RBRACE

%left '+' '-' 
%left '*' '/'

%type <val> expr stmt stmts if_stmt while_stmt block

%%

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

stmt: expr SEMI { $$ = $1; }
    | IDENTIFIER ASSIGN expr SEMI { set_var($1, $3); $$ = $3; printf("%s = %d\n", $1, $3); }
    | if_stmt
    | while_stmt
    | block
    ;

block: LBRACE stmts RBRACE { $$ = $2; }
     ;

stmts: /* 空规则 */ { $$ = 0; }
     | stmts stmt { $$ = $2; }
     ;

if_stmt: IF LPAREN expr RPAREN stmt { if ($3) $$ = $5; else $$ = 0; }
       | IF LPAREN expr RPAREN stmt ELSE stmt { if ($3) $$ = $5; else $$ = $7; }
       ;

while_stmt: WHILE LPAREN expr RPAREN stmt { while ($3) { $5; } $$ = 0; }
          ;

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

%%

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

int main() {
    printf("控制结构解析器\n");
    printf("支持变量赋值、if-else语句和while循环\n");
    return yyparse();
}

对应的Lex文件：

/* 词法分析器 */
%{
#include "y.tab.h"
#include <string.h>
%}

%%

[0-9]+      { yylval.val = atoi(yytext); return NUMBER; }
[a-zA-Z_][a-zA-Z0-9_]* {
    if (strcmp(yytext, "if") == 0) return IF;
    if (strcmp(yytext, "else") == 0) return ELSE;
    if (strcmp(yytext, "while") == 0) return WHILE;
    yylval.str = strdup(yytext); return IDENTIFIER;
}
"="         { return ASSIGN; }
";"         { return SEMI; }
"("         { return LPAREN; }
")"         { return RPAREN; }
"{"         { return LBRACE; }
"}"         { return RBRACE; }
"+"         { return '+'; }
"-"         { return '-'; }
"*"         { return '*'; }
"/"         { return '/'; }
"\n"        { return EOL; }
[ \t]       { /* 忽略空白字符 */ }
.

%%

int yywrap() {
    return 1;
}

代码优化建议

  1. 抽象语法树优化：

    • 使用更高效的内存管理策略，如内存池
    • 实现AST的优化遍历，如常量折叠
    • 考虑使用更紧凑的AST表示，减少内存占用

  2. 错误处理优化：

    • 实现更详细的错误信息，包括错误位置和预期的token
    • 添加错误恢复规则，使解析器在遇到错误后能够继续解析
    • 使用yyerror函数的扩展版本，提供更丰富的错误上下文

  3. 性能优化：

    • 对于大型文法，使用Yacc的-v选项生成分析报告，识别和解决冲突
    • 合理设计文法规则，避免左递归和二义性
    • 考虑使用Bison的一些高级特性，如GLR解析器，处理更复杂的文法

  4. 可维护性优化：

    • 将复杂的语义动作分离到单独的函数中
    • 使用注释清晰地说明文法规则的含义
    • 模块化设计，将不同功能的语法规则分组
    • 考虑使用Bison的%define指令，自定义生成的解析器的行为

总结

本集我们深入学习了Yacc的语法规则定义，包括：

  1. 产生式的基本写法和语义动作
  2. 语义值的传递和自定义类型
  3. 优先级和结合性的声明
  4. %prec声明的使用
  5. 实际案例：表达式解析器、抽象语法树构建、控制结构解析

通过这些知识，你已经可以构建更复杂的语法分析器，处理包括表达式、控制结构在内的各种语法结构。在后续的课程中，我们将学习更多关于语法分析器生成器的高级特性，以及如何将它们应用到实际的编译器开发中。

« 上一篇 Yacc / Bison 入门 下一篇 » Yacc 高级特性
↑