构建解释器：设计 AST
Building an interpreter: designing an AST
所以我正在为我正在制作的类似于 Python 的语言制作解释器。现在我明白这不是一项小任务，我不希望它能很好地工作或做很多事情，但我希望它具有一些基本功能（变量、函数、循环、if 语句等）。
所以目前我正处于解释器获取文件并将其拆分为标记列表的阶段，现在我准备将这些标记转换为 AST。我打算用递归下降解析器来做到这一点，我相信我理解，但这就是问题所在。假设我有以下输入
1 + 2 * 3
这会输出 7，因为使用 BIDMAS 会先完成乘法，所以
2 * 3 = 6
然后在
之后进行加法
1 + 6 = 7
我知道如何获得这个顺序，因为我有一个简单的语法，但我不知道如何将其存储为 AST。为了简化答案，我们假设这是您将收到的唯一输入，语法可以是
program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}
所以基本上，您如何制作数据结构来存储 AST？
P.S。我在 C 中这样做。
我会使用 "Shunting Yard" 算法 -> https://en.wikipedia.org/wiki/Shunting-yard_algorithm
那里也有伪代码。
自由贸易协定：
在计算机科学中，调车场算法是一种解析以中缀表示法指定的数学表达式的方法。它可用于生成后缀表示法字符串（也称为逆波兰表示法 (RPN)）或抽象语法树 (AST)。该算法由 Edsger Dijkstra 发明，并命名为 "shunting yard" 算法，因为它的操作类似于铁路调车场。 Dijkstra 在 Mathematisch Centrum 报告 MR 34/61 中首次描述了调车场算法。
和RPN的评价一样，调车场算法也是基于栈的。中缀表达式是大多数人习惯的数学符号形式，例如“3+4”或“3+4*(2−1)”。对于转换，有两个文本变量（字符串），即输入和输出。还有一个堆栈保存尚未添加到输出队列的运算符。为了转换，程序按顺序读取每个符号并根据该符号执行某些操作。上述示例的结果将是“3 4 +”或“3 4 2 1 - * +”。
调车场算法后来被推广到运算符优先级解析中。
代码，因为有人指出这不是存储它的方法（如果你不喜欢 C - 从 http://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm 中选择）：
#include <sys/types.h>
#include <regex.h>
#include <stdio.h>
typedef struct {
const char *s;
int len, prec, assoc;
} str_tok_t;
typedef struct {
const char * str;
int assoc, prec;
regex_t re;
} pat_t;
enum assoc { A_NONE, A_L, A_R };
pat_t pat_eos = {"", A_NONE, 0};
pat_t pat_ops[] = {
{"^\)", A_NONE, -1},
{"^\*\*", A_R, 3},
{"^\^", A_R, 3},
{"^\*", A_L, 2},
{"^/", A_L, 2},
{"^\+", A_L, 1},
{"^-", A_L, 1},
{0}
};
pat_t pat_arg[] = {
{"^[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?"},
{"^[a-zA-Z_][a-zA-Z_0-9]*"},
{"^\(", A_L, -1},
{0}
};
str_tok_t stack[256]; /* assume these are big enough */
str_tok_t queue[256];
int l_queue, l_stack;
#define qpush(x) queue[l_queue++] = x
#define spush(x) stack[l_stack++] = x
#define spop() stack[--l_stack]
void display(const char *s)
{
int i;
printf("3[1;1H3[JText | %s", s);
printf("\nStack| ");
for (i = 0; i < l_stack; i++)
printf("%.*s ", stack[i].len, stack[i].s); // uses C99 format strings
printf("\nQueue| ");
for (i = 0; i < l_queue; i++)
printf("%.*s ", queue[i].len, queue[i].s);
puts("\n\n<press enter>");
getchar();
}
int prec_booster;
#define fail(s1, s2) {fprintf(stderr, "[Error %s] %s\n", s1, s2); return 0;}
int init(void)
{
int i;
pat_t *p;
for (i = 0, p = pat_ops; p[i].str; i++)
if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED))
fail("comp", p[i].str);
for (i = 0, p = pat_arg; p[i].str; i++)
if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED))
fail("comp", p[i].str);
return 1;
}
pat_t* match(const char *s, pat_t *p, str_tok_t * t, const char **e)
{
int i;
regmatch_t m;
while (*s == ' ') s++;
*e = s;
if (!*s) return &pat_eos;
for (i = 0; p[i].str; i++) {
if (regexec(&(p[i].re), s, 1, &m, REG_NOTEOL))
continue;
t->s = s;
*e = s + (t->len = m.rm_eo - m.rm_so);
return p + i;
}
return 0;
}
int parse(const char *s) {
pat_t *p;
str_tok_t *t, tok;
prec_booster = l_queue = 0;
display(s);
while (*s) {
p = match(s, pat_arg, &tok, &s);
if (!p || p == &pat_eos) fail("parse arg", s);
/* Odd logic here. Don't actually stack the parens: don't need to. */
if (p->prec == -1) {
prec_booster += 100;
continue;
}
qpush(tok);
display(s);
re_op: p = match(s, pat_ops, &tok, &s);
if (!p) fail("parse op", s);
tok.assoc = p->assoc;
tok.prec = p->prec;
if (p->prec > 0)
tok.prec = p->prec + prec_booster;
else if (p->prec == -1) {
if (prec_booster < 100)
fail("unmatched )", s);
tok.prec = prec_booster;
}
while (l_stack) {
t = stack + l_stack - 1;
if (!(t->prec == tok.prec && t->assoc == A_L)
&& t->prec <= tok.prec)
break;
qpush(spop());
display(s);
}
if (p->prec == -1) {
prec_booster -= 100;
goto re_op;
}
if (!p->prec) {
display(s);
if (prec_booster)
fail("unmatched (", s);
return 1;
}
spush(tok);
display(s);
}
return 1;
}
int main()
{
int i;
const char *tests[] = {
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3", /* RC mandated: OK */
"123", /* OK */
"3+4 * 2 / ( 1 - 5 ) ^ 2 ^ 3.14", /* OK */
"(((((((1+2+3**(4 + 5))))))", /* bad parens */
"a^(b + c/d * .1e5)!", /* unknown op */
"(1**2)**3", /* OK */
0
};
if (!init()) return 1;
for (i = 0; tests[i]; i++) {
printf("Testing string `%s' <enter>\n", tests[i]);
getchar();
printf("string `%s': %s\n\n", tests[i],
parse(tests[i]) ? "Ok" : "Error");
}
return 0;
}
免责声明：此表示是主观的，仅用于说明。
从根本上说，您的 AST 将像二叉树一样构造，其中每个 AST 节点都是一个 "C" 结构，其中包含 "left" 和 "right" 指针。 AST 的其他元素通常是上下文相关的。例如，变量声明与函数定义或函数中的表达式。对于您引用的示例，粗糙的树将反映：
+
/ \
1 *
/\
2 3
因此，将上述节点 1 + (2 * 3) 替换为您的 AST 构造将类似于：
-----------------
| type: ADDOP |
| left: struct* |
| right: struct*|
-----------------
/ \
/ \
(ADDOP left points to) (ADDOP right points to)
------------------------ --------------------------
| type: NUMLITERAL | | type: MULTOP |
| value: 1 | | left: struct* |
| left: struct* (null) | | right: struct* |
| right: struct*(null) | --------------------------
------------------------ / \
/ \
(MULTOP left points to) (MULTOP right points to)
------------------------ --------------------------
| type: NUMLITERAL | | type: NUMLITERAL |
| value: 2 | | value: 3 |
| left: struct* (null) | | left: struct* (null) |
| right: struct*(null) | | right: struct* (null) |
------------------------ --------------------------
我假设您对 "C" 以及如何 malloc 节点和分配 left/right 指针有足够的了解。
现在剩下的 activity 将是对树进行 post 顺序遍历以评估表达式并产生结果或发出适当的中间 code/machine 代码与编译结果对齐。任何一种选择都会带来你大量的思考和计划。
顺便说一句：如前所述，AST 节点通常具有基于您要表示的抽象级别的属性。另请注意，典型的编译器可能出于不同原因利用多个 AST。是的，更多 reading/studying 你的部分。
注意：这说明了 AST 的数据结构，但@mikeb 的回答对于如何将字符串“1 + 2 * 3”放入此类节点的方式非常可靠一个结构。
所以我正在为我正在制作的类似于 Python 的语言制作解释器。现在我明白这不是一项小任务，我不希望它能很好地工作或做很多事情，但我希望它具有一些基本功能（变量、函数、循环、if 语句等）。
所以目前我正处于解释器获取文件并将其拆分为标记列表的阶段，现在我准备将这些标记转换为 AST。我打算用递归下降解析器来做到这一点，我相信我理解，但这就是问题所在。假设我有以下输入
1 + 2 * 3
这会输出 7，因为使用 BIDMAS 会先完成乘法，所以
2 * 3 = 6
然后在
之后进行加法1 + 6 = 7
我知道如何获得这个顺序，因为我有一个简单的语法，但我不知道如何将其存储为 AST。为了简化答案，我们假设这是您将收到的唯一输入，语法可以是
program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}
所以基本上，您如何制作数据结构来存储 AST？
P.S。我在 C 中这样做。
我会使用 "Shunting Yard" 算法 -> https://en.wikipedia.org/wiki/Shunting-yard_algorithm
那里也有伪代码。
自由贸易协定：
在计算机科学中，调车场算法是一种解析以中缀表示法指定的数学表达式的方法。它可用于生成后缀表示法字符串（也称为逆波兰表示法 (RPN)）或抽象语法树 (AST)。该算法由 Edsger Dijkstra 发明，并命名为 "shunting yard" 算法，因为它的操作类似于铁路调车场。 Dijkstra 在 Mathematisch Centrum 报告 MR 34/61 中首次描述了调车场算法。
和RPN的评价一样，调车场算法也是基于栈的。中缀表达式是大多数人习惯的数学符号形式，例如“3+4”或“3+4*(2−1)”。对于转换，有两个文本变量（字符串），即输入和输出。还有一个堆栈保存尚未添加到输出队列的运算符。为了转换，程序按顺序读取每个符号并根据该符号执行某些操作。上述示例的结果将是“3 4 +”或“3 4 2 1 - * +”。
调车场算法后来被推广到运算符优先级解析中。
代码，因为有人指出这不是存储它的方法（如果你不喜欢 C - 从 http://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm 中选择）：
#include <sys/types.h>
#include <regex.h>
#include <stdio.h>
typedef struct {
const char *s;
int len, prec, assoc;
} str_tok_t;
typedef struct {
const char * str;
int assoc, prec;
regex_t re;
} pat_t;
enum assoc { A_NONE, A_L, A_R };
pat_t pat_eos = {"", A_NONE, 0};
pat_t pat_ops[] = {
{"^\)", A_NONE, -1},
{"^\*\*", A_R, 3},
{"^\^", A_R, 3},
{"^\*", A_L, 2},
{"^/", A_L, 2},
{"^\+", A_L, 1},
{"^-", A_L, 1},
{0}
};
pat_t pat_arg[] = {
{"^[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?"},
{"^[a-zA-Z_][a-zA-Z_0-9]*"},
{"^\(", A_L, -1},
{0}
};
str_tok_t stack[256]; /* assume these are big enough */
str_tok_t queue[256];
int l_queue, l_stack;
#define qpush(x) queue[l_queue++] = x
#define spush(x) stack[l_stack++] = x
#define spop() stack[--l_stack]
void display(const char *s)
{
int i;
printf("3[1;1H3[JText | %s", s);
printf("\nStack| ");
for (i = 0; i < l_stack; i++)
printf("%.*s ", stack[i].len, stack[i].s); // uses C99 format strings
printf("\nQueue| ");
for (i = 0; i < l_queue; i++)
printf("%.*s ", queue[i].len, queue[i].s);
puts("\n\n<press enter>");
getchar();
}
int prec_booster;
#define fail(s1, s2) {fprintf(stderr, "[Error %s] %s\n", s1, s2); return 0;}
int init(void)
{
int i;
pat_t *p;
for (i = 0, p = pat_ops; p[i].str; i++)
if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED))
fail("comp", p[i].str);
for (i = 0, p = pat_arg; p[i].str; i++)
if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED))
fail("comp", p[i].str);
return 1;
}
pat_t* match(const char *s, pat_t *p, str_tok_t * t, const char **e)
{
int i;
regmatch_t m;
while (*s == ' ') s++;
*e = s;
if (!*s) return &pat_eos;
for (i = 0; p[i].str; i++) {
if (regexec(&(p[i].re), s, 1, &m, REG_NOTEOL))
continue;
t->s = s;
*e = s + (t->len = m.rm_eo - m.rm_so);
return p + i;
}
return 0;
}
int parse(const char *s) {
pat_t *p;
str_tok_t *t, tok;
prec_booster = l_queue = 0;
display(s);
while (*s) {
p = match(s, pat_arg, &tok, &s);
if (!p || p == &pat_eos) fail("parse arg", s);
/* Odd logic here. Don't actually stack the parens: don't need to. */
if (p->prec == -1) {
prec_booster += 100;
continue;
}
qpush(tok);
display(s);
re_op: p = match(s, pat_ops, &tok, &s);
if (!p) fail("parse op", s);
tok.assoc = p->assoc;
tok.prec = p->prec;
if (p->prec > 0)
tok.prec = p->prec + prec_booster;
else if (p->prec == -1) {
if (prec_booster < 100)
fail("unmatched )", s);
tok.prec = prec_booster;
}
while (l_stack) {
t = stack + l_stack - 1;
if (!(t->prec == tok.prec && t->assoc == A_L)
&& t->prec <= tok.prec)
break;
qpush(spop());
display(s);
}
if (p->prec == -1) {
prec_booster -= 100;
goto re_op;
}
if (!p->prec) {
display(s);
if (prec_booster)
fail("unmatched (", s);
return 1;
}
spush(tok);
display(s);
}
return 1;
}
int main()
{
int i;
const char *tests[] = {
"3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3", /* RC mandated: OK */
"123", /* OK */
"3+4 * 2 / ( 1 - 5 ) ^ 2 ^ 3.14", /* OK */
"(((((((1+2+3**(4 + 5))))))", /* bad parens */
"a^(b + c/d * .1e5)!", /* unknown op */
"(1**2)**3", /* OK */
0
};
if (!init()) return 1;
for (i = 0; tests[i]; i++) {
printf("Testing string `%s' <enter>\n", tests[i]);
getchar();
printf("string `%s': %s\n\n", tests[i],
parse(tests[i]) ? "Ok" : "Error");
}
return 0;
}
免责声明：此表示是主观的，仅用于说明。
从根本上说，您的 AST 将像二叉树一样构造，其中每个 AST 节点都是一个 "C" 结构，其中包含 "left" 和 "right" 指针。 AST 的其他元素通常是上下文相关的。例如，变量声明与函数定义或函数中的表达式。对于您引用的示例，粗糙的树将反映：
+
/ \
1 *
/\
2 3
因此，将上述节点 1 + (2 * 3) 替换为您的 AST 构造将类似于：
-----------------
| type: ADDOP |
| left: struct* |
| right: struct*|
-----------------
/ \
/ \
(ADDOP left points to) (ADDOP right points to)
------------------------ --------------------------
| type: NUMLITERAL | | type: MULTOP |
| value: 1 | | left: struct* |
| left: struct* (null) | | right: struct* |
| right: struct*(null) | --------------------------
------------------------ / \
/ \
(MULTOP left points to) (MULTOP right points to)
------------------------ --------------------------
| type: NUMLITERAL | | type: NUMLITERAL |
| value: 2 | | value: 3 |
| left: struct* (null) | | left: struct* (null) |
| right: struct*(null) | | right: struct* (null) |
------------------------ --------------------------
我假设您对 "C" 以及如何 malloc 节点和分配 left/right 指针有足够的了解。
现在剩下的 activity 将是对树进行 post 顺序遍历以评估表达式并产生结果或发出适当的中间 code/machine 代码与编译结果对齐。任何一种选择都会带来你大量的思考和计划。
顺便说一句：如前所述，AST 节点通常具有基于您要表示的抽象级别的属性。另请注意，典型的编译器可能出于不同原因利用多个 AST。是的，更多 reading/studying 你的部分。
注意：这说明了 AST 的数据结构，但@mikeb 的回答对于如何将字符串“1 + 2 * 3”放入此类节点的方式非常可靠一个结构。