Pegged: Syntax Highlighting

[Andrei Alexandrescu]

On 3/17/12 3:53 PM, Philippe Sigaud wrote:
> On Sat, Mar 17, 2012 at 18:11, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org>  wrote:
>
>>> The D grammar is a 1000-line / hundreds of rules monster. I finished
>>> writing it and am now crushing bugs.
>>> God, that generates a 10_000 line module to parse it. I should
>>> simplify the code generator somewhat.
>>
>>
>> Science is done. Welcome to implementation :o).
>
> Hey, it's only 3.000 lines now :) Coming from a thousand-lines
> grammar, it's not that much an inflation.

That's quite promising.

> Indeed, but I fear the D grammar is a bit too complex to be easily
> walked. Now that I read it, I realize that '1' is parsed as a
> 10-levels deep leaf!
> Compared to lisp, it's... not in the same league, to say the least. I
> will see to drastically simplify the parse tree.

This is where custom directives for helping AST creation might help. 
Also, ANTLR solves that problem by allowing people to define tree 
walkers. They have much simpler grammars (heck, the hard job has already 
been done - no more ambiguities). At an extreme, languages such as ML 
are good at walking trees because they essentially embed a tree walker 
in their pattern matching grammar for function parameters.

> Does anyone have experience with other languages similar to D and that
> offer AST-walking? Doesn't C# have something like this?
> (I'll have a look at Scala macros)

Heck, I just found this which destroys ANTLR's tree walkers:

http://www.antlr.org/article/1170602723163/treewalkers.html

Didn't read it yet, but clearly it's an opposing viewpoint and relevant 
to your work (don't forget to also read the article to which it's 
replying http://antlr.org/article/1100569809276/use.tree.grammars.tml).

>> 1. Would you consider submitting your work to Phobos?
>
> Yes, of course. It's already Boost-licensed.
> Seeing the review processes for other modules, it'd most certainly put
> the code in great shape. But then, it's far from being submittable
> right now.

Let us know how we can help. This is an important project.

>> 2. Do you think your approach can generate parsers competitive with
>> hand-written ones? If not, why?
>
> Right now, no, if only because I didn't take any step in making it
> fast or in limiting its RAM consumption.
> After applying some ideas I have, I don't know. There are many people
> here that are parser-aware and could help make the code faster. But at
> the core, to allow mutually recursive rules, the design use classes:
>
> class A : someParserCombinationThatMayUseA { ... }
>
> Which means A.parse (a static method) is just typeof(super).parse
> (also static, and so on). Does that entail any crippling disadvantage
> compared to hand-written parser?

I'm not sure without seeing more code.


Andrei