[antlr-interest] Lexer/Parser Design Issues

Jason jasonriz at yahoo.com
Sun Jul 25 19:31:20 PDT 2004


Hello,

I'm trying to write a parser for MDX a query language
which looks remotely similar to SQL.  The BNF has
these two characteristics:

1) There are three or four rules which have several
indirect recursions between them.

2) The language contains several (~40) predefined
functions which occur on the right hand side of the
recursive rules.  I'm treating each separate function
name as it's own token.

I've carefully factored out all of the indirect left
recursions and built my parser.  Unfortunately, it
seems that as a result of the combination of (1) and
(2) above along with ANTLRs approximate lookahead, I
end up with almost each token type in each rule! 
Nothing is parsing correctly!  The first alternative
is matched pretty much each time.  I started just
sprinking syntactic predicates at every turn but it
seems that I'm going to need so many of them that once
I get this thing working it will be impractically
slow.

A couple of questions:

1) Given these two alternatives for example:

set: Children '(' item ')'
      |
     Descendents '(' item ')'

would most ANTLR users define 'children' and
'descendents' as separate tokens and recognize them in
the lexer or just write a rule something like:

set: Identifier '(' item ')' ?

2) One down side to having to factor out all of the
indirect left recursions is that what I'm left with
once I'm done is for certain rules less than intuitive
:)  Is it possible that all of the recursions just
make my language a bad candidate for an LL parser?  

Thanks in advance for any thoughts anyone might have
on these general questions.

-jason


	
		
__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - 100MB free storage!
http://promotions.yahoo.com/new_mail 


 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
    antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 



More information about the antlr-interest mailing list