Asp Forum - Ruby Parser Combinator

Scott Weeks

1/20/2006 8:00:00 AM

Hello all,

this is my first post on the ruby-talk list. I've been using ruby for a
while though :-)

Anyway, just horsing around I tried my hand at writing a ruby parser
combinator. It (along with an explanation) is at

http://twelvestone.com/forum_thread/...

(the explanation and link to the gem and source tar are most of the way
down the page (the post with the catapult in it)).

Anyway I'm still a bit of a noob when it comes to fp and parsing stuffs
so if anyone wants to correct me I'd be grateful for the help :)

Cheers,
Scott

19 Answers

Christian Neukirchen

1/20/2006 4:01:00 PM

Scott Weeks <weeksie@twelvestone.com> writes:

> Hello all,
>
> this is my first post on the ruby-talk list. I've been using ruby for
> a while though :-)
>
> Anyway, just horsing around I tried my hand at writing a ruby parser
> combinator. It (along with an explanation) is at
>
> http://twelvestone.com/forum_thread/...
>
> (the explanation and link to the gem and source tar are most of the
> way down the page (the post with the catapult in it)).
>
> Anyway I'm still a bit of a noob when it comes to fp and parsing
> stuffs so if anyone wants to correct me I'd be grateful for the help
> :)

You may be interested in
http://chneuk.../blog/archive/2005/10/the-rightyear-parsing-li...

> Cheers,
> Scott
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

ptkwt

1/20/2006 7:23:00 PM

In article <m23bjizy6o.fsf@gmail.com>,
Christian Neukirchen <chneukirchen@gmail.com> wrote:
>Scott Weeks <weeksie@twelvestone.com> writes:
>
>> Hello all,
>>
>> this is my first post on the ruby-talk list. I've been using ruby for
>> a while though :-)
>>
>> Anyway, just horsing around I tried my hand at writing a ruby parser
>> combinator. It (along with an explanation) is at
>>
>> http://twelvestone.com/forum_thread/...
>>
>> (the explanation and link to the gem and source tar are most of the
>> way down the page (the post with the catapult in it)).
>>
>> Anyway I'm still a bit of a noob when it comes to fp and parsing
>> stuffs so if anyone wants to correct me I'd be grateful for the help
>> :)
>
>You may be interested in
>http://chneukirchen.org/blog/archive/2005/10/the-rightyear-parsing-li...
>

I wonder how the speed of these functional parsers compares with the speed of
RACC or even Grammar ( http://rubyforge.org/project... )?

Phil

Scott Weeks

1/20/2006 8:04:00 PM

>
> You may be interested in
> http://chneukirchen.org/blog/archive/2005/10/the-rightyea...
> library.html
>

Cool! That sure is a lot simpler than mine. Thanks for the link :-)

Scott Weeks

1/20/2006 8:10:00 PM

On 21/01/2006, at 6:49 AM, Logan Capaldo wrote:

>
> Minor correction your example calculator has a prefix syntax, not an
> infix syntax. Otherwise I likes dem der combinators. and cor lets you
> do scanner forking, which is always fun. Neat.

ha! thanks for the correction, I have a tendency to do stuff like that.
I'll update the examples/code :-)

Cheers

Eric Mahurin

1/21/2006 8:01:00 AM

On 1/20/06, Scott Weeks <weeksie@twelvestone.com> wrote:
> Hello all,
>
> this is my first post on the ruby-talk list. I've been using ruby for a
> while though :-)
>
> Anyway, just horsing around I tried my hand at writing a ruby parser
> combinator. It (along with an explanation) is at
>
> http://twelvestone.com/forum_thread/...
>
> (the explanation and link to the gem and source tar are most of the way
> down the page (the post with the catapult in it)).
>
> Anyway I'm still a bit of a noob when it comes to fp and parsing stuffs
> so if anyone wants to correct me I'd be grateful for the help :)
>
> Cheers,
> Scott

Take a look here:

http://rubyforge.org/project...

I think this is the same concept that you are talking about. I just
took it to the next level.

Sorry I haven't been working on this for a while. I just haven't had
time with a new job where I'm working too much. I have lots of
updates, but haven't had time to get back to it.

Scott Weeks

1/21/2006 10:33:00 AM

>
> Take a look here:
>
> http://rubyforge.org/project...
>

Nice! It's a bit different since it seems to be a classic style parser
library and not quite in the same vein but still very cool. I
especially like how you overrode | and + to make expressing production
rules more natural

...

Hey Christian, I couldn't find the code for your parser combinator in
that blog entry, could you post a link? I'd love to look at your
implementation because it seems like you've done it in a more elegant
way (at least from the examples you gave).

Cheers,
Scott

On 21/01/2006, at 3:01 AM, Christian Neukirchen wrote:

> Scott Weeks <weeksie@twelvestone.com> writes:
>
>> Hello all,
>>
>> this is my first post on the ruby-talk list. I've been using ruby for
>> a while though :-)
>>
>> Anyway, just horsing around I tried my hand at writing a ruby parser
>> combinator. It (along with an explanation) is at
>>
>> http://twelvestone.com/forum_thread/...
>>
>> (the explanation and link to the gem and source tar are most of the
>> way down the page (the post with the catapult in it)).
>>
>> Anyway I'm still a bit of a noob when it comes to fp and parsing
>> stuffs so if anyone wants to correct me I'd be grateful for the help
>> :)
>
> You may be interested in
> http://chneuk.../blog/archive/2005/10/the-rightyea...
> library.html
>
>> Cheers,
>> Scott
> --
> Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...
>
>
>

