在 C 中从 bash 创建一个 AST

Question

我正在尝试在没有任何高级库帮助的情况下（即从头开始）在 C 中构建一个迷你 Bash 解释器。我必须管理简单的运算符，例如 '<'、'|'、'<<'、'>>'、'>'.
我被告知要构建输入的 AST 以促进执行过程。问题是我不明白我应该如何建造一个。

到目前为止，我已经将我的输入转换为标记，但不知道如何从中创建 AST：

typedef struct       s_token
{
    enum e_TokenType type;
    char             *lexeme;
    struct s_token   *prev;
    struct s_token   *next;
}                    t_token;

你能解释一下如何把它变成函数式 AST 吗？例如这个输入：

cat << EOF > file | wc -c | tr -d " " > file2

我想 AST 应该是这样的：

我看过其他描述如何操作的帖子，但它们是在 JS/Python（我不熟悉这些语言）并且在我感兴趣的部分使用库。

Answer 1

我会创建一个更像这样的 AST：

                         __ PIPELINE__
                     ___/              \____
                    /                       \
            COMMAND                    __ PIPELINE _
          /        \                  /             \
    ARGUMENTS   REDIRECTIONS      COMMAND         _ COMMAND __
        |          |     |           |           /            \
       cat        <<     >       ARGUMENTS    ARGUMENTS   REDIRECTIONS
                   |     |         |   |      |   |   |        |
                 "..."  file      wc  -c      tr  -d " "       >
                                                               |
                                                             file2

与您的显着差异：

命令由参数列表和重定向列表组成。
重定向具有类型（<、>、>> 等）和字符串或文件 source/target.
EOF heredoc 被转换为纯字符串节点（"..." 以上）。 here 文档最终只是字符串的语法糖。如果我这样做，我会在词法分析阶段处理 EOF 并将其转换为一个简单的字符串供解析器处理。 EOF 不会出现在 AST 中。

这是一个粗略的草图，但其想法是以更合乎逻辑的方式表示组件。你画你的方式，> 和 << 看起来像二元运算符，其他部分作为操作数。这就是您解析 C 程序而不是 shell 命令的方式。

在 C 中从 bash 创建一个 AST

Create an AST from bash in C

c

bash

abstract-syntax-tree