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

核心知识点讲解

文法设计

设计一个良好的算术表达式文法是实现正确语法分析的基础。算术表达式文法需要考虑以下因素：

运算符优先级：不同运算符的计算顺序
结合性：相同优先级运算符的计算顺序
括号处理：改变运算顺序的括号结构
表达式结构：基本表达式、复合表达式等

一个典型的算术表达式文法：

expr → expr + term | expr - term | term
term → term * factor | term / factor | term % factor | factor
factor → primary ^ factor | primary
primary → NUMBER | ID | ( expr ) | - primary

这个文法定义了：

最高优先级：括号、一元负号、幂运算
中等优先级：乘法、除法、取模
最低优先级：加法、减法
左结合：加减乘除取模
右结合：幂运算

实现分析器

实现算术表达式分析器的常见方法有：

递归下降分析器：手写实现，灵活性高
运算符优先级分析器：专门为表达式设计
生成器工具：如Yacc/Bison，自动生成

本实战将使用递归下降分析器实现，因为它易于理解和定制。

递归下降分析器的实现步骤：

词法分析器：识别token
语法分析器：递归处理不同优先级的表达式
错误处理：检测和报告语法错误
语义动作：执行表达式计算或构建AST

构建 AST

为了后续的语义分析和代码生成，通常需要构建抽象语法树(AST)。AST节点设计应考虑：

节点类型：表达式、运算符、常量等
子节点：操作数
属性：运算符类型、常量值等
位置信息：源代码位置，用于错误报告

常见的AST节点类型：

二元表达式节点：处理二元运算符
一元表达式节点：处理一元运算符
常量节点：处理数字常量
标识符节点：处理变量名
括号表达式节点：处理括号包围的表达式

测试

测试算术表达式分析器应覆盖以下场景：

基本表达式：单个数字或标识符
复合表达式：包含多个运算符的表达式
优先级测试：验证运算符优先级是否正确
结合性测试：验证运算符结合性是否正确
括号测试：验证括号是否正确改变运算顺序
错误处理：验证错误检测和报告是否有效
边界情况：如空表达式、嵌套括号等

实用案例分析

完整的算术表达式分析器实现

下面是一个完整的算术表达式分析器实现，包括词法分析、语法分析、AST构建和表达式计算：

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

// 词法分析器相关定义
typedef enum {
    TOKEN_NUMBER,
    TOKEN_ID,
    TOKEN_PLUS,
    TOKEN_MINUS,
    TOKEN_MULT,
    TOKEN_DIV,
    TOKEN_MOD,
    TOKEN_POW,
    TOKEN_LPAREN,
    TOKEN_RPAREN,
    TOKEN_EOF,
    TOKEN_ERROR
} TokenType;

// 全局变量
TokenType current_token;
double number_value;
char id_name[100];
char* input;
int position;

// AST节点类型
typedef enum {
    NODE_BINARY,
    NODE_UNARY,
    NODE_CONSTANT,
    NODE_IDENTIFIER
} NodeType;

// AST节点结构
typedef struct ASTNode {
    NodeType type;
    union {
        struct {
            char op;
            struct ASTNode *left;
            struct ASTNode *right;
        } binary;
        struct {
            char op;
            struct ASTNode *expr;
        } unary;
        double constant;
        char identifier[100];
    } value;
} ASTNode;

