[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: AST transformations
Hi Jeff.
It has been a while, and nobody answered. So, I'll try to help you.
I have attached to this message a simple, yet complete example of a
tranformation to simplify the SableCC generated AST after parsing.
The problem is that a SableCC grammar has to explicitely express
operator precedence. This is good for parsing unambiguously. But, the
resulting AST is not exactly what we would generally like to work with.
The ideal AST would normally be as simple as possible.
An ambiguous is a problem for parsing, but it is not really a problem in
an AST, because the AST expresses the exact interpretation we want. The
only potential problem with an AST of an ambiguous grammar is when you
want to "print" back the program: for expressions, you need to add
parentheses.
So, here us the example:
You have a simple expression grammar. Here's the LALR(1) version:
Tokens
plus = '+';
mult = '*';
num = ['0'..'9']+;
Productions
exp =
{plus} exp plus factor |
{fator} factor;
factor =
{mult} factor mult num |
{num} num;
You would probably like to work with an AST that uses the following
grammar instead:
Productions
exp =
{plus} [lexp]:exp plus [rexp]:exp |
{mult} [lexp]:exp mult [rexp]:exp |
{num} num;
So here is how you would proceed. First you use "hidden alternatives"
to make SableCC generate additional AST nodes for the new grammar.
This also means that you should change the name of the {plus}
alternative of the "exp" production in the LALR(1) grammar.
exp =
{tmpplus} exp plus factor |
{factor} factor |
({plus} [lexp]:exp plus [rexp]:exp) |
({mult} [lexp]:exp mult [rexp]:exp) |
({num} num);
factor =
{mult} factor mult num |
{num} num;
Then you build an AST fixer by extending DepthFirstAdapter and doing a
bottom up transformation. The tricky part is to use a hashtable to
avoid type problems. You should override the "outAXXX" for each
alternative of the original grammar that you want to eliminate.
I hope this helps you.
Etienne
P.S.: The ASTPrinter class should be a very interesting debugging tools
for visualizing ANY SableCC AST.
jvb@uwyo.edu wrote:
>
> Has anybody worked a tool that enables one to write simple
> transformations on ASTs and have the messy java code that
> actually manipulates the ASTs be generated automatically?
>
> Thanks in advance,
>
> Jeff
> ----
>
> Jeffrey Van Baalen
> Computer Science Department and Automated Software Engineering Group
> University of Wyoming NASA Ames Research Center
> jvb@uwyo.edu jvb@ptolemy.arc.nasa.gov
--
----------------------------------------------------------------------
Etienne M. Gagnon, M.Sc. e-mail: egagnon@j-meg.com
Author of SableCC: http://www.sable.mcgill.ca/sablecc/
----------------------------------------------------------------------
import java.util.*;
import exp.analysis.*;
import exp.node.*;
public class ASTFixer extends DepthFirstAdapter
{
// A single instance. (Assumes no nulti-threading).
private static final ASTFixer instance = new ASTFixer();
private final Hashtable results = new Hashtable();
private ASTFixer()
{
}
public static void fix(Node ast)
{
ast.apply(instance);
}
// Start with "num" and go up. (Easier for my brain to visualize the AST fixing progression this way).
public void outANumFactor(ANumFactor node)
{
// We cannot replace the node, so we store the replacement in the hashtable.
results.put(node, new ANumExp(node.getNum()));
}
public void outAMultFactor(AMultFactor node)
{
// We cannot replace the node, so we store the replacement in the hashtable.
results.put(node, new AMultExp(
(PExp) results.remove(node.getFactor()), // retrieve and clear to save memory
node.getMult(),
new ANumExp(node.getNum())));
}
public void outAFactorExp(AFactorExp node)
{
node.replaceBy((PExp) results.remove(node.getFactor()));
}
public void outATmpplusExp(ATmpplusExp node)
{
node.replaceBy(new APlusExp(
node.getExp(),
node.getPlus(),
(PExp) results.remove(node.getFactor())));
}
}
import java.util.*;
import exp.analysis.*;
import exp.node.*;
public class ASTPrinter extends DepthFirstAdapter
{
// A single instance. (Assumes no nulti-threading).
private static final ASTPrinter instance = new ASTPrinter();
private ASTPrinter()
{
}
private int indent = 0;
private void indent()
{
System.out.print(System.getProperty("line.separator"));
for(int i = 0; i < indent; i++)
{
System.out.print(" ");
}
}
public static void print(Node ast)
{
ast.apply(instance);
}
public void defaultIn(Node node)
{
indent();
System.out.print(node.getClass() + ":[");
indent++;
}
public void defaultOut(Node node)
{
indent--;
indent();
System.out.print("]");
}
public void defaultCase(Node node)
{
indent();
System.out.print("(" + ((Token) node).getText() + ")");
}
}
Package exp;
Tokens
plus = '+';
mult = '*';
num = ['0'..'9']+;
blank = (' ' | 10 | 13)+;
Ignored Tokens
blank;
Productions
exp =
{tmpplus} exp plus factor |
{factor} factor |
({plus} [lexp]:exp plus [rexp]:exp) |
({mult} [lexp]:exp mult [rexp]:exp) |
({num} num);
factor =
{mult} factor mult num |
{num} num;
import java.io.*;
import exp.lexer.*;
import exp.parser.*;
import exp.node.*;
public class Main
{
public static void main(String[] arguments)
{
try
{
if(arguments.length != 1)
{
System.out.println("usage:");
System.out.println(" java Main filename");
System.exit(1);
}
Node ast = new Parser(
new Lexer(
new PushbackReader(
new BufferedReader(
new FileReader(arguments[0])), 1024))).parse();
ASTFixer.fix(ast);
ASTPrinter.print(ast);
}
catch(Exception e)
{
e.printStackTrace();
System.out.println(e);
System.exit(1);
}
}
}