You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

如何为类tcsh Shell构建AST？含重定向、管道等功能需求

avatar
云原生阿岚
2026-7-27
问题描述

我是一名学生，正在复刻tcsh类Shell，目前已有可运行的基础版本，需要为其添加以下功能：

  • 重定向：>、<、>>、<<
  • 管道：|
  • 分号：;

调研了解到AST可以按优先级执行命令，但不知道如何基于已有的token数组构建AST；同时也希望了解更易实现的方案。

我已经实现了词法分析器，能将命令行切割为token数组，例如命令echo ls >> cc | cat -e ; ls > cc; cat < cc会生成如下token数组：
{"echo ls", ">>", "cc", "|", "cat -e ", ";", "ls", ">", "cc", ";", "cat", "<", "cc"}

以下是我的词法分析器代码：

typedef enum{
    TOKEN_REDIR_L,
    TOKEN_DQ,
    TOKEN_REDIR_R,
    TOKEN_DB_REDIR_L,
    TOKEN_DB_REDIR_R,
    TOKEN_PIPE,
    TOKEN_SEMI,
    TOKEN_CMD
} e_token_type;

typedef struct s_token_name{
    char *name;
    e_token_type type;
    unsigned int size; 
} token;

typedef struct s_token_lexer{
    int size;
    token list[2048];
} token_lexer;

static const token tok_name[] =
{
    {">>", TOKEN_DB_REDIR_L, 2},
    {"<<", TOKEN_DB_REDIR_R, 2},
    {">", TOKEN_REDIR_L, 1},
    {"<", TOKEN_DB_REDIR_R, 1},
    {"|", TOKEN_PIPE, 1},
    {";", TOKEN_SEMI, 1},
    {NULL, 1, 0}
};

token search_token_type(const char* str)
{
    const token *tmp = tok_name;
    token not_found = {0, 0, 0};

    while (tmp->name){
        if (my_strncmp(str, tmp->name, tmp->size)){
            return (*tmp);
        }
        ++tmp;
    }
    return (not_found);
}

void add_to_lexer
(token_lexer *li, char const *str, int text_size, e_token_type type)
{
    token tok;
    int i = 0;
    while (*str == ' ' && *str != '\0'){
        str++; i++;
    }
    tok.name = my_strncpy(tok.name, str, text_size - i);
    tok.size = text_size;
    tok.type = type;
    li->list[li->size] = tok;
    li->size++;
}

token_lexer *make_token_list(char const *str)
{
    char const *prev = str;
    int size = 0;
    token curr;
    token_lexer *li = malloc(sizeof(token_lexer));
    li->size = 0;

    for (; *str; str++){
        curr = search_token_type(str);
        if (curr.name != 0 && !my_strcmp(prev, str)){
            str += curr.size;
            add_to_lexer(li, prev, str - prev - curr.size, TOKEN_CMD);
            prev = str;
        }if (curr.name != 0){
            li->list[li->size++] = curr;
            str += curr.size;
        }
    }add_to_lexer(li, prev, str - prev, TOKEN_CMD);
    return (li);
}

int main(int ac, char **av)
{
    char *str = "echo ls >> cc | cat -e  cc ; ls > cc; cat < cc";
    token_lexer *li = make_token_list(str);
    for (int i = 0; i < li->size; i++){
        printf("%s\n", li->list[i]);
    }
}
解决方案

一、更易实现的分步处理方案

Shell命令优先级从高到低为：重定向 > 管道 > 分号。可以按该优先级分层处理token数组，无需构建完整AST：

1. 拆分分号分隔的命令块

分号;是最低优先级的命令分隔符，先将整个token数组按TOKEN_SEMI拆分为独立命令块。示例中的命令会拆成3个块：

  • ["echo ls", ">>", "cc", "|", "cat -e "]
  • ["ls", ">", "cc"]
  • ["cat", "<", "cc"]

每个块独立处理，按顺序执行即可。

2. 处理命令块中的管道

管道|优先级高于分号，对每个命令块，按TOKEN_PIPE拆分为多个子命令段（每个段包含命令和对应的重定向）。第一个块会拆成：

  • ["echo ls", ">>", "cc"]
  • ["cat -e "]

管道处理逻辑：前一个命令的输出作为后一个命令的输入，需依次创建子进程，用pipe()系统调用连接它们的标准输入输出。

3. 处理子命令段的重定向

重定向优先级最高，对每个子命令段解析重定向符号和文件名：

  • >/>>：对应标准输出重定向，前者覆盖文件，后者追加内容
  • </<<：对应标准输入重定向，<<为here-doc，需读取输入直到分界符

处理时，执行命令前用open()打开文件，再用dup2()替换子进程的STDIN_FILENO或STDOUT_FILENO，最后关闭原文件描述符。

实现伪代码示例 

