On 02/26/2012 02:07 PM, Timon Gehr wrote:
> On 02/26/2012 01:55 PM, d coder wrote:
>>
>> I know. CTFE is flexible enough and implementing this would be quite
>> simple. However, if ctpg serves your needs well, just use that.
>>
>>
>> Thanks Timon
>>
>> You mean I do not need to use function style when using CTFE?
>> I will try parsing myself as you suggested. This approach would give
>> me a better handle.
>>
>> Regards
>> - Puneet
>>
>
> Almost the complete language is available in CTFE, therefore classes
> could be used to implement the parse tree representation. However, a
> limitation that does exist is that classes

objects, obviously

> that were created in CTFE
> cannot yet be stored in static variables or enums. How will the
> interface to your library look like?

(2012/02/26 20:56), d coder wrote:
>
>     Hisayuki Mima's ctpg is compile-time parser generater, and the
>     generated parser works in compile time!
>     https://github.com/youkei/ctpg
>
>     Kenji Hara
>
>
> Thanks Kenji
>
> This is very interesting. Also I think ctpg is being actively developed.
> I will try to figure out how to make use of it.
>
> Regards
> - Puneet

Hello, Puneet

I'm writing ctpg and really sorry about too little documentation of it.
I'm going to at least some sample codes which sketchily shows how to use ctpg within a few days.

By the way, ctpg is only parser (and converter) generator.
If you want to parse some expressions, you have to write DSL ,which is like PEG or BNF, in order to generate parsers.

If that helps, generated parser works in both compile time and run time.

Hisayuki Mima

> Almost the complete language is available in CTFE, therefore classes
could be used to implement the parse tree representation. However, a limitation that does exist is that classes that were created in CTFE cannot yet be stored in static variables or enums. How will the interface to your library look like?

I recently wrote a parsing expression grammar module in D, also to create grammars and parsers at compile-time and parse inputs at CT.

(PEG: http://en.wikipedia.org/wiki/Parsing_expression_grammar)

Usage is like this:

mixin Grammar(
      "JSON <- '{' ( Pair ( ',' Pair )* )? '}'"
    , "Pair <- String ':' Value"
    , "Value <- String / Number / JSON / Array / True / False / Null"
    , `True <- "true"`
(..., rest of JSON grammar)
);

enum result = JSON.parse(
`{ "Hello":42,
    "World!":
    {
        "a":[0,1,2,3]
    }
}`);

I deliberatly used classes to construct the parsers, for I wanted an extended class template example in a big tutorial on templates I'm writing. For now, the resulting grammars are space-insensitive, because I grew tired of always inserting Spaces parsers everywhere.

The parse tree is done with a tree struct. Since it holds strings (captures), it can be manipulated at CT to recreate new code. Any tree-walking function can collect the captures to build a D code string which can then be mixed in.

For exampe, last week, I created a template constraints parser, to then
test the resulting tree with template parameters. It tests the entire
constraint with passed parameters and, if it fails, it recursively tests
the sub-constraints to find ones that return false.
So, given "if (isIntegral!T && !(isFloatingPoint!(U) || is(U : W)))", it
will test "isIntegral!T" and so on.

All in all, it's quite fun and works OK, it just slows down compilation a bit. What was just an example in a tutorial is slowly becoming its own project. I think I'll put it on Github in a week or two.

Philippe

On 2/26/12 5:07 AM, kenji hara wrote:
> Hisayuki Mima's ctpg is compile-time parser generater, and the
> generated parser works in compile time!
> https://github.com/youkei/ctpg
>
> Kenji Hara

This seems to be great work, but a 30-seconds skim did not reveal to me how exactly it works. Are there some examples or more documentation?

Thanks,

Andrei

On 26.02.2012 15:07, kenji hara wrote:
> Hisayuki Mima's ctpg is compile-time parser generater, and the
> generated parser works in compile time!
> https://github.com/youkei/ctpg
>
> Kenji Hara
>

Nice! I'm curious as to which parsing method the generated parser does employ (it isn't immediately obvious ;) ).
Examples look good, but I don't seem to get how recursive sample
fails match(?) e.g. "aaaaa" given the grammar:
recursive -> A $
A -> a A a | a

I mean it's any odd-length sequence of a.

-- 
Dmitry Olshansky

