25 Jun 2003 01:21:56 -0400

Related articles |
---|

Recursive Descent vs. LALR JohnMResler@netscape.net (John Resler) (2003-06-20) |

Re: Recursive Descent vs. LALR bear@sonic.net (2003-06-25) |

Re: Recursive Descent vs. LALR cfc@shell01.TheWorld.com (Chris F Clark) (2003-07-02) |

Re: Recursive Descent vs. LALR kamalpr@yahoo.com (2003-07-03) |

Re: Recursive Descent vs. LALR John.M.Resler@Boeing.com (Boeing) (2003-07-04) |

Re: Recursive Descent vs. LALR bear@sonic.net (2003-07-04) |

From: | bear@sonic.net |

Newsgroups: | comp.compilers |

Date: | 25 Jun 2003 01:21:56 -0400 |

Organization: | ...disorganized... |

References: | 03-06-093 |

Keywords: | parse |

Posted-Date: | 25 Jun 2003 01:21:56 EDT |

John Resler wrote:

*>*

*> I got halfway through a compiler theory course a few years back and*

*> finances required dropping out of school. Since then I've been messing*

*> around with Parsing tools and the like and have been using JavaCC. It is*

*> a recursive descent parser and I understand a bit of the way a Recursive*

*> Descent Parser works versus bottom up parsing. I seem to recall a*

*> theorem that said any LALR(K) grammar could be rewritten to an LALR(1)*

*> grammar and another theorem that said Recursive Descent versus LALR(1)*

*> were equally capable. Can anyone shed some light on this? I am also*

*> curious if anyone knows anything about the JJTree tool? I subscribe to*

*> the JavaCC mailing list but even there, few individuals are aware of*

*> JJTree's capabilities and thus its uses. I'd appreciate any information*

*> anybody could give me. Thanks in advance.*

Any LALR(K) grammar can be rewritten as an LALR(1) grammar. The

number of nonterminals in the new grammar will be up to K! times the

number of nonterminals in the old grammar or less (usally considerably

less). Therefore, all of these languages are considered to be "level

3" languages (linear languages) in the Chomsky hierarchy. The process

of transforming an LALR(K) grammar into an LALR(1) grammar is called

"factoring". If you own the Dragon Book, it will show you several

examples of factoring.

Recursive descent to read a level 3 language can be implemented

without backtracking. However, there's a special case somewhere

between Chomsky's level 2 and level 3 (well, actually I guess it's a

special class of level 2 languages) that recursive descent without

backtracking can read, but which cannot be expressed as an LALR(K)

language for any constant K.

If you want to read level 2 languages (context-free languages)

generally, you will need to go a formalism that has at least the power

of recursive descent with backtracking. Note that you can write a

recursive descent parser with backtracking for level 3 languages, and

it's easier to write than a "good" recursive-descent parser; but in

efficiency terms, that's always a mistake. People do it because they

don't want to bother calculating the "first" and "follow" sets from

their grammar, or don't know how. You don't actually *need*

backtracking unless you're reading a language for which first and

follow sets aren't defined. And that would be a level 2 language.

First and follow sets aren't defined for level 1 or level 0 either,

but recursive descent won't parse those anyway regardless of

backtracking, so recursive descent with backtracking is really only

warranted for level-2 languages.

Level-1 languages are context-sensitive; level-1 parsers are generally

considered to be beyond the scope of compiler construction, but have

been implemented for natural-language efforts. The usual formalism is

a "Recursive Transition Network" (Google is your friend).

There are also level-0 languages, but there aren't really any specific

rules about what kind of parser is needed for them other than that it

can be implemented as a Turing machine. Which isn't saying much. A

broad class of level-0 languages (again sometimes used by us

Natural-Language geeks) can be parsed by an "Augmented Transition

Network" parser. (Google is your friend again if you're interested.)

HTH,

Bear

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.