第94集：语法分析实战（一）—— 算术表达式

算术表达式是编程语言中最基础、最常见的语法结构之一，也是学习语法分析的理想起点。本集我们将通过实现一个完整的算术表达式分析器，从实战角度掌握语法分析的核心技术，包括文法设计、分析器实现、抽象语法树（AST）构建和测试验证。

一、文法设计

1. 需求分析

我们需要设计一个能够处理以下算术表达式的文法：

  • 基本运算符：加 (+)、减 (-)、乘 (*)、除 (/)
  • 括号：用于改变运算优先级
  • 数字：支持整数
  • 运算符优先级：乘除高于加减
  • 左结合性：相同优先级的运算符从左到右计算

2. 文法定义

根据需求，我们可以设计如下的上下文无关文法：

expr    → term (+ term | - term)*
term   → factor (* factor | / factor)*
factor → NUMBER | ( expr )

这个文法通过分层结构自然地处理了运算符优先级：

  • expr 处理加减法（最低优先级）
  • term 处理乘除法（中等优先级）
  • factor 处理括号和数字（最高优先级）

同时，使用重复产生式 (* term | - term)* 和 (* factor | / factor)* 确保了左结合性。

二、递归下降分析器实现

1. 数据结构定义

首先，我们需要定义词法单元（Token）和抽象语法树（AST）节点的数据结构：

// Token 类型定义
typedef enum {
    TOKEN_PLUS,     // +
    TOKEN_MINUS,    // -
    TOKEN_MULTIPLY, // *
    TOKEN_DIVIDE,   // /
    TOKEN_LPAREN,   // (
    TOKEN_RPAREN,   // )
    TOKEN_NUMBER,   // 数字
    TOKEN_EOF       // 结束符
} TokenType;

// Token 结构
typedef struct {
    TokenType type;
    int value;      // 仅用于 TOKEN_NUMBER
} Token;

// AST 节点类型
typedef enum {
    AST_ADD,        // 加法
    AST_SUBTRACT,   // 减法
    AST_MULTIPLY,   // 乘法
    AST_DIVIDE,     // 除法
    AST_NUMBER      // 数字
} ASTNodeType;

// AST 节点结构
typedef struct ASTNode {
    ASTNodeType type;
    int value;              // 仅用于 AST_NUMBER
    struct ASTNode *left;   // 左子节点
    struct ASTNode *right;  // 右子节点
} ASTNode;

// 词法分析器状态
typedef struct {
    const char *input;
    int pos;
} Lexer;

2. 词法分析器实现

词法分析器负责将输入字符串转换为Token序列：

// 初始化词法分析器
void lexer_init(Lexer *lexer, const char *input) {
    lexer->input = input;
    lexer->pos = 0;
}

// 获取下一个 Token
Token lexer_next(Lexer *lexer) {
    // 跳过空白字符
    while (isspace(lexer->input[lexer->pos])) {
        lexer->pos++;
    }
    
    char c = lexer->input[lexer->pos];
    
    // 处理运算符和括号
    switch (c) {
        case '+':
            lexer->pos++;
            return (Token){TOKEN_PLUS, 0};
        case '-':
            lexer->pos++;
            return (Token){TOKEN_MINUS, 0};
        case '*':
            lexer->pos++;
            return (Token){TOKEN_MULTIPLY, 0};
        case '/':
            lexer->pos++;
            return (Token){TOKEN_DIVIDE, 0};
        case '(':
            lexer->pos++;
            return (Token){TOKEN_LPAREN, 0};
        case ')':
            lexer->pos++;
            return (Token){TOKEN_RPAREN, 0};
        case '\0':
            return (Token){TOKEN_EOF, 0};
    }
    
    // 处理数字
    if (isdigit(c)) {
        int value = 0;
        while (isdigit(lexer->input[lexer->pos])) {
            value = value * 10 + (lexer->input[lexer->pos] - '0');
            lexer->pos++;
        }
        return (Token){TOKEN_NUMBER, value};
    }
    
    // 处理未知字符
    fprintf(stderr, "Unexpected character: %c\n", c);
    exit(1);
}

3. 递归下降分析器实现

根据文法规则，我们实现对应的递归函数：

// 语法分析器状态
typedef struct {
    Lexer *lexer;
    Token current_token;
} Parser;

// 初始化语法分析器
void parser_init(Parser *parser, Lexer *lexer) {
    parser->lexer = lexer;
    parser->current_token = lexer_next(lexer);
}

// 匹配当前 Token 并前进
void parser_match(Parser *parser, TokenType expected_type) {
    if (parser->current_token.type == expected_type) {
        parser->current_token = lexer_next(parser->lexer);
    } else {
        fprintf(stderr, "Syntax error: expected token type %d, got %d\n", 
                expected_type, parser->current_token.type);
        exit(1);
    }
}

