Re: Advice for recursive descent parser

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
errors.


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


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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