Let's stop parser Hell

[Chad J]

On 07/07/2012 03:13 PM, Roman D. Boiko wrote:
> On Saturday, 7 July 2012 at 18:55:57 UTC, Chad J wrote:
>
>> 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).
>

 From some of my earlier scribblings:

enum : SyntaxElement
{
   AST_EXPRESSION          = 0x0001_0000_0000_0000,
     AST_UNARY_EXPR        = 0x0000_0001_0000_0000 | AST_EXPRESSION,
       AST_NEGATE_EXPR     = 0x0000_0000_0001_0000 |  AST_UNARY_EXPR,
       AST_COMPLIMENT_EXPR = 0x0000_0000_0002_0000 |  AST_UNARY_EXPR,
       AST_POST_ADD_EXPR   = 0x0000_0000_0003_0000 |  AST_UNARY_EXPR,
       AST_POST_SUB_EXPR   = 0x0000_0000_0004_0000 |  AST_UNARY_EXPR,
       AST_PRE_ADD_EXPR    = 0x0000_0000_0005_0000 |  AST_UNARY_EXPR,
       AST_PRE_SUB_EXPR    = 0x0000_0000_0006_0000 |  AST_UNARY_EXPR,
     AST_BINARY_EXPR       = 0x0000_0002_0000_0000 | AST_EXPRESSION,
       AST_AND_EXPR        = 0x0000_0000_0001_0000 |  AST_BINARY_EXPR,
       AST_OR_EXPR         = 0x0000_0000_0002_0000 |  AST_BINARY_EXPR,
       AST_XOR_EXPR        = 0x0000_0000_0003_0000 |  AST_BINARY_EXPR,
       AST_AND_AND_EXPR    = 0x0000_0000_0004_0000 |  AST_BINARY_EXPR,
       AST_OR_OR_EXPR      = 0x0000_0000_0005_0000 |  AST_BINARY_EXPR,
       AST_ADD_EXPR        = 0x0000_0000_0006_0000 |  AST_BINARY_EXPR,
     AST_TRINARY_EXPR      = 0x0000_0003_0000_0000 | AST_EXPRESSION,
     AST_NARY_EXPR         = 0x0000_0004_0000_0000 | AST_EXPRESSION,
   AST_STATEMENT           = 0x0002_0000_0000_0000,
}


bool isA( SyntaxElement leafier, SyntaxElement rootier )
{
	SyntaxElement mask = 0;
	
	if ( rootier & 0x0000_0000_FFFF_FFFF )
	{
		if ( rootier & 0x0000_0000_0000_FFFF )
			mask = 0xFFFF_FFFF_FFFF_FFFF;
		else
			mask = 0xFFFF_FFFF_FFFF_0000;
	}
	else
	{
		if ( rootier & 0x0000_FFFF_FFFF_FFFF )
			mask = 0xFFFF_FFFF_0000_0000;
		else
			mask = 0xFFFF_0000_0000_0000;
	}
	
	return (leafier & mask) == rootier;
}

unittest
{
	assert(  isA( AST_EXPRESSION,  AST_EXPRESSION) );
	assert(  isA( AST_NEGATE_EXPR, AST_NEGATE_EXPR) );
	assert(  isA( AST_NEGATE_EXPR, AST_EXPRESSION) );
	assert(  isA( AST_NEGATE_EXPR, AST_UNARY_EXPR) );
	assert( !isA( AST_EXPRESSION,  AST_STATEMENT) );
	assert( !isA( AST_NEGATE_EXPR, AST_BINARY_EXPR) );
	assert( !isA( AST_NEGATE_EXPR, AST_STATEMENT) );
	assert( !isA( AST_NEGATE_EXPR, AST_COMPLIMENT_EXPR) );
	assert(false);
}

This approach of course has shameful nesting limitations, but I feel 
like these determinations could be fairly well optimized even for the 
general case.  For example: another approach that I might be more 
inclined to take is to give each token/symbol a low-valued index into a 
small inheritance table.

I would expect the regex engine to call the isA function as one of it's 
operations.  Thus placing an AST_EXPRESSION into your expression would 
also match an AST_NEGATE_EXPR too.