Re: BNF-like grammar specified DIRECTLY in Ruby

I noticed that yahoo base64 encoded my attachments in my
original message.  Under linux you can pipe it through mmdecode
-u to get the source.  Does anybody want me to repost?

Other comments below...

--- Florian Gro<[e-mail]> wrote:

> Eric Mahurin wrote:
> 
> > Hello everybody,
> > 
> > I hope I'm not intruding, but I think I found
> > something you'll like.  I think I finally found the
> > holy grail I was looking for in a language - the
> > ability to easily write a readable grammar (BNF-like)
> > directly in the target langauge.  I attached a
> > syntax.rb that defines all the classes needed and
> > generic expression evaluator example.
> 
> This is good stuff and I will have a deeper look at it soon
> as I still 
> need a good parsing foundation for that Joy implementation I
> want to do 
> in Ruby.
> 
> I have done something more or less similar as well in the
> past: I did an 
> OOP API for regular expressions which looks like this:
> 
> > irc_re = Regexp::English.new do
> >   crlf = literal("\r\n")
> >   space = literal(" ")
> > 
> >   nospecial = outside("\x00", "\r", "\n", " ", ":")
> >   middle = nospecial + (literal(":") |
> nospecial).zero_or_more
> >   trailing = (inside(":", " ") | nospecial).zero_or_more
> > 
> >   shortname = (letter | digit) +
> >               inside(letter, digit, "-").zero_or_more +
> >               (letter | digit).zero_or_more
> >   hostname = shortname + (literal(".") +
> shortname).zero_or_more
> >   user = outside("\x00", "\r", "\n", " ", "@").multiple
> >   special = inside("[]\\`_^{|}")
> >   # The spec limits nick names to 9 characters. We don't.
> >   nickname = (letter | special) +
> >              inside(letter, digit, special,
> "-").zero_or_more
> > 
> >   prefix = hostname | (nickname +
> >              ((literal("!") + user).optional +
> >               literal("@") + hostname).optional)
> >   command = letter.multiple | digit * 3
> >   # This isn't what the spec does. It seems to enforce a
> maximum of 14 params.
> >   trailing_param = literal(":") + trailing
> >   params = trailing_param |
> >            (middle + (space + middle).zero_or_more.minimal
> +
> >             (space + trailing_param).optional)
> >            
> >   message = (literal(":") + prefix.capture(:prefix) +
> space).optional +
> >             command.capture(:command) +
> >             (space + params.capture(:params)).optional +
> >             crlf
> >   whole_string(message)
> > end

My stuff looks similar, but I think more readable and
definitely more powerful.

> It does not really solve the problems of using regular
> expressions as 
> parsers however.

It matches to a general "stream" which could come from a
string, IO, or just about any sequential structure.  A "stream"
in this context is like a C++/Java iterator - we need that
concept in Ruby.  The additional feature I added to the stream
is the "buffer" method that allows the iterator to jump back to
a certain point.  You could think of the buffer method creating
a new stream to iterate on and the associated code using that
instead.

> What I wonder about is how you solved the problem of
> recursive rules and 
> ones that refer to each other. Is this possible?

Excellent question!!  I wrestled with this a bit.  The cleanest
solution I came up was to break the loop by using an additional
syntax object.  You create an empty syntax object, use it, and
then insert its contents later.  This is demonstrated in my
example expression evaluator:

expr = Syntax::Pass.new # need to predefine object for
recursion

atom =
    (number+ws).qualify{|m|m[0]} |
    ("(" + expr + ")" + ws).qualify{|m|m[1]}

...

expr << ( # << inserts/appends a syntax into another syntax
    ws + term + ( ("+"|"-") + ws + term )*(0..INF)
).qualify { |m|
    sum = m[0]
    m[1].each { |m|
        case m[0]
            when "+" then sum += m[1]
            when "-" then sum -= m[1]
        end
    }
    sum
}

> > Here would be a few more niceties for this syntax
> > stuff if Ruby had these:
> > 
> > - Ranges without a end (and/or begin?).  If
> > syntactically this is a problem, nil could be used
> > instead.  Of course you'd need to raise an exception
> > when you did a bad thing with them (i.e. to_a).  For
> > example:
> >     (b..)===x  ->  x>=b
> >     (b..).each {}  -> infinite loop starting with b
> >     (..e)===x  ->  x<=e
> >     (..) ===x  ->  true
> 
> While this is no official solution it still works (but see
> note):
> 
> Math::Infinity = Math::PosInfinity = (1.0 / 0.0)
> Math::NegInfinity = -Math::PosInfinity
> 
> And it might be nice to add a bit of syntax sugar as well:
> 
> def Range.from(range_start)
>    range_start .. Math::Infinity
> end
> 
> def Range.to(range_end)
>    Math::NegInfinity .. range_end
> end
> 
> def Range.full() Range.from(Math::NegInfinity) end
> 
> Range.from(b) === x   # x >= b
> Range.from(b).each {} # infinite loop, be careful with .to_a
> and so on
> Range.to(e)   === x   # x <= e, can not iterate
> Range.full    === x   # always true, can not iterate
> 
> Note: This is not guaranteed to work portably as there might
> be machines 
> which don't have infinity float values or which don't yield
> them when 
> dividing by zero. One way around this is to create custom
> objects which 
> define <=> and (optionally) the mathematical operators
> correctly.

That's what I'm doing now, but not using the "sugar" because it
is more verbose (look above at (0..INF) - a zero or more loop).
 Another problem with this solution is that doesn't work with
non-numeric ranges.  I think using nil as the begin or end
would be better, but I couldn't figure out how to override
Range to allow it.

> > - Allow an object to be used like a method.  This
> > would require a new operator - I'll call it: ().  An
> > object followed by {} or do/end would also be treated
> > the same (that's the part I really want).  With this,
> > I could replace the "qualify" method with this thing. 
> > Here is an example:
> >     class Test;
> >       def ()(*args,&code); ... end
> >     end
> >     a = Test.new
> >     a { ... }
> 
> Something like this is experimentally being introduced in the
> CVS builds 
> of Ruby 1.9. I'm not sure if it is general enough to make
> your example 
> work, though.

Cool.  I guess I need to try it.

Is it possible to override the whitespace operator?  i.e. this
works:

p("Hello " "world!")

gives:

"Hello world!"

I would much rather use whitespace rather than "+" just like
BNF.

> > p.s. I just learned Ruby last week!  I really love
> > this language!  It's got the best of Perl, C++, and
> > Java.  My main complaint is a syntactic one - the use
> > of "end" instead of {}.  That's probably the influence
> > of Python.
> 
> Welcome and thanks for sharing and producing Good Stuff.

Thank you!  Progamming in Ruby has been a joy.



		
__________________________________ 
Do you Yahoo!? 
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/