抽象语法树和打印

Question

目标是使用提供的 Node、IDNode、INTNode 和 StringNode classes 在 JavaCC 中创建 AST。我相信这部分没问题，但我还需要创建一个打印方法，它采用 Node 参数并打印 AST 节点标签。最初，我的问题是节点的子节点是 LinkedLists，不能将其转换为节点以进行递归打印。目前，我收到编译错误，声称节点 n 可能未在 AST 的几个部分中初始化。

我已经尝试过递归打印和循环打印以及直接从 LinkedList 对象而不是从 Node 对象访问标签。我什至无法测试以确保 AST 按预期工作（我按照 class 和实验室 sheet 中显示的方式对其进行编码）因为我无法获得 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 may not have been initialized"，即使它是。

Answer 1

这是一种任务递归。您没有列出所有错误，所以我不知道这是否会解决问题，但这是朝着正确方向迈出的一步。您的问题是您试图打印 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);
        }
    }

Answer 2

我认为主要问题在于您如何编写 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也有类似的错误。

抽象语法树和打印

Abstract Syntax Tree and printing

java

javacc