4. 构建递归下降解析器

任务说明

为简单算术表达式文法实现递归下降解析器，支持整数常量、四则运算、括号和一元负号，输出抽象语法树（AST）。文法如下：

expr    := term (('+' | '-') term)*
term    := factor (('*' | '/') factor)*
factor  := ('-' factor) | primary
primary := NUMBER | '(' expr ')'

输入为字符串表达式，输出为AST的内存表示及可视化打印结果。

AST节点定义

// ast.h
#ifndef AST_H
#define AST_H

typedef enum {
    NODE_NUMBER,
    NODE_BINARY_OP,
    NODE_UNARY_OP
} NodeType;

typedef struct Node {
    NodeType type;
    union {
        int value;              // NODE_NUMBER
        struct {
            char op;            // '+', '-', '*', '/'
            struct Node* left;
            struct Node* right;
        } binary;               // NODE_BINARY_OP
        struct {
            char op;            // '-'
            struct Node* operand;
        } unary;                // NODE_UNARY_OP
    } data;
} Node;

Node* new_number(int value);
Node* new_binary(char op, Node* left, Node* right);
Node* new_unary(char op, Node* operand);
void free_ast(Node* node);
void print_ast(Node* node, int depth);

#endif

词法分析器

// lexer.h
#ifndef LEXER_H
#define LEXER_H

typedef enum {
    _NUMBER,
    _PLUS, _MINUS, _STAR, _SLASH,
    _LPAREN, _RPAREN,
    _END
} TokenType;

typedef struct {
    TokenType type;
    int value;  // 仅当type为_NUMBER时有意义
} ;

#endif

// lexer.c
#include <stdio.h>
#include <ctype.h>
#include "lexer.h"

typedef struct {
    const char* src;
    int pos;
} Lexer;

static void skip_whitespace(Lexer* lex) {
    while (lex->src[lex->pos] == ' ' || lex->src[lex->pos] == '\t')
        lex->pos++;
}

static  next_(Lexer* lex) {
    skip_whitespace(lex);
     tok;
    char c = lex->src[lex->pos];

    if (c == '\0') {
        tok.type = _END;
        return tok;
    }

    if (isdigit(c)) {
        int val = 0;
        while (isdigit(lex->src[lex->pos])) {
            val = val * 10 + (lex->src[lex->pos] - '0');
            lex->pos++;
        }
        tok.type = _NUMBER;
        tok.value = val;
        return tok;
    }

    switch (c) {
        case '+': tok.type = _PLUS; break;
        case '-': tok.type = _MINUS; break;
        case '*': tok.type = _STAR; break;
        case '/': tok.type = _SLASH; break;
        case '(': tok.type = _LPAREN; break;
        case ')': tok.type = _RPAREN; break;
        default:
            fprintf(stderr, "词法错误: 非法字符 '%c'\n", c);
            tok.type = _END;
            return tok;
    }
    lex->pos++;
    return tok;
}

// 供解析器使用的流接口
typedef struct {
    Lexer lexer;
     current;
    int has_current;
} TokenStream;

void ts_init(TokenStream* ts, const char* src) {
    ts->lexer.src = src;
    ts->lexer.pos = 0;
    ts->has_current = 0;
}

 ts_peek(TokenStream* ts) {
    if (!ts->has_current) {
        ts->current = next_(&ts->lexer);
        ts->has_current = 1;
    }
    return ts->current;
}

 ts_advance(TokenStream* ts) {
     t = ts_peek(ts);
    ts->has_current = 0;
    return t;
}

int ts_expect(TokenStream* ts, TokenType type) {
     t = ts_peek(ts);
    if (t.type != type) {
        fprintf(stderr, "语法错误: 期望类型 %d, 实际 %d\n", type, t.type);
        return 0;
    }
    ts_advance(ts);
    return 1;
}

递归下降解析器

// parser.c
#include <stdio.h>
#include <stdlib.h>
#include "ast.h"
#include "lexer.h"

typedef struct {
    TokenStream* ts;
} Parser;

static Node* parse_expr(Parser* p);
static Node* parse_term(Parser* p);
static Node* parse_factor(Parser* p);
static Node* parse_primary(Parser* p);

static Node* parse_expr(Parser* p) {
    Node* left = parse_term(p);
    while (1) {
         t = ts_peek(p->ts);
        if (t.type == _PLUS || t.type == _MINUS) {
            ts_advance(p->ts);
            Node* right = parse_term(p);
            left = new_binary(t.type == _PLUS ? '+' : '-', left, right);
        } else {
            break;
        }
    }
    return left;
}

