From: "Mauricio Fernández" <batsman.geo@...>
Date: 2002-09-29T04:37:33+09:00
Subject: Re: Is Ruby's grammar LL(k)?

On Sat, Sep 28, 2002 at 08:26:15AM +0900, MikkelFJ wrote:
> 
> "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.

So I understand we can possibly create a LL(2) [according to matz]
grammar to parse the Ruby language (considered as the set of all the
possible valid program source codes), but the semantics of the direct
interpretation of the resulting parse-tree wouldn't match the "real" ones.

I do however have some suspicions about statement modifiers (if,
unless...) rendering Ruby unparseable w/ LL(k). I feel the corresponding
productions cannot be left-factored.

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

Thanks for the explanation. I was curious about Parrot's languages/ruby
recursive descent parser; now I can see what's going on.

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com
  
Not only Guinness - Linux is good for you, too.
	-- Banzai on IRC