// 解析 factor
ASTNode* parser_parse_factor(Parser *parser) {
    Token token = parser->current_token;
    
    if (token.type == TOKEN_NUMBER) {
        // 匹配数字
        parser_match(parser, TOKEN_NUMBER);
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = AST_NUMBER;
        node->value = token.value;
        node->left = NULL;
        node->right = NULL;
        return node;
    } else if (token.type == TOKEN_LPAREN) {
        // 匹配括号表达式
        parser_match(parser, TOKEN_LPAREN);
        ASTNode *node = parser_parse_expr(parser);
        parser_match(parser, TOKEN_RPAREN);
        return node;
    } else {
        fprintf(stderr, "Syntax error: unexpected token type %d\n", token.type);
        exit(1);
    }
}

// 解析 term
ASTNode* parser_parse_term(Parser *parser) {
    ASTNode *node = parser_parse_factor(parser);
    
    while (parser->current_token.type == TOKEN_MULTIPLY || 
           parser->current_token.type == TOKEN_DIVIDE) {
        Token token = parser->current_token;
        
        if (token.type == TOKEN_MULTIPLY) {
            parser_match(parser, TOKEN_MULTIPLY);
        } else {
            parser_match(parser, TOKEN_DIVIDE);
        }
        
        ASTNode *new_node = malloc(sizeof(ASTNode));
        new_node->left = node;
        new_node->right = parser_parse_factor(parser);
        
        if (token.type == TOKEN_MULTIPLY) {
            new_node->type = AST_MULTIPLY;
        } else {
            new_node->type = AST_DIVIDE;
        }
        
        node = new_node;
    }
    
    return node;
}

// 解析 expr
ASTNode* parser_parse_expr(Parser *parser) {
    ASTNode *node = parser_parse_term(parser);
    
    while (parser->current_token.type == TOKEN_PLUS || 
           parser->current_token.type == TOKEN_MINUS) {
        Token token = parser->current_token;
        
        if (token.type == TOKEN_PLUS) {
            parser_match(parser, TOKEN_PLUS);
        } else {
            parser_match(parser, TOKEN_MINUS);
        }
        
        ASTNode *new_node = malloc(sizeof(ASTNode));
        new_node->left = node;
        new_node->right = parser_parse_term(parser);
        
        if (token.type == TOKEN_PLUS) {
            new_node->type = AST_ADD;
        } else {
            new_node->type = AST_SUBTRACT;
        }
        
        node = new_node;
    }
    
    return node;
}

三、抽象语法树（AST）构建

在上面的递归下降分析器实现中，我们已经在解析过程中构建了AST。每个解析函数都会返回一个AST节点，代表当前解析的语法结构。

1. AST 节点创建

在解析过程中，我们根据语法结构创建不同类型的AST节点：

  • 对于数字，创建 AST_NUMBER 节点，存储数字值
  • 对于二元运算，创建对应的运算节点（如 AST_ADD、AST_MULTIPLY 等），并设置左右子节点
  • 对于括号表达式，直接返回括号内表达式的AST节点

2. AST 结构示例

对于表达式 2 * (3 + 4) - 5，构建的AST结构如下：

       SUBTRACT
      /        
   MULTIPLY     NUMBER(5)
  /       \nNUMBER(2)   ADD
          /    
     NUMBER(3) NUMBER(4)

四、AST 遍历与求值

为了验证AST的正确性，我们可以实现一个AST遍历函数，计算表达式的值：

// 计算 AST 的值
int evaluate_ast(ASTNode *node) {
    switch (node->type) {
        case AST_NUMBER:
            return node->value;
        case AST_ADD:
            return evaluate_ast(node->left) + evaluate_ast(node->right);
        case AST_SUBTRACT:
            return evaluate_ast(node->left) - evaluate_ast(node->right);
        case AST_MULTIPLY:
            return evaluate_ast(node->left) * evaluate_ast(node->right);
        case AST_DIVIDE:
            return evaluate_ast(node->left) / evaluate_ast(node->right);
        default:
            fprintf(stderr, "Unknown AST node type: %d\n", node->type);
            exit(1);
    }
}

// 释放 AST 内存
void free_ast(ASTNode *node) {
    if (node == NULL) {
        return;
    }
    free_ast(node->left);
    free_ast(node->right);
    free(node);
}

五、完整示例

现在，我们将上述组件整合起来，创建一个完整的算术表达式分析器示例：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 类型定义部分（省略，见上文）

// 函数声明部分（省略，见上文）

int main() {
    // 测试表达式
    const char *expressions[] = {
        "1 + 2",
        "1 + 2 * 3",
        "(1 + 2) * 3",
        "10 - 5 / 5",
        "2 * (3 + 4) - 5",
        NULL
    };
    
    // 测试每个表达式
    for (int i = 0; expressions[i] != NULL; i++) {
        const char *expr = expressions[i];
        printf("\nTesting expression: %s\n", expr);
        
        // 初始化词法分析器
        Lexer lexer;
        lexer_init(&lexer, expr);
        
        // 初始化语法分析器
        Parser parser;
        parser_init(&parser, &lexer);
        
        // 解析表达式
        ASTNode *ast = parser_parse_expr(&parser);
        
        // 验证是否到达输入结束
        if (parser.current_token.type != TOKEN_EOF) {
            fprintf(stderr, "Syntax error: unexpected tokens after expression\n");
            free_ast(ast);
            continue;
        }
        
        // 计算并输出结果
        int result = evaluate_ast(ast);
        printf("Result: %d\n", result);
        
        // 释放内存
        free_ast(ast);
    }
    
    return 0;
}