// 词法分析函数
void get_token() {
    // 跳过空白字符
    while (input[position] && isspace(input[position])) {
        position++;
    }
    
    if (!input[position]) {
        current_token = TOKEN_EOF;
        return;
    }
    
    char c = input[position];
    
    // 识别运算符
    switch (c) {
        case '+':
            current_token = TOKEN_PLUS;
            position++;
            return;
        case '-':
            current_token = TOKEN_MINUS;
            position++;
            return;
        case '*':
            current_token = TOKEN_MULT;
            position++;
            return;
        case '/':
            current_token = TOKEN_DIV;
            position++;
            return;
        case '%':
            current_token = TOKEN_MOD;
            position++;
            return;
        case '^':
            current_token = TOKEN_POW;
            position++;
            return;
        case '(':
            current_token = TOKEN_LPAREN;
            position++;
            return;
        case ')':
            current_token = TOKEN_RPAREN;
            position++;
            return;
    }
    
    // 识别数字
    if (isdigit(c) || c == '.') {
        char num_str[100];
        int i = 0;
        while (input[position] && (isdigit(input[position]) || input[position] == '.')) {
            num_str[i++] = input[position++];
        }
        num_str[i] = '\0';
        number_value = atof(num_str);
        current_token = TOKEN_NUMBER;
        return;
    }
    
    // 识别标识符
    if (isalpha(c) || c == '_') {
        int i = 0;
        while (input[position] && (isalnum(input[position]) || input[position] == '_')) {
            id_name[i++] = input[position++];
        }
        id_name[i] = '\0';
        current_token = TOKEN_ID;
        return;
    }
    
    // 未知字符
    current_token = TOKEN_ERROR;
    position++;
}

// AST节点创建函数
ASTNode* create_binary_node(char op, ASTNode *left, ASTNode *right) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_BINARY;
    node->value.binary.op = op;
    node->value.binary.left = left;
    node->value.binary.right = right;
    return node;
}

ASTNode* create_unary_node(char op, ASTNode *expr) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_UNARY;
    node->value.unary.op = op;
    node->value.unary.expr = expr;
    return node;
}

ASTNode* create_constant_node(double value) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_CONSTANT;
    node->value.constant = value;
    return node;
}

ASTNode* create_identifier_node(const char *name) {
    ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
    node->type = NODE_IDENTIFIER;
    strcpy(node->value.identifier, name);
    return node;
}

// 释放AST
void free_ast(ASTNode *node) {
    if (!node) return;
    
    switch (node->type) {
        case NODE_BINARY:
            free_ast(node->value.binary.left);
            free_ast(node->value.binary.right);
            break;
        case NODE_UNARY:
            free_ast(node->value.unary.expr);
            break;
        case NODE_CONSTANT:
        case NODE_IDENTIFIER:
            break;
    }
    
    free(node);
}

// 表达式计算
 double evaluate(ASTNode *node) {
    switch (node->type) {
        case NODE_BINARY:
            {
                double left_val = evaluate(node->value.binary.left);
                double right_val = evaluate(node->value.binary.right);
                switch (node->value.binary.op) {
                    case '+': return left_val + right_val;
                    case '-': return left_val - right_val;
                    case '*': return left_val * right_val;
                    case '/': return left_val / right_val;
                    case '%': return (int)left_val % (int)right_val;
                    case '^': return pow(left_val, right_val);
                    default: return 0;
                }
            }
        case NODE_UNARY:
            {
                double val = evaluate(node->value.unary.expr);
                if (node->value.unary.op == '-') {
                    return -val;
                }
                return val;
            }
        case NODE_CONSTANT:
            return node->value.constant;
        case NODE_IDENTIFIER:
            // 简单处理：返回0，实际应该从符号表查找
            printf("警告: 未定义变量 '%s'，使用值 0\n", node->value.identifier);
            return 0;
        default:
            return 0;
    }
}

// 打印AST
void print_ast(ASTNode *node, int indent) {
    if (!node) return;
    
    for (int i = 0; i < indent; i++) {
        printf("  ");
    }
    
    switch (node->type) {
        case NODE_BINARY:
            printf("BinaryOp: %c\n", node->value.binary.op);
            print_ast(node->value.binary.left, indent + 1);
            print_ast(node->value.binary.right, indent + 1);
            break;
        case NODE_UNARY:
            printf("UnaryOp: %c\n", node->value.unary.op);
            print_ast(node->value.unary.expr, indent + 1);
            break;
        case NODE_CONSTANT:
            printf("Constant: %g\n", node->value.constant);
            break;
        case NODE_IDENTIFIER:
            printf("Identifier: %s\n", node->value.identifier);
            break;
    }
}

// 递归下降分析器

