Re: Advice for recursive descent parser

Chris F Clark <>
Wed, 01 Apr 2009 18:49:01 -0400

          From comp.compilers

Related articles
Advice for recursive descent parser pk@pk.invalid (pk) (2009-03-31)
Re: Advice for recursive descent parser (2009-04-01)
Re: Advice for recursive descent parser (Chris F Clark) (2009-04-01)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Wed, 01 Apr 2009 18:49:01 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 09-03-126
Keywords: parse, LL(1)
Posted-Date: 04 Apr 2009 09:46:17 EDT

pk <pk@pk.invalid> writes:

> I'm trying to write a recursive descent parser for this grammar (simplified
> regexes - sorry for the non formal grammar):
> RE -> BR ('|' BR)* # alternation
> BR -> EX (EX)* # concatenation
> BR() {
> if !EX() error()
> while cursym()!="|" && !cursym()!=")" && !end_of_RE {
> if !EX() error()
> }
> return 1
> }
> But it looks kind of hackish, and I'm not really sure that is the way to go.
> I could change the grammar and introduce an explicit concatenation operator
> for EXs (which I don't really like too much), but before doing that, can
> anybody please advise?

What you have done is exactly why I get so upset at people
hand-writing recursive descent parsers. Your body of code does not
correspond to the grammar you wrote.

You have the error detection in the wrong place. Your non-terminal BR
has no reference to |, ), or end and your thus implementation
shouldn't either. This either means your grammar is wrong or your
implekmentation is wrong. A more correct translation of your grammar
would be:

> BR() {
> if !EX() error();
> while EX() { /* do nothing */ }
> return 1
> }

Using this version will clear up some (perhaps all) of your problems.
I didn't look enough at the other code to see if you made other

Although the translation of a (well-formed LL) grammar to a recursive
parser is a simple mechanical task, it is one that humans tend to
short-cut or modify and get wrong. Therefore, if you want to do
recursive descent, get yourself a copy of PCCTS/ANTLR or JavaCC or
Coco/R or any of the other fine recursive descent parser generators
and get a correct mapping of your grammar to code.

Hope this helps,

Chris Clark Internet:
Compiler Resources, Inc. or:
23 Bailey Rd Web Site:
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

Post a followup to this message

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