Let's stop parser Hell

[Dmitry Olshansky]

On 08-Jul-12 00:09, Andrei Alexandrescu wrote:
> On 7/7/12 3:17 PM, Dmitry Olshansky wrote:
>> I'll have to point out that the whole point about integrated lexing is
>> moot. It's more of liability then benefit. At very least it's just
>> implementation curiosity not advantage.
>
> Interesting. I'll have to ask for more details on why.
>

I think I told that before but anyway the main point is:
the reason lexer exists is performance.

It's obvious that one can write grammar without ever using lexer. If the 
notation is good say regex or the one used in PEG (that is not quite the 
same it turns out) then token can be easily describe in grammar. Once we 
got lexer can give only 2 things:
	-manageability, it's jsut splitting grammar in 2 parts that could be 
maintained separately (in fact some "lexers" are not DFA nor regular)
(sometimes it could go the opposite direction - it could be  better to 
have one integrated grammar)
	- speed. The reason it could be faster is because lexer can use highly 
deterministic grammar.

Now back to PEGs and packrats. What I see everywhere I look is 
essentially integration of a backtracking-NFA lexer, that is not fast 
nor is particularly convenient. The notation is the whole other matter.

So my view on the matter: whether or not lexer is integrated is two-fold 
question: notation vs implementation.

E.g. it may make regular lexer-like things a part of notation thus 
having rules like:
	Identifier  -> Alpha (Alpha|Number|_)*

Yet it may or may use the same engine for _all_ _rules_, in fact if 
implementation optimize things by ripping off regular parts of grammar 
to small DFA engines it would make some kind of lexer behind the scenes!

Anyway highly hybrid parsers are all the rage now, and reasons are 
obvious - they runs fast and can be bend by some magic to quite 
convoluted grammars of modern languages ;)

-- 
Dmitry Olshansky