Re: Using the wisent parser-generator, as it creates faster parsers

[Lynn Winebarger <owinebar@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1975 bytes --]

On Sun, Dec 25, 2022, 11:03 PM <ambulajan@gmail.com> wrote:

> A follow-up note after reading earlier discussion with a subject "Re:
> Why tree-sitter instead of Semantic?".
>
> > If you want to build a parser that sits on the lexer, there is more
> > to it, as I recommend using the wisent parser-generator, as it
> > creates faster parsers. In the wisent .wy files, you define %tokens
> > using a bison-like syntax, and that in turns builds analyzers that
> > you include in your lexer.
>
> I doubt that the problem of Semantic parsers was ever in Elisp being
> slow for that purpose.
> For me it was writing a LALR parser. Everything else was logical -
> lexers, SemanticDB, etc. But a grammar in development that stalls at
> every step with shift/reduce and reduce/reduce conflicts is like
> pushing against a wall. LALR algorithm never meant to be an interface
> for a developer, rather a workaround for slow CPUs with small memory
> systems of the 1980s.
>

I don't agree - conflicts detected by the parser generator indicate that
distinct ASTs map to the same text, at least according to the reduction
method being used.  I like using LR derivations (including ones produced by
LALR) because of the bottom-up recognition of grammar symbols.


I've written an Earley parser, and so far it looks in the same
> performance category as LALR(wisent) written in Elisp.
> Earley parser works with any grammar you throw at it. No conflicts.
> Each token gets full context of rules that are in effect at that point.
> Seems like there's no need to build parse trees, a list of states-
> tokens can be thought of as a flattened parse tree.
> Though there's a lot of testing for this concept ahead.
>


The above is not to discourage adding Earley parsing to the toolkit.
However, just defers the to resolution of ambiguities to your code rather
than by refining your grammar. For specifying a programming language, this
seems like inviting difficult to debug cases to me.

Lynn

[-- Attachment #2: Type: text/html, Size: 2774 bytes --]