java用标记列表构造抽象语法树

Question

我想从标记列表中构造一个AST。我正在编写一种脚本语言，我已经完成了词法分析部分，但我不知道如何创建AST。所以问题是，我该如何看待这样的事情：

WORD, int
WORD, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

并将其转换为抽象语法树？最好是，我希望这样做而不需要像ANTLR之类的库，我宁愿尝试自己从头开始。不过，如果这是一项非常复杂的任务，我不介意使用库：）谢谢

Answer 1

一点也不难；事实上，这是我做过的最简单的事情之一。 一般的想法是，每个结构（又名parser rules）只是其他结构的列表，当调用parse（）函数时，它们只是循环遍历它们的子结构，并告诉它们进行解析。这不是一个无限循环；标记是结构，当调用它们的parse（）时，它们扫描lexer输出。他们也应该有一个名字来识别，但这不是必需的。 parse（）通常会返回一个解析树。解析树就像结构一样——子结构列表。有一个“文本”字段及其父结构用于标识也很好。 下面是一个示例（您希望更好地组织它，并为实际项目处理空值）：

public void push(ParseTree tree) { // ParseTree
    children.add(tree);
    text += tree.text;
}

public ParseTree parse() { // Structure
    ParseTree tree = new ParseTree(this);
    for(Structure st: children) {
        tree.push(st.parse());
    }
    return tree;
}

public ParseTree parse() { // Token
    if(!lexer.nextToken() || !matches(lexer.token))
        return null;
    ParseTree tree = new ParseTree(this);
    tree.text = lexer.token;
    return tree;
}

在那里。调用主结构的parse（），就会得到一个AST。当然，这是一个非常简单的例子，不能开箱即用。 有“修饰语”也很有用；e、 g.匹配儿童3一次或多次，儿童2是可选的。这也很容易做到；将它们存储在与子计数大小相同的数组中，并在解析时检查：

public void setModifier(int id, int mod) {
    mods[id] = mod;
}

public ParseTree parse() {
    ...
    ParseTree t;
    switch(mods[i]) {
        case 1: // Optional
            if((t = st.parse()) != null) tree.push(t);
        case 2: // Zero or more times
            while((t = st.parse()) != null) tree.push(t);
        ...
        default:
            tree.push(st.parse());
    }
    ...
}