[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:roducer (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.



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

 

[Eric Mahurin]

- 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.=20
Still, pretty neat that you can create a turing-complete
interpreter in 150 lines of code!



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

 

[Phil Tomson]

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:roducer (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 ;-)

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.

 

[Sean O'Halpin]

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]

=20
Just in time for writing our new Ruby parser in Ruby to solve
the default=20
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.=20
I would expect a very nice speedup doing this.



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