如何用JJTree生成的AST还原原始代码？JavaCC编译器作业咨询

I’ve worked through similar projects using JavaCC and JJTree, so let’s break this down step by step to help you generate an AST and then traverse it to produce formatted code from your input.

Step 1: Define Your Grammar & AST Nodes with JJTree #

First, you’ll need a .jjt file that combines your language K’s grammar rules with AST node definitions. JJTree uses this to generate both the AST classes and the JavaCC parser that builds the tree.

Here’s a simplified snippet tailored to your example input:

// Define the AST node hierarchy
NODE_SCOPE_BEGIN
public abstract class ASTNode extends SimpleNode {
    public ASTNode(int id) { super(id); }
    public abstract void accept(ASTVisitor visitor);
}

public interface ASTVisitor {
    void visit(ASTProgram program);
    void visit(ASTAssignment assignment);
    void visit(ASTWhileLoop whileLoop);
    void visit(ASTBinaryExpr expr);
    void visit(ASTIdent ident);
    void visit(ASTNumber number);
}

public class ASTProgram extends ASTNode {
    private List<ASTNode> statements = new ArrayList<>();
    public ASTProgram(int id) { super(id); }
    public void addStatement(ASTNode stmt) { statements.add(stmt); }
    public List<ASTNode> getStatements() { return statements; }
    @Override public void accept(ASTVisitor v) { v.visit(this); }
}

public class ASTAssignment extends ASTNode {
    private ASTIdent ident;
    private ASTExpr expr;
    public ASTAssignment(int id) { super(id); }
    public void setIdent(ASTIdent ident) { this.ident = ident; }
    public ASTIdent getIdent() { return ident; }
    public void setExpr(ASTExpr expr) { this.expr = expr; }
    public ASTExpr getExpr() { return expr; }
    @Override public void accept(ASTVisitor v) { v.visit(this); }
}

// Add ASTWhileLoop, ASTBinaryExpr, ASTIdent, ASTNumber classes with similar structure
NODE_SCOPE_END

// Grammar rules that map to AST nodes
Program ::= "begin" (Statement)* "end" # ASTProgram(Statement*)

Statement ::= Assignment | WhileLoop

Assignment ::= IDENT ":=" Expr # ASTAssignment(IDENT, Expr)

WhileLoop ::= "while" Expr "begin" (Statement)* "end" # ASTWhileLoop(Expr, Statement*)

Expr ::= IDENT # ASTIdent(IDENT)
       | NUMBER # ASTNumber(NUMBER)
       | ("+" | "-" | "*") Expr Expr # ASTBinaryExpr(Token, Expr, Expr)

// Lexer rules
TOKEN : { <IDENT: ["a"-"z","A"-"Z"]+> }
TOKEN : { <NUMBER: ["0"-"9"]+> }
TOKEN : { <ASSIGN: ":="> }
TOKEN : { <WHILE: "while"> }
TOKEN : { <BEGIN: "begin"> }
TOKEN : { <END: "end"> }
SKIP : { [" ", "\t", "\n", "\r"] }

This defines:

• An abstract ASTNode base class and ASTVisitor interface for structured traversal
• Concrete nodes for your program’s core structures (Program, Assignment, WhileLoop, etc.)
• Grammar rules that create AST nodes instead of just parsing tokens

Step 2: Generate Parser & AST Classes #

Once your .jjt file is ready, run these commands to generate the necessary code:

1. Run JJTree to convert the .jjt file to a JavaCC .jj file:

   java jjtree YourGrammar.jjt
   

2. Run JavaCC on the generated .jj file to produce the parser, lexer, and AST node classes:

   java javacc YourGrammar.jj
   

This will create all the Java classes you need to parse input into an AST.

Step 3: Implement the Pretty-Print Visitor #

To convert the AST back to formatted code, use the Visitor Pattern—this keeps your traversal logic clean and separate from the AST nodes.

Create a PrettyPrintVisitor that implements your ASTVisitor interface, handling indentation and formatting for each node type:

public class PrettyPrintVisitor implements ASTVisitor {
    private int indentLevel = 0;
    private static final String INDENT = "    "; // 4 spaces for indentation

    private void printIndent() {
        for (int i = 0; i < indentLevel; i++) {
            System.out.print(INDENT);
        }
    }

    @Override
    public void visit(ASTProgram program) {
        System.out.println("begin");
        indentLevel++;
        for (ASTNode stmt : program.getStatements()) {
            printIndent();
            stmt.accept(this);
            System.out.println();
        }
        indentLevel--;
        printIndent();
        System.out.println("end");
    }

    @Override
    public void visit(ASTAssignment assignment) {
        System.out.print(assignment.getIdent().getName() + " := ");
        assignment.getExpr().accept(this);
    }

    @Override
    public void visit(ASTWhileLoop whileLoop) {
        System.out.print("while ");
        whileLoop.getCondition().accept(this);
        System.out.println();
        indentLevel++;
        printIndent();
        System.out.println("begin");
        indentLevel++;
        for (ASTNode stmt : whileLoop.getBody()) {
            printIndent();
            stmt.accept(this);
            System.out.println();
        }
        indentLevel--;
        printIndent();
        System.out.println("end");
        indentLevel--;
    }

    @Override
    public void visit(ASTBinaryExpr expr) {
        System.out.print(expr.getOp().image + " ");
        expr.getLeft().accept(this);
        System.out.print(" ");
        expr.getRight().accept(this);
    }

    @Override
    public void visit(ASTIdent ident) {
        System.out.print(ident.getName());
    }

    @Override
    public void visit(ASTNumber number) {
        System.out.print(number.getValue());
    }
}

Key features here:

• Indentation management for nested begin/end blocks
• Proper spacing around operators and assignment symbols
• Preservation of your language’s prefix operator syntax (like + s * a a)

Step 4: Parse Input & Pretty-Print #

Now, tie it all together in your main program:

import java.io.StringReader;

public class CompilerMain {
    public static void main(String[] args) throws ParseException {
        // Your input code
        String input = "begin a := 2 s := 0 while - a 12 begin s := + s * a a a := + a 2 end end";
        
        // Parse input into AST
        KParser parser = new KParser(new StringReader(input));
        ASTProgram rootNode = parser.program();
        
        // Pretty-print the AST
        PrettyPrintVisitor printer = new PrettyPrintVisitor();
        rootNode.accept(printer);
    }
}

When you run this, the output will be your formatted code:

begin
    a := 2
    s := 0
    while - a 12
        begin
            s := + s * a a
            a := + a 2
        end
end

Key Tips for Success #

• Test incrementally: Start with parsing simple expressions, then add statements, then loops.
• Validate AST structure: Add debug prints to your visitor to ensure the AST matches your input.
• Customize node classes: Use JJTree’s NODE_SCOPE_BEGIN/END to add helper methods (like getters) to your AST nodes for cleaner traversal.

内容的提问来源于stack exchange，提问作者MG_LM_SE