03-语法分析与AST¶

// parser.c - 递归下降语法分析器
#include <stdio.h>  // 引入头文件
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// ========== AST节点定义 ==========
typedef enum {
    NODE_NUMBER,    // 数字字面量
    NODE_BINOP,     // 二元运算
    NODE_UNARY      // 一元运算（负号）
} NodeType;

typedef struct ASTNode {  // struct结构体：自定义复合数据类型
    NodeType type;
    union {
        int number;                     // NODE_NUMBER
        struct {                        // NODE_BINOP
            char op;
            struct ASTNode *left;
            struct ASTNode *right;
        } binop;
        struct {                        // NODE_UNARY
            char op;
            struct ASTNode *operand;
        } unary;
    };
} ASTNode;

// 创建数字节点
ASTNode *make_number(int value) {
    ASTNode *node = (ASTNode *)malloc(sizeof(ASTNode));  // 动态内存分配，需手动free释放
    node->type = NODE_NUMBER;
    node->number = value;
    return node;
}

// 创建二元运算节点
ASTNode *make_binop(char op, ASTNode *left, ASTNode *right) {
    ASTNode *node = (ASTNode *)malloc(sizeof(ASTNode));
    node->type = NODE_BINOP;
    node->binop.op = op;
    node->binop.left = left;
    node->binop.right = right;
    return node;
}

// ========== 简易Lexer ==========
typedef enum { T_NUM, T_PLUS, T_MINUS, T_MUL, T_DIV, T_LPAREN, T_RPAREN, T_EOF } TokType;
typedef struct { TokType type; int value; } Token;

const char *src;  // 指针：存储变量的内存地址
int pos;

Token next_token() {
    while (src[pos] == ' ') pos++;
    Token t;
    if (src[pos] == '\0')      { t.type = T_EOF;    return t; }
    if (isdigit(src[pos])) {
        t.type = T_NUM;
        t.value = 0;
        while (isdigit(src[pos])) { t.value = t.value * 10 + (src[pos++] - '0'); }
        return t;
    }
    char c = src[pos++];
    switch (c) {
        case '+': t.type = T_PLUS;   break;
        case '-': t.type = T_MINUS;  break;
        case '*': t.type = T_MUL;    break;
        case '/': t.type = T_DIV;    break;
        case '(': t.type = T_LPAREN; break;
        case ')': t.type = T_RPAREN; break;
        default:
            fprintf(stderr, "未知字符: '%c'\n", c);
            exit(1);
    }
    return t;
}

// ========== 递归下降解析 ==========
Token current_token;

void eat(TokType expected) {
    if (current_token.type != expected) {
        fprintf(stderr, "语法错误: 期望Token类型 %d, 实际 %d\n", expected, current_token.type);
        exit(1);
    }
    current_token = next_token();
}

// 前向声明
ASTNode *parse_expression();

// factor = NUMBER | '(' expression ')'
ASTNode *parse_factor() {
    if (current_token.type == T_NUM) {
        int val = current_token.value;
        eat(T_NUM);
        return make_number(val);
    }
    if (current_token.type == T_LPAREN) {
        eat(T_LPAREN);
        ASTNode *node = parse_expression();
        eat(T_RPAREN);
        return node;
    }
    fprintf(stderr, "语法错误: 期望数字或左括号\n");
    exit(1);
}

// term = factor (('*' | '/') factor)*
ASTNode *parse_term() {
    ASTNode *node = parse_factor();
    while (current_token.type == T_MUL || current_token.type == T_DIV) {
        char op = (current_token.type == T_MUL) ? '*' : '/';
        current_token = next_token();
        ASTNode *right = parse_factor();
        node = make_binop(op, node, right);
    }
    return node;
}

// expression = term (('+' | '-') term)*
ASTNode *parse_expression() {
    ASTNode *node = parse_term();
    while (current_token.type == T_PLUS || current_token.type == T_MINUS) {
        char op = (current_token.type == T_PLUS) ? '+' : '-';
        current_token = next_token();
        ASTNode *right = parse_term();
        node = make_binop(op, node, right);
    }
    return node;
}

// ========== AST求值 ==========
int eval(ASTNode *node) {
    if (node->type == NODE_NUMBER) return node->number;
    if (node->type == NODE_BINOP) {
        int l = eval(node->binop.left);
        int r = eval(node->binop.right);
        switch (node->binop.op) {
            case '+': return l + r;
            case '-': return l - r;
            case '*': return l * r;
            case '/': return r != 0 ? l / r : 0;
        }
    }
    return 0;
}

// ========== AST打印 ==========
void print_ast(ASTNode *node, int depth) {
    for (int i = 0; i < depth; i++) printf("  ");
    if (node->type == NODE_NUMBER) {
        printf("Number(%d)\n", node->number);
    } else if (node->type == NODE_BINOP) {
        printf("BinOp('%c')\n", node->binop.op);
        print_ast(node->binop.left, depth + 1);
        print_ast(node->binop.right, depth + 1);
    }
}

// 释放AST
void free_ast(ASTNode *node) {
    if (!node) return;
    if (node->type == NODE_BINOP) {
        free_ast(node->binop.left);
        free_ast(node->binop.right);
    }
    free(node);
}

int main() {
    const char *expressions[] = {
        "3 + 4 * 2",
        "(3 + 4) * 2",
        "10 - 2 * 3 + 1",
        "100 / (5 * 4)",
    };
    int n = sizeof(expressions) / sizeof(expressions[0]);

    for (int i = 0; i < n; i++) {
        src = expressions[i];
        pos = 0;
        current_token = next_token();

        printf("表达式: %s\n", src);
        ASTNode *ast = parse_expression();
        printf("AST结构:\n");
        print_ast(ast, 1);
        printf("计算结果: %d\n\n", eval(ast));
        free_ast(ast);
    }
    return 0;
}

// 这段代码的else属于哪个if？
if (a)
    if (b)
        stmt1;
    else        // 属于内层if(b)还是外层if(a)？
        stmt2;

// C/C++规则：else与最近的未匹配if配对
// 即 else 属于 if(b)