Christian Neukirchen

1/21/2006 2:42:00 PM

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Scott Weeks

1/21/2006 9:54:00 PM

Cool! Thanks for that, I love reading other people's code :-)

I'm really more interested in this as an exercise to get a better
understanding of functional programming techniques by seeing how they
could/can be implemented in Ruby. I love this sort of stuff.

On 22/01/2006, at 1:42 AM, Christian Neukirchen wrote:

> Scott Weeks <weeksie@twelvestone.com> writes:
>
>> Hey Christian, I couldn't find the code for your parser combinator in
>> that blog entry, could you post a link? I'd love to look at your
>> implementation because it seems like you've done it in a more elegant
>> way (at least from the examples you gave).
>
> I attached all I have. It's not really practical because flow-control
> with throw/catch isn't as fast as I wished... but it could be
> interesting nevertheless.
>
>> Cheers,
>> Scott
>
> <rightyear.tar.gz>--
> Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Eric Mahurin

1/22/2006 12:51:00 AM

On 1/21/06, Scott Weeks <weeksie@twelvestone.com> wrote:
>
> >
> > Take a look here:
> >
> > http://rubyforge.org/project...
> >
>
> Nice! It's a bit different since it seems to be a classic style parser
> library and not quite in the same vein but still very cool. I
> especially like how you overrode | and + to make expressing production
> rules more natural

I think what I did is closer to what your blog talks about than
classic parsers. Basically, you start with leaf "Grammar" objects and
build complex Grammar productions by combining Grammars.

If want to see the very basics of this technique, here is a stripped
down version of it with a calculator example (self contained and
executable):

class SimpleGrammar
def initialize(grammar)
@grammar = grammar
end
def scan(cursor,buffer)
@grammar.scan(cursor,buffer)
end
def |(other); Code.new { |cursor,buffer|
scan(cursor,buffer) || other.scan(cursor,buffer)
} end
def +(other); Code.new { |cursor,buffer|
scan(cursor,buffer) && other.scan(cursor,buffer)
} end
def filter(buf0,&block); Code.new { |cursor,buffer|
buf = buf0.clone
scan(cursor,buf) && buffer.concat(block[buf])
} end
def discard; Code.new { |cursor,buffer|
scan(cursor,[])
} end
class Code < SimpleGrammar
def initialize(&block)
@block = block
end
def scan(cursor,buffer)
@block[cursor,buffer]
end
end
class Recurse < SimpleGrammar
def initialize(&block)
@grammar = block[self]
end
def scan(cursor,buffer)
@grammar.scan(cursor,buffer)
end
end
class Element < SimpleGrammar
def initialize(pattern)
@pattern = pattern
end
def scan(cursor,buffer)
c = cursor.read1after
if @pattern===c
buffer << c
cursor.skip1next
true
end
end
end
# Make methods for our classes that call new for us
constants.each { |klass|
eval("
def #{klass}(*args,&block)
#{klass}.new(*args,&block)
end
def self.#{klass}(*args,&block)
#{klass}.new(*args,&block)
end
")
}
NULL = Code.new { true }
end

class IO
# implement just the methods we need to look like a cursor
def read1after;c=getc;ungetc(c);c;end
def skip1next;getc&&true;end
end

class Expression < SimpleGrammar::Recurse
def initialize; super() { |expr|
digit = Element(?0..?9)
int = Recurse { |int| digit+(int|NULL) }
number =
(int + (
Element(?.)+int |
NULL
)).filter("") { |n| [n.to_f] }
primary = Recurse { |primary|
number |
Element(?-).discard + primary + Code { |_,b| b[-1]=-b[-1] } |
Element(?().discard + expr + Element(?)).discard
}
product = Recurse { |product|
primary + (
Element(?*).discard + product + Code { |_,b|
b[-2]*=b[-1];b.pop } |
Element(?/).discard + product + Code { |_,b|
b[-2]/=b[-1];b.pop } |
NULL
)
}
sum = Recurse { |sum|
product + (
Element(?+).discard + sum + Code { |_,b| b[-2]+=b[-1];b.pop } |
Element(?-).discard + sum + Code { |_,b| b[-2]-=b[-1];b.pop } |
NULL
)
}
} end
end

Expression.new.scan(STDIN,buf=[]) && p(buf[0])

In the grammar package on rubyforge, the API is very similar to above,
but I added a bunch of stuff to improve performance, usability, and
features. Notice in the above, I'm not really tied to using a
character stream (IO). You could be parsing a token stream or
whatever. You just need to implement a subset of the Cursor (another
package of mine) API. This way you can build lexers, parsers,
preprocessors, etc in the same way.

Less religion, More brains

1/17/2010 8:41:00 PM

Tracey12 wrote:
> The Atheist is a trapped man by his own belief system.
>

The atheist is more free than the theist. A theist is given a long list of
things that they're not allowed to do e.g. fornication, which nine times out
of ten is harmless, and in some cases even masturbation, which is
unbelievable because it does no harm at all. In fact its necessary and
normal.
And those things have nothing to do with morality even. They were just old
societal guidelines. They had nothing to do with God. And neither do a lot
of other things in the Bible.

comp.lang.ruby

Ruby Parser Combinator

Scott Weeks

Christian Neukirchen

ptkwt

Scott Weeks

Scott Weeks

Eric Mahurin

Scott Weeks

Christian Neukirchen

Scott Weeks

Eric Mahurin

Less religion, More brains

x Login to ForumsZone