From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2002-10-01T02:37:21+09:00
Subject: Re: Is Ruby's grammar LL(k)?


"Mark Probert" <probertm@nortelnetworks.com> wrote in message
news:5.1.0.14.2.20020930095528.00b0ffc8@zcard04k.ca.nortel.com...
> At 06:29 AM 9/29/2002 +0900, MikkelFJ wrote:

> It is true that Ruby parsers exist, the question was more related to LL(1)
> parsers for Ruby.  In this case, the challenge isn't the linebreak (I just
> yanked that code from the Pickaxe book), rather it is the if and unless
> conditions.

It has very much to do with linebreaks:

>      if <cond> then
>          <statements>
>      end
>
>      if <cond>
>          <statements>
>      end

The above are the same form - you can have the rule
<then> ::= (then [linebreak] | linebreak)
<if> ::= if <cond> <then> <statement-list> end

>
>      <statement> if <cond>

This variant of "if" can only happen after an unterminated statement. So
therefore we define two statement types: terminated and unterminated
statements.

<terminated-statement> ::= <unterminated-statement> (linebreak |  semicolon
| EOF)
<trailing-if> ::= <unterminated-statement> if <cond>

The above isn't exact becuase you also need to include statements terminated
by end in <terminated-statement>.

So by having linebreak as a token, it should be possible to deal with.
The problem is that when you have the linebreak, it becomes annoying in many
places such as

<add-expr> ::= <value> plus [linebreak] <value>

But then I guess linebreak is so important in Ruby, that you generally need
to be aware of it. You can't just ignore it becuase:

<bad-add-expr> ::= <value> [linebreak] plus [linebreak] <value>

is not possible.

....
> It is going to be fun to try, though ;-)

So altogether it should be possible - but perhaps the above is what you
meant by fun :-)
Of course I haven't covered everything, and I don't know the Ruby syntax
well enough. But I don't see the examples as being particularly impossible
to parse in LL(1).

Mikkel