Let's stop parser Hell

[Roman D. Boiko]

On Saturday, 7 July 2012 at 18:55:57 UTC, Chad J wrote:
> I was thinking the same thing.
>
> My intent is to create a kind of regular-expression-of-nodes 
> with push/pop operators to recognize ascent and descent on the 
> tree.  Such a regular expression would allow one to capture 
> subtrees out of generalized patterns and then place them into 
> new trees that then become the input for the next pattern or 
> set of patterns.  I think this is much closer to how I 
> conceptualize semantic analysis than how semantic analysis is 
> done in front ends like DMD: it should to be done with pattern 
> recognition and substitution, not with myriad nested 
> if-statements and while-loops.
Funny, we've discussed an idea to introduce some hybrid of regex 
and xpath for querying, searching and traversing AST with Dmitry 
a few weeks ago. A custom NDepend-like Code Query Language was 
the major alternative we considered. Discussion started on this 
forum and continued via email.

> In this vision I do not use classes and inheritance for my AST.
>  Instead I use structs that contain some kind of nodeType 
> member that would be one of the tokens/symbols in the grammar, 
> like TOK_WHILE_NODE in the above code.  Dynamic dispatch is 
> instead performed by (very fast) DFAs recognizing parts of the 
> AST.

Exactly. This idea first came to me in April after I implemented 
the first top-down recursive descent custom parser for a D 
subset. I tried Visitor pattern before that and wasn't happy. 
There are some subtle difficulties which I believe will be 
possible to overcome, most important being the need to introduce 
a mechanism for hierarchical classification (like a pow 
expression being an assign expression at the same time).