Search code examples
javajavacc

Abstract Syntax Tree and printing

Goal is to create an AST in JavaCC using the Node, IDNode, INTNode and StringNode classes provided. I believe that part is fine, but I also need to create a print method which takes a Node param and prints the AST Node labels. Originally, my problem was that the children for the Nodes are LinkedLists which can't be cast into Node for recursive printing. Currently, I'm getting compile errors claiming that Node n may not have been initialized in several parts of the AST.

I've tried recursive printing and loop printing as well as accessing the labels from LinkedList objects directly instead of from Node objects. I can't even test to make sure the AST is working as it's intended (I coded it the way I was shown in class and the lab sheet) because I can't get the java to compile.

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

Expect to build AST and print the labels of the Nodes in order. Instead I get compile errors, with some print methods I get a conversion error or incompatible type error between LinkedList and Node. Other methods it starts saying "n may not have been initialized" in some of the grammar methods, even though it is.

Solution

  • I think the main problem is in how you wrote Statement and similar routines. You have

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

    The problem is that composition has higher precedence than alternation. You need parentheses. Like this.

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

    There are a similar errors in Term, Factor, and Compare_Operator.