所以，我正在爲我正在製作的語言做一個類似於Python的解釋器。現在我明白這不是一個小任務，我不期望它工作得很好或者做得很多，但我希望它具有一些基本功能（變量，函數，循環，if語句等）。建立一個口譯員：設計一個AST
因此，目前我處於解釋器獲取文件並將其分割爲令牌列表的階段，現在我準備將這些令牌轉換爲AST。我打算用遞歸下降解析器來做到這一點，我相信我明白，但這是問題所在。比方說，我有以下輸入
1 + 2 * 3
這將輸出7，因爲使用BIDMAS乘法完成首次如此
2 * 3 = 6
然後在添加後
1 + 6 = 7
我知道做如何獲得這個訂單，因爲我有一個簡單的語法，但我不知道如何將它作爲AST存儲。爲了簡化事情的答案，讓我們假設這是您將收到和語法可以
program = add
add = mul {"+" mul}
mul = NUM {"*" NUM}
所以基本上唯一的輸入，你如何讓一個數據結構（S）來存儲一個AST？
P.S.我在C.
免責聲明：本表示是主觀的只是爲了照亮。
基本上，您的AST將像二叉樹一樣構造，其中每個AST節點都是一個「C」結構，它同時包含「左」和「右」指針。 AST的其他元素通常是上下文相關的。例如，變量聲明與函數定義或函數中的表達式。通過替換上述節點1 +（2×3）與您的AST結構將類似於
+
/ \
1 *
/\
2 3
所以：
-----------------
| 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」以及如何對節點進行了足夠的瞭解，並指定了左/右指針。
現在剩下的活動就是對樹進行後期遍歷，以評估表達式併產生結果或發出與編譯結果對齊的適當中間代碼/機器代碼。任何選擇都會帶來大量的思考和計劃。
順便說一句：如前所述，AST節點將通常具有基於您想要表示的抽象級別的屬性。還要注意，一個典型的編譯器可能會因不同的原因而利用多個AST。是的，你有更多的閱讀/學習。
注意：這說明了AST的數據結構，但@mikeb答案對於如何將字符串「1 + 2 * 3」獲取到此類結構的節點中是堅實的。
我會用「調車場」算法，這樣做 - >https://en.wikipedia.org/wiki/Shunting-yard_algorithm
有psudocode有太多。
FTA：
在計算機科學中，調度場算法是用於解析在中間符號指定的數學表達式的方法。它可用於生成後綴表示法字符串（也稱爲反向波蘭表示法（RPN））或抽象語法樹（AST）。該算法由Edsger Dijkstra發明並命名爲「調車場」算法，因爲其操作類似於鐵路調車場。 Dijkstra首先在Mathematisch Centrum報告MR 34/61中描述了Shunting Yard算法。
就像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("\033[1;1H\033[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，只有一種方法來「解決」一個 –
你應該從Aho Seti和Ullman購買編譯器「dragon」書籍，而一個名爲bison的工具可以幫助你在幾分之一的時間內完成你打算「手工」操作的目標 – Leo
我不能使用野牛，因爲這個項目的目標是「手工」完成所有這一切。無論如何感謝 –