Re: Recursive Descent vs. LALR

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

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