Let's stop parser Hell

[David Piepgrass]

On Sunday, 8 July 2012 at 21:22:39 UTC, Roman D. Boiko wrote:
> On Sunday, 8 July 2012 at 21:03:41 UTC, Jonathan M Davis wrote:
>> It's been too long since I was actively working on parsers to 
>> give any details, but it is my understanding that because a 
>> hand-written parser is optimized for a specific grammar, it's 
>> going to be faster.
>
> My aim is to find out any potential bottlenecks and ensure that 
> those are possible to get rid of. So, let's try.
>
> I believe it would not hurt generality or quality of a parser 
> generator if it contained sews for inserting custom (optimized) 
> code where necessary, including those needed to take advantage 
> of some particular aspects of D grammar. Thus I claim that 
> optimization for D grammar is possible.

I'm convinced that the output of a parser generator (PG) can be 
very nearly as fast as hand-written code. ANTLR's output (last I 
checked) was not ideal, but the one I planned to make (a few 
years ago) would have produced faster code.

By default the PG's output will not be the speed of hand-written 
code, but the user can optimize it. Assuming an ANTLR-like PG, 
the user can inspect the original output looking for inefficient 
lookahead, or cases where the parser looks for rare cases before 
common cases, and then improve the grammar and insert ... I 
forget all the ANTLR terminology ... syntactic predicates or 
whatever, to optimize the parser.

> So far discussion goes in favor of LL(*) parser like ANTLR, 
> which is top-down recursive-descent. Either Pegged will be 
> optimized with LL(*) algorithms, or a new parser generator 
> created.

Right, for instance I am interested in writing a top-down PG 
because I understand them better and prefer the top-down approach 
due to its flexibility (semantic actions, allowing custom code) 
and understandability (the user can realistically understand the 
output; in fact readability would be a specific goal of mine)

Roman, regarding what you were saying to me earlier:
>In stage 2 you have only performed some basic analysis, like, 
>e.g., matched braces to define some hierarchy. This means that 
>at the time when you find a missing brace, for example, you 
>cannot tell anything more than that braces don't match.

Stage 2 actually can tell more than just "a brace is missing 
somewhere". Because so many languages are C-like. So given this 
situation:

    frob (c &% x)
       blip # gom;
    }

It doesn't need to know what language this is to tell where the 
brace belongs. Even in a more nebulous case like:

    frob (c &% x) bar @ lic
       blip # gom;
    }

probably the brace belongs at the end of the first line.

Perhaps your point is that there are situations where a parser 
that knows the "entire" grammar could make a better guess about 
where the missing brace/paren belongs. That's certainly true.

However, just because it can guess better, doesn't mean it can 
reinterpret the code based on that guess. I mean, I don't see any 
way to "back up" a parser by an arbitrary amount. A hypothetical 
stage 2 would probably be hand-written and could realistically 
back up and insert a brace/paren anywhere that the heuristics 
dictate, because it is producing a simple data structure and it 
doesn't need to do any semantic actions as it parses. A "full" 
parser, on the other hand, has done a lot of work that it can't 
undo, so the best it can do is report to the user "line 54: 
error: brace mismatch; did you forget a brace on line 13?" The 
heuristic is still helpful, but it has already parsed lines 13 to 
54 in the wrong context (and, in some cases, has already split 
out a series of error messages that are unrelated to the user's 
actual mistake).

> As I demonstrated in some examples, it could get the output 
> which implies incorrect structure

I was unable to find the examples you refer to... this thread's 
getting a little unweildy :)