From: Scott Weeks <weeksie@...>
Date: 2006-01-22T17:49:30+09:00
Subject: Re: Ruby Parser Combinator

Cool, Thanks for the examples! One of the things I was thinking about 
was bringing the example I wrote further inline with Parsec where it 
can handle a list of tokens of any sort rather than just an IO stream 
as you've done with the Cursor library.

My main aim with this was to understand combinators more intimately and 
I feel that it's been quite good for doing that and has certainly given 
me a lot of perspective in regards to a Haskell project that I'm 
working on.

Cheers,
Scott




On 22/01/2006, at 11:50 AM, Eric Mahurin wrote:

> On 1/21/06, Scott Weeks <weeksie@twelvestone.com> wrote:
>>
>>>
>>> Take a look here:
>>>
>>> http://rubyforge.org/projects/grammar/
>>>
>>
>> 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.
>
>
>