Re: Recursive decent parsing - problem with two particular productions.

"Intercodes" <intercodes@gmail.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
> R5RS)
>
> <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
> production.


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 comp.compilers page.
Search the comp.compilers archives again.