From: MikkelFJ Date: 2002-09-28T08:26:15+09:00 Subject: Re: Is Ruby's grammar LL(k)? "Mauricio Fern�ndez" 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