六、测试与验证

1. 测试用例设计

我们设计了以下测试用例，覆盖不同的语法结构和边界情况：

测试用例 预期结果 测试目的
1 + 2 3 基本加法
1 + 2 * 3 7 运算符优先级
(1 + 2) * 3 9 括号改变优先级
10 - 5 / 5 9 减法和除法
2 * (3 + 4) - 5 9 复杂表达式

2. 编译与运行

将完整代码保存为 expr_parser.c，然后编译并运行：

gcc expr_parser.c -o expr_parser
./expr_parser

3. 预期输出

Testing expression: 1 + 2
Result: 3

Testing expression: 1 + 2 * 3
Result: 7

Testing expression: (1 + 2) * 3
Result: 9

Testing expression: 10 - 5 / 5
Result: 9

Testing expression: 2 * (3 + 4) - 5
Result: 9

七、错误处理改进

我们的初始实现使用了简单的错误处理方式（直接退出程序）。在实际应用中，我们可以改进错误处理，提供更友好的错误信息：

1. 错误恢复策略

// 改进的错误处理函数
void parser_error(Parser *parser, const char *message) {
    fprintf(stderr, "Syntax error at position %d: %s\n", 
            parser->lexer->pos, message);
    
    // 简单的错误恢复：跳过当前 token，继续解析
    if (parser->current_token.type != TOKEN_EOF) {
        parser->current_token = lexer_next(parser->lexer);
    }
}

2. 错误信息增强

// 解析 factor 时的错误处理
ASTNode* parser_parse_factor(Parser *parser) {
    Token token = parser->current_token;
    
    if (token.type == TOKEN_NUMBER) {
        // 匹配数字
        parser_match(parser, TOKEN_NUMBER);
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = AST_NUMBER;
        node->value = token.value;
        node->left = NULL;
        node->right = NULL;
        return node;
    } else if (token.type == TOKEN_LPAREN) {
        // 匹配括号表达式
        parser_match(parser, TOKEN_LPAREN);
        ASTNode *node = parser_parse_expr(parser);
        if (parser->current_token.type != TOKEN_RPAREN) {
            parser_error(parser, "Expected ')' after expression");
            // 返回一个默认值节点，允许继续解析
            ASTNode *error_node = malloc(sizeof(ASTNode));
            error_node->type = AST_NUMBER;
            error_node->value = 0;
            error_node->left = NULL;
            error_node->right = NULL;
            return error_node;
        }
        parser_match(parser, TOKEN_RPAREN);
        return node;
    } else {
        parser_error(parser, "Expected number or '('");
        // 返回一个默认值节点，允许继续解析
        ASTNode *error_node = malloc(sizeof(ASTNode));
        error_node->type = AST_NUMBER;
        error_node->value = 0;
        error_node->left = NULL;
        error_node->right = NULL;
        return error_node;
    }
}

八、扩展与优化

1. 支持浮点数

要支持浮点数，我们需要修改：

  • Token 结构，添加浮点数类型
  • 词法分析器，识别浮点数
  • AST 节点结构，存储浮点数值
  • 求值函数，处理浮点数运算

2. 支持更多运算符

可以添加取模 (%)、幂运算 (^) 等运算符，需要：

  • 在 Token 类型中添加新运算符
  • 在词法分析器中识别新运算符
  • 在文法中添加新的产生式规则
  • 在解析函数中处理新运算符
  • 在 AST 中添加新的节点类型
  • 在求值函数中实现新运算符的计算

3. 性能优化

对于大型表达式，可以考虑以下优化：

  • 记忆化：缓存重复子表达式的计算结果
  • 常量折叠：在解析时预先计算常量表达式
  • AST 优化：合并相邻的常量运算

九、总结

通过本集的实战练习，我们成功实现了一个完整的算术表达式分析器，涵盖了语法分析的核心技术：

  1. 文法设计：通过分层结构处理运算符优先级和结合性
  2. 递归下降分析：实现了与文法规则对应的递归解析函数
  3. 抽象语法树构建：在解析过程中构建了表达语法结构的AST
  4. AST 遍历与求值：通过遍历AST计算表达式的值
  5. 测试与验证：设计了全面的测试用例验证分析器的正确性
  6. 错误处理：实现了基本的错误检测和报告机制

这个算术表达式分析器虽然简单，但它展示了语法分析的基本原理和实现方法。通过理解和扩展这个示例，你可以掌握更复杂的语法分析技术，为实现完整的编程语言编译器打下坚实的基础。

在后续的实战章节中，我们将逐步扩展语法分析器的能力，处理更复杂的语法结构，如变量声明、控制流语句和函数定义等。

« 上一篇 手写 vs 生成器（语法分析） 下一篇 » 语法分析实战（一）—— 算术表达式
↑