|Recursive decent parsing - problem with two particular productions. firstname.lastname@example.org (Intercodes) (2006-02-24)|
|Re: Recursive decent parsing - problem with two particular productions email@example.com (Pascal Bourguignon) (2006-02-24)|
|From:||Pascal Bourguignon <firstname.lastname@example.org>|
|Date:||24 Feb 2006 13:17:00 -0500|
"Intercodes" <email@example.com> writes:
> I have these two troublesome production that if completed will finish
> my parsing module. But I have no idea how to proceed with these two
> particular productions. I am parsing the scheme grammar(R5RS) using a
> simple recursive decent technique. Here are the productions. (from
> <command or definition> -> <definition> | (begin <command or
> definition>+) | (more items....)
> <definition> -> (begin <definition>*) | (more items...)
> Now, when I write a function for the non-terminal '<command or
> definition>' I run into deep trouble. You can notice from the <command
> or definition> production that ,after I match 'begin' token I have
> ambiguity over selecting the next non-terminal (as both <command or
> definition> and <definition> have 'begin' followed by their own
> functions). I also guess the K in LL(k) doesn't matter here.
> I can't frame the question more clearly but if someone could understand
> my problem and suggest some cheap tricks to overcome this (like adding
> extra non-terminals or a simple pseudo-code to overcome this
> ambiguity), I would be very helpful.
> And if it matters, so far in coding the parser for this grammar (almost
> 95 % grammar complete) I did not encounter such a problem with any
Assuming the (more items...) are different in the two productions, you
can merely factorize out the (begin:
command-or-definition -> definition-items | command-items | begin-block
definition-items -> (more-definitions items ...)
command-items -> (more-commands items ...)
begin-block -> (begin definitions|commands)
definition-begin-block -> (begin commands)
command-begin-block -> (begin commands)
definitions -> definition...
definition -> definition-items | definition-begin-block
commands -> command...
command -> command-items | command-begin-block
__Pascal Bourguignon__ http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.
Return to the
Search the comp.compilers archives again.