带语法的抽象语法树

Question

我正在用regex构建一个简单的语法解析器。它可以工作，但现在我想添加抽象语法树。但我还是不知道怎么设置它。我包括了解析器。解析器获取一个字符串，并使用lexer对其进行标记。

这些标记包括值和类型。知道如何设置节点来构建AST吗？

public class Parser {
    lexer lex;
    Hashtable<String, Integer> data = new Hashtable<String, Integer>();


    public Parser( String str){
       ArrayList<Token> token = new ArrayList<Token>();

       String[] strpatt = { "[0-9]*\\.[0-9]+", //0
                            "[a-zA-Z_][a-zA-Z0-9_]*",//1
                            "[0-9]+",//2
                            "\\+",//3
                            "\\-",//4
                            "\\*",//5
                            "\\/",//6
                            "\\=",// 7
                            "\\)",// 8
                            "\\("//9
                          };

        lex = new lexer(strpatt, "[\\ \t\r\n]+");
        lex.set_data(str);
    }
    public int peek() {
      //System.out.println(lex.peek().type);
      return lex.peek().type;
    }
    public boolean peek( String[] regex) {
      return lex.peek(regex);
    }
    public void set_data( String s) {
      lex.set_data(s);
    }
    public Token scan() {
      return lex.scan();
    }
    public int goal() {
      int ret = 0;
      while(peek() != -1) {
        ret = expr();
      }
      return ret;
    }


}

Answer 1

目前，您只是在分析以下内容时进行评估：

ret = ret * term()

想到AST最简单的方法是，它只是一种不同类型的评估。不是像上面那样从数值子计算中生成数值结果，而是根据子计算的描述生成计算的描述。描述被表示为包含基本信息的小结构：

ret = BuildProductNode(ret, term());

或者，也许

    ret = BuildBinaryNode(Product, ret, term());

它是一棵树，因为正在传递的Node对象引用其他Node对象，而不存在具有两个不同父节点的循环或节点。

显然，上面遗漏了很多细节，特别是Node对象的精确性质。但这是个粗略的轮廓。