java - 如何打印java中给定语法的解析器生成的解析树？

Question

我有一个扫描仪，它返回 token 对象的 ArrayList。每个 token 对象由令​​牌和 token 类型组成。我的目标是使用以下语法将标记解析为树:

expression → term { + term } 
term → factor { - factor }
factor → piece { / piece }
piece → element { * element }
element → ( expression ) | NUMBER | IDENTIFIER

我设法用 java 编写了以下解析器:

public class parserModule {

private ArrayList <Tokens> tokens;

public void consume_token() {
     tokens.remove(0);
}

public String next_token(String func) {

     if (func == "type") {
         return tokens.get(0).getType();
     }

     else {
         return tokens.get(0).getToken();
     }
}

public interface PTNode {
    PTNode getLeftSubtree();
    PTNode getRightSubtree();
}

class PTInteriorNode implements PTNode {

    char operator;
    PTNode left;
    PTNode right;

    public PTInteriorNode(char operator, PTNode left, PTNode right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }

    char getOperator() {
        return operator;
    }

    @Override
    public PTNode getLeftSubtree() {
        return left;
    }

    @Override
    public PTNode getRightSubtree() {
        return right;
    }

}

class PTLeafNode implements PTNode {

    private double number;
    private String identifier;

    public PTLeafNode(double n) {
        number = n;
    }

    public PTLeafNode(String n) {
        identifier = n;
    }

    double getNumber() {
        return number;
    }

    String getIden() {
        return identifier;
    }

    @Override
    public PTNode getLeftSubtree() {
        return null;
    }

    @Override
    public PTNode getRightSubtree() {
        return null;
    }
}

PTNode parseElement() { 
    if (next_token(" ").contentEquals("(")) {
        consume_token();
        PTNode tree = parseExpression();

        if(next_token(" ").contentEquals(")")) {
            consume_token();
            return tree;
        }

        else {
            System.out.println("ERROR") ;
        }
    }

    else if(next_token("type").equals("NUMBER")) {
        Double n = Double.valueOf(next_token(" "));
        consume_token();
        return new PTLeafNode(n);
    }

    else if(next_token("type").equals("IDENTIFIER")) {
        String n = next_token(" ");
        consume_token();
        return new PTLeafNode(n);
    }

    else {
        System.out.println("ERROR");
    }
    return null;

}

PTNode parsePiece() { 
    PTNode tree = parseElement(); 

    while (next_token(" ").equals("*"))  {
        consume_token();
        tree = new PTInteriorNode('*', tree, parseElement());
    }

    return tree;
}

PTNode parseFactor() { 
    PTNode tree = parsePiece(); 

    while (next_token(" ").equals("/"))  {
        consume_token();
        tree = new PTInteriorNode('/', tree, parsePiece());
    }

    return tree;
}

PTNode parseTerm() { 
    PTNode tree = parseFactor(); 

    while (next_token(" ").equals("-"))  {
        consume_token();
        tree = new PTInteriorNode('-', tree, parseFactor());
    }

    return tree;
}

PTNode parseExpression() { 
    PTNode tree = parseTerm(); 

    while (next_token(" ").equals("+"))  {
        consume_token();
        tree = new PTInteriorNode('+', tree, parseTerm());
    }

    return tree;
}

public void Parser(ArrayList <Tokens> tokenList) {
    tokens = tokenList;
}
}

如果输入为:4 * (8 + 2/x - 1)

我的输出目标是:

* : PUNCTUATION
    4 : NUMBER
    + : PUNCTUATION
            8 : NUMBER
            - : PUNCTUATION
                    / : PUNCTUATION
                            2 : NUMBER
                            x : IDENTIFIER
                    1 : NUMBER

我不知道如何遍历这个。

Answer 1

基本上，您想要对解析树进行递归前序遍历，并包含一个整数深度参数，以便您知道缩进多远这是一个简单的示例(保证不一定是工作代码，但它应该给你一个总体思路):

public class Node<T,V> {
    T type;
    V value;
    Node<T,V> left, right;
}

// ...

private static final int INDENT_WIDTH = 4;
// ...

public void printParseTree(Node root) {
    preOrder(root, 0);
}

private void preOrder(Node root, int depth){
    if (root != null) {
        for (int i = 0; i < depth * INDENT_WIDTH; ++i) {
            System.out.print(" ");
        }
        System.out.println(root.value.toString() + ":" + root.type.toString());
        preOrder(root.left, depth+1);
        preOrder(root.right, depth+1);
    }
}

根据您的应用程序的需要进行调整。