// 按分号拆分命令块
void split_by_semi(token_lexer *li, list *cmd_blocks) {
    token_lexer current_block;
    current_block.size = 0;
    for (int i=0; i<li->size; i++) {
        if (li->list[i].type == TOKEN_SEMI) {
            add_block(cmd_blocks, current_block);
            reset_block(&current_block);
        } else {
            add_token(&current_block, li->list[i]);
        }
    }
    add_block(cmd_blocks, current_block);
}

// 处理单个命令块的管道逻辑
void process_pipe_block(token_lexer *block) {
    int prev_pipe[2];
    int has_prev_pipe = 0;
    token_lexer cmd_segment;
    cmd_segment.size = 0;

    for (int i=0; i<block->size; i++) {
        if (block->list[i].type == TOKEN_PIPE) {
            execute_cmd_segment(&cmd_segment, has_prev_pipe, prev_pipe);
            pipe(prev_pipe);
            has_prev_pipe = 1;
            reset_block(&cmd_segment);
        } else {
            add_token(&cmd_segment, block->list[i]);
        }
    }
    execute_cmd_segment(&cmd_segment, has_prev_pipe, prev_pipe);
}

// 处理单个命令段的重定向并执行
void execute_cmd_segment(token_lexer *seg, int has_prev_pipe, int prev_pipe[2]) {
    int stdin_fd = STDIN_FILENO;
    int stdout_fd = STDOUT_FILENO;
    char *cmd = NULL;

    for (int i=0; i<seg->size; i++) {
        if (seg->list[i].type == TOKEN_CMD) {
            cmd = seg->list[i].name;
        } else if (seg->list[i].type == TOKEN_REDIR_L) { // >
            i++;
            stdout_fd = open(seg->list[i].name, O_WRONLY | O_CREAT | O_TRUNC, 0644);
        } else if (seg->list[i].type == TOKEN_DB_REDIR_L) { // >>
            i++;
            stdout_fd = open(seg->list[i].name, O_WRONLY | O_CREAT | O_APPEND, 0644);
        } else if (seg->list[i].type == TOKEN_REDIR_R) { // <
            i++;
            stdin_fd = open(seg->list[i].name, O_RDONLY, 0644);
        } else if (seg->list[i].type == TOKEN_DB_REDIR_R) { // <<
            i++;
            int tmp_fd = open("/tmp/here_doc.tmp", O_WRONLY | O_CREAT | O_TRUNC, 0644);
            char buf[1024];
            while (fgets(buf, 1024, stdin)) {
                if (strcmp(buf, seg->list[i].name) == 0) break;
                write(tmp_fd, buf, strlen(buf));
            }
            close(tmp_fd);
            stdin_fd = open("/tmp/here_doc.tmp", O_RDONLY, 0644);
        }
    }

    pid_t pid = fork();
    if (pid == 0) {
        if (has_prev_pipe) {
            dup2(prev_pipe[0], STDIN_FILENO);
            close(prev_pipe[0]);
            close(prev_pipe[1]);
        }
        if (stdin_fd != STDIN_FILENO) {
            dup2(stdin_fd, STDIN_FILENO);
            close(stdin_fd);
        }
        if (stdout_fd != STDOUT_FILENO) {
            dup2(stdout_fd, STDOUT_FILENO);
            close(stdout_fd);
        }
        char **argv = split_cmd_to_argv(cmd);
        execvp(argv[0], argv);
        perror("execvp");
        exit(1);
    } else if (pid > 0) {
        if (has_prev_pipe) close(prev_pipe[1]);
        waitpid(pid, NULL, 0);
    }
}

二、基于AST的实现方案

若要构建AST，需先定义节点类型，再用递归下降解析器构建AST，最后遍历执行。

1. AST节点类型定义 

typedef enum {
    NODE_CMD,       // 基础命令节点
    NODE_REDIR,     // 重定向节点
    NODE_PIPE,      // 管道节点
    NODE_SEMI       // 命令分隔节点
} ast_node_type;

typedef struct ast_node {
    ast_node_type type;
    union {
        char **cmd_argv; // 基础命令的参数数组
        struct { // 重定向节点：子命令+文件名+类型
            struct ast_node *cmd;
            char *filename;
            e_token_type redir_type;
        } redir;
        struct { // 管道节点：前后命令
            struct ast_node *left;
            struct ast_node *right;
        } pipe;
        struct { // 分号节点：前后命令块
            struct ast_node *left;
            struct ast_node *right;
        } semi;
    } data;
} ast_node;

2. 递归下降解析器实现

按优先级从低到高编写解析函数：

int token_idx = 0;
token_lexer *global_lexer;

// 解析分号分隔的命令序列
ast_node *parse_semi() {
    ast_node *node = parse_pipe();
    while (token_idx < global_lexer->size && global_lexer->list[token_idx].type == TOKEN_SEMI) {
        token_idx++;
        ast_node *new_node = malloc(sizeof(ast_node));
        new_node->type = NODE_SEMI;
        new_node->data.semi.left = node;
        new_node->data.semi.right = parse_pipe();
        node = new_node;
    }
    return node;
}

