From: Eric Mahurin <eric_mahurin@...>
Date: 2005-10-16T00:13:19+09:00
Subject: Re: [ANN] grammar-0.5

--- Phil Tomson <ptkwt@aracnet.com> wrote:

> In article
> <20051014030528.909.qmail@web36103.mail.mud.yahoo.com>,
> Eric Mahurin  <eric_mahurin@yahoo.com> wrote:
> >Well, I'm finally doing a release of my grammar package:
> >
> >http://rubyforge.org/projects/grammar/
> >
> >I also released cursor-0.9 to go along with it:
> >
> >http://rubyforge.org/projects/cursor/
> >
> >Here are some of the features of it:
> >
> >* BNF-like grammar written directly in Ruby (by overriding
> +,
> >|, *, &, ~, etc operators)
> >
> >* lexer and parser grammars are specified in exactly the
> same
> >way - one parses characters and the other tokens
> >
> >* can write a lexer-free parser
> >
> >* may define tokens however is appropriate
> >
> >* variety of Cursor options for connecting lexer to parser
> >
> >* can put lexer and parser in different threads
> >
> >* defaults to one character/token lookahead, but can extend
> to
> >arbitrary lookahead where needed
> >
> >* autogenerates flattened code by using a macro-like
> facility
> >
> >* ruby actions easily specified in blocks
> >
> >* lots of convienent Grammar methods to combine and
> manipulate
> >grammars
> >
> >
> >TODO:
> >
> >* error reporting needs work.  File/line/column numbers is
> >needed
> >
> >* Cursor::Producer (multithreaded lexer cursor) needs some
> >love.  It doesn't have a very robut interface.
> >
> >* various small API changes.  need more examples to see what
> >would be good to have.
> >
> >* better testing.  only have partial random testing.
> >
> >
> >I also have to samples that you can look at:
> >
> >- tcl interpreter: a complete tcl parser (no lexer needed)
> and
> >interpreter written in under 150 lines of ruby code.  The
> >example fact.tcl shows a recursive proc being defined and
> used
> >in tcl.
> >
> >- infix 2 postfix expression converter: shows a lexer and
> >parser and how they can be multi-threaded.  converts an
> infix
> >expression into a postfix expression (looks like Joy)
> returned
> >in a simple array.
> >
> 
> Just in time for writing our new Ruby parser in Ruby to solve
> the default 
> block argument conundrum ;-)

Actually, that's what I've decided to do...  The meta-ruby guys
might use it.

> BTW: didn't you use this to write a Verilog parser?

Not yet.  I wrote a verilog parser over a year ago using ANTLR.
 It could probably be translated to Grammar pretty easily since
both are LL.

I don't know how many of you have looked at the code yet or
not, but it is pretty simple.  After seeing what #+ and #| do
(they are methods of just a few lines) and how recursion works
(through the base Grammar class), you should be able figure out
everything else pretty easily.  This is because I have a LL
parser instead of LR (yacc).  The main thing that complicates
this is that I do code flattening (macro-like stuff), but this
is only an optimization - you can ignore it for understanding
the functionality.

Previously, I was simply calling #scan for each child Grammar
using Grammar::Code instead of Grammar::Inline.  With one of my
very simple samples, I saw a speedup of at least 60% (don't
have exact before/after numbers) using flattening.  I'd expect
much more on larger Grammar's since inlining does have a
startup penalty.  Or maybe Cursor is my bottleneck.

Another idea I had was to use ruby2c to convert this flattened
ruby code (doesn't stop until it hits recursion) to C and use
the C for #scan instead of ruby.  I may also provide an
IO-to-Cursor #extend module so that I can bypass the Cursor
layer for the subset of the Cursor API that I use in Grammar. 
I would expect a very nice speedup doing this.



		
__________________________________ 
Yahoo! Music Unlimited 
Access over 1 million songs. Try it free.
http://music.yahoo.com/unlimited/