std.d.lexer : voting thread

[Dmitry Olshansky]

08-Oct-2013 04:16, Andrei Alexandrescu пишет:
> On 10/4/13 5:24 PM, Andrei Alexandrescu wrote:
> To put my money where my mouth is, I have a proof-of-concept tokenizer
> for C++ in working state.
>
> http://dpaste.dzfl.pl/d07dd46d
>
> It contains some rather unsavory bits (I'm sure a ctRegex would be nicer
> for parsing numbers etc), but it works on a lot of code just swell.

No - ctRegex as it stands right now is too generic and conservative with 
the code it generates so "\d+" would do:
a) use full Unicode for "Number"
b) keep tabs on where to return as if there could be ambiguity of how 
many '\d' it may eat (no maximal munch etc.). The reason is that the 
fact that said '\d+' may be in the middle of some pattern (e.g. 9\d+0), 
and the fact that it's unambiguous on its own is not exploited.

Both are quite suboptimal and there is a long road I going to take to 
have a _general_ solution for both points. One day we would reach that 
goal though. ATM just hack your way through if pattern is sooo simple.

> Most importantly, there's a clear distinction between the generic core
> and the C++-specific part. It should be obvious how to use the generic
> matcher for defining a D tokenizer.



> Token representation is minimalistic and expressive. Just write tk!"<<"
> for left shift, tk!"int" for int etc. Typos will be detected during
> compilation. One does NOT need to define and use TK_LEFTSHIFT or TK_INT;
> all needed by the generic tokenizer is the list of tokens. In return, it
> offers an efficient trie-based matcher for all tokens.
>
> (Keyword matching is unusual in that keywords are first found by the
> trie matcher, and then a simple check figures whether more characters
> follow, e.g. "if" vs. "iffy".

+1

Given that many tokenizers use a hashtable
> anyway to look up all symbols, there's no net loss of speed with this
> approach.

Yup. The only benefit is slimmer giant switch.
Another "hybrid" option is insated of hash-table use a generated keyword 
trie searcher separately as a function. Then just test each identifier 
with it. This is what std.d.lexer does and is quite fast. (awaiting 
latest benchmarks)

> The lexer generator compiles fast and should run fast. If not, it should
> be easy to improve at the matcher level.
>
> Now, what I'm asking for is that std.d.lexer builds on this design
> instead of the traditional one. At a slight delay, we get the proverbial
> fishing rod IN ADDITION TO of the equally proverbial fish, FOR FREE. It
> is quite evident there's a bunch of code sharing going on already
> between std.d.lexer and the proposed design, so it shouldn't be hard to
> effect the adaptation.

Agreed. Let us take a moment to incorporate a better design.

> So with this I'm leaving it all within the hands of the submitter and
> the review manager. I didn't count the votes, but we may have a "yes"
> majority built up. Since additional evidence has been introduce, I
> suggest at least a revote. Ideally, there would be enough motivation for
> Brian to suspend the review and integrate the proposed design within
> std.d.lexer.
>
>
> Andrei
>


-- 
Dmitry Olshansky