[antlr-interest] Help getting familiar with ANTLR

[Nigel Sheridan-Smith]

Hi Oscar, 

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Oscar Simpson
> Sent: Saturday, 18 June 2005 4:41 PM
> To: ANTLRInterest
> Subject: [antlr-interest] Help getting familiar with ANTLR
> 
> 
> 4. In ANTLR is the operator precedence explicit or implied? I noticed that
> the Java 1.3 grammar included the precedence level in the comments but
> there
> didn't appear to an explicit declaration. If they are implicit by the
> order
> of declaration is there a way to explicitly set the precedence?
> 
> ***Note: From what I can tell the operator precedence in the AST is
> implicit
> by order of inclusion - just want to make sure that's the case.
> 

LL(k) works by descending into sub-rules, so generally speaking you do
precedence by which order the rules refer to each other. E.g.

expr: and_expr (OR and_expr)* ;
and_expr: literal (AND literal)* ;
literal: LIT;

...

OR: "|";
AND: "&";
LIT: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9');


Ensures that '&' has higher precedence compared to '|'. This is because the
parser is forced to match any '&' before any '|'. If you put some precedence
operators in the same rule, then they will match together. 

I picture it in my head as if I am traversing through the branches of a
tree. "expr" must match non-terminal "and_expr" first, and thus, it attempts
to match non-terminal "literal" (and consequently, terminal "LIT"), and then
optionally terminal "AND" (followed by another literal, followed by "AND",
etc) before returning to the "expr" rule and matching terminal "OR". 

As for left-to-right and right-to-left associativeness, have a look thru the
list archive (2-3 months ago?) to see how people have handled that with tree
parsers and normal parsers (with automatic AST construction). The way you
structure your rules (with ^ markers in normal parser) alters the way the
tree is constructed.

expr: and_expr (^OR and_expr)* ;
and_expr: literal (^AND literal)* ;
literal: LIT;


... will construct (I think?) :


a&b&c|d&e&f|g&h  

              |
            /   \
          /       \
        /           \
       |             & 
     /   \          / \
   /       \        g h
   &        & 
 /   \     ...
 &    c 
/ \
a b


Because the root keeps on getting promoted each time the optional part
matches... 

Nigel

--
Nigel Sheridan-Smith
PhD research student

Faculty of Engineering
University of Technology, Sydney
Phone: 02 9514 7946
Fax: 02 9514 2435