[ANN] grammar-0.5

[Eric Mahurin]

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.

__________________________________
Yahoo! Mail - PC Magazine Editors' Choice 2005
http://mail.yahoo.com

[Eric Mahurin]

--- Eric Mahurin <eric_m...@yahoo.com> wrote:

> - 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.

Actually, I meant a complete parser/interpreter *engine* was
written in 150 lines. You still need to write all of the tcl
library procs. I only put basic procs in there to demo.
Still, pretty neat that you can create a turing-complete
interpreter in 150 lines of code!

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

[itsme213]

"Eric Mahurin" <eric_m...@yahoo.com> wrote in message

> Well, I'm finally doing a release of my grammar package:

Thanks for this!

Didn't you have some usage examples etc. earlier on the web? Any chance you
could put those somewhere accessible, or into the rdoc home page (I believe
that can be done, don't know how).

[Phil Tomson]

In article <200510140305...@web36103.mail.mud.yahoo.com>,

Just in time for writing our new Ruby parser in Ruby to solve the default
block argument conundrum ;-)

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

Phil

[George Moschovitis]

Hey, just what I needed for a pet project of mine ;-)

Thanks,
-g.

--
http://www.gmosx.com
http://www.navel.gr
http://www.nitrohq.com

[Eric Mahurin]

--- itsme213 <itsm...@hotmail.com> wrote:

Here are the samples under CVS that you can look at:

http://rubyforge.org/cgi-bin/viewcvs.cgi/samples/?cvsroot=grammar

[Sean O'Halpin]

On 10/14/05, Eric Mahurin <eric_m...@yahoo.com> wrote:

> Well, I'm finally doing a release of my grammar package:

It looks good. How would you go about adding, say, unary minus to the
infix example?

Regards,

Sean

[Eric Mahurin]

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.