Абстрактное синтаксическое дерево и печать

Question

Цель состоит в том, чтобы создать AST в JavaCC, используя предоставленные классы Node, IDNode, INTNode и StringNode.Я считаю, что это нормально, но мне также нужно создать метод печати, который принимает параметр Node и печатает метки узла AST.Первоначально моя проблема заключалась в том, что дочерние узлы для узлов - это списки LinkedList, которые нельзя преобразовать в узлы для рекурсивной печати.В настоящее время я получаю ошибки компиляции, утверждая, что узел n, возможно, не был инициализирован в некоторых частях AST.

Я пробовал рекурсивную печать и циклическую печать, а также непосредственно обращался к меткам из объектов LinkedListиз от узловых объектов.Я даже не могу проверить, чтобы убедиться, что AST работает так, как задумано (я кодировал его так, как я показывал в классе и на лабораторном листе), потому что я не могу заставить java компилироваться.

public class Node
{
    String label;
    LinkedList<Node> children;

    public Node(String label)
    {
        this.label = label;
    }

    public void addChild(Node n)
    {
        if(children == null)
            children = new LinkedList<Node>();
        children.add(n);
    }
}

public class IDNode extends Node
{
    String id;

    public IDNode(String id)
    {
        super("ID");
        this.id = id;
    }
}

public class INTNode extends Node
{
    int value;

    public INTNode(String value)
    {
        super("INT");
        this.value = Integer.parseInt(value);
    }
}

public class StringNode extends Node
{
    String text;

    public StringNode(String text)
    {
        super("STRING");
        this.text = text;
    }
}

PARSER_BEGIN(PPL)

    import java.io.*;
    import java.util.LinkedList;

    class PPL
    {
        public static void main(String[] args) throws ParseException, TokenMgrError
        {
            if(args.length > 0)
            {
                try
                {
                    PPL scan = new PPL(new FileInputStream(args[0]));
                    scan.Program();
                }
                catch(FileNotFoundException ex)
                {
                    System.out.println("File " + args[0] + " not found.");
                }
            }
            else
            {
                System.out.println("Must specify source code file name.");
            }

            Node n = Program();
            printAST(n);
        }

        public static void printAST(Node n)
        {
            if(n == null)
            {
                return;
            }

            System.out.println(n.label);

            while(n != null)
            {
                LinkedList<Node> m = n.children;
                System.out.println(m.label);
            }
        }
    }

/* JavaCC input file for PPL
/* Author: Michael Lord
*/

PARSER_BEGIN(PPL)

    import java.io.*;
    import java.util.LinkedList;

    class PPL
    {
        public static void main(String[] args) throws ParseException, TokenMgrError
        {
            if(args.length > 0)
            {
                try
                {
                    PPL scan = new PPL(new FileInputStream(args[0]));
                    scan.Program();
                }
                catch(FileNotFoundException ex)
                {
                    System.out.println("File " + args[0] + " not found.");
                }
            }
            else
            {
                System.out.println("Must specify source code file name.");
            }

            Node n = Program();
            printAST(n);
        }

        public static void printAST(Node n)
        {
            if(n == null)
            {
                return;
            }

            System.out.println(n.label);

            while(n != null)
            {
                LinkedList<Node> m = n.children;
                System.out.println(m.label);
            }
        }
    }

PARSER_END(PPL)

