[antlr-interest] Creating a simple expression language

James Abley james.abley at gmail.com
Tue Nov 25 14:13:21 PST 2008


2008/11/23 Ivar Refsdal <refsdal.ivar at gmail.com>:
> Hi,
>
> I'm also a newbie (thus everything could be wrong) so I can't help that
> much... But anyway:
> Here is a edited Expr grammar:
>
> grammar Expr;
>
> options {
>    output=AST;
>    ASTLabelType=CommonTree;
>    k = 1;
> }
>
> prog    :    (stat {System.out.println($stat.tree.toStringTree());} )+ ;
>
> stat    :    expr    -> expr;
>
> expr    :    multExpr (('+' ^  | '-'^) multExpr)*
>    ;
>
> multExpr    :    atom ('*'^ atom)*
>    ;
>
> atom    :    INT
>    |    function
>    /* We don't want nodes for the parentheses */
>    |    '('! expr ')'!
>    ;
>
> /* We don't want nodes for the paretheses or commas. */
> function    :    fname^ '('! variable_list? ')'! ;
>
> variable_list
>    :    (variable ( ','! variable )* )
>    ;
>
> variable    :    FUNCNAME;
>
> fname    :    FUNCNAME;
>
> FUNCNAME    :    ( 'a' .. 'z' | 'A' .. 'Z')+  ;
> INT    :    '0' .. '9'+ ;
> WS    :    ( ' ' | '\t' | '\n' | '\r' ) + {skip(); };
>
>
> It makes it a little bit easier to debug..
> Lexer rules (upper case) will not be included/"named" in the parse tree,
> but parser rules  (lower case) will, so it's easier to have an overview
> like this.
>
> Note also: You don't need to bother with using WS i parser rules as they
> will already have
> been skipped on the lexer level.
>
> Here is a screenshot of debugging the input with (almost) the orginal
> grammar,
> showing the parse tree:
> http://ivarref.at.ifi.uio.no/antlr_screen.png
>
> The input was:
> "somefn(arga,argb,argc)"
>
> So as you can see it's not quite generating what you're expecting.
> The same holds for using the interactive interpreter, but I prefer the
> debugger at the moment.
>
> It works more or less like expected with the revised grammar..
>
> Also, are you sure you want k=1? Check out the backtrack=true option
> also, that helped me
> for grammars that wasn't easily determined (multiple alternatives). If
> you ever run into that.
>
> I've read just a little bit of the Dragon book (new edition), that
> helped me a little bit..
>
> Well, good luck,
> Ivar
>
> (first post, hope this works.)
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>

Hi Ivar,

Thanks for the response. The Dragon book is good, isn't it? I skimmed
it last year, but probably need to go through it again and do more of
the exercises this time. Ditto Programming Language Pragmatics by
Michael Scott and Essentials of Programming Languages. I am doing the
latter at the moment, exercises and all, but it's Scheme, so it's
great, but not immediately applicable to using ANTLR.

I think I'm fairly happy with the grammar in terms of it parsing my
expected input. Doubtless I will refine it as my understanding grows.
Where I'm stuck is how to evaluate my AST; i.e. Eval.g is where I'm
not sure how to procee, rather than Expr.g.

I think k=1 is the right choice. My understanding is that you want the
smallest possible value of k for performance reasons. You can use a
higher value (ideally scoped by production) to resolve ambiguities,
etc; but you should always strive to resolve that by using
left-factoring, semantic or syntactic predicate. Similarly for
backtracking; it's powerful and useful, but there are other options.

So in summary, I'm still stuck and looking for an example of how to
register and execute my functions. I intuitively feel that my
tree-walking approach is wrong, but I'm not sure what the idiomatic,
best-practice for ANTLR would be.

Cheers,

James


More information about the antlr-interest mailing list