// 解析管道连接的命令
ast_node *parse_pipe() {
    ast_node *node = parse_redir();
    while (token_idx < global_lexer->size && global_lexer->list[token_idx].type == TOKEN_PIPE) {
        token_idx++;
        ast_node *new_node = malloc(sizeof(ast_node));
        new_node->type = NODE_PIPE;
        new_node->data.pipe.left = node;
        new_node->data.pipe.right = parse_redir();
        node = new_node;
    }
    return node;
}

// 解析带重定向的命令
ast_node *parse_redir() {
    ast_node *node = parse_cmd();
    while (token_idx < global_lexer->size && 
           (global_lexer->list[token_idx].type == TOKEN_REDIR_L ||
            global_lexer->list[token_idx].type == TOKEN_DB_REDIR_L ||
            global_lexer->list[token_idx].type == TOKEN_REDIR_R ||
            global_lexer->list[token_idx].type == TOKEN_DB_REDIR_R)) {
        e_token_type redir_type = global_lexer->list[token_idx].type;
        token_idx++;
        char *filename = global_lexer->list[token_idx].name;
        token_idx++;
        ast_node *new_node = malloc(sizeof(ast_node));
        new_node->type = NODE_REDIR;
        new_node->data.redir.cmd = node;
        new_node->data.redir.filename = filename;
        new_node->data.redir.redir_type = redir_type;
        node = new_node;
    }
    return node;
}

// 解析基础命令
ast_node *parse_cmd() {
    ast_node *node = malloc(sizeof(ast_node));
    node->type = NODE_CMD;
    char *cmd_str = global_lexer->list[token_idx].name;
    node->data.cmd_argv = split_cmd_to_argv(cmd_str);
    token_idx++;
    return node;
}

// 构建AST入口
ast_node *build_ast(token_lexer *lexer) {
    global_lexer = lexer;
    token_idx = 0;
    return parse_semi();
}

3. 遍历AST执行命令 

void execute_ast(ast_node *node) {
    if (!node) return;
    switch (node->type) {
        case NODE_CMD: {
            pid_t pid = fork();
            if (pid == 0) {
                execvp(node->data.cmd_argv[0], node->data.cmd_argv);
                perror("execvp");
                exit(1);
            } else if (pid > 0) {
                waitpid(pid, NULL, 0);
            }
            break;
        }
        case NODE_REDIR: {
            int fd = -1;
            switch (node->data.redir.redir_type) {
                case TOKEN_REDIR_L:
                    fd = open(node->data.redir.filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
                    dup2(fd, STDOUT_FILENO);
                    break;
                case TOKEN_DB_REDIR_L:
                    fd = open(node->data.redir.filename, O_WRONLY | O_CREAT | O_APPEND, 0644);
                    dup2(fd, STDOUT_FILENO);
                    break;
                case TOKEN_REDIR_R:
                    fd = open(node->data.redir.filename, O_RDONLY, 0644);
                    dup2(fd, STDIN_FILENO);
                    break;
                case TOKEN_DB_REDIR_R: {
                    int tmp_fd = open("/tmp/here_doc.tmp", O_WRONLY | O_CREAT | O_TRUNC, 0644);
                    char buf[1024];
                    while (fgets(buf, 1024, stdin)) {
                        if (strcmp(buf, node->data.redir.filename) == 0) break;
                        write(tmp_fd, buf, strlen(buf));
                    }
                    close(tmp_fd);
                    fd = open("/tmp/here_doc.tmp", O_RDONLY, 0644);
                    dup2(fd, STDIN_FILENO);
                    break;
                }
            }
            execute_ast(node->data.redir.cmd);
            if (fd != -1) {
                close(fd);
            }
            break;
        }
        case NODE_PIPE: {
            int pipe_fd[2];
            pipe(pipe_fd);
            pid_t left_pid = fork();
            if (left_pid == 0) {
                close(pipe_fd[0]);
                dup2(pipe_fd[1], STDOUT_FILENO);
                close(pipe_fd[1]);
                execute_ast(node->data.pipe.left);
                exit(0);
            }
            pid_t right_pid = fork();
            if (right_pid == 0) {
                close(pipe_fd[1]);
                dup2(pipe_fd[0], STDIN_FILENO);
                close(pipe_fd[0]);
                execute_ast(node->data.pipe.right);
                exit(0);
            }
            close(pipe_fd[0]);
            close(pipe_fd[1]);
            waitpid(left_pid, NULL, 0);
            waitpid(right_pid, NULL, 0);
            break;
        }
        case NODE_SEMI:
            execute
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
火山引擎 最新活动
全面开放
Doubao-Seedance-2.5全新模型升级

模型再升级,30秒超长叙事, 模态参考扩容

HOT
方舟Codingplan

模型自由，工具不限，最新支持 Deepseek-V4 系列、GLM-5.3 系列

HOT
方舟Agent plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列

HOT
新用户特惠专场

大模型19元起，Al应用9.9元畅享，新人首购爆款尽享优惠

最近更新时间：2026.07.27 10:13:57