(2012/02/27 19:42), Dmitry Olshansky wrote:
> On 26.02.2012 15:07, kenji hara wrote:
>> Hisayuki Mima's ctpg is compile-time parser generater, and the
>> generated parser works in compile time!
>> https://github.com/youkei/ctpg
>>
>> Kenji Hara
>>
>
> Nice! I'm curious as to which parsing method the generated parser does
> employ (it isn't immediately obvious ;) ).
> Examples look good, but I don't seem to get how recursive sample
> fails match(?) e.g. "aaaaa" given the grammar:
> recursive -> A $
> A -> a A a | a
>
> I mean it's any odd-length sequence of a.
>

Parsing method which the generated parser employs is Recursive Descent Parsing.
And the behavior of the parsers recursive and A is a little bit complicated.
The parser recursive matches the sequence of 'a' whose length is 2^n-1 such as 1, 3, 7 and 15.
Anyway, I'm going to write more documentation of ctpg within a few days.
I hope it'll help you.

Hisayuki Mima

On 27.02.2012 20:36, Hisayuki Mima wrote:
> (2012/02/27 19:42), Dmitry Olshansky wrote:
>> On 26.02.2012 15:07, kenji hara wrote:
>>> Hisayuki Mima's ctpg is compile-time parser generater, and the
>>> generated parser works in compile time!
>>> https://github.com/youkei/ctpg
>>>
>>> Kenji Hara
>>>
>>
>> Nice! I'm curious as to which parsing method the generated parser does
>> employ (it isn't immediately obvious ;) ).
>> Examples look good, but I don't seem to get how recursive sample
>> fails match(?) e.g. "aaaaa" given the grammar:
>> recursive -> A $
>> A -> a A a | a
>>
>> I mean it's any odd-length sequence of a.
>>
>
> Parsing method which the generated parser employs is Recursive Descent
> Parsing.

OK, does it check for Left recursive grammars?

> And the behavior of the parsers recursive and A is a little bit
> complicated.
> The parser recursive matches the sequence of 'a' whose length is 2^n-1
> such as 1, 3, 7 and 15.

Well I'm missing something about that BNF-grammar(right?) but undoubtedly:
recursive -> A $ -> a A a $ -> a a A a a $ - > a a a a a $
As for task of parsing only 2^n-1 sequences of "a" by CFG that's news for me.

> Anyway, I'm going to write more documentation of ctpg within a few days.
> I hope it'll help you.
>

Please do, the project with such potential should not stay undocumented.

-- 
Dmitry Olshansky

>
>
> Parsing method which the generated parser employs is Recursive Descent
> Parsing.
> And the behavior of the parsers recursive and A is a little bit
> complicated.
> The parser recursive matches the sequence of 'a' whose length is 2^n-1
> such as 1, 3, 7 and 15.
> Anyway, I'm going to write more documentation of ctpg within a few days.
> I hope it'll help you.
>
>
It sure will. Meanwhile, it would help if you can share some example code.

I surely do have an EBNF notation for the expressions I want to parse. Is it possible to parse any EBNF of arbitrary complexity using your parser generator?

Regards
- Puneet

(2012/02/28 2:24), d coder wrote:
> Is it possible to parse any EBNF of arbitrary complexity using your
> parser generator?

Yes, but some rewrites is required.

1) If your EBNF have (indirect) left recursion, you have to eliminate it because the DSL which ctpg uses to generate parser is based on PEG, parsing expression grammar.
For details, see: http://en.wikipedia.org/wiki/Parsing_expression_grammar .

2) As the example of parsing simple arithmetic expression shows, the parser generated by ctpg have type such as int and string.
EBNF doesn't have type system so you have to add appropriate type conversion into your EBNF.

Thanks,
Hisayuki Mima

(2012/02/28 2:22), Dmitry Olshansky wrote:
> OK, does it check for Left recursive grammars?

No, it doesn't.
So currently left recursive grammar causes infinite loop.
I know the way to deal with the left recursive grammar well which is using memoization, but memoization causes very bad performance.

> Well I'm missing something about that BNF-grammar(right?) but undoubtedly:
> recursive -> A $ -> a A a $ -> a a A a a $ - > a a a a a $
> As for task of parsing only 2^n-1 sequences of "a" by CFG that's news
> for me.

If it is BNF, the expansion you said (recursive -> A $ -> a A a $ -> a a A a a $ - > a a a a a $) is right.
But the DSL which ctpg uses to generate parser is based on PEG.
Unlike BNF's choice operator "|", PEG's choice operator "/" is ordered.
For details, see: http://en.wikipedia.org/wiki/Parsing_expression_grammar#Definition .

Thanks,
Hisayuki Mima