"Mauricio Fern?ndez" <batsman.geo / yahoo.com> wrote in message
news:20020927180455.GB535 / kodos...

> But right now Ruby's main implementation uses bison, ie LALR(1). I'm not
> sure if you can actually parse things outside LALR(1) (w/ dirty hacks I
> suppose) while staying with yacc, but Ruby cannot indeed be too far from
> LALR(1). But I do have my doubts about LL(k)...

There is a difference between grammar and language.

The same language can be defined by multiple grammars and many LALR(1)
grammars can be rewritten into LL(1) grammars. Most importantly recursion
must change from right to left and common prefixes must be collected into a
common rule. Likewise, many LL(k) grammars can be rewritten to LL(1) by
adding more rules.
LL grammars can be easier to hack with various conditions that must be true
to make a match. So in praxis this shouldn't be a major worry unless you
have a LL(1) tool that doesn't provide the option for tweaking. (ANTLR has
plenty of possibilities to add conditions and is LL(something)).

Most languages need some sort of tweaking in any case - the dangling else is
a popular example.

Since it is tedious to rewrite grammars to conform to dumb tools, we prefer
stronger tools. RockIt has, AFAIK a fairly strong parallel parsing algorithm
that make it possible to handle many conflicts that LALR(1) wouldn't -
useful for natural language parsing. Such powerful parsing features may come
at a time and space performance cost and it does pay off to make the grammar
parser friendly.

Mikkel