// 解析 primary
ASTNode* parse_primary() {
    ASTNode *node = NULL;
    
    switch (current_token) {
        case TOKEN_NUMBER:
            node = create_constant_node(number_value);
            get_token();
            break;
        case TOKEN_ID:
            node = create_identifier_node(id_name);
            get_token();
            break;
        case TOKEN_LPAREN:
            get_token();
            node = parse_expression();
            if (current_token != TOKEN_RPAREN) {
                printf("错误: 缺少右括号\n");
                free_ast(node);
                return NULL;
            }
            get_token();
            break;
        case TOKEN_MINUS:
            get_token();
            node = create_unary_node('-', parse_primary());
            break;
        default:
            printf("错误: 意外的token\n");
            return NULL;
    }
    
    return node;
}

// 解析 factor (处理幂运算)
ASTNode* parse_factor() {
    ASTNode *node = parse_primary();
    
    while (current_token == TOKEN_POW) {
        char op = '^';
        get_token();
        ASTNode *right = parse_primary();
        node = create_binary_node(op, node, right);
    }
    
    return node;
}

// 解析 term (处理乘除取模)
ASTNode* parse_term() {
    ASTNode *node = parse_factor();
    
    while (current_token == TOKEN_MULT || current_token == TOKEN_DIV || current_token == TOKEN_MOD) {
        char op;
        switch (current_token) {
            case TOKEN_MULT:
                op = '*';
                break;
            case TOKEN_DIV:
                op = '/';
                break;
            case TOKEN_MOD:
                op = '%';
                break;
            default:
                op = ' ';
        }
        get_token();
        ASTNode *right = parse_factor();
        node = create_binary_node(op, node, right);
    }
    
    return node;
}

// 解析 expression (处理加减)
ASTNode* parse_expression() {
    ASTNode *node = parse_term();
    
    while (current_token == TOKEN_PLUS || current_token == TOKEN_MINUS) {
        char op = (current_token == TOKEN_PLUS) ? '+' : '-';
        get_token();
        ASTNode *right = parse_term();
        node = create_binary_node(op, node, right);
    }
    
    return node;
}

// 主函数
int main() {
    char buffer[1000];
    
    printf("算术表达式分析器\n");
    printf("支持的运算符: +, -, *, /, %, ^, (, )\n");
    printf("输入表达式，按回车计算 (输入 quit 退出)\n\n");
    
    while (1) {
        printf("输入: ");
        if (!fgets(buffer, sizeof(buffer), stdin)) {
            break;
        }
        
        // 处理输入
        buffer[strcspn(buffer, "\n")] = '\0';
        if (strcmp(buffer, "quit") == 0) {
            break;
        }
        if (strlen(buffer) == 0) {
            continue;
        }
        
        // 初始化
        input = buffer;
        position = 0;
        get_token();
        
        // 解析表达式
        ASTNode *ast = parse_expression();
        
        // 检查解析结果
        if (ast && current_token == TOKEN_EOF) {
            // 打印AST
            printf("AST:\n");
            print_ast(ast, 0);
            
            // 计算结果
            double result = evaluate(ast);
            printf("结果: %g\n\n", result);
            
            // 释放AST
            free_ast(ast);
        } else {
            printf("解析失败\n\n");
            if (ast) {
                free_ast(ast);
            }
        }
    }
    
    printf("再见!\n");
    return 0;
}

运行效果

算术表达式分析器
支持的运算符: +, -, *, /, %, ^, (, )
输入表达式，按回车计算 (输入 quit 退出)

输入: 2 + 3 * 4
AST:
BinaryOp: +
  Constant: 2
  BinaryOp: *
    Constant: 3
    Constant: 4
结果: 14

输入: (2 + 3) * 4
AST:
BinaryOp: *
  BinaryOp: +
    Constant: 2
    Constant: 3
  Constant: 4
结果: 20

输入: 2 ^ 3 + 4
AST:
BinaryOp: +
  BinaryOp: ^
    Constant: 2
    Constant: 3
  Constant: 4
结果: 12

