Evaluating expressions
|
View:
New views
10 Messages
—
Rating Filter:
Alert me
|
 |
Evaluating expressions
by Henrique Rocha
::
Rate this Message:
Hi,
I'm having a really hard time using SableCC because the documentation is really bad in my opinion. I've read the paper and some chapters of the full thesis and I don't know how to evaluate for example an expression like 1 + 1. In the paper there is an interpreter for a BASIC like language. The method caseADivExpression is defined like this: public void caseADivExpression(ADivExpression node) { try { node.getLeft().apply(this); node.getRight().apply(this); setIntValue(node, getIntValue(node.getLeft()) / getIntValue(node.getRight())); } catch (....) {} } The setIntValue and getIntValue are not listed in the paper. In my code I have: @Override public void caseAPlusExp(APlusExp node) { node.getLeft().apply(this); node.getRight().apply(this); // i need more code here } How can I get the values of both the left and right side and how can I set the value of the plus expression as the sum of the evaluated expressions? I suppose this is really easy to do but I couldn't find any docs on how to do this. :( Thanks. -- Henrique Rocha infossuga.blogspot.com ExpertRating Certified Windows XP Professional ExpertRating Certified Unix Shell Script Professional ExpertRating Certified Unix Professional ExpertRating Certified Object-Oriented Concepts Professional ExpertRating Certified Professional Computer Technician Skills ExpertRating Certified HTML 4 Professional Follow me on Twitter: twitter.com/HenriqueRocha _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: Evaluating expressions
by Etienne M. Gagnon
::
Rate this Message:
Hi Henrique,
With SableCC 3.2 and Java 1.5 or later, you can write: Abstract Syntax Tree
exp =
{div] [left]:exp div [right]:exp |
...
class Evaluator extends DepthFirstAdaptor {
public static int evaluate(Node ast) {
Evaluator evaluator = new Evaluator();
ast.apply(evaluator);
return evaluator.results.get(ast);
}
private Map<Node, Integer> results = new HashMap<Node,Integer>();
public void outADivExp(ADivExp node) {
int left = results.get(node.getLeft());
int right = results.get(node.getRight());
int result = left / right;
results.put(node, result);
}
...
}
...
// in the main() method
System.out.println("result = " + Evaluator.evaluate(ast));
...
This code should be pretty self-explanatory.Note: You should definitely use the outXXX() methods to evaluate expressions; it saves you from writing useless code (e.g. apply() calls). In the paper, I did not have enough space to explain the difference between inXXX, caseXXX, and outXXX methods (caseXXX was required to interpret IF statements). If you find this information useful, feel welcome to write a complete expression evaluator, then add a Wiki page on the site to fully explain your example for future new users. You simply need to create an account, login, then type an url such as http://sablecc.org/wiki/ExpressionEvaluator to create the page. Once you're done, simply add a link to it on the documentation page. Others are welcome to help you, too! (Hint, hint....) Have fun! Etienne Henrique Rocha wrote:
-- Etienne M. Gagnon, Ph.D. SableCC: http://sablecc.org _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
|
|
|
Re: Evaluating expressions
by Henrique Rocha
::
Rate this Message:
Thanks,
You really helped me a lot! I had to analyze your example a little because I'm using SableCC 3 but like SableCC 2 because your paper doesn't have info about 3.x. I've read that it's now possible to do CST to AST transformations, but I'll have to read about that later. I'm still learning about SableCC as you can see, with the main goal of implementing a concurrent imperative language like C but with fork, lock and unlock primitives for a stackless virtual machine. I needed to add this (took some time to find out): public void caseTIntegerLiteral(TIntegerLiteral node) { this.results.put(node, Integer.parseInt(node.getText())); } Because my grammar was very simple, just something like: exp = {number} integer_literal | {plus} [left]:integer_literal plus [right]:integer_literal; I'll learn a bit more about SableCC and I think tomorrow I'll add the expression evaluator with a little explanation for people like me. =) Thanks for developing this tool. -- Henrique Rocha infossuga.blogspot.com ExpertRating Certified Windows XP Professional ExpertRating Certified Unix Shell Script Professional ExpertRating Certified Unix Professional ExpertRating Certified Object-Oriented Concepts Professional ExpertRating Certified Professional Computer Technician Skills ExpertRating Certified HTML 4 Professional Follow me on Twitter: twitter.com/HenriqueRocha _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: Evaluating expressions
by Niklas Matthies
::
Rate this Message:
I actually hacked the SableCC code templates to generate visitors with
return values. With generics, you can enhance the visitor pattern like this: interface Visitor<T> { T visit(A a); T visit(B b); ... } interface Foo { <T> T accept(Visitor<T> visitor); } class A implements Foo { public <T> T accept(Visitor<T> visitor) { return visitor.visit(this); } } class MyConcreteVisitor implements Visitor<Integer> { Integer visit(A a) { return 0; } ... } etc. Foo foo = ...; MyConcreteVisitor evaluation = ...; int result = foo.accept(evaluation); This way you can use visitors as functions without having to do brittle state handling. The above Visitor is really nothing but a function from Foo to T. (And if no return type is needed, the convention is to use Visitor<Void>). It would be nice if SableCC 4.0 would do something like this. -- Niklas Matthies On Tue 2009-03-24 at 13:36h, Javier Abdul Cordoba Gandara wrote on sablecc-discussion: > > That part is not only SableCC crazy implementation. Find some resource you understand > about the VISITOR design pattern, understand 'apply' as the 'accept' method and suddenly all > makes sense. I see the inXXX, caseXXX and outXXX as an extension to the > basic 'visit' method. Navigating a syntax tree is an instance of the general > problem of mapping methods (interpretation) to an arbitrary set of objects > (in this case a tree). The return value of the 'visit' method in the classic pattern > is void (side effects needed). If you need to produce a value you could declare > the 'visit' method as returning something (expressions have values), SableCC's 'apply' > value is void, live with it. > > Please correct me if I am wrong. > > > Javier Abdul Córdoba Gándara > Buró de Crédito > Sistemas - Desarrollo > Tel. 54494900 Ext. 5935 > > El presente mensaje es confidencial, dirigido únicamente para el destinatario. > Si usted no es el destinatario, no deberá copiarlo, revelarlo o distribuirlo. > Cualquier acción realizada en este sentido, será ilegal. Si por error recibe el > presente mensaje, por favor notifique al remitente. > > This communication is confidential and intended only for the addressee. If you > are not the intended recipient, you may not copy, disclose, or distribute this > message to anyone else; any such actions may be unlawful. If you have received > this communication in error, please contact the sender of the message to inform > him or her of the error. > > -----Mensaje original----- > De: sablecc-discussion-bounces+cordobaj=burodecredito.com.mx@... [mailto:sablecc-discussion-bounces+cordobaj=burodecredito.com.mx@...] En nombre de Henrique Rocha > Enviado el: Martes, 24 de Marzo de 2009 10:36 a.m. > Para: sablecc-discussion@... > Asunto: Evaluating expressions > > > Hi, > > I'm having a really hard time using SableCC because the documentation is really bad in my opinion. I've read the paper and some chapters of the full thesis and I don't know how to evaluate for example an expression like 1 + 1. > > In the paper there is an interpreter for a BASIC like language. The method caseADivExpression is defined like this: > > public void caseADivExpression(ADivExpression node) { > try { > node.getLeft().apply(this); > node.getRight().apply(this); > setIntValue(node, getIntValue(node.getLeft()) / getIntValue(node.getRight())); > } catch (....) {} > } > > The setIntValue and getIntValue are not listed in the paper. > > In my code I have: > > @Override > public void caseAPlusExp(APlusExp node) { > node.getLeft().apply(this); > node.getRight().apply(this); > // i need more code here > } > > How can I get the values of both the left and right side and how can I set the value of the plus expression as the sum of the evaluated expressions? I suppose this is really easy to do but I couldn't find any docs on how to do this. :( > > Thanks. > > -- > Henrique Rocha > infossuga.blogspot.com > ExpertRating Certified Windows XP Professional > ExpertRating Certified Unix Shell Script Professional ExpertRating Certified Unix Professional ExpertRating Certified Object-Oriented Concepts Professional ExpertRating Certified Professional Computer Technician Skills ExpertRating Certified HTML 4 Professional Follow me on Twitter: twitter.com/HenriqueRocha > > _______________________________________________ > SableCC-Discussion mailing list SableCC-Discussion@... > http://lists.sablecc.org/listinfo/sablecc-discussion > > _______________________________________________ > SableCC-Discussion mailing list > SableCC-Discussion@... > http://lists.sablecc.org/listinfo/sablecc-discussion _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: Evaluating expressions
by Rowan Worth
::
Rate this Message:
On Wed, Mar 25, 2009 at 06:38:53AM +0900, Niklas Matthies wrote:
> I actually hacked the SableCC code templates to generate visitors with > return values. Nice one! I've been using a stack to keep track of evaluation results, and after typing: foo.apply(this); Reference result = stack.pop(); so many times, it dawned on me that an apply() which took advantage of the existing call stack by returning a Reference would be delightful. > On Tue 2009-03-24 at 13:36h, Javier Abdul Cordoba Gandara wrote on sablecc-discussion: > > > > That part is not only SableCC crazy implementation. Find some resource you understand > > about the VISITOR design pattern, understand 'apply' as the 'accept' method and suddenly all > > makes sense. This is probably the wrong topic to bring up here, but how does everyone feel about the visitor pattern as used to implement switches? Personally it feels somewhat complex and awkward to me... Say I have this grammar excerpt: Tokens lpar = '('; rpar = ')'; curly = '{'; brace = '}'; pipe = '|'; id = (['a'..'z'] | ['A'..'Z'] | '_')*; ... Productions funcall = func lpar expr_list? rpar; func = {named} id | {anon} curly pipe id_list pipe expr brace; That is, some ruby-like lambda syntax, where I can define an anonymous function like {|x,y| x+y}. Now, say I'm dealing with the part of the evaluator that actually does a function call. If there's some runtime error, I want to generate an error message that includes either the function name or "<anonymous>". Using visitor we have something like: public caseAFuncall(AFuncall node) { try { ... /* do function call */ } catch(Exception e) { String funcname; node.getFunc().apply( new AnalysisAdapter() { public void caseANamedFunc(ANamedFunc node) { funcname = node.getId().getText(); } public void caseAAnonFunc(AAnonFunc node) { funcname = "<anonymous>"; } } ) throw new Exception("in function "+funcname, e); } } Of course, that won't compile - I can't access non-final variables like funcname within anonymous classes. I tried a couple of other methods but it seems to be very difficult to extract any state from an anonymous class, unless the heirachy has been designed to allow it (eg a function like "public Object result()"). Eventually what I did was to move the throw into the anonymous class, which works for my case but doesn't seem very general. Compare to the "less civilised" approach of: String funcname; if(node.getFunc() instanceof ANamedFunc) { funcname = node.getId().getText(); } else if(node.getFunc() instanceof AAnonFunc) { funcname = "<anonymous>"; } throw new Exception("in function "+funcname, e); How simple is that? No fancy constructs, no extra object instantiation, no extra stack frames... if you had an enum of alternatives you could even get away without the consecutive comparisons: String funcname; switch(node.getFunc().getType()) { case A.NamedFunc: funcname = node.getId().getText(); break; case A.AnonFunc: funcname = "<anonymous>"; break; } throw new Exception("in function "+funcname, e); Credit where credit is due, I've never used any grammar generator aside from Sable and it has been a pretty agreeable experience, it just feels to me like things could be a bit simpler. -Rowan _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
|
|
|
Re: Evaluating expressions
by Rowan Worth
::
Rate this Message:
On Wed, Mar 25, 2009 at 06:11:26PM +0900, Christopher Van Kirk wrote:
> > From: Rowan Worth <rowanw@...> > > Subject: Re: Evaluating expressions > > Why would this approach > > > node.getFunc().apply( > > new AnalysisAdapter() { > > public void caseANamedFunc(ANamedFunc node) { > > funcname = node.getId().getText(); > > } > > be more 'civilized' than this one: > > > if(node.getFunc() instanceof ANamedFunc) { > > funcname = node.getId().getText(); > > } <snip> Maybe it's just the people I've worked with... I never really embraced java culture myself, but I get the impression that instanceof is considered somewhat dirty. Also, considering the first approach is SableCC's approach, I figured it would be status quo around here. > It seems to me that the latter is doable in SableCC 3x and makes for much easier to understand code. I'm not going to disagree with either of those assertions :) > It should perform better too. As I recall, one of the arguments in Etienne's paper was that function dispatch is O(1) compared to an O(N) chain of instanceof comparisons. Of course, when N=2 I would be very surprised if the overhead of vtable lookups and such is worth it. -Rowan _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
|
|
|
|
signature.asc (265 bytes) 
| Free embeddable forum powered by Nabble | Forum Help |
