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

[Alexandr Karbivnichyi]

On Mon, 2022-12-26 at 08:54 -0500, Lynn Winebarger wrote:
> On Sun, Dec 25, 2022, 11:03 PM <ambulajan@gmail.com> wrote:
> 
> 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. 

True for LALR parsers. Tried-and-tested system, for industrial
compilers built on a formal standard with simple grammar that doesn't
change often.
I explored parsing from time to time having in mind an idealistic view
of a system where given some grammar a lot of automatic features appear
almost ready for use.
So AST. It's required unambiguous to generate assembler mnemonics. It's
unavoidable in LALR to build AST in order to make any sense of the
parse.
Earley parser creates a state(list of grammar rules) at each scan
step(shift). I discovered that it's all what's needed at this stage in
the case when I don't intent to create executable. The state contains
all current grammar rules with a "dot" inside them(rule's progress at
point), from all possible parse trees. It's enough to compute
indentation, create smart completion, compose explicative error
messages.
The beauty of Early's algorithm is in possibility to write some grammar
and then keeping in mind the algorithm to write states by hand in a
text file for each token. The parser concept prints those states in
Message buffer, provides human readable interface. It gives an analogy
of 'syntax-ppss' function(elisp reader) but with full grammar contex. 

After all, the possibility of invoking one parser with different lexers
turns out to be an interesting idea. For different purposes. Some
tokens can be just blocks of text, either not contributing to the
current purpose or put aside to be reparsed recursively when contents
of that block-token change while editing.

> 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.  

And reciprocally not to discourage usage of existing tried-and-tested
parsers. Semantic allows that a parser may(should) be a separate
library. All in all, it's Emacs.

GLR algorithm doesn't reject grammar with conflicts and doesn't use
defaults to resolve. It's a LALR parser that starts parallel branches
for conflicts. Then after subsequent shifts only one branch survives -
conflict is resolved. The problem is that all parsing branches invoke
actions, all actions must be cached somehow during parsing and only
those actions of the survived branch to be included in parser's output.

In any case, there are no other tools in existence than Emacs that
would allow even reasoning about these ideas implying their practical
implementation.