On Thu, Sep 12, 2013 at 07:00:09AM +0200, deadalnix wrote:
> 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.
[...]
This can be handled by using an intermediate grammar rule. Reduce all
(...) into an intermediate type, say ArgList, so the reduction
happens something like this:
int foo () () {}
Type Ident ArgList ArgList ^
Then have the rule:
CompileTimeArgs ::= ArgList
RuntimeArgs ::= ArgList
TemplateDecl ::= Type Ident CompileTimeArgs RuntimeArgs '{' ...
FuncDecl ::= Type Ident RuntimeArgs '{' ...
So first, all (...) gets parsed to ArgList, but it's not yet fixed
whether they are compile-time arguments or runtime arguments. It's only
after you see the next '(' or '{' that you decide whether ArgList should
reduce to CompileTimeArgs or RuntimeArgs.
ArgList itself, of course, will accept all possible parameters (both
runtime and compile-time): types, expressions, symbols. Then when you
reduce it to RuntimeArgs, you reject stuff that can't be interpreted as
parameter declarations.
T
--
There are two ways to write error-free programs; only the third one works.