static Node* parse_term(Parser* p) {
    Node* left = parse_factor(p);
    while (1) {
         t = ts_peek(p->ts);
        if (t.type == _STAR || t.type == _SLASH) {
            ts_advance(p->ts);
            Node* right = parse_factor(p);
            left = new_binary(t.type == _STAR ? '*' : '/', left, right);
        } else {
            break;
        }
    }
    return left;
}

static Node* parse_factor(Parser* p) {
     t = ts_peek(p->ts);
    if (t.type == _MINUS) {
        ts_advance(p->ts);
        Node* operand = parse_factor(p);
        return new_unary('-', operand);
    }
    return parse_primary(p);
}

static Node* parse_primary(Parser* p) {
     t = ts_peek(p->ts);
    if (t.type == _NUMBER) {
        ts_advance(p->ts);
        return new_number(t.value);
    }
    if (t.type == _LPAREN) {
        ts_advance(p->ts);
        Node* expr = parse_expr(p);
        if (!ts_expect(p->ts, _RPAREN)) {
            fprintf(stderr, "缺少右括号\n");
            free_ast(expr);
            return NULL;
        }
        return expr;
    }
    fprintf(stderr, "语法错误: 意外的\n");
    return NULL;
}

Node* parse(const char* src) {
    TokenStream ts;
    ts_init(&ts, src);
    Parser p;
    p.ts = &ts;
    Node* ast = parse_expr(&p);
    if (ts_peek(&ts).type != _END) {
        fprintf(stderr, "语法错误: 表达式后有多余内容\n");
        free_ast(ast);
        return NULL;
    }
    return ast;
}

AST实现与打印

// ast.c
#include <stdio.h>
#include <stdlib.h>
#include "ast.h"

Node* new_number(int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->type = NODE_NUMBER;
    n->data.value = value;
    return n;
}

Node* new_binary(char op, Node* left, Node* right) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->type = NODE_BINARY_OP;
    n->data.binary.op = op;
    n->data.binary.left = left;
    n->data.binary.right = right;
    return n;
}

Node* new_unary(char op, Node* operand) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->type = NODE_UNARY_OP;
    n->data.unary.op = op;
    n->data.unary.operand = operand;
    return n;
}

void free_ast(Node* node) {
    if (!node) return;
    if (node->type == NODE_BINARY_OP) {
        free_ast(node->data.binary.left);
        free_ast(node->data.binary.right);
    } else if (node->type == NODE_UNARY_OP) {
        free_ast(node->data.unary.operand);
    }
    free(node);
}

void print_ast(Node* node, int depth) {
    if (!node) return;
    for (int i = 0; i < depth; i++) printf("  ");
    switch (node->type) {
        case NODE_NUMBER:
            printf("Num(%d)\n", node->data.value);
            break;
        case NODE_BINARY_OP:
            printf("BinOp('%c')\n", node->data.binary.op);
            print_ast(node->data.binary.left, depth + 1);
            print_ast(node->data.binary.right, depth + 1);
            break;
        case NODE_UNARY_OP:
            printf("UnOp('%c')\n", node->data.unary.op);
            print_ast(node->data.unary.operand, depth + 1);
            break;
    }
}

主程序与运行

// main.c
#include <stdio.h>
#include "ast.h"

Node* parse(const char* src);  // 在parser.c中实现

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

    for (int i = 0; i < n; i++) {
        printf("表达式: %s\n", expressions[i]);
        Node* ast = parse(expressions[i]);
        if (ast) {
            print_ast(ast, 0);
            free_ast(ast);
        } else {
            printf("解析失败\n");
        }
        printf("---\n");
    }
    return 0;
}

编译与运行

gcc -o parser main.c parser.c ast.c lexer.c
./parser

预期输出

表达式: 1+2*3
BinOp('+')
  Num(1)
  BinOp('*')
    Num(2)
    Num(3)
---
表达式: (1+2)*3
BinOp('*')
  BinOp('+')
    Num(1)
    Num(2)
  Num(3)
---
表达式: -5+10
BinOp('+')
  UnOp('-')
    Num(5)
  Num(10)
---
表达式: 2*(3+4)-8/2
BinOp('-')
  BinOp('*')
    Num(2)
    BinOp('+')
      Num(3)
      Num(4)
  BinOp('/')
    Num(8)
    Num(2)
---
表达式: 1-2-3
BinOp('-')
  BinOp('-')
    Num(1)
    Num(2)
  Num(3)
---

验证要点

• 优先级正确：1+2*3 的AST中 * 位于 + 之下，说明乘法先结合。
• 括号生效：(1+2)*3 中 + 成为 * 的左子树，括号改变了结合顺序。
• 左结合：1-2-3 解析为 (1-2)-3，AST呈左深结构。
• 一元负号：-5+10 中 -5 被解析为 UnOp('-') 包裹 Num(5)。