From: Robert Feldt <feldt@...>
Date: 2003-07-31T15:59:09+09:00
Subject: Re: Parser generator

Clifford Heath <cjh_nospam@managesoft.com> skrev den 31 Jul 2003 09:24:23 
+1000:

> Robert Feldt wrote:
>> Recently some new algorithms and ideas for GLR has made C 
>> implementations
>> approach bison (LALR) in performance (I think the best are within 3-10% 
>> of
>> bison) when the grammar is unambigous (which they are the majority of 
>> the time in practice). This is the best of worlds since you only take 
>> the performance hit when there is no way to decide early which parse 
>> tree is the correct one.
>>
>> Rockit 0.3.8 is too immature (bugs and poor performance) to use for 
>> parsing large grammars/inputs unfortunately since I haven't had enough 
>> time to work on it. There is a later version that uses one of the new C- 
>> implemented GLR backend's for nice speed but I never get enough time to 
>> tighten/pack it up.
>
> Robert,
>
> I have thought it would be good to have a native Ruby parser generator.
>
I agree.

> Are these GLR algorithms implemented in sufficiently readable fashion
> that it would be worth translating?  I have delved into various parser
> generators and implemented many parsers, but I do find that much code
> written by the sort of language-theory buffs that build these things to
> be completely but unnecessarily impenetrable.
>
> One reason for a native implementation is to allow dynamic extension
> of a grammar - so you can add rules to an operating parser and have the
> generator re-generate the parser on the fly. Great for parser development
> and extensible languages...
>
My plan is to get it working as I want with the C back-ends and then
translate the necessary parts to Ruby. Having a pure Ruby one is
essential yes.

I'd say they are not super-easy to translate since there is no real
docs on the design and internals. However, you can start with
only the parts that are necessary during parsing since they are generally
smaller than the rest. Thus you can generate both fast parsers using C
but can be compiled to Ruby extension and have a pure Ruby parser when
you want for portability. When that is in place you can focus on
doing the rest of it in pure Ruby (Since the GLR generation phase is
very similar to the LALR one you could actually use parts of Racc,
unclear if its worth it though).

> Can you point me to the GLR implementations of which you speak?
>
Elkhound is the fastest but its C++ and I wanted a pure-C one. So
I use D Parser (dparser.sf.net).

If you wanna work on translating it to Ruby I think its good if we 
collaborate on it since there are obvious overlaps / connections
to rockit.

Regards,

Robert