[antlr-interest] Resolving a First/Follow Conflict in Logo.

Michael Matera mike.matera at xilinx.com
Mon Nov 1 11:18:29 PDT 2010


Hi Again,

I think I may have resolved my own issue.  Looking at the code for my 
second solution I saw that I may have put my semantic predicate in the 
wrong place.  This rewrite compiles without a warning:

statement
   : 'fd' statement
   | 'bk' statement
   | IDENTIFIER {need=lookup();} ({count<need}? statement {count++;})*
   ;

It seems that putting the predicate BEFORE the token that causes the 
First/Follow conflict resolves the conflict.  Is this true?  In other 
words if (need<count) then I can always expect a follow?

Cheers
./m


Michael Matera wrote:
> Hi Everyone,
> 
> For kicks I'm writing a parser for the Logo programming language.  Logo 
> has an ambiguity in its syntax in that:
> 
>   1. Statements are values (Like in C)
>   2. Subroutine's arguments are not marked with delimiters
> 
> Here's a simplified example of a parser rule for Logo:
> 
> statement
>    : 'fd' statement
>    | 'bk' statement
>    | IDENTIFIER statement*
>    ;
> 
> As you can see, this rule is ambiguous.  Logo parsers must determine how 
> many arguments are taken by 'IDENTIFIER' and use that to resolve the 
> conflict.  I've brainstormed a couple of solutions for this problem but 
> I need help with things that I was unable to figure out.
> 
> Here's my first solution:
> 
> In the scanner, lookup 'IDENTIFIER' in a table to determine the number 
> of arguments it requires, then create a fake token to inform the parser. 
>   The rules would look something like this:
> 
> statement
>    : 'fd' statement
>    | 'bk' statement
>    | ZERO_ARG IDENTIFIER
>    | ONE_ARG IDENTIFIER statement
>    | TWO_ARG IDENTIFIER statement statement
>    | THREE_ARG IDENTIFIER statement statement statement
>    ;
> 
> IDENTIFIER
>    : ('a' .. 'z')+
>    {
>       lookup(getText());
>       <<INSERT_FAKE_TOKEN>>
>    }
>    ;
> 
> Question: How do I create and insert a fake token in the scanner?
> 
> Here's my second solution:
> 
> Use a predicate to inform the First/Follow conflict.  I've tried to use 
> a semantic predicate to control the match without success.  The 
> following is a non-working attempt to show what I mean:
> 
> statement
>    : 'fd' statement
>    | 'bk' statement
>    | IDENTIFIER {args=lookup()} (statement {count<args}? {count++})*
>    ;
> 
> Question: Is it possible to resolve a First/Follow conflict this way in 
> ANTLR?  If so, how do I do it?
> 
> ~~~~
> 
> If there's a solution I've missed please let me know, and thanks for 
> your time and consideration.
> 
> Cheers
> ./m
> 
> This email and any attachments are intended for the sole use of the named recipient(s) and contain(s) confidential information that may be proprietary, privileged or copyrighted under applicable law. If you are not the intended recipient, do not read, copy, or forward this email message or any attachments. Delete this email message and any attachments immediately.
> 
> 
> 
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
> 

This email and any attachments are intended for the sole use of the named recipient(s) and contain(s) confidential information that may be proprietary, privileged or copyrighted under applicable law. If you are not the intended recipient, do not read, copy, or forward this email message or any attachments. Delete this email message and any attachments immediately.




More information about the antlr-interest mailing list