Как напечатать дерево разбора, сгенерированное парсером для данной грамматики в Java? - PullRequest
Новая
       14

Как напечатать дерево разбора, сгенерированное парсером для данной грамматики в Java?

0 голосов
/ 27 октября 2019

У меня есть сканер, который возвращает ArrayList объектов-токенов. Каждый объект токена состоит из токена и типа токена. Моя цель - разобрать токены в дерево, используя следующую грамматику: 

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

Понятия не имею, как это пройти.

1 Ответ

1 голос
/ 27 октября 2019

Обычно вам нужен рекурсивный обход по предварительному порядку дерева синтаксического анализа с включенным целочисленным аргументом глубина , чтобы вы знали, как далеко отступать. Вот простой пример (гарантированно не обязательно работающий код, но он должендать вам общее представление): 

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);
    }
}

Адаптируйте по мере необходимости для вашего приложения.

...