From: Eric Mahurin <eric.mahurin@...>
Date: 2005-11-06T00:03:58+09:00
Subject: Re: parser performance comparisions

------=_Part_41583_5431276.1131203036023
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 11/5/05, Jim Freeze <jim@freeze.org> wrote:
>
> On 11/4/05, Phil Tomson <ptkwt@aracnet.com> wrote:
> > A better comparison would be to create a Ruby grammar...


And compare to what? We have no ruby parsers in ruby.

I would like to compare to something else too. If anybody else has other
suggestions, here's what I would need to compare with:

- racc (or even working rockit) grammar
- a large test file that takes at least several seconds to parse
- hope something simple enough that it won't take much time to convert to
Grammar (I don't want to distract from my ruby parser much)

Other comparisons may be needed, but this one is very important.
> It says that Grammar can play equally with RACC in terms of speed,
> which is important if you are the new kid on the block.
>
> What I would like to see is grammar speed up a bit so that the
> one-token-at-a-time
> is as fast as Racc with the C extension. Then it would almost be a no
> brainer
> to use Grammar instead of Racc.


Why is the one-token-at-a-time Grammar lexer important? If you already have
a Regexp lexer (for RACC or whatever), it is very easy to make it a lexer
for a Grammar parser - just make it an object that has a read1next method
(like a Cursor) - similar to next_token with yacc. Until I start generating
C code, it will be hard to compete against a Regexp lexer since it does
stuff in C.

If you are starting from scratch though, the recommended way for making a
lexer for a Grammar parser is with Grammar is the multi-threaded approach.
This gives the most flexibility and better readability for complex lexers.
With this approach, the Grammar of the lexer parses the whole file and
generates all tokens (instead of parsing just one token). By doing it this
way, most lexers don't need to hold state internal to the lexer. For
example, if a string corresponds to multiple tokens, the token-at-atime
lexer would have to set a lexer state when it entered a string so that the
next time it is called it would return a string-type token (and reset that
state when it found the end-of-string). With the lexer parsing all tokens,
when it finds a string it just generates all the tokens for that string
right there - no need for a lexer state.

But, Grammar will get faster over time. Here are some of my ideas:

- use ruby2c to convert my generated ruby code to C.
- if that doesn't pan out, make another set of Grammar classes/methods (sam=
e
API) that generate C code and inline it.
- optimize the methods from various Cursor classes that Grammar might use.

Also keep in mind that with my Grammar stuff, parser generation is done at
run-time (included in the numbers I gave). This should typically take a
fraction of a second for most parsers. If it becomes an issue I will add th=
e
ability to dump the generated code to a file. But, for now I'd like to leav=
e
it because the programmer not having to worry about the parser generation
stage and how to integrate that the generated file makes the usability much
higher. Grammar can be treated as just another library.

Good work Eric.


Thanks, Jim.

------=_Part_41583_5431276.1131203036023--