Rockit: A Parser Generator for Ruby

50 %
50 %
Information about Rockit: A Parser Generator for Ruby

Published on December 27, 2007

Author: jmorrison

Source: slideshare.net

Description

Discusses Rockit, a parser generator for the Ruby langauge. Touches on versions 0.3.8 and 0.7.2, which are GLR and PEG, respectively. Describes GLR and PEG. Given for http://www.cs.rit.edu/~ats/lp-2006-2/

Rockit Jason Morrison Language Processors and Compiler Construction Winter 2006-3

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

It used to be GLR First home I found: http://rockit.sourceforge.net/ Version 0.3.8, updated October 2001 What did it look like?

First home I found:

http://rockit.sourceforge.net/

Version 0.3.8, updated October 2001

What did it look like?

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

Ruby Rockit: Overview It used to be GLR. What’s that? Maybe in the future it will be PEG. It’s kind of there. Let’s see!

It used to be GLR.

What’s that?

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

What’s GLR? Generalized LR Parse tables have multiple transitions When it hits S/R or R/R conflict: Fork parse stack Follow both paths Got a rule that produces no transition? Discard that stack.

Generalized LR

Parse tables have multiple transitions

When it hits S/R or R/R conflict:

Fork parse stack

Follow both paths

Got a rule that produces no transition? Discard that stack.

How well does it work? Run time scales with degree of nondeterminism. O(n) on deterministic grammar. Optimize: share common stack prefix/suffix. (Leads to a state lattice rather than stack)

Run time scales with degree of nondeterminism.

O(n) on deterministic grammar.

Optimize: share common stack prefix/suffix. (Leads to a state lattice rather than stack)

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

Maybe in the future it will be PEG. Rockit 0.8.0 C-based parser, Ruby production rules Unambiguous,  lookahead, O(n) Packrat parsing Ruby and Java grammars, analyzers, pretty-printers

Rockit 0.8.0

C-based parser, Ruby production rules

Unambiguous,  lookahead, O(n) Packrat parsing

Ruby and Java grammars, analyzers, pretty-printers

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. … PEG? Packrat? It’s kind of there. Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

… PEG? Packrat?

It’s kind of there.

Let’s see!

What’s PEG? “Parsing Expression Grammar” No separate tokenizing phase Unambiguous (one tree for valid parse) No left recursion (as with LL)

“Parsing Expression Grammar”

No separate tokenizing phase

Unambiguous (one tree for valid parse)

No left recursion (as with LL)

What’s PEG? Fixes “dangling else” via prioritization Infinite lookahead via syntactic predicates Let’s hear it from B ryan Ford (coined PEG) http://www.bford.info/pub/lang/peg-slides.pdf

Fixes “dangling else” via prioritization

Infinite lookahead via syntactic predicates

Let’s hear it from B ryan Ford (coined PEG)

What’s Packrat? Essentially: recursive descent Memoization yields O(n) with unlimited lookahead and backtracking Packrat parsers: Java: Rats! (from xtc, eXTensible C project) Haskell: Pappy

Essentially: recursive descent

Memoization yields O(n) with unlimited lookahead and backtracking

Packrat parsers:

Java: Rats! (from xtc, eXTensible C project)

Haskell: Pappy

Packrat: Since when? Theory has been formalized since the 70s Memoization was too heavy, then. Now, RAM is cheap; memoization often consumes less than subsequent compilation steps.

Theory has been formalized since the 70s

Memoization was too heavy, then.

Now, RAM is cheap; memoization often consumes less than subsequent compilation steps.

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. What do you mean by that? Let’s see!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

What do you mean by that?

Let’s see!

Rockit 0.7.2 Newest available Deemed 0.8.0 preview Pure Ruby (=> slow) recursive-descent parser Does not support syntactic predicates Examples are only documentation Unorganized source No error hooks

Newest available

Deemed 0.8.0 preview

Pure Ruby (=> slow) recursive-descent parser

Does not support syntactic predicates

Examples are only documentation

Unorganized source

No error hooks

Ruby Rockit: Overview It used to be GLR. Maybe in the future it will be PEG. It’s kind of there. Let’s see! Let’s see it anyways!

It used to be GLR.

Maybe in the future it will be PEG.

It’s kind of there.

Let’s see!

Let’s see it anyways!

Rockit 0.7.2 Arithmetic expression example

Arithmetic expression example

Conclusion 0.7.2 is interesting, but doesn’t have: Syntactic predicates Memoization Still denotes grammar in code. Pros: Quick, familiar. Cons: Difficult to analyze. If 0.8.0 is released as promised, should be great!

0.7.2 is interesting, but doesn’t have:

Syntactic predicates

Memoization

Still denotes grammar in code.

Pros: Quick, familiar.

Cons: Difficult to analyze.

If 0.8.0 is released as promised, should be great!

Resources These slides and I: http:// jayunit.net/rockit jason.p.morrison@gmail.com PEG ML: https:// lists.csail.mit.edu/mailman/listinfo/peg Bryan Ford: http:// pdos.csail.mit.edu/~baford/packrat Wikipedia, Google for: GLR parser, PEG grammar, Packrat parser

These slides and I:

http:// jayunit.net/rockit

jason.p.morrison@gmail.com

PEG ML:

https:// lists.csail.mit.edu/mailman/listinfo/peg

Bryan Ford:

http:// pdos.csail.mit.edu/~baford/packrat

Wikipedia, Google for:

GLR parser, PEG grammar, Packrat parser

Add a comment

Related presentations

Related pages

Rockit REAME

Example of using the rockit lib in Ruby code? require 'rockit/rockit' parser = Parse.generate ... of the parser generator all but the parser taking ...
Read more

Parser Generators - Ruby Developer's Guide - Chapter 9

... way to write parsers in Ruby. The result was the parser generators and combinators ... Rockit as a Parser Generator If you think the ...
Read more

Rockit: A Parser Generator for Ruby - Technology

Discusses Rockit, a parser generator for the Ruby langauge. Touches on versions 0.3.8 and 0.7.2, which are GLR and PEG, respectively. Describes GLR and PEG.
Read more

Why are parser tools rarely used in ruby?(Rockit) - Google ...

On Wed, 18 Sep 2002, Phil Tomson wrote: > There have been a couple of positive mentions of Rockit in this thread. > I've not used it, but I read the ...
Read more

Why are parser tools rarely used in ruby?(Rockit) - Google ...

In article , Robert Feldt wrote: >On Wed, 18 Sep 2002, Phil Tomson ...
Read more

ruby, Parser? - computer-programming-forum.com

The Ruby parser is one example in rockit ... Ruby code for a parser). ... Current status is that the parser generator in rockit bootstraps itself
Read more

Help me find an appropriate ruby/python parser generator ...

The first parser generator I've ... Help me find an appropriate ruby/python parser generator. ... python or ruby. I was referring to debugging the parser ...
Read more

GitHub - zdavatz/rockit: Rockit Version 0.3.8

zdavatz / rockit. Code. Issues 0. ... reduce_actions_generator.rb: rockit.rb: rockit_grammar_ast_eval.rb: rockit_grammars_parser.rb: sourcecode_dumpable.rb:
Read more