输入: -2 * 3
AST:
BinaryOp: *
  UnaryOp: -
    Constant: 2
  Constant: 3
结果: -6

输入: 10 / (2 + 3)
AST:
BinaryOp: /
  Constant: 10
  BinaryOp: +
    Constant: 2
    Constant: 3
结果: 2

技术要点总结

文法设计的重要性：
- 良好的文法是正确分析的基础
- 优先级和结合性必须在文法中明确体现
- 递归结构便于处理嵌套表达式
递归下降分析器的实现：
- 为每个非终结符创建一个函数
- 按优先级从低到高处理表达式
- 递归处理子表达式
AST的构建和使用：
- AST是表达式的结构化表示
- 便于后续的语义分析和代码生成
- 支持表达式的计算和优化
错误处理的实现：
- 检测语法错误并提供明确的错误信息
- 处理意外的token和缺少的括号
- 提供错误恢复机制
测试的全面性：
- 测试基本表达式和复合表达式
- 验证优先级和结合性
- 测试括号和一元运算符
- 测试错误处理

代码优化建议

词法分析器优化：
- 使用状态机提高词法分析效率
- 支持更多的数字格式（科学计数法等）
- 改进错误处理，提供更详细的词法错误信息
语法分析器优化：
- 实现更智能的错误恢复
- 支持更多的运算符类型
- 优化递归调用，避免栈溢出
AST优化：
- 添加位置信息，用于更精确的错误报告
- 实现AST优化（如常量折叠）
- 支持更多的表达式类型
内存管理：
- 实现内存池，减少内存分配开销
- 添加内存泄漏检测
- 优化AST节点的内存布局
功能扩展：
- 支持函数调用（如 sin、cos 等）
- 添加变量支持和符号表
- 支持赋值表达式
- 实现更复杂的表达式类型

高级应用技巧

运算符优先级表的实现

对于支持大量运算符的表达式分析器，可以使用优先级表来管理运算符优先级：

// 运算符优先级表
typedef struct {
    char op;
    int precedence;
    int associativity; // 0: 左结合, 1: 右结合
} OperatorInfo;

OperatorInfo operators[] = {
    {'^', 4, 1},  // 右结合
    {'*', 3, 0},
    {'/', 3, 0},
    {'%', 3, 0},
    {'+', 2, 0},
    {'-', 2, 0},
    {'', 0, 0}
};

// 获取运算符信息
OperatorInfo* get_operator_info(char op) {
    for (int i = 0; operators[i].op != '\0'; i++) {
        if (operators[i].op == op) {
            return &operators[i];
        }
    }
    return NULL;
}

表达式优化

在AST构建后，可以进行表达式优化：

常量折叠：计算常量表达式
公共子表达式消除：消除重复计算
死代码消除：移除无用的表达式
代数简化：简化表达式结构

与其他系统集成

将表达式分析器集成到更大的系统中：

符号表集成：处理变量和函数
类型系统集成：处理不同类型的表达式
代码生成集成：生成目标代码
交互式环境集成：支持实时表达式计算

最佳实践总结

文法设计：
- 从简单到复杂，逐步构建文法
- 明确优先级和结合性
- 使用递归结构处理嵌套表达式
分析器实现：
- 选择适合的分析方法（递归下降、生成器等）
- 按优先级分层处理
- 实现详细的错误处理
AST构建：
- 设计清晰的AST节点结构
- 支持后续的语义分析和代码生成
- 实现AST的内存管理
测试策略：
- 全面测试各种表达式类型
- 验证优先级和结合性
- 测试错误处理
- 测试边界情况
性能优化：
- 优化词法分析和语法分析
- 实现AST优化
- 合理管理内存

通过本集的学习，你已经掌握了算术表达式语法分析的核心技术，包括文法设计、分析器实现、AST构建和测试等步骤。这些技术不仅适用于算术表达式，也是实现更复杂语法分析器的基础。在实际应用中，你可以根据具体需求扩展和优化这个分析器，以支持更复杂的表达式类型和功能。