Recursive decent parsing - problem with two particular productions.

"Intercodes" <>
24 Feb 2006 09:43:31 -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: "Intercodes" <>
Newsgroups: comp.compilers
Date: 24 Feb 2006 09:43:31 -0500
Keywords: parse, question, Scheme
Posted-Date: 24 Feb 2006 09:43:31 EST

Hello everyone,

  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

Thank you.

Post a followup to this message

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