SKIP : { " " }
TOKEN : { <NEWLINE : "\n"> }
TOKEN : { <TAB : "\t"> }
TOKEN : { <IN : "IN"> }
TOKEN : { <OUT : "OUT"> }
TOKEN : { <IS : "IS"> }
TOKEN : { <IF : "IF"> }
TOKEN : { <ELSE : "ELSE"> }
TOKEN : { <REPEATIF : "REPEATIF"> }
TOKEN : { <PLUS : "+"> }
TOKEN : { <MINUS : "-"> }
TOKEN : { <MUL : "*"> }
TOKEN : { <DIV : "/"> }
TOKEN : { <LEFT_PAREN : "("> }
TOKEN : { <RIGHT_PAREN : ")"> }
TOKEN : { <LESS_THAN : "<"> }
TOKEN : { <MORE_THAN : ">"> }
TOKEN : { <LESS_THAN_OR_EQUAL : "<="> }
TOKEN : { <MORE_THAN_OR_EQUAL : ">=">}
TOKEN : { <NOT_EQUAL : "NOT="> }
TOKEN : { <EQUAL : "="> }
TOKEN : { <AND : "AND"> }
TOKEN : { <OR : "OR"> }
TOKEN : { <NOT : "NOT"> }
TOKEN : { <INT : "0" | ["1" - "9"](["0" - "9"])*> }
TOKEN : { <ID : (["a" - "z", "A" - "Z"])+ ((["0" - "9"] | ["_"])* (["a" - "z", "A" - "Z"])*)* > }
TOKEN : { <OPEN_STRING: "\""> :  STRING }
<STRING> TOKEN : { <STRING_BODY : ("\\\\" | "\\\"" | ~["\"", "\\"])+> }
<STRING> TOKEN : { <CLOSE_STRING : "\""> : DEFAULT }


Node Program():
{
    Node n, child;
}
{
                 { n = new Node("Program"); }
    child = Statement_List() { n.addChild(child); }
    <EOF>
                 { return n; }
}

Node Statement_List():
{
    Node n, child;
}
{
                 { n = new Node("Statement_list"); }
    child = Statement()      { n.addChild(child); }
    (
    child = Statement_List() { n.addChild(child); }
    )?
                 { return n; }
}

Node Statement():
{
    Node n, child;
}
{
                  { n = new Node("Statement"); }
    child = Input()       { n.addChild(child); }
    |
    child = Output()      { n.addChild(child); }
    |
    child = Assign()      { n.addChild(child); }
    |
    child = Conditional() { n.addChild(child); }
    |
    child = Loop()        { n.addChild(child); }
    |
    <NEWLINE>
                  { return n; }
}

Node Input():
{
    Node n, child;
}
{
                 { n = new Node("IN"); }    
    <IN> 
    child = Identifier() { n.addChild(child); } 
    <NEWLINE>
                 { return n; }
}

Node Output():
{
    Node n, child;
    Token t;
}
{
                  { n = new Node("OUT"); }
    <OUT> 
    <LEFT_PAREN> 
    (
    <OPEN_STRING> 
    t = <STRING_BODY>     { n.addChild(new StringNode(t.image)); }
    <CLOSE_STRING> 
    (
    child = Concatenate() { n.addChild(child); }
    child =  Factor()     { n.addChild(child); }
    ( 
    child = Concatenate() { n.addChild(child); }
    <OPEN_STRING> 
    t = <STRING_BODY>     { n.addChild(new StringNode(t.image)); } 
    <CLOSE_STRING>
    )?)?) 
    <RIGHT_PAREN> 
    <NEWLINE>
                  { return n; } 
}

Node Assign():
{
    Node n, child;
}
{
                 { n = new Node("IS"); }
    child = Identifier() { n.addChild(child); } 
    <IS> 
    child = Expression() { n.addChild(child); }
    <NEWLINE>
                 { return n; }
}

Node Conditional():
{
    Node n, child;
}
{
                 { n = new Node("IF"); }
    <IF> 
    <LEFT_PAREN> 
    child = Comparison() { n.addChild(child); }
    <RIGHT_PAREN> 
    <NEWLINE> 
    child = Block()      { n.addChild(child); }
    (
    <ELSE> 
    child = Block()      { n.addChild(child); }
    )?
                 {return n; }
}

Node Loop():
{
    Node n, child;
}
{
    <REPEATIF>      { n = new Node("REPEATIF"); }
    <LEFT_PAREN>
    child = Comparison()    { n.addChild(child); }
    <RIGHT_PAREN>
    <NEWLINE> 
    child = Block()     { n.addChild(child); }
                { return n; }
}

Node Block():
{
    Node n, child;
}
{
                { n = new Node("Block"); }
    (
    <TAB> 
    child = Statement() { n.addChild(child); }
    )+ 
    <NEWLINE>
                { return n; } 
}

