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

Pascal Bourguignon <>
24 Feb 2006 13:17:00 -0500

          From comp.compilers

Related articles
Recursive decent parsing - problem with two particular productions. (Intercodes) (2006-02-24)
Re: Recursive decent parsing - problem with two particular productions (Pascal Bourguignon) (2006-02-24)
| List of all articles for this month |

From: Pascal Bourguignon <>
Newsgroups: comp.compilers
Date: 24 Feb 2006 13:17:00 -0500
Organization: Informatimago
References: 06-02-164
Keywords: parse
Posted-Date: 24 Feb 2006 13:17:00 EST

"Intercodes" <> 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__
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.