[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Mapping lists during AST transformation
Hi Niklas,
Niklas Matthies wrote:
> On Sat 2006-10-28 at 17:29h, Etienne Gagnon wrote on sablecc-user:
>>If this doesn't work, it is probably because the "context" can only be
>>determined by the "right" context (i.e. by tokens that follow id_list).
> That's exactly the case, read below.
I see. So, to answer your original question: no, it is not possible to
build distinct id* and expr* lists depending on the context because
CST->AST transformation happens during the parsing phase. SableCC
doesn't currently have post-parsing automatic CST->AST. That would be
an interesting M.Sc. project... Just send me an interested student to
work on it. ;-)
> ((a, b, c) -> a + b * c)(1, 2, 3)
Neat. :-)
One thing you could do, though, is to approach the problem from a
different angle. You could allow for a wider parsing language and then
weed the AST of illegal constructs. This would lead to some interesting
consequences:
1- You can report more meaningful messages to users.
2- It is quite easy to do the pruning.
3- The post-parsing "manual" AST transformations is simple to do, as
there is a single case to deal with (transform exp* into id*).
I have attached a fully functional example illustrating this solution.
Note how it can tell the user that the Nth parameter is invalid. This
is much clearer than a parse error about an unexpected '->'. :-)
Hoping this helps,
Etienne
--
Etienne M. Gagnon, Ph.D. http://www.info2.uqam.ca/~egagnon/
SableVM: http://www.sablevm.org/
SableCC: http://www.sablecc.org/
import functional.parser.*;
import functional.lexer.*;
import functional.node.*;
import functional.analysis.*;
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args) throws Exception
{
System.out.print("Please type an expression: ");
Start ast =
new Parser(new Lexer(new PushbackReader(new InputStreamReader(System.in), 1024))).parse();
ast.apply(new Weeder());
ast.apply(new Transformer());
// You'll likely want to weed the ast again, now, to disallow
// empty tuples. You'll probably want to also transform simple
// tuples (with one expression) into exp; in other words, remove
// one depth level for simple tuples. I leave this as an
// exercise. :-)
System.out.println("==>");
ast.getPProgram().apply(new PrettyPrinter());
System.out.println();
}
}
class Weeder extends DepthFirstAdapter
{
@Override
public void caseAObsoleteExp(AObsoleteExp node)
{
// params should be a var or a tuple
PExp params = node.getParams();
if(!(params instanceof AVarExp || params instanceof ATupleExp))
{
TArrow arrow = node.getArrow();
throw new RuntimeException(
"Semantic error: Invalid parameter list before '->' at [" +
arrow.getLine() + "," + arrow.getPos() + "]");
}
// if it is a tuple, then it must be a list of vars.
if(params instanceof ATupleExp)
{
List<PExp> exps = ((ATupleExp) params).getExps();
int current_param = 0;
for(PExp exp : exps)
{
current_param++;
if(!(exp instanceof AVarExp))
{
TArrow arrow = node.getArrow();
throw new RuntimeException(
"Semantic error: Invalid parameter number " + current_param + " before '->' at [" +
arrow.getLine() + "," + arrow.getPos() + "]");
}
}
}
}
}
class Transformer extends DepthFirstAdapter
{
@Override
public void outAObsoleteExp(AObsoleteExp node)
{
if(node.getParams() instanceof AVarExp)
{
AVarExp params = (AVarExp) node.getParams();
LinkedList<TId> idList = new LinkedList<TId>();
idList.add(params.getVar());
node.replaceBy(new ALambdaExp(idList, node.getBody()));
}
else
{
ATupleExp params = (ATupleExp) node.getParams();
List<PExp> exps = params.getExps();
LinkedList<TId> idList = new LinkedList<TId>();
for(PExp exp : exps)
{
AVarExp param = (AVarExp) exp;
idList.add(param.getVar());
}
node.replaceBy(new ALambdaExp(idList, node.getBody()));
}
}
}
class PrettyPrinter extends DepthFirstAdapter
{
private int indentation;
private void indent()
{
System.out.println();
for(int i = 0; i < indentation; i++)
{
System.out.print(" ");
}
}
@Override
public void defaultIn(Node node)
{
indent();
System.out.print("[" + node.getClass().getSimpleName() + ":");
indentation++;
}
@Override
public void defaultCase(Node node)
{
Token token = (Token) node;
indent();
System.out.print(token.getText());
}
@Override
public void defaultOut(Node node)
{
indentation--;
indent();
System.out.print("]");
}
}
Package functional;
Helpers
any = [0..0xffff];
cr = 13;
lf = 10;
tab = 9;
spc = ' ';
eol = cr | lf | cr lf;
not_eol = [any-[cr+lf]];
digit = ['0'..'9'];
letter = [['a'..'z']+['A'..'Z']];
Tokens
l_par = '(';
r_par = ')';
comma = ',';
plus = '+';
minus = '-';
arrow = '->';
number = digit+;
id = letter (letter | digit)*;
blank = (spc | tab | eol)+;
comment = '//' not_eol eol?;
Ignored Tokens
blank,
comment;
Productions
program = exp;
exp_list {-> exp* } =
l_par exp_list_body? r_par {-> [exp_list_body.exp] };
exp_list_body {-> exp* } =
exp additional_exp* {-> [exp, additional_exp.exp] };
additional_exp {-> exp } =
comma exp {-> exp };
exp =
{lambda} term arrow exp {-> New exp.obsolete(term.exp, arrow, exp) } |
{simple} arith_exp {-> arith_exp.exp };
arith_exp {-> exp } =
{add} arith_exp plus application_exp {-> New exp.add(arith_exp.exp, application_exp.exp) } |
{sub} arith_exp minus application_exp {-> New exp.sub(arith_exp.exp, application_exp.exp) } |
{simple} application_exp {-> application_exp.exp };
application_exp {-> exp } =
{apply} application_exp term {-> New exp.apply(application_exp.exp, term.exp) } |
{simple} term {-> term.exp };
term {-> exp } =
{tuple} exp_list {-> New exp.tuple([exp_list.exp]) } |
{number} number {-> New exp.number(number) } |
{var} id {-> New exp.var(id) };
Abstract Syntax Tree
program = exp;
exp =
{obsolete} [params]:exp arrow [body]:exp | // parsing AST, before weeding
{lambda} [params]:id* [body]:exp | // after-weeding AST
{add} [l_exp]:exp [r_exp]:exp |
{sub} [l_exp]:exp [r_exp]:exp |
{apply} [l_exp]:exp [r_exp]:exp |
{tuple} [exps]:exp* |
{number} number |
{var} [var]:id;