Node Expression():
{
    Node n, child;
}
{
             { n = new Node("Expression"); }
    child = Term()   { n.addChild(child); }
    ((
    <PLUS>       { n.addChild(new Node("PLUS")); }
    |
    <MINUS>      { n.addChild(new Node("MINUS")); }
    )
    child = Term()   { n.addChild(child); }
    )*
             { return n; }
}

Node Term():
{
    Node n, child;
}
{
             { n = new Node("Term"); }
    child = Factor() { n.addChild(child); }
    ((
    <MUL>        { n.addChild(new Node("MUL")); }
    |
    <DIV>        { n.addChild(new Node("DIV")); }
    )
    child = Factor() { n.addChild(child); }
    )*
             { return n; }
}

Node Factor():
{
    Node n, child;
}
{
                 { n = new Node("Factor"); }
    child = Identifier() { n.addChild(child); }
    |
    child = Integer()    { n.addChild(child); }
    |
    <LEFT_PAREN> 
    child = Expression() { n.addChild(child); } 
    <RIGHT_PAREN>
                 { return n; }
}

IDNode Identifier():
{
    Token t;
}
{
    t = <ID> { return new IDNode(t.image); }
}

INTNode Integer():
{
    Token t;
}
{
    t = <INT> { return new INTNode(t.image); }
}

Node Comparison():
{
    Node n, child;
}
{
                   { n = new Node("Comparison"); }
    child = Factor()           { n.addChild(child); } 
    (
    child = Compare_Operator() { n.addChild(child); }
    child = Factor()       { n.addChild(child); }
    )?
                   { return n; }
}

Node Compare_Operator():
{
    Node n;
}
{
                { n = new Node("Compare_Operator"); }
    <LESS_THAN>         { n.addChild(new Node("LESS THAN")); }
    |
    <MORE_THAN>         { n.addChild(new Node("MORE THAN")); }
    |
    <LESS_THAN_OR_EQUAL>    { n.addChild(new Node("LESS THAN OR EQUAL")); }
    |
    <MORE_THAN_OR_EQUAL>    { n.addChild(new Node("MORE THAN OR EQUAL")); }
    |
    <NOT_EQUAL>     { n.addChild(new Node("NOT EQUAL")); }
    |
    <EQUAL>         { n.addChild(new Node("EQUAL")); }
                { return n; }
}

Node Concatenate():
{
}
{
    <PLUS>  { return new Node("PLUS"); }
}

Предполагается построить AST и распечатать метки узлов по порядку.Вместо этого я получаю ошибки компиляции, с некоторыми методами печати я получаю ошибку преобразования или несовместимую ошибку типа между LinkedList и Node.В других методах он начинает говорить «n, возможно, не был инициализирован» в некоторых грамматических методах, даже если это так.

Answer 1

Я думаю, что главная проблема в том, как вы написали Statement и подобные процедуры.У вас есть

Node Statement():
{
    Node n, child;
}
{
                  { n = new Node("Statement"); }
    child = Input()       { n.addChild(child); }
    |
    child = Output()      { n.addChild(child); }
    | 
       etc etc
    |
    <NEWLINE>
                  { return n; }
}

Проблема в том, что композиция имеет более высокий приоритет, чем чередование.Вам нужны скобки.Вот так.

Node Statement():
{
    Node n, child;
}
{
    { n = new Node("Statement"); }
    (
       child = Input()       { n.addChild(child); }
    |
       child = Output()      { n.addChild(child); }
    | 
       etc etc
    |
       <NEWLINE>
    )
    { return n; }
}

Есть похожие ошибки в Term, Factor и Compare_Operator.

Answer 2

Для рекурсии заданий такого типа.Вы не перечислили все свои ошибки, поэтому я не знаю, исправит ли это, но это шаг в правильном направлении.Ваша проблема заключалась в том, что вы пытались напечатать метку m, но m - это LinkedList, а не узел.Вам необходимо распечатать метки узлов, содержащихся в LinkedList.

    public static void printAST(Node n)
    {
        if(n == null)
        {
            return;
        }


        System.out.println(n.label);

        if (n.children == null) {
            return;
        }
        for (Node m : n.children)
        {
            printAST(m);
        }
    }