std.d.lexer: pre-voting review / discussion

[deadalnix]

On Thursday, 12 September 2013 at 03:37:55 UTC, H. S. Teoh wrote:
> I still don't understand why backtracking is necessary in the 
> first
> place. I would've thought a modern parser should be well able 
> to encode
> seen tokens in its state so that backtracking is never 
> necessary. Or
> does D grammar have tricky bits that cannot be handled this 
> way, that
> I'm unaware of?
>

The problem is that it can cause a exponential (and I literally 
mean exponential here) amount of complexity.

In some cases, the complexity is manageable, but in other that 
don't make any sense (it has to be noted that even full lexing 
don't make any sens here). For instance :

int foo()() {}
        ^

When you are at the caret position, you don't know if you face a 
function declaration or a template declaration. You could go for 
some ambiguous parsing, but each template argument can itself be 
a type, an expression or a symbol.

In such situation, it is much simpler to skip input to the 
closing parentheses, check what's coming after and act 
accordingly. The alternative is to go for some ambiguous 
function/template parameters parsing and resolve at the end, but 
as template argument are themselves ambiguous 
type/expression/symbols, the amount of complexity in the parser 
is doomed to explode. Note that the example is not self 
contained, for instance, both template parameters and argument 
can imply template instantiation, which means ambiguous argument 
parsing.

SDC does a good deal of ambiguous parsing without backtracking 
(more than DMD does), but you got to draw the line somewhere.

What I'd like to see is a go to the closing token feature, that 
can eventually take a fast path to do so, or an efficient token 
buffering system (I'm not sure which feature would be the 
fastest, but I'm inclined to think this is the first one, 
however, that won't be suited for a dmd style parser).