Lexer and parser generators using CTFE

[Andrei Alexandrescu]

On 2/28/12 8:58 AM, Hisayuki Mima wrote:
> Certainly, I don't write yet the documentation of my library, ctpg.
> (But a few examples available here:
> https://github.com/youkei/ctpg/tree/master/example)

Nice! I have a few comments. I should say that they entail a fair amount 
of work.

The current setup makes things very difficult for a common case - 
generating a parse tree. The user would need to insert a lot of custom 
code to create the appropriate nodes, but that's very easy for the 
parser because it already has the components. The parser should have a 
"build AST" option, in which case it should build all nodes without much 
effort from the user. That's what ANTLR does, and it has a special 
operator "^" to indicate where the root of the tree should be 
(http://www.antlr2.org/doc/trees.html).

So here's what I think your examples should look like:

The syntax could be changed a bit - it should be less like D and more 
like PEG. The "$" is implicit and shouldn't be needed. The ";" is a 
useful terminator for large productions spanning more than one line, so 
let's keep it. I don't understand the use of "!", for example the PEG 
for expression parsing at 
http://en.wikipedia.org/wiki/Parsing_expression_grammar is:

Value   ← [0-9]+ / '(' Expr ')'
Product ← Value (('*' / '/') Value)*
Sum     ← Product (('+' / '-') Product)*
Expr    ← Sum

but your grammar has:

int primary = !"(" addExp !")" / intLit_p;

whereas it seems to me it should be

int primary = "(" addExp ")" / intLit_p;

No?

Here's how I think a parser that also builds an AST looks like:

mixin generateParsers!(
   Options.createAST,
   q{
     root    <- addExp;
     addExp  <- mulExp (("+" / "-")^ addExp)?
     mulExp  <- primary (("*" / "/")^ mulExp)?
     primary <- "(" addExp ")"% / intLit_p;
   }
);

I used the following notation: a node suffixed with "^" becomes the root 
of the produced AST, and a node suffixed with "%" will be dropped 
altogether (that's because ")" is not needed in the AST after the 
expression has been parsed). With only three characters I informed the 
parser what the shape of the AST will be.

At this point calling parse!root("1+2*3") would return an object of type 
ASTNode!"addExp", which in turn has two children, lhs and rhs. The lhs 
node has type ASTNode!"intLit_p" which has inside a value "1". The rhs 
node has type ASTNode!"mulExp", and that in turn has two children nodes 
lhs and rhs, both of type ASTNode!"intLit_p", each with its own value 
("2" and "3", respectively). All these nodes are dynamically created by 
the parsing process and inherit a common type, e.g. ASTNode!"" or some 
type ASTRootNode.

> So, I'd like to describe it here.
>
> To be honest, ctpg is inspired by one module of Scala's standard
> library, Parser Combinators.
> One of the differences between Parser Combinators and ctpg is that
> Parser Combinators generates parsers in run-time, but ctpg generates
> parsers in compile-time by the power of CTFE and mixin.
>
> A parser generated by ctpg is a recursive descent parser, so it does
> lexical analysis and parsing at a time.

Oh, I forgot this property of PEGs - integrated lexing and parsing. So 
no need for a separate lexer!

> And the type of input which it
> can accept is string, wstring, dstring and ForwardRange whose element
> type is char, wchar or dchar.

Great. I think we should actually define the notion of BufferedRange. 
I'll get to that topic later.

> So, dividing lexical analysis and parsing into two processes is
> difficult in ctpg.

Yes, sorry I forgot about that!

> Importantly, a parser generated by ctpg is statically typed as one of
> the examples, "parsing simple arithmetic expression" shows.
> Generally a parser generated by other tool and accepting tokens returns
> the abstract syntax tree, but it return the evaluated value in the example.
> In other words, it does lexical analysis, parsing and (type) converting
> at a time.
> If you want simply abstract syntax tree, it may be a little pain to use
> ctpg.
>
> That's all I'd like to say about ctpg here.

Why would it be difficult to integrate AST creation with parsing? I'm 
not sure I understand this. My understanding is that you should be able 
to add a couple of simple operators ("^" and "%" as described above) to 
inform AST creation, and you're done!


Thanks,

Andrei