Let's stop parser Hell

[Roman D. Boiko]

On Saturday, 7 July 2012 at 21:43:58 UTC, David Piepgrass wrote:
> Still... it's a fun concept, and even if the initial parsing 
> ends up using the good-old lex-parse approach, semantic 
> analysis and lowering can benefit from a tree parser. Tree 
> parsing, of course, is just a generalization of linear parsing 
> and so a tree parser generator (TPG) could work equally well 
> for flat input.

Exactly. Semantic analysis is what would benefit from that, as 
well as client code (for example, refactoring tools, etc.)

Parser would become quite complicated. Probably it would need to 
perform complex tree navigation (which might decrease performance 
proportionally to the average tree depth or even more, if parser 
algorithms were themselves fast). Any non-trivial query would 
require direct character manipulation (like comparing sub-strings 
of captures with string literals, etc.). Probably you would get 
frequent cache misses because of the need to jump throughout the 
(incomplete) AST. It would definitely be problematic to build an 
immutable AST model, thus (IMO) significantly and needlessly 
constraining you and users of your library. And likely you would 
have to deal with many more problems __without__ significant 
gains.