在 C 中从 bash 创建 AST

Question

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

到目前为止，我制作了一个链表，将我的输入转换为标记，但不知道如何从中制作 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

与您的显着差异:

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

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