www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Lexer and parser generators using CTFE

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
I'm starting a new thread on this because I think the matter is of 
strategic importance.

We all felt for a long time that there's a lot of potential in CTFE, and 
potential applications have been discussed more than a few times, 
ranging from formatting strings parsed to DSLs and parser generators.

Such feats are now approaching fruition because a number of factors 
converge:

* Dmitry Olshansky's regex library (now in Phobos) generates efficient D 
code straight from regexen.

* The scope and quality of CTFE has improved enormously, making more 
advanced uses possible and even relatively easy (thanks Don!)

* Hisayuki Mima implemented a parser generator in only 3000 lines of 
code (sadly, no comments or documentation yet :o))

* With the occasion of that announcement we also find out Philippe 
Sigaud has already a competing design and implementation of a parser 
generator.

This is the kind of stuff I've had an eye on for the longest time. I'm 
saying it's of strategic importance because CTFE technology, though not 
new and already available with some languages, has unique powers when 
combined with other features of D. With CTFE we get to do things that 
are quite literally impossible to do in other languages.

We need to have a easy-to-use, complete, seamless, and efficient 
lexer-parser generator combo in Phobos, pronto. The lexer itself could 
use a character-level PEG or a classic automaton, and emit tokens for 
consumption by a parser generator. The two should work in perfect tandem 
(no need for glue code). At the end of the day, defining a complete 
lexer+parser combo for a language should be just a few lines longer than 
the textual representation of the grammar itself.

What do you all think? Let's get this project off the ground!


Thanks,

Andrei
Feb 27 2012
next sibling parent reply "CTFE-4-the-win" <CTFE 4the.win> writes:
On Tuesday, 28 February 2012 at 07:59:16 UTC, Andrei Alexandrescu
wrote:
 I'm starting a new thread on this because I think the matter is 
 of strategic importance.

 We all felt for a long time that there's a lot of potential in 
 CTFE, and potential applications have been discussed more than 
 a few times, ranging from formatting strings parsed to DSLs and 
 parser generators.

 Such feats are now approaching fruition because a number of 
 factors converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates 
 efficient D code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making 
 more advanced uses possible and even relatively easy (thanks 
 Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 
 lines of code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out 
 Philippe Sigaud has already a competing design and 
 implementation of a parser generator.

 This is the kind of stuff I've had an eye on for the longest 
 time. I'm saying it's of strategic importance because CTFE 
 technology, though not new and already available with some 
 languages, has unique powers when combined with other features 
 of D. With CTFE we get to do things that are quite literally 
 impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and 
 efficient lexer-parser generator combo in Phobos, pronto. The 
 lexer itself could use a character-level PEG or a classic 
 automaton, and emit tokens for consumption by a parser 
 generator. The two should work in perfect tandem (no need for 
 glue code). At the end of the day, defining a complete 
 lexer+parser combo for a language should be just a few lines 
 longer than the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Definitely, I applaud this initiative! I've long been of the opinion that CTFE parsing is D's killer-feature, which would allow me to "sneak" D into a "nameless above average size company". ;)
Feb 28 2012
next sibling parent bls <bizprac orange.fr> writes:
On 02/28/2012 12:36 AM, CTFE-4-the-win wrote:
 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect tandem
 (no need for glue code). At the end of the day, defining a complete
 lexer+parser combo for a language should be just a few lines longer than
 the textual representation of the grammar itself.

Are you aware of Philippe Sigaud's PEG work (may become part of his template book) Quote Philippe .. 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] } }`); End Quote No that bad :) , I think. Well, I am still a fan of EBNF based parser generators (recursive decent) but that's an other story. If I recall correctly BCS has created something working. ( BNF , so limited)
Feb 28 2012
prev sibling next sibling parent reply Piotr Szturmaj <bncrbme jadamspam.pl> writes:
Jonathan M Davis wrote:
 On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is
 impressive. However, I fail to see a killer-feature in
 generating a lexer-parser generator at compile-time instead of
 run-time.

 A run-time generator would benefit from not having to execute
 within the limited CTFE environment and would always be on-par in
 that respect. A compile time generator would internalize the
 generation and compilation of the result (with possible
 glue-code), simplifying the build process somewhat.

 What am I failing to pick up on?

Well, one cool thing would be that a compiler could effectively compile itself - or at least the lexer and parser would compile themselves. You wouldn't have to run a program to generate them. It could be self-contained.

CTFE code can be much slower than native one, and I would like to see some kind of compiler cache for such code.
Feb 28 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/1/12 1:54 AM, Marco Leise wrote:
 Am 29.02.2012, 02:30 Uhr, schrieb Piotr Szturmaj <bncrbme jadamspam.pl>:

 CTFE code can be much slower than native one, and I would like to see
 some kind of compiler cache for such code.

I second this. As a fan of clean optimizations this is one of the things I tossed around my head for a while. It could use a cache file or the compiler could be started as a daemon process keeping a memory cache. All code that is called through CTFE would go into the cache, indexed by the internal representation of the function body and parameters.

I think this is the kind of development that will be naturally motivated and pushed by serious CTFE applications pushing the boundary. I'm not very worried about it right now as about investigating CTFE potential and blockers. Andrei
Mar 01 2012
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 7:16 PM, Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is impressive.
 However, I fail to see a killer-feature in generating a lexer-parser
 generator at compile-time instead of run-time.

 A run-time generator would benefit from not having to execute within the
 limited CTFE environment and would always be on-par in that respect. A
 compile time generator would internalize the generation and compilation
 of the result (with possible glue-code), simplifying the build process
 somewhat.

 What am I failing to pick up on?

Barrier of entry and granularity of approach, I think. Currently if one wants to parse some simple grammar, there are options such as (a) do it by hand, (b) use boost::spirit, or (c) use lex/yacc. Parsing by hand has the obvious disadvantages. Using boost::spirit has a steep learning curve and tends to create very contorted grammar representations, full of representation noise, and scales very poorly. Using lex/yacc is hamfisted - there's an additional build step, generated files to deal with, and the related logistics, which make lex/yacc a viable choice only for "big" grammars. An efficient, integrated parser generator would lower the barrier of entry dramatically - if we play our cards right, even a sprintf specifier string could be parsed simpler and faster using an embedded grammar, instead of painfully writing the recognizer by hand. Parsing config files, XML, JSON, CSV, various custom file formats and many others - all would all be a few lines away. Ideally a user who has a basic understanding of grammars should have an easier time using a small grammar to parse simple custom formats, than writing the parsing code by hand. Andrei
Feb 29 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 3:45 AM, Philippe Sigaud wrote:
 mixin(Grammar!("Doc <- Node*"
 "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction,
 "OpeningTag <- '<' Identifier '>'", OpeningAction,
 "ClosingTag <-  `</` Identifier '>'", ClosingAction,
 "Text <- (!(OpeningTag / ClosingTag) _)+"));

That looks about right, but still has a fair amount of noise. I think the approach of putting the entire grammar in one string is best. Andrei
Feb 29 2012
next sibling parent deadalnix <deadalnix gmail.com> writes:
Le 29/02/2012 17:45, Andrei Alexandrescu a écrit :
 On 2/29/12 3:45 AM, Philippe Sigaud wrote:
 mixin(Grammar!("Doc <- Node*"
 "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction,
 "OpeningTag <- '<' Identifier '>'", OpeningAction,
 "ClosingTag <- `</` Identifier '>'", ClosingAction,
 "Text <- (!(OpeningTag / ClosingTag) _)+"));

That looks about right, but still has a fair amount of noise. I think the approach of putting the entire grammar in one string is best. Andrei

It make sense so an external file can be imported as string and processed at compile time.
Mar 01 2012
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2012-03-01 18:21, Philippe Sigaud wrote:
  > > But how to associate actions with a rule, in that case? I mean, some
  > > rules will have actions, some not.
  >
  > You could maybe just put D code in the grammar string, which gets
  > compiled as a string mixin by CTFE?

 I could, but one of my driving goals while beginning this project a
 month ao was to use the shiny new lambda syntax directly :)

 "rule1", o => o
 "rule2", o => o

 etc.

Maybe we can take some ideas from the CoffeeScript compiler (written in CoffeeScript) : Grammar: http://jashkenas.github.com/coffee-script/documentation/docs/grammar.html Lexer: http://jashkenas.github.com/coffee-script/documentation/docs/lexer.html -- /Jacob Carlborg
Mar 01 2012
prev sibling next sibling parent reply Hisayuki Mima <youxkei gmail.com> writes:
(2012/02/28 16:59), Andrei Alexandrescu wrote:
 I'm starting a new thread on this because I think the matter is of
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE, and
 potential applications have been discussed more than a few times,
 ranging from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient D
 code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of
 code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out Philippe
 Sigaud has already a competing design and implementation of a parser
 generator.

 This is the kind of stuff I've had an eye on for the longest time. I'm
 saying it's of strategic importance because CTFE technology, though not
 new and already available with some languages, has unique powers when
 combined with other features of D. With CTFE we get to do things that
 are quite literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect tandem
 (no need for glue code). At the end of the day, defining a complete
 lexer+parser combo for a language should be just a few lines longer than
 the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Hello Andrei, 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) 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. And the type of input which it can accept is string, wstring, dstring and ForwardRange whose element type is char, wchar or dchar. So, dividing lexical analysis and parsing into two processes is difficult in ctpg. 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. By the way, I wholeheartedly agree with Andrei's opinion. But currently, I think, CTFE is limited because of this issue: http://d.puremagic.com/issues/show_bug.cgi?id=6498 . Without dealing with this issue, We couldn't bring out the full potential of CTFE. Thanks, Hisayuki Mima
Feb 28 2012
next sibling parent reply Hisayuki Mima <youxkei gmail.com> writes:
(2012/02/28 23:58), Hisayuki Mima wrote:
 (2012/02/28 16:59), Andrei Alexandrescu wrote:
 I'm starting a new thread on this because I think the matter is of
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE, and
 potential applications have been discussed more than a few times,
 ranging from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient D
 code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of
 code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out Philippe
 Sigaud has already a competing design and implementation of a parser
 generator.

 This is the kind of stuff I've had an eye on for the longest time. I'm
 saying it's of strategic importance because CTFE technology, though not
 new and already available with some languages, has unique powers when
 combined with other features of D. With CTFE we get to do things that
 are quite literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect tandem
 (no need for glue code). At the end of the day, defining a complete
 lexer+parser combo for a language should be just a few lines longer than
 the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Hello Andrei, 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) 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. And the type of input which it can accept is string, wstring, dstring and ForwardRange whose element type is char, wchar or dchar. So, dividing lexical analysis and parsing into two processes is difficult in ctpg. 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. By the way, I wholeheartedly agree with Andrei's opinion. But currently, I think, CTFE is limited because of this issue: http://d.puremagic.com/issues/show_bug.cgi?id=6498 . Without dealing with this issue, We couldn't bring out the full potential of CTFE. Thanks, Hisayuki Mima

A minimum of documentation is now available here: https://github.com/youkei/ctpg/wiki/Home-en Hisayuki Mima
Feb 29 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 10:03 AM, Hisayuki Mima wrote:
 A minimum of documentation is now available here:
 https://github.com/youkei/ctpg/wiki/Home-en

Great start, you may want to aggressively add examples. Then people would love using ctpg and will write more documentation, tutorials etc. Andrei
Feb 29 2012
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Feb 29 2012
parent reply Hisayuki Mima <youxkei gmail.com> writes:
(2012/03/01 1:19), Andrei Alexandrescu wrote:
 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

Certainly, "built AST" option is very interesting. I don't know whether building AST is a common case or not because I'm unfamiliar with syntax analysis. But I'd like to complete ctpg as D version of boost::spirit::qi first. Currently, ctpg can be used probably like boost::spirit::qi. (Both do typed syntax analysis.) There are some points where ctpg is superior to boost::spirit::qi. For example, The source code written by using ctpg is simple because it is like PEG. In addition, I'm planning to improve error messages by making excellent use of #line and __LINE__. I'd like to write the library which is functionally same boost::spirit::qi and written in D style. Hence, I'd like to make implementing "built AST" option i.e. untyped syntax analysis a low priority. What is your idea? P.S. prefix operator "!" is same as postfix operator "%" which you said. The types which parsers on both sides of "/" operator have should be compatible. The type of "(" addExp ")" is Tuple!(string, int, string) and the type of intLit_p is int. They are not compatible. The type of !"(" addExp !")" is int. So the types of !"(" addExp !")" and intLit_p are compatible. Thanks, Hisayuki Mima
Mar 04 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/4/12 8:34 AM, Hisayuki Mima wrote:
 Certainly, "built AST" option is very interesting.
 I don't know whether building AST is a common case or not because I'm
 unfamiliar with syntax analysis.
 But I'd like to complete ctpg as D version of boost::spirit::qi first.
 Currently, ctpg can be used probably like boost::spirit::qi. (Both do
 typed syntax analysis.)
 There are some points where ctpg is superior to boost::spirit::qi. For
 example, The source code written by using ctpg is simple because it is
 like PEG.
 In addition, I'm planning to improve error messages by making excellent
 use of #line and __LINE__.
 I'd like to write the library which is functionally same
 boost::spirit::qi and written in D style.
 Hence, I'd like to make implementing "built AST" option i.e. untyped
 syntax analysis a low priority.
 What is your idea?

It's your project so you define what's fun to work on. Let me just say that I worked on a lot of parsing-related stuff, and most often projects that start as "this grammar is simple enough, let's just do processing during parsing" ultimately required a rewrite to do generate AST, process it, and then use it for computation. You can get away without an AST for the simplest grammars (e.g. printf etc.) but in that case you compete with hand-written code. I wouldn't think of parsing a serious grammar with more than a few productions without generating an AST. My intuition is that your work will best excel at those grammars. Andrei
Mar 04 2012
prev sibling next sibling parent "Ben Hanson" <Ben.Hanson tikit.com> writes:
On Sunday, 4 March 2012 at 21:00:00 UTC, Andrei Alexandrescu
wrote:
 You can get away without an AST for the simplest grammars (e.g. 
 printf etc.) but in that case you compete with hand-written 
 code. I wouldn't think of parsing a serious grammar with more 
 than a few productions without generating an AST. My intuition 
 is that your work will best excel at those grammars.

This chimes nicely with the comments made at the Going Native conference with regard to clang generating an AST and MSVC and GCC not. Herb Sutter referred to it as "AST envy" (as in he wished MSVC took the AST route). I only mention it as maybe not everyone here watched that vid. Andrei himself was at the conference of course! Regards, Ben
Mar 05 2012
prev sibling next sibling parent reply d coder <dlang.coder gmail.com> writes:
--f46d0401fc3fbb449f04c107fa0b
Content-Type: text/plain; charset=ISO-8859-1

 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.

Hello Youkei I am trying to use CTPG for compile time parsing for a DSL I am working on. I have tried the examples you created in the examples directory. I would like the parser to effect some side effects. For this purpose, I tried including the parser mixin into a class, but I got a strange error saying: Error: need 'this' to access member parse I have copied the code I am trying to compile at the end of the email. Let me know what I could be doing wrong here. Regards - Puneet import ctpg; import std.array: join; import std.conv: to; class Foo { int result; mixin(generateParsers(q{ int root = mulExp $; int mulExp = primary !"*" mulExp >> (lhs, rhs){ return lhs * rhs; } / primary; int primary = !"(" mulExp !")" / [0-9]+ >> join >> to!int; })); void frop() { result = parse!root("5*8"); } } void main(){ Foo foo = new Foo(); foo.frop(); } --f46d0401fc3fbb449f04c107fa0b Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br> Generally a parser generated by other tool and accepting tokens returns the= abstract syntax tree, but it return the evaluated value in the example.<br=

a time.<br> If you want simply abstract syntax tree, it may be a little pain to use ctp= g.<br></blockquote><div><br></div><div>=A0Hello Youkei</div><div><br></div>= <div>I am trying to use CTPG for compile time parsing for a DSL I am workin= g on. I have tried the examples you created in the examples directory.</div=

<div><br></div><div>I would like the parser to effect some side effects. Fo= r this purpose, I tried including the parser mixin into a class, but I got = a strange error saying:</div><div><br></div><div>Error: need &#39;this&#39;= to access member parse</div> <div><br></div><div>I have copied the code I am trying to compile at the en= d of the email. Let me know what I could be doing wrong here.</div><div><br=
</div><div>Regards</div><div>- Puneet</div><div><br></div><div><br></div>

<div><div>import ctpg;</div><div>import std.array: join;</div><div>import s= td.conv: to;</div><div><br></div><div>class Foo</div><div>{</div><div>=A0 i= nt result;</div><div>=A0 mixin(generateParsers(q{</div><div>=A0 =A0 =A0 =A0= int root =3D mulExp $;</div> <div><br></div><div>=A0 =A0 =A0 =A0 int mulExp =3D</div><div>=A0 =A0 =A0 = =A0 =A0 primary !&quot;*&quot; mulExp &gt;&gt; (lhs, rhs){ return lhs * rhs= ; }</div><div>=A0 =A0 =A0 =A0 / primary;</div><div><br></div><div>=A0 =A0 = =A0 =A0 int primary =3D !&quot;(&quot; mulExp !&quot;)&quot; / [0-9]+ &gt;&= gt; join &gt;&gt; to!int;</div> <div>=A0 =A0 =A0 }));</div><div><br></div><div>=A0 void frop() {</div><div>= =A0 =A0 result =3D parse!root(&quot;5*8&quot;);</div><div>=A0 }</div><div>}= </div><div><br></div><div><br></div><div>void main(){</div><div>=A0 Foo foo= =3D new Foo();</div> <div>=A0 foo.frop();</div><div>}</div></div><div><br></div></div> --f46d0401fc3fbb449f04c107fa0b--
May 27 2012
parent Hisayuki Mima <youxkei gmail.com> writes:
(2012年05月28日 02:31), d coder wrote:
     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.


   Hello Youkei

 I am trying to use CTPG for compile time parsing for a DSL I am working
 on. I have tried the examples you created in the examples directory.

 I would like the parser to effect some side effects. For this purpose, I
 tried including the parser mixin into a class, but I got a strange error
 saying:

 Error: need 'this' to access member parse

 I have copied the code I am trying to compile at the end of the email.
 Let me know what I could be doing wrong here.

 Regards
 - Puneet


 import ctpg;
 import std.array: join;
 import std.conv: to;

 class Foo
 {
    int result;
    mixin(generateParsers(q{
          int root = mulExp $;

          int mulExp =
            primary !"*" mulExp >> (lhs, rhs){ return lhs * rhs; }
          / primary;

          int primary = !"(" mulExp !")" / [0-9]+ >> join >> to!int;
        }));

    void frop() {
      result = parse!root("5*8");
    }
 }


 void main(){
    Foo foo = new Foo();
    foo.frop();
 }

Hello Puneet, Thank you for your report. I fixed it. Now CTPG creates a static function as a parser. But I'm afraid this fix doesn't help you because I don't understand what a side effect you said is. Can you show me some examples which include the side effect? Thanks, Hisayuki Mima
May 31 2012
prev sibling parent d coder <dlang.coder gmail.com> writes:
--e0cb4efe2a285041ff04c1084a72
Content-Type: text/plain; charset=ISO-8859-1

 I would like the parser to effect some side effects. For this purpose, I
 tried including the parser mixin into a class, but I got a strange error
 saying:

 Error: need 'this' to access member parse

the class has not been instantiated yet. I will have to think of other solutions. Basically, I am trying to use the parser to create functions that I can use at run time. But I wanted to create two functions from the same parser. I have succeeded with creating one function. I do not want to create two separate parsers because each of these parsers would add to memory footprint of the compiler. Any ideas? Maybe I could use tuples here? Regards - Puneet --e0cb4efe2a285041ff04c1084a72 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"m= argin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D= "gmail_quote"> <div><br></div><div>I would like the parser to effect some side effects. Fo= r this purpose, I tried including the parser mixin into a class, but I got = a strange error saying:</div><div><br></div><div>Error: need &#39;this&#39;= to access member parse</div> <div><br></div></div></blockquote><div><br></div><div>Ok. I see my folly. A= t compile time, there would not be any &quot;this&quot; since the class has= not been instantiated yet.</div><div><br></div><div>I will have to think o= f other solutions. Basically, I am trying to use the parser to create funct= ions that I can use at run time. But I wanted to create two functions from = the same parser. I have succeeded with creating one function. I do not want= to create two separate parsers because each of these parsers would add to = memory footprint of the compiler.</div> <div><br></div><div>Any ideas? Maybe I could use tuples here?</div><div><br=
</div><div>Regards</div><div>- Puneet</div><div>=A0</div></div>

--e0cb4efe2a285041ff04c1084a72--
May 27 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 28, 2012 at 01:59:21AM -0600, Andrei Alexandrescu wrote:
 I'm starting a new thread on this because I think the matter is of
 strategic importance.

+1.
 We all felt for a long time that there's a lot of potential in CTFE,
 and potential applications have been discussed more than a few times,
 ranging from formatting strings parsed to DSLs and parser
 generators.

CTFE is one of the big features that attracted me to D. [...]
 This is the kind of stuff I've had an eye on for the longest time.
 I'm saying it's of strategic importance because CTFE technology,
 though not new and already available with some languages, has unique
 powers when combined with other features of D. With CTFE we get to do
 things that are quite literally impossible to do in other languages.

For example?
 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect
 tandem (no need for glue code). At the end of the day, defining a
 complete lexer+parser combo for a language should be just a few lines
 longer than the textual representation of the grammar itself.

Definitely agree. I frequently work with code that requires some amount of lexing/parsing; having something like this in Phobos would be absolutely awesome.
 What do you all think? Let's get this project off the ground!

+1. On that note, I'd like to mention that CTFE currently has some parts that need more work: (1) We need compile-time alternatives to the functions in std.math so that functions that are currently only implemented in asm can be used in CTFE. (2) It should be possible to generate AA literals from CTFE and use them to initialize things like parsing/lexing lookup tables, etc.. While this in itself is not a major critical issue, it would make D look bad if we tout D's CTFE capabilities yet at the same time AA's have to be created by static this() at runtime. T -- Which is worse: ignorance or apathy? Who knows? Who cares? -- Erich Schubert
Feb 28 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 9:57 AM, H. S. Teoh wrote:
 On Tue, Feb 28, 2012 at 01:59:21AM -0600, Andrei Alexandrescu wrote:
 This is the kind of stuff I've had an eye on for the longest time.
 I'm saying it's of strategic importance because CTFE technology,
 though not new and already available with some languages, has unique
 powers when combined with other features of D. With CTFE we get to do
 things that are quite literally impossible to do in other languages.

For example?

For example integrated lexer and parser generators! Andrei
Feb 29 2012
parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jiljf7$18em$1 digitalmars.com...
 On 2/28/12 9:57 AM, H. S. Teoh wrote:
 On Tue, Feb 28, 2012 at 01:59:21AM -0600, Andrei Alexandrescu wrote:
 This is the kind of stuff I've had an eye on for the longest time.
 I'm saying it's of strategic importance because CTFE technology,
 though not new and already available with some languages, has unique
 powers when combined with other features of D. With CTFE we get to do
 things that are quite literally impossible to do in other languages.

For example?

For example integrated lexer and parser generators!

...With statically-checked symbol names that can include arbitrary characters: Sym!"+" Sym!"{" Sym!"<Foo>" etc...
Feb 29 2012
prev sibling next sibling parent reply "mist" <none none.none> writes:
Something similar to Boost::Spirit2 but with sane syntax and 
better debugging would have been awesome.
Feb 28 2012
next sibling parent reply bcs <bcs example.com> writes:
On 02/28/2012 08:23 AM, mist wrote:
 Something similar to Boost::Spirit2 but with sane syntax and better
 debugging would have been awesome.

How about not having to encode the syntax as arithmetic expressions? D can do string parsing of eBNF at compile time if you want that.
Feb 28 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 12:07 AM, bcs wrote:
 On 02/28/2012 08:23 AM, mist wrote:
 Something similar to Boost::Spirit2 but with sane syntax and better
 debugging would have been awesome.

How about not having to encode the syntax as arithmetic expressions? D can do string parsing of eBNF at compile time if you want that.

I think that's what he meant by "sane syntax". Andrei
Feb 29 2012
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 10:23 AM, mist wrote:
 Something similar to Boost::Spirit2 but with sane syntax and better
 debugging would have been awesome.

Exactly. Boost::Spirit2 is a perfect illustration of a dancing bear - using inadequate technology for a specific purpose. Andrei
Feb 29 2012
prev sibling next sibling parent reply "Martin Nowak" <dawg dawgfoto.de> writes:
On Tue, 28 Feb 2012 08:59:21 +0100, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 I'm starting a new thread on this because I think the matter is of  
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE, and  
 potential applications have been discussed more than a few times,  
 ranging from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors  
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient D  
 code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more  
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of  
 code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out Philippe  
 Sigaud has already a competing design and implementation of a parser  
 generator.

 This is the kind of stuff I've had an eye on for the longest time. I'm  
 saying it's of strategic importance because CTFE technology, though not  
 new and already available with some languages, has unique powers when  
 combined with other features of D. With CTFE we get to do things that  
 are quite literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient  
 lexer-parser generator combo in Phobos, pronto. The lexer itself could  
 use a character-level PEG or a classic automaton, and emit tokens for  
 consumption by a parser generator. The two should work in perfect tandem  
 (no need for glue code). At the end of the day, defining a complete  
 lexer+parser combo for a language should be just a few lines longer than  
 the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

I wrote a generic lexer generator some time ago. It already let to some compiler O(N^2) optimizations, because the token declarations sneak into the mangling :(. I also finally added a workaround for a remaining CTFE bug (#6815). https://gist.github.com/1255439 - lexer generator https://gist.github.com/1262321 - complete and fast D lexer I've ditched an attempt to write a parser combinator. It was based on expression templates and ended up at spirit craziness. <PERSONAL OPINION The hassle of providing good error messages and synthesizing parse results in a generic parser outweigh the benefit of a declarative grammar. /PERSONAL OPINION> A lot becomes feasible from the CTFE perspective, despite some bugfixes I only miss exp and log currently. I do not agree that it's the right moment to write a parser though. It hits the first of phobos two biggest shortcomings, the lack of a good I/O system and the missing Allocators. Any parser written now will either risk to not play nice with ranges or has to come up with it's own buffering again.
Feb 28 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 28.02.2012 22:46, Martin Nowak wrote:
 On Tue, 28 Feb 2012 08:59:21 +0100, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 I'm starting a new thread on this because I think the matter is of
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE,
 and potential applications have been discussed more than a few times,
 ranging from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient
 D code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of
 code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out Philippe
 Sigaud has already a competing design and implementation of a parser
 generator.

 This is the kind of stuff I've had an eye on for the longest time. I'm
 saying it's of strategic importance because CTFE technology, though
 not new and already available with some languages, has unique powers
 when combined with other features of D. With CTFE we get to do things
 that are quite literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect
 tandem (no need for glue code). At the end of the day, defining a
 complete lexer+parser combo for a language should be just a few lines
 longer than the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


To be truly successful it should have some distinct properties like: - being faster or identical to handwritten stuff we already have (like e.g. std.json ), reminds us of recent INI parser proposal, should be an easy pick for general parser. - be flexible, the result need not be a predefined AST tree nodes, Hisayuki Mima's parser shows some nice movement in this direction - have reasonable compile times and memory consumption (though it will only improve over time) Recalling EBNF parser idea that I run with before finally being dragged down by real life. Roughly I thought to follow hybrid LL(*) aproach, while I had a solid plan on doing DFA for lexer and parser lookahead, the other things were more or less floating.
 Thanks,

 Andrei

I wrote a generic lexer generator some time ago. It already let to some compiler O(N^2) optimizations, because the token declarations sneak into the mangling :(. I also finally added a workaround for a remaining CTFE bug (#6815). https://gist.github.com/1255439 - lexer generator

Cool stuff.
 https://gist.github.com/1262321 - complete and fast D lexer

 I've ditched an attempt to write a parser combinator. It was based on
 expression templates and ended up at spirit craziness.

 <PERSONAL OPINION
 The hassle of providing good error messages and synthesizing parse results
 in a generic parser outweigh the benefit of a declarative grammar.
 /PERSONAL OPINION>

Error reporting is the weak spot, still no good ideas on solving that.
 A lot becomes feasible from the CTFE perspective,
 despite some bugfixes I only miss exp and log currently.

Reminds me that I have to dig up a wonderful CTFE bug in std.regex that's being somehow worked around by duping arrays since August.
 I do not agree that it's the right moment to write a parser though.
 It hits the first of phobos two biggest shortcomings, the lack of a good
 I/O
 system and the missing Allocators.
 Any parser written now will either risk to not play nice with ranges
 or has to come up with it's own buffering again.

All good points. There is prototype of interactive regex matcher that works directly on stream (buried in std.regex), it even passed dry-run unittests back then. Though I had to postpone till I/O is sorted out. I really loved Steven's design with it's easy access to buffer and well thought out primitives, hope it will come about sometime soon. -- Dmitry Olshansky
Feb 28 2012
next sibling parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29.02.2012 0:19, H. S. Teoh wrote:
 On Tue, Feb 28, 2012 at 11:52:52PM +0400, Dmitry Olshansky wrote:
 On 28.02.2012 22:46, Martin Nowak wrote:
 On Tue, 28 Feb 2012 08:59:21 +0100, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org>  wrote:


 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself
 could use a character-level PEG or a classic automaton, and emit
 tokens for consumption by a parser generator. The two should work in
 perfect tandem (no need for glue code). At the end of the day,
 defining a complete lexer+parser combo for a language should be just
 a few lines longer than the textual representation of the grammar
 itself.



 To be truly successful it should have some distinct properties like:
 - being faster or identical to handwritten stuff we already have
 (like e.g. std.json ), reminds us of recent INI parser proposal,
 should be an easy pick for general parser.

We probably have to use string mixins to achieve this. OTOH, a generic parser generator is unlikely to be able to handle special case optimizations such as operator-precedence parsers (http://en.wikipedia.org/wiki/Operator-precedence_parser), because operator precedence is only implied by grammar rules, and to optimize for this case requires explicitly specifying each operator's precedence. There is some price to be paid for generality, unfortunately.

Well I see no problem in defining a separate OperatorGrammar constructor, that will take base Unit production and a bunch of operators with arity, plus brackets with their priority is plenty. Semantic then actions are trivially defined for each of operators respectively. Someway of stacking grammars is bonus points for the project. As Andrei started with lexer+parser, I see no problem with it being lexer+parser(+parser)*.
 - be flexible, the result need not be a predefined AST tree nodes,
 Hisayuki Mima's parser shows some nice movement in this direction

In my mind, D's delegates are ideal for this sort of thing. Each grammar rule will have an associated callback. We can provide default callbacks that generates AST nodes, but the user can override them with his own delegates to do whatever they want (evaluate expressions/commands on the fly, build only AST subtrees of interest, etc.).

Yup delegates and mixins are the tools. More over lambdas shine here, less clutter + type deduction.
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

This will be good motivation to improve dmd's CTFE implementation. ;-) [...]
 Error reporting is the weak spot, still no good ideas on solving that.

This is not specific to D, though, right?

Such a framework relying on mixins is bound to produce awful error messages at compile-time, unless explicitly stuffed up to watterline with some kind of static assert(__traits(compiles,...),"Error x + info");
 [...]
 I do not agree that it's the right moment to write a parser though.
 It hits the first of phobos two biggest shortcomings, the lack of a
 good I/O system and the missing Allocators.  Any parser written now
 will either risk to not play nice with ranges or has to come up with
 it's own buffering again.

All good points. There is prototype of interactive regex matcher that works directly on stream (buried in std.regex), it even passed dry-run unittests back then. Though I had to postpone till I/O is sorted out. I really loved Steven's design with it's easy access to buffer and well thought out primitives, hope it will come about sometime soon.

Are you talking about std.io? I glanced over that code briefly recently; it looks very promising. Hope it will make it into Phobos soon. We *need* to integrate streams, ranges, and the stdio writeln, etc., stuff. The current situation to an outsider looks quite bad (streams not compatible with stdio, no easy way to substitute string buffer for files, etc.).

Aye, that's it. Not to mention DIP9, though that's another topic in itself.
 We also need automatic UTF encoding detection for all input
 streams/files/ranges/whatever. Including mismatching endianness (i.e.
 auto byte-swapping).  In a recent personal project to write a D lexer
 (as an exercise to help me learn D better), I ended up having to roll my
 own input stream abstraction in order to handle automatic encoding
 detection. Which is quite poorly written, I've to admit. Something like
 this needs to be standardized in Phobos with a well-written
 implementation.


 T

-- Dmitry Olshansky
Feb 29 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 3:48 AM, Dmitry Olshansky wrote:
 Someway of stacking grammars is bonus points for the project. As Andrei
 started with lexer+parser, I see no problem with it being
 lexer+parser(+parser)*.

What does stacking grammars mean? Anyhow, one thing that would become important is tree walkers - e.g. you have the tree and you define code for evaluating it etc.
 Such a framework relying on mixins is bound to produce awful error
 messages at compile-time, unless explicitly stuffed up to watterline
 with some kind of static assert(__traits(compiles,...),"Error x + info");

We need to figure out ways to make that simpler. Andrei
Feb 29 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29.02.2012 20:47, Andrei Alexandrescu wrote:
 On 2/29/12 3:48 AM, Dmitry Olshansky wrote:
 Someway of stacking grammars is bonus points for the project. As Andrei
 started with lexer+parser, I see no problem with it being
 lexer+parser(+parser)*.

What does stacking grammars mean?

In general it should be read as using one parser as lexer for another parser. But there is some nice ways to integrate another parser within recursive descent parser. Let's assume simple recursive descent parser that uses operator precedence grammar. Suppose we have the main grammar: Declaration = Type Identifier; Statement = 'if' '(' Expr ')' | Expr Type = int | float | ... Where Expr is connected to the second grammar expressed as ... Ok, let's sketch it, skipping semantic actions: operatorGrammar!q{ Expr Unit: Constant | Identifier //assume we have lexer Operators: Not, !, prefix, 4 UnMinus, -, prefix, 4 Mul, *, binary, 3 Mul, /, binary, 3 Plus, +, binary, 2 BiMinus, -, binary, 2 Index, [], brace-like postfix Braces, (), brace-like }; Effectively operator grammar for expressions parses "token" Expr. It's easy in recursive descent because it can just try to call this parser, then try the other alternative if it fails. I'm not sure this stacking does add that much, but it's something to keep in mind.
 Anyhow, one thing that would become important is tree walkers - e.g. you
 have the tree and you define code for evaluating it etc.

Yes, it's a must have if AST is generated generically via annotations.
 Such a framework relying on mixins is bound to produce awful error
 messages at compile-time, unless explicitly stuffed up to watterline
 with some kind of static assert(__traits(compiles,...),"Error x + info");

We need to figure out ways to make that simpler. Andrei

-- Dmitry Olshansky
Feb 29 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
 To be truly successful it should have some distinct properties like:
 - being faster or identical to handwritten stuff we already have (like
 e.g. std.json ), reminds us of recent INI parser proposal, should be an
 easy pick for general parser.

Yes.
 - be flexible, the result need not be a predefined AST tree nodes,
 Hisayuki Mima's parser shows some nice movement in this direction

Yes. But AST creation should be supported without any custom code.
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

Yes. I guess PEGs have problems there.
 Recalling EBNF parser idea that I run with before finally being dragged
 down by real life. Roughly I thought to follow hybrid LL(*) aproach,
 while I had a solid plan on doing DFA for lexer and parser lookahead,
 the other things were more or less floating.

Well, maybe you could integrate that within your up-and-coming research. Grammars have been considered a solved problem every five years since 1970, and there's always new work coming :o).
 There is prototype of interactive regex matcher that
 works directly on stream (buried in std.regex), it even passed dry-run
 unittests back then. Though I had to postpone till I/O is sorted out. I
 really loved Steven's design with it's easy access to buffer and well
 thought out primitives, hope it will come about sometime soon.

An interactive regex would be a dream come true to me... Andrei
Feb 29 2012
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jiljsg$193s$1 digitalmars.com...
 On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

Yes. I guess PEGs have problems there.

Probably LR, too, unless you build the state tables in a separate prior build step.
 There is prototype of interactive regex matcher that
 works directly on stream (buried in std.regex), it even passed dry-run
 unittests back then. Though I had to postpone till I/O is sorted out. I
 really loved Steven's design with it's easy access to buffer and well
 thought out primitives, hope it will come about sometime soon.

An interactive regex would be a dream come true to me...

One thing I've been wanting to see in a lexer's regex would be a way to match things like D's nested comments or: qEOS fancy string blah blah EOS Support for either one would probably render it "not *technically* a regex" but it should be entirely possible by just adding some extra data/processing to the states.
Feb 29 2012
next sibling parent "Nick Sabalausky" <a a.a> writes:
"Nick Sabalausky" <a a.a> wrote in message 
news:jilmhr$1dul$1 digitalmars.com...
 "Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
 news:jiljsg$193s$1 digitalmars.com...
 On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

Yes. I guess PEGs have problems there.

Probably LR, too, unless you build the state tables in a separate prior build step.

Erm, I mean LALR specifically.
Feb 29 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 11:15 AM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:jiljsg$193s$1 digitalmars.com...
 On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

Yes. I guess PEGs have problems there.

Probably LR, too, unless you build the state tables in a separate prior build step.

It's been a while since I read about PEGs (the packrat parser paper), but think it's a more fundamental issue with PEGs because they need to memoize several possible parses of the input. Andrei
Feb 29 2012
parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jilnjg$1eu9$3 digitalmars.com...
 On 2/29/12 11:15 AM, Nick Sabalausky wrote:
 "Andrei Alexandrescu"<SeeWebsiteForEmail erdani.org>  wrote in message
 news:jiljsg$193s$1 digitalmars.com...
 On 2/28/12 1:52 PM, Dmitry Olshansky wrote:
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

Yes. I guess PEGs have problems there.

Probably LR, too, unless you build the state tables in a separate prior build step.

It's been a while since I read about PEGs (the packrat parser paper), but think it's a more fundamental issue with PEGs because they need to memoize several possible parses of the input.

I don't know much about packrat parsers, but what I meant is that generating LALR tables (which are then used by an LALR parser) can be very computationally expensive: For simple grammars, it's trivial, but for more complex "typical programming langauge" grammars, it can easily take upwards of quite a few minutes when *not* done in CTFE (at least on my underpowered machine). Although maybe my implementation and GOLD's implementation both just have some additional hidden scaling issue that isn't inherent to the algorithms? Actually using an *already*-generated LALR table (which only needs to be generated once per grammar, not once per input) to parse doesn't have major inherent efficiency issues compared to other parsing algorithms, AFAIK.
Feb 29 2012
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
On 29.02.2012 20:31, Andrei Alexandrescu wrote:
 Recalling EBNF parser idea that I run with before finally being dragged
 down by real life. Roughly I thought to follow hybrid LL(*) aproach,
 while I had a solid plan on doing DFA for lexer and parser lookahead,
 the other things were more or less floating.

Well, maybe you could integrate that within your up-and-coming research. Grammars have been considered a solved problem every five years since 1970, and there's always new work coming :o).

It might involve parsing and grammars, unless academia folk seduce me with their ideas of optimization for highly parallel architectures :).
 There is prototype of interactive regex matcher that
 works directly on stream (buried in std.regex), it even passed dry-run
 unittests back then. Though I had to postpone till I/O is sorted out. I
 really loved Steven's design with it's easy access to buffer and well
 thought out primitives, hope it will come about sometime soon.

An interactive regex would be a dream come true to me...

Where you've been? ;) I mean during GSOC we've spent days with Fawzi talking about shoehorning regex matcher to work on buffered streams. He actually did that prototype, I was mostly reviewing/fixing the source to make sure it fits. Recalling the inner works it was even expected to optionally do NFC normalization on the fly (wow, now that was ambitious) and all that without copying stuff around 99% of the time. -- Dmitry Olshansky
Feb 29 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 28, 2012 at 07:46:04PM +0100, Martin Nowak wrote:
[...]
 I wrote a generic lexer generator some time ago.
 It already let to some compiler O(N^2) optimizations, because the token
 declarations sneak into the mangling :(.
 I also finally added a workaround for a remaining CTFE bug (#6815).
 
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Cool! I'll have to take a look at this sometime. [...]
 <PERSONAL OPINION
 The hassle of providing good error messages and synthesizing parse results
 in a generic parser outweigh the benefit of a declarative grammar.
 /PERSONAL OPINION>

But things like lex/yacc have been useful throughout the years. With D's delegates, lexer/parser action rules should be even cleaner, no?
 A lot becomes feasible from the CTFE perspective, despite some
 bugfixes I only miss exp and log currently.

All of std.math should have CTFE versions so that we can perform complex calculations at compile-time (e.g., create table of scaled sin/cos values for use in high-performance 3D apps -- no need to waste time to generate these tables at startup time).
 I do not agree that it's the right moment to write a parser though.
 It hits the first of phobos two biggest shortcomings, the lack of a
 good I/O system and the missing Allocators.  Any parser written now
 will either risk to not play nice with ranges or has to come up with
 it's own buffering again.

OTOH, perhaps once we start writing a lexer/parser generator, that will force us to fix the I/O and allocator system. Without a good project to motivate us to fix these tedious issues, it seems that we just lose inspiration to do it after a while. T -- The computer is only a tool. Unfortunately, so is the user. -- Armaphine, K5
Feb 28 2012
parent deadalnix <deadalnix gmail.com> writes:
Le 28/02/2012 21:02, H. S. Teoh a crit :
 OTOH, perhaps once we start writing a lexer/parser generator, that will
 force us to fix the I/O and allocator system. Without a good project to
 motivate us to fix these tedious issues, it seems that we just lose
 inspiration to do it after a while.

std.conainer is already a good candidate for allocators. Back to the topic, this is a great idea, but isn't it building on weak bases ? We still have issue with const correctness, or postblit, and on lib side, we lack allocators, error handling is poor, containers are poor, etc . . .
Feb 28 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 28, 2012 at 11:52:52PM +0400, Dmitry Olshansky wrote:
 On 28.02.2012 22:46, Martin Nowak wrote:
On Tue, 28 Feb 2012 08:59:21 +0100, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:


We need to have a easy-to-use, complete, seamless, and efficient
lexer-parser generator combo in Phobos, pronto. The lexer itself
could use a character-level PEG or a classic automaton, and emit
tokens for consumption by a parser generator. The two should work in
perfect tandem (no need for glue code). At the end of the day,
defining a complete lexer+parser combo for a language should be just
a few lines longer than the textual representation of the grammar
itself.



 To be truly successful it should have some distinct properties like:
 - being faster or identical to handwritten stuff we already have
 (like e.g. std.json ), reminds us of recent INI parser proposal,
 should be an easy pick for general parser.

We probably have to use string mixins to achieve this. OTOH, a generic parser generator is unlikely to be able to handle special case optimizations such as operator-precedence parsers (http://en.wikipedia.org/wiki/Operator-precedence_parser), because operator precedence is only implied by grammar rules, and to optimize for this case requires explicitly specifying each operator's precedence. There is some price to be paid for generality, unfortunately.
 - be flexible, the result need not be a predefined AST tree nodes,
 Hisayuki Mima's parser shows some nice movement in this direction

In my mind, D's delegates are ideal for this sort of thing. Each grammar rule will have an associated callback. We can provide default callbacks that generates AST nodes, but the user can override them with his own delegates to do whatever they want (evaluate expressions/commands on the fly, build only AST subtrees of interest, etc.).
 - have reasonable compile times and memory consumption (though it will
 only improve over time)

This will be good motivation to improve dmd's CTFE implementation. ;-) [...]
 Error reporting is the weak spot, still no good ideas on solving that.

This is not specific to D, though, right? [...]
I do not agree that it's the right moment to write a parser though.
It hits the first of phobos two biggest shortcomings, the lack of a
good I/O system and the missing Allocators.  Any parser written now
will either risk to not play nice with ranges or has to come up with
it's own buffering again.

All good points. There is prototype of interactive regex matcher that works directly on stream (buried in std.regex), it even passed dry-run unittests back then. Though I had to postpone till I/O is sorted out. I really loved Steven's design with it's easy access to buffer and well thought out primitives, hope it will come about sometime soon.

Are you talking about std.io? I glanced over that code briefly recently; it looks very promising. Hope it will make it into Phobos soon. We *need* to integrate streams, ranges, and the stdio writeln, etc., stuff. The current situation to an outsider looks quite bad (streams not compatible with stdio, no easy way to substitute string buffer for files, etc.). We also need automatic UTF encoding detection for all input streams/files/ranges/whatever. Including mismatching endianness (i.e. auto byte-swapping). In a recent personal project to write a D lexer (as an exercise to help me learn D better), I ended up having to roll my own input stream abstraction in order to handle automatic encoding detection. Which is quite poorly written, I've to admit. Something like this needs to be standardized in Phobos with a well-written implementation. T -- "You know, maybe we don't *need* enemies." "Yeah, best friends are about all I can take." -- Calvin & Hobbes
Feb 28 2012
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 28, 2012 at 10:03:42PM +0100, Martin Nowak wrote:
[...]
 I won't deny that the combination of CTFE text processing and static
 introspection could improve on this. It could be made more feasible by
 some conventions, e.g. parse result always uses structs or classes and
 built-in arrays.

Excellent idea, I like this.
 class Module
 {
     this(Declaration[]);
 }
 
 class StructDeclaration : Declaration
 {
     enum _enbf = "struct $1=Identifier { $2=Declaration* }";
 
     this(Identifier, Declaration[]);
 }
 
 ...
 
 Parser!(Module, StructDeclaration, ...) parser;
 Module m = parser.parse(read("file.d"));

I like this! Definitely an improvement over yacc syntax. T -- Unix was not designed to stop people from doing stupid things, because that would also stop them from doing clever things. -- Doug Gwyn
Feb 28 2012
parent reply "Nick Sabalausky" <a a.a> writes:
"H. S. Teoh" <hsteoh quickfur.ath.cx> wrote in message 
news:mailman.215.1330472867.24984.digitalmars-d puremagic.com...
 On Tue, Feb 28, 2012 at 10:03:42PM +0100, Martin Nowak wrote:
 [...]
 I won't deny that the combination of CTFE text processing and static
 introspection could improve on this. It could be made more feasible by
 some conventions, e.g. parse result always uses structs or classes and
 built-in arrays.

Excellent idea, I like this.
 class Module
 {
     this(Declaration[]);
 }

 class StructDeclaration : Declaration
 {
     enum _enbf = "struct $1=Identifier { $2=Declaration* }";

     this(Identifier, Declaration[]);
 }

 ...

 Parser!(Module, StructDeclaration, ...) parser;
 Module m = parser.parse(read("file.d"));

I like this! Definitely an improvement over yacc syntax.

In Goldie, I've taken an inverted approach, which IMHO is easier to use: The types are automatically generated from the grammar, not the other way around. So applying that approach to the above code, it'd be more like this: mixin genGrammar!("myGrammar", ` Identifier = [a-zA-Z_][a-zA-Z_0-9]* Module = Declaration+ Declaration = StructDeclaration StructDeclaration = 'struct' Identifier '{' Declaration* '}' `); Which generates these classes: Parser!"myGrammar" Symbol!("myGrammar.Identifier") Symbol!("myGrammar.Module") Symbol!("myGrammar.Declaration") Symbol!("myGrammar.StructDeclaration") and/or these: Parser_myGrammar Symbol_myGrammar!"Identifier" Symbol_myGrammar!"Module" Symbol_myGrammar!"Declaration" Symbol_myGrammar!"StructDeclaration" would could then be aliased by the user however they wanted: alias Symbol_myGrammar MySym; And there can still be hooks (delegates, subclassing, whatever) to add customized behavior/functionality.
Feb 28 2012
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Nick Sabalausky" <a a.a> wrote in message 
news:jikcca$1vq7$1 digitalmars.com...
 "H. S. Teoh" <hsteoh quickfur.ath.cx> wrote in message 
 news:mailman.215.1330472867.24984.digitalmars-d puremagic.com...
 On Tue, Feb 28, 2012 at 10:03:42PM +0100, Martin Nowak wrote:
 [...]
 I won't deny that the combination of CTFE text processing and static
 introspection could improve on this. It could be made more feasible by
 some conventions, e.g. parse result always uses structs or classes and
 built-in arrays.

Excellent idea, I like this.
 class Module
 {
     this(Declaration[]);
 }

 class StructDeclaration : Declaration
 {
     enum _enbf = "struct $1=Identifier { $2=Declaration* }";

     this(Identifier, Declaration[]);
 }

 ...

 Parser!(Module, StructDeclaration, ...) parser;
 Module m = parser.parse(read("file.d"));

I like this! Definitely an improvement over yacc syntax.

In Goldie, I've taken an inverted approach, which IMHO is easier to use: The types are automatically generated from the grammar, not the other way around. So applying that approach to the above code, it'd be more like this: mixin genGrammar!("myGrammar", ` Identifier = [a-zA-Z_][a-zA-Z_0-9]* Module = Declaration+ Declaration = StructDeclaration StructDeclaration = 'struct' Identifier '{' Declaration* '}' `); Which generates these classes: Parser!"myGrammar" Symbol!("myGrammar.Identifier") Symbol!("myGrammar.Module") Symbol!("myGrammar.Declaration") Symbol!("myGrammar.StructDeclaration") and/or these: Parser_myGrammar Symbol_myGrammar!"Identifier" Symbol_myGrammar!"Module" Symbol_myGrammar!"Declaration" Symbol_myGrammar!"StructDeclaration" would could then be aliased by the user however they wanted: alias Symbol_myGrammar MySym; And there can still be hooks (delegates, subclassing, whatever) to add customized behavior/functionality.

Hmm, maybe I need to think about what it would take to make Goldie able to parse at compile-time...
Feb 28 2012
parent reply "Nick Sabalausky" <a a.a> writes:
"Nick Sabalausky" <a a.a> wrote in message 
news:jikcit$201o$1 digitalmars.com...
 Hmm, maybe I need to think about what it would take to make Goldie able to 
 parse at compile-time...

Just gave it a quick shot. It was looking like it might not be too bad, but then I hit: Assertion failure: 'ctfeStack.stackPointer() == 0' on line 4823 in file 'interpret.c' Bleh. (This was with DMD 2.058)
Feb 28 2012
parent "Nick Sabalausky" <a a.a> writes:
"Nick Sabalausky" <a a.a> wrote in message 
news:jikfpi$25cc$1 digitalmars.com...
 "Nick Sabalausky" <a a.a> wrote in message 
 news:jikcit$201o$1 digitalmars.com...
 Hmm, maybe I need to think about what it would take to make Goldie able 
 to parse at compile-time...

Just gave it a quick shot. It was looking like it might not be too bad, but then I hit: Assertion failure: 'ctfeStack.stackPointer() == 0' on line 4823 in file 'interpret.c' Bleh. (This was with DMD 2.058)

Filed: http://d.puremagic.com/issues/show_bug.cgi?id=7667
Mar 07 2012
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 11:15 PM, Nick Sabalausky wrote:
 In Goldie, I've taken an inverted approach, which IMHO is easier to use: The
 types are automatically generated from the grammar, not the other way
 around. So applying that approach to the above code, it'd be more like this:

 mixin genGrammar!("myGrammar", `
      Identifier = [a-zA-Z_][a-zA-Z_0-9]*
      Module = Declaration+
      Declaration = StructDeclaration
      StructDeclaration = 'struct' Identifier '{' Declaration* '}'
 `);

 Which generates these classes:

 Parser!"myGrammar"
 Symbol!("myGrammar.Identifier")
 Symbol!("myGrammar.Module")
 Symbol!("myGrammar.Declaration")
 Symbol!("myGrammar.StructDeclaration")

 and/or these:

 Parser_myGrammar
 Symbol_myGrammar!"Identifier"
 Symbol_myGrammar!"Module"
 Symbol_myGrammar!"Declaration"
 Symbol_myGrammar!"StructDeclaration"

 would could then be aliased by the user however they wanted:

 alias Symbol_myGrammar MySym;

 And there can still be hooks (delegates, subclassing, whatever) to add
 customized behavior/functionality.

I think this is the right approach. Andrei
Feb 29 2012
parent reply "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:jilkj6$1a50$2 digitalmars.com...
 On 2/28/12 11:15 PM, Nick Sabalausky wrote:
 In Goldie, I've taken an inverted approach, which IMHO is easier to use: 
 The
 types are automatically generated from the grammar, not the other way
 around. So applying that approach to the above code, it'd be more like 
 this:

 mixin genGrammar!("myGrammar", `
      Identifier = [a-zA-Z_][a-zA-Z_0-9]*
      Module = Declaration+
      Declaration = StructDeclaration
      StructDeclaration = 'struct' Identifier '{' Declaration* '}'
 `);

 Which generates these classes:

 Parser!"myGrammar"
 Symbol!("myGrammar.Identifier")
 Symbol!("myGrammar.Module")
 Symbol!("myGrammar.Declaration")
 Symbol!("myGrammar.StructDeclaration")

 and/or these:

 Parser_myGrammar
 Symbol_myGrammar!"Identifier"
 Symbol_myGrammar!"Module"
 Symbol_myGrammar!"Declaration"
 Symbol_myGrammar!"StructDeclaration"

 would could then be aliased by the user however they wanted:

 alias Symbol_myGrammar MySym;

 And there can still be hooks (delegates, subclassing, whatever) to add
 customized behavior/functionality.

I think this is the right approach.

What? We agree? ;)
Feb 29 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/29/12 11:05 AM, Nick Sabalausky wrote:
 What? We agree? ;)

It's 2012 after all. Andrei
Feb 29 2012
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
--20cf302d4d72330f6404ba173ffd
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Le 29 f=C3=A9vr. 2012 07:20, "Nick Sabalausky" <a a.a> a =C3=A9crit :
 "Nick Sabalausky" <a a.a> wrote in message
 news:jikcit$201o$1 digitalmars.com...
 Hmm, maybe I need to think about what it would take to make Goldie able


 parse at compile-time...

Just gave it a quick shot. It was looking like it might not be too bad,

 then I hit:

 Assertion failure: 'ctfeStack.stackPointer() =3D=3D 0' on line 4823 in fi=

 'interpret.c'

 Bleh.

 (This was with DMD 2.058)

Yeah, I had the very same yesterday :( Also, another one on line 94 in interpret.c 'v->ctfeSomethin' failing. Too bad. In my case, I found a workaround: I was doing array[] ~=3D SomeStruct(args); which asserts at CTFE. But: auto s =3D SomeStructs(args); array[] ~=3D s; works. --20cf302d4d72330f6404ba173ffd Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p><br> Le 29 f=C3=A9vr. 2012 07:20, &quot;Nick Sabalausky&quot; &lt;a a.a&gt; a = =C3=A9crit=C2=A0:<br> &gt;<br> &gt; &quot;Nick Sabalausky&quot; &lt;a a.a&gt; wrote in message<br> &gt; news:jikcit$201o$1 digitalmars.com...<br> &gt; &gt;<br> &gt; &gt; Hmm, maybe I need to think about what it would take to make Goldi= e able to<br> &gt; &gt; parse at compile-time...<br> &gt; &gt;<br> &gt;<br> &gt; Just gave it a quick shot. It was looking like it might not be too bad= , but<br> &gt; then I hit:<br> &gt;<br> &gt; Assertion failure: &#39;ctfeStack.stackPointer() =3D=3D 0&#39; on line= 4823 in file<br> &gt; &#39;interpret.c&#39;<br> &gt;<br> &gt; Bleh.<br> &gt;<br> &gt; (This was with DMD 2.058)</p> <p>Yeah, I had the very same yesterday :(</p> <p>Also, another one on line 94 in interpret.c &#39;v-&gt;ctfeSomethin&#39;= failing.</p> <p>Too bad.</p> <p>In my case, I found a workaround: I was doing</p> <p>array[] ~=3D SomeStruct(args);</p> <p>which asserts at CTFE.</p> <p>But:</p> <p>auto s =3D SomeStructs(args);<br> array[] ~=3D s;</p> <p>works.<br></p> --20cf302d4d72330f6404ba173ffd--
Feb 29 2012
parent "Nick Sabalausky" <a a.a> writes:
"Philippe Sigaud" <philippe.sigaud gmail.com> wrote in message 
news:mailman.229.1330508922.24984.digitalmars-d puremagic.com...
Le 29 fvr. 2012 07:20, "Nick Sabalausky" <a a.a> a crit :
 Just gave it a quick shot. It was looking like it might not be too bad,

 then I hit:

 Assertion failure: 'ctfeStack.stackPointer() == 0' on line 4823 in file
 'interpret.c'

 Bleh.

 (This was with DMD 2.058)

Yeah, I had the very same yesterday :( Also, another one on line 94 in interpret.c 'v->ctfeSomethin' failing. Too bad. In my case, I found a workaround: I was doing array[] ~= SomeStruct(args); which asserts at CTFE. But: auto s = SomeStructs(args); array[] ~= s; works.

Ooh, cool! I know exactly where I'm doing that!
Feb 29 2012
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 2/28/12 12:46 PM, Martin Nowak wrote:
 I wrote a generic lexer generator some time ago.
 It already let to some compiler O(N^2) optimizations, because the token
 declarations sneak into the mangling :(.
 I also finally added a workaround for a remaining CTFE bug (#6815).

 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Wow, now we have an embarrassment of riches!
 I've ditched an attempt to write a parser combinator. It was based on
 expression templates and ended up at spirit craziness.

I'm not sure what a parser combinator is. I think grammar inheritance could actually be interesting to explore.
 <PERSONAL OPINION
 The hassle of providing good error messages and synthesizing parse results
 in a generic parser outweigh the benefit of a declarative grammar.
 /PERSONAL OPINION>

I think synthesizing ASTs is a solved problem, see my post before. Error messages are still a hassle, but I missed the point they became good in hand-written parsers :o).
 A lot becomes feasible from the CTFE perspective,
 despite some bugfixes I only miss exp and log currently.

 I do not agree that it's the right moment to write a parser though.
 It hits the first of phobos two biggest shortcomings, the lack of a good
 I/O
 system and the missing Allocators.
 Any parser written now will either risk to not play nice with ranges
 or has to come up with it's own buffering again.

Agreed, but that doesn't seem like the largest hurdle to me. Andrei
Feb 29 2012
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?
Feb 29 2012
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 02/29/2012 07:28 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop.

I did that.
Feb 29 2012
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 02/29/2012 09:03 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 20:30:43 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 02/29/2012 07:28 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch>
 wrote:

 On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop.

I did that.

Interesting, I've commented it out https://gist.github.com/1262321#L1559 and get the following. <<< PHOBOS=~/Code/D/DPL/phobos mkdir test_lexer cd test_lexer curl https://raw.github.com/gist/1255439/lexer.d > lexer.d curl https://raw.github.com/gist/1262321/dlexer.d > dlexer.d curl https://raw.github.com/gist/1262321/entity.d > entity.d dmd -O -release -inline dlexer lexer entity wc -l ${PHOBOS}/std/*.d time ./dlexer ${PHOBOS}/std/*.d




I get 0.160s for lexing using your lexer. Parsing the same file with DMDs parser takes 0.155 seconds. The difference grows with larger files.
Feb 29 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Feb 29, 2012 at 07:28:48PM +0100, Martin Nowak wrote:
 On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:
 
On 02/28/2012 07:46 PM, Martin Nowak wrote:
https://gist.github.com/1255439 - lexer generator
https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop. There is also an --echo option which recreates the complete source from the tokens.

This sounds like something I ran into in my D lexer project. Lexing Phobos took upwards of 10-15 seconds, which is extremely slow considering that dmd can *compile* it in just a few seconds. So I did some profiling, and found out that most of the time was spent formatting tokens into strings and running writeln. After I commented that out, the running time dropped to just a few seconds. :-) T -- The fact that anyone still uses AOL shows that even the presence of options doesn't stop some people from picking the pessimal one. - Mike Ellis
Feb 29 2012
prev sibling next sibling parent reply d coder <dlang.coder gmail.com> writes:
--f46d042f93fa21d24304ba1ed0e5
Content-Type: text/plain; charset=ISO-8859-1

 This sounds like something I ran into in my D lexer project. Lexing
 Phobos took upwards of 10-15 seconds, which is extremely slow
 considering that dmd can *compile* it in just a few seconds. So I did
 some profiling, and found out that most of the time was spent formatting
 tokens into strings and running writeln. After I commented that out, the
 running time dropped to just a few seconds. :-)

--f46d042f93fa21d24304ba1ed0e5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"HOE= nZb"><div class=3D"h5"><br> </div></div>This sounds like something I ran into in my D lexer project. Le= xing<br> Phobos took upwards of 10-15 seconds, which is extremely slow<br> considering that dmd can *compile* it in just a few seconds. So I did<br> some profiling, and found out that most of the time was spent formatting<br=


le-span" color=3D"#888888"><br></font></blockquote><div><br></div><div>And = how different was just a few seconds from 10-15 seconds? :-)=A0</div></div> --f46d042f93fa21d24304ba1ed0e5--
Feb 29 2012
parent "Nick Sabalausky" <a a.a> writes:
"d coder" <dlang.coder gmail.com> wrote in message 
news:mailman.241.1330541814.24984.digitalmars-d puremagic.com...
 This sounds like something I ran into in my D lexer project. Lexing
 Phobos took upwards of 10-15 seconds, which is extremely slow
 considering that dmd can *compile* it in just a few seconds. So I did
 some profiling, and found out that most of the time was spent formatting
 tokens into strings and running writeln. After I commented that out, the
 running time dropped to just a few seconds. :-)


~10 seconds ;)
Feb 29 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 01, 2012 at 12:19:30AM +0530, d coder wrote:
 This sounds like something I ran into in my D lexer project. Lexing
 Phobos took upwards of 10-15 seconds, which is extremely slow
 considering that dmd can *compile* it in just a few seconds. So I did
 some profiling, and found out that most of the time was spent formatting
 tokens into strings and running writeln. After I commented that out, the
 running time dropped to just a few seconds. :-)


OK so I was imprecise. It was 2-3 seconds compared to 10-15 seconds. So it's about an order of magnitude difference. :) T -- "I speak better English than this villain Bush" -- Mohammed Saeed al-Sahaf, Iraqi Minister of Information
Feb 29 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 01, 2012 at 12:04:39AM +0100, Martin Nowak wrote:
[...]
 Mmh, I've retested and you're right dmd's lexer is about 2x faster.
 The main overhead stems from using ranges and enforce.
 
 Quick profiling shows that 25% is spent in popFront and
 std.utf.stride.  Last time I worked on this I rewrote std.utf.decode
 to be much faster.  But utf characters are still "decoded" twice, once
 for front and then again for popFront. Also stride uses table lookup
 and can't be inlined.

One way to not decode characters twice is by using a single-dchar buffer in your range. Something like: struct MyRange { private File src; char buf[]; dchar readahead; this(File _src) { // ... fill up buf from src here popFront(); } property pure dchar front() { return readahead; } void popFront() { int stride; readahead = decode(buf, stride); buf = buf[stride..$]; // ... fill up buf more if needed } } T -- "A man's wife has more power over him than the state has." -- Ralph Emerson
Feb 29 2012
prev sibling parent "Ben Hanson" <Ben.Hanson tikit.com> writes:
Hi Nick,

On Wednesday, 29 February 2012 at 17:16:44 UTC, Nick Sabalausky
wrote:
 One thing I've been wanting to see in a lexer's regex would be 
 a way to
 match things like D's nested comments or:

I have already implemented a lexer generator that can handle recursion in the token definitions (using multiple lexer states). See http://www.benhanson.net/lexertl.html The library is C++ and generates lexers at runtime, but the concepts should be easily transferable. Basically I have a boolean for pop in the end state and a separate column for push_dfa_: if (end_state_) { // Return longest match if (pop_) { start_state_ = results_.stack.top ().first; results_.stack.pop (); } else if (push_dfa_ != results_.npos ()) { results_.stack.push (typename results::id_type_pair (push_dfa_, id_)); } . . . I'm happy to answer any questions etc. Regards, Ben
Mar 05 2012
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Tue, 28 Feb 2012 21:02:24 +0100, H. S. Teoh <hsteoh quickfur.ath.cx>  
wrote:

 On Tue, Feb 28, 2012 at 07:46:04PM +0100, Martin Nowak wrote:
 [...]
 I wrote a generic lexer generator some time ago.
 It already let to some compiler O(N^2) optimizations, because the token
 declarations sneak into the mangling :(.
 I also finally added a workaround for a remaining CTFE bug (#6815).

 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Cool! I'll have to take a look at this sometime. [...]
 <PERSONAL OPINION
 The hassle of providing good error messages and synthesizing parse  
 results
 in a generic parser outweigh the benefit of a declarative grammar.
 /PERSONAL OPINION>

But things like lex/yacc have been useful throughout the years. With D's delegates, lexer/parser action rules should be even cleaner, no?

automaton obfuscation. And even at that price the results are still hard to maintain klingon sources. http://supercollider.git.sourceforge.net/git/gitweb.cgi?p=supercollider/supercollider;a=blob;f=lang/LangSource/Bison/lang11d I won't deny that the combination of CTFE text processing and static introspection could improve on this. It could be made more feasible by some conventions, e.g. parse result always uses structs or classes and built-in arrays. ---- class Module { this(Declaration[]); } class StructDeclaration : Declaration { enum _enbf = "struct $1=Identifier { $2=Declaration* }"; this(Identifier, Declaration[]); } ... Parser!(Module, StructDeclaration, ...) parser; Module m = parser.parse(read("file.d"));
Feb 28 2012
prev sibling next sibling parent "Christopher Bergqvist" <spambox0 digitalpoetry.se> writes:
On Tuesday, 28 February 2012 at 08:36:13 UTC, CTFE-4-the-win 
wrote:
 On Tuesday, 28 February 2012 at 07:59:16 UTC, Andrei 
 Alexandrescu
 wrote:
 I'm starting a new thread on this because I think the matter 
 is of strategic importance.

 We all felt for a long time that there's a lot of potential in 
 CTFE, and potential applications have been discussed more than 
 a few times, ranging from formatting strings parsed to DSLs 
 and parser generators.

 Such feats are now approaching fruition because a number of 
 factors converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates 
 efficient D code straight from regexen.

 * The scope and quality of CTFE has improved enormously, 
 making more advanced uses possible and even relatively easy 
 (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 
 lines of code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out 
 Philippe Sigaud has already a competing design and 
 implementation of a parser generator.

 This is the kind of stuff I've had an eye on for the longest 
 time. I'm saying it's of strategic importance because CTFE 
 technology, though not new and already available with some 
 languages, has unique powers when combined with other features 
 of D. With CTFE we get to do things that are quite literally 
 impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and 
 efficient lexer-parser generator combo in Phobos, pronto. The 
 lexer itself could use a character-level PEG or a classic 
 automaton, and emit tokens for consumption by a parser 
 generator. The two should work in perfect tandem (no need for 
 glue code). At the end of the day, defining a complete 
 lexer+parser combo for a language should be just a few lines 
 longer than the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Definitely, I applaud this initiative! I've long been of the opinion that CTFE parsing is D's killer-feature, which would allow me to "sneak" D into a "nameless above average size company". ;)

I agree that the current direction of D in this area is impressive. However, I fail to see a killer-feature in generating a lexer-parser generator at compile-time instead of run-time. A run-time generator would benefit from not having to execute within the limited CTFE environment and would always be on-par in that respect. A compile time generator would internalize the generation and compilation of the result (with possible glue-code), simplifying the build process somewhat. What am I failing to pick up on?
Feb 28 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is
 impressive. However, I fail to see a killer-feature in
 generating a lexer-parser generator at compile-time instead of
 run-time.
 
 A run-time generator would benefit from not having to execute
 within the limited CTFE environment and would always be on-par in
 that respect. A compile time generator would internalize the
 generation and compilation of the result (with possible
 glue-code), simplifying the build process somewhat.
 
 What am I failing to pick up on?

Well, one cool thing would be that a compiler could effectively compile itself - or at least the lexer and parser would compile themselves. You wouldn't have to run a program to generate them. It could be self-contained. - Jonathan M Davis
Feb 28 2012
prev sibling next sibling parent James Miller <james aatch.net> writes:
On 29 February 2012 14:16, Christopher Bergqvist
<spambox0 digitalpoetry.se> wrote:
 On Tuesday, 28 February 2012 at 08:36:13 UTC, CTFE-4-the-win wrote:
 On Tuesday, 28 February 2012 at 07:59:16 UTC, Andrei Alexandrescu
 wrote:
 I'm starting a new thread on this because I think the matter is of
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE, an=



 potential applications have been discussed more than a few times, rangi=



 from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient =



 code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of co=



 (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out Philippe Siga=



 has already a competing design and implementation of a parser generator=



 This is the kind of stuff I've had an eye on for the longest time. I'm
 saying it's of strategic importance because CTFE technology, though not=



 and already available with some languages, has unique powers when combi=



 with other features of D. With CTFE we get to do things that are quite
 literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could =



 character-level PEG or a classic automaton, and emit tokens for consump=



 by a parser generator. The two should work in perfect tandem (no need f=



 glue code). At the end of the day, defining a complete lexer+parser com=



 for a language should be just a few lines longer than the textual
 representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Definitely, I applaud this initiative! I've long been of the opinion that CTFE parsing is D's killer-feature, which would allow me to "sneak" D into a "nameless above average size company". ;)

I agree that the current direction of D in this area is impressive. =C2=A0However, I fail to see a killer-feature in generating a lexer-parse=

 generator at compile-time instead of run-time.

 A run-time generator would benefit from not having to execute within the
 limited CTFE environment and would always be on-par in that respect. =C2=

 compile time generator would internalize the generation and compilation o=

 the result (with possible glue-code), simplifying the build process
 somewhat.

 What am I failing to pick up on?

As far as I can tell, the advantage of compile-time parser-generation is that you get significantly better start-up times for the program. Generating a lexer/parser at runtime produces signficant overhead. Also, if you want to do a yacc-style action system, then it being created at compile-time means that you don't have the overhead of using anonymous functions or delegates at runtime, you can just give it a raw string of D code. The CTFE environment is not that limited, and has enough functionality to produce a lexer/parser. Complex language definitions would be benefited by CTFE parser-generation since the load times to create the generator can be quite long, a problem for programs that may not be long-running (a lint tool for example). -- James Miller
Feb 28 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Feb 28, 2012 at 08:25:21PM -0500, Jonathan M Davis wrote:
 On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is impressive.
 However, I fail to see a killer-feature in generating a lexer-parser
 generator at compile-time instead of run-time.
 
 A run-time generator would benefit from not having to execute within
 the limited CTFE environment and would always be on-par in that
 respect. A compile time generator would internalize the generation
 and compilation of the result (with possible glue-code), simplifying
 the build process somewhat.
 
 What am I failing to pick up on?

Well, one cool thing would be that a compiler could effectively compile itself - or at least the lexer and parser would compile themselves. You wouldn't have to run a program to generate them. It could be self-contained.

You also eliminate possibly lengthy program startup initialization. Which can add up, if the program is run many times. Plus, if something can already be computed at compile-time, why waste time & resources doing it at runtime? T -- Без труда не выловишь и рыбку из пруда.
Feb 28 2012
prev sibling next sibling parent d coder <dlang.coder gmail.com> writes:
--f46d04083be99db04804ba10e6a7
Content-Type: text/plain; charset=ISO-8859-1

 On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is impressive.
 However, I fail to see a killer-feature in generating a lexer-parser
 generator at compile-time instead of run-time.



CTFE parsing is especially useful for DSEL (Domain Specific Embedded Languages) or internal DSLs. The advantages are: 1. Syntactic errors (in the parsed constructs) are given out at compile time. 2. D reflections are available only at compile time. Referencing the variables/identifiers in the parsed subset of DSL with the mainstream D code is impossible without reflections in place. Regards - Puneet --f46d04083be99db04804ba10e6a7 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"HOE= nZb"><div class=3D"h5"><br> &gt; On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:<= br> &gt; &gt; I agree that the current direction of D in this area is impressiv= e.<br> &gt; &gt; However, I fail to see a killer-feature in generating a lexer-par= ser<br> &gt; &gt; generator at compile-time instead of run-time.<br> &gt; &gt;</div></div></blockquote><div><br></div><div>CTFE parsing is espec= ially useful for DSEL (Domain Specific Embedded Languages) or internal DSLs= . The advantages are:</div><div><br></div><div>1. Syntactic errors (in the = parsed constructs) =A0are given out at compile time.</div> <div>2. D reflections are available only at compile time. Referencing the v= ariables/identifiers in the parsed subset of DSL with the mainstream D code= is impossible without reflections in place.</div><div><br></div><div> Regards</div> <div>- Puneet</div><div><br></div></div> --f46d04083be99db04804ba10e6a7--
Feb 28 2012
prev sibling next sibling parent bcs <bcs example.com> writes:
On 02/27/2012 11:59 PM, Andrei Alexandrescu wrote:
 I'm starting a new thread on this because I think the matter is of
 strategic importance.

 We all felt for a long time that there's a lot of potential in CTFE, and
 potential applications have been discussed more than a few times,
 ranging from formatting strings parsed to DSLs and parser generators.

 Such feats are now approaching fruition because a number of factors
 converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates efficient D
 code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making more
 advanced uses possible and even relatively easy (thanks Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 lines of
 code (sadly, no comments or documentation yet :o))

A bit outdated but.... http://dsource.org/projects/scrapple/browser/trunk/dparser/dparse.d BTW, that uses very little in the way of CTFE and even less in the way of string mixins. Those are, IMHO, very powerful tools that should only be combined as weapons of last resort.
 * With the occasion of that announcement we also find out Philippe
 Sigaud has already a competing design and implementation of a parser
 generator.

 This is the kind of stuff I've had an eye on for the longest time. I'm
 saying it's of strategic importance because CTFE technology, though not
 new and already available with some languages, has unique powers when
 combined with other features of D. With CTFE we get to do things that
 are quite literally impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and efficient
 lexer-parser generator combo in Phobos, pronto. The lexer itself could
 use a character-level PEG or a classic automaton, and emit tokens for
 consumption by a parser generator. The two should work in perfect tandem
 (no need for glue code). At the end of the day, defining a complete
 lexer+parser combo for a language should be just a few lines longer than
 the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Feb 28 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--20cf3074d3d2c0b1d504ba173390
Content-Type: text/plain; charset=UTF-8

 On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvist wrote:
 I agree that the current direction of D in this area is impressive.
 However, I fail to see a killer-feature in generating a lexer-parser
 generator at compile-time instead of run-time.



CTFE parsing is especially useful for DSEL (Domain Specific Embedded

 1. Syntactic errors (in the parsed constructs)  are given out at compile

 2. D reflections are available only at compile time. Referencing the

code is impossible without reflections in place. One of my goals while writing a CT grammar generator was to get a compile-time parse-tree. Since it contains strings, it's easy to walk the tree, assembling strings as you go and generating the code you want (if//when you want to write code, that is) Strings are a D way to represent code, so any way to get structured strings at compile-time opens whole vistas for code generation. As for semantic actions, I added them in my code yesterday. I had hopes for using D's new anonymous syntax (p => p), but by being anonymous, they cannot be inserted easily in string mixins (other modules do not now about __lambda1 and co). Anyway, I now have semantic actions at compile-time, I used them to write a small (as in, veeery simple) XML parser: I use semantic actions to push node names while encountering them and pop the last tag while encountering a closing tag. It seems to work OK. That looks a bit like this (sorry, writing on a pad) mixin(Grammar!("Doc <- Node*" "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction, "OpeningTag <- '<' Identifier '>'", OpeningAction, "ClosingTag <- `</` Identifier '>'", ClosingAction, "Text <- (!(OpeningTag / ClosingTag) _)+")); The PEG for Text just means: any char, as long as it's not an OpeningTag nor a ClosingTag. PEG use '.' to say 'Any char', but I wanted to be able to deal with qualified names, so I chose '_' instead. When there is no action, it default to NoOp, as is the case for Doc, Node and Text. I also added named captures (and capture comparison), to be able to say: "I want a sequence of equal chars": "Equal <- _ first (_=first)*" That is: any char, store it as "first", then take any number of char, long as their match is equal to first's match. All this work at CT. I'm afraid being in holidays right now means I do not have easy access to GitHub (no git on a pad, and the computer I use to code right now does not have any network connection). I'll put all this online in a few days, because that must seems like the ramblings of a madman right now... Philippe --20cf3074d3d2c0b1d504ba173390 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p><br> &gt;&gt; &gt; On Wednesday, February 29, 2012 02:16:12 Christopher Bergqvis= t wrote:<br> &gt;&gt; &gt; &gt; I agree that the current direction of D in this area is = impressive.<br> &gt;&gt; &gt; &gt; However, I fail to see a killer-feature in generating a = lexer-parser<br> &gt;&gt; &gt; &gt; generator at compile-time instead of run-time.<br> &gt;&gt; &gt; &gt;<br> &gt;<br> &gt;<br> &gt; CTFE parsing is especially useful for DSEL (Domain Specific Embedded L= anguages) or internal DSLs. The advantages are:<br> &gt;<br> &gt; 1. Syntactic errors (in the parsed constructs) =C2=A0are given out at = compile time.<br> &gt; 2. D reflections are available only at compile time. Referencing the v= ariables/identifiers in the parsed subset of DSL with the mainstream D code= is impossible without reflections in place.<br></p> <p>One of my=C2=A0 goals while writing a CT grammar generator was to get a = compile-time parse-tree. Since it contains strings, it&#39;s easy to walk t= he tree, assembling strings as you go and generating the code you want (if/= /when you want to write code, that is)</p> <p>Strings are a D way to represent code, so any way to get structured stri= ngs at compile-time opens whole vistas for code generation.</p> <p>As for semantic actions, I added them in my code yesterday. I had hopes = for using D&#39;s new anonymous syntax (p =3D&gt; p), but by being anonymou= s, they cannot be inserted easily in string mixins (other modules do not no= w about __lambda1 and co).</p> <p>Anyway, I now have semantic actions at compile-time, I used them to writ= e a small (as in, veeery simple) XML parser: I use semantic actions to push= node names while encountering them and pop the last tag while encountering= a closing tag. It seems to work OK.</p> <p>That looks a bit like this (sorry, writing on a pad)</p> <p>mixin(Grammar!(&quot;Doc &lt;- Node*&quot;<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 &quot;Node &lt;- OpeningTag (Text / Node)* ClosingTag&quot;= , NodeAction,<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 &quot;OpeningTag &lt;- &#39;&lt;&#39; Identifier &#39;&gt;&= #39;&quot;, OpeningAction,<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 &quot;ClosingTag &lt;-=C2=A0 `&lt;/` Identifier &#39;&gt;&#= 39;&quot;, ClosingAction,<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 &quot;Text &lt;- (!(OpeningTag / ClosingTag) _)+&quot;));</= p> <p>The PEG for Text just means: any char, as long as it&#39;s not an Openin= gTag nor a ClosingTag. PEG use &#39;.&#39; to say &#39;Any char&#39;, but I= wanted to be able to deal with qualified names, so I chose &#39;_&#39; ins= tead.<br> When there is no action, it default to NoOp, as is the case for=C2=A0 Doc, = Node and Text.</p> <p>I also added named captures (and capture comparison), to be able to say:= &quot;I want a sequence of equal chars&quot;:</p> <p>&quot;Equal &lt;- _ first (_=3Dfirst)*&quot;</p> <p>That is: any char, store it as &quot;first&quot;, then take any number o= f char, long as their match is equal to first&#39;s match.</p> <p>All this work at CT.</p> <p>I&#39;m=C2=A0 afraid being in holidays right now means I do not have eas= y access to GitHub (no git on a pad, and the computer I use to code right n= ow does not have any network connection). I&#39;ll put all this online in a= few days, because that must seems like the ramblings of a madman right now= ...<br> </p> <p>Philippe<br> </p> --20cf3074d3d2c0b1d504ba173390--
Feb 29 2012
prev sibling next sibling parent d coder <dlang.coder gmail.com> writes:
--f46d042c6497c1875d04ba1a5bf5
Content-Type: text/plain; charset=ISO-8859-1

 I'm  afraid being in holidays right now means I do not have easy access to
 GitHub (no git on a pad, and the computer I use to code right now does not
 have any network connection). I'll put all this online in a few days,
 because that must seems like the ramblings of a madman right now...

I am eagerly waiting for you to upload the stuff on GitHub. Regards - Puneet --f46d042c6497c1875d04ba1a5bf5 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p>I&#39;m=A0 afr= aid being in holidays right now means I do not have easy access to GitHub (= no git on a pad, and the computer I use to code right now does not have any= network connection). I&#39;ll put all this online in a few days, because t= hat must seems like the ramblings of a madman right now...</p> </blockquote><div><br></div><div>I am eagerly waiting for you to upload the= stuff on GitHub.=A0</div><div><br></div><div>Regards</div><div>- Puneet</d= iv><div><br></div></div> --f46d042c6497c1875d04ba1a5bf5--
Feb 29 2012
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop. There is also an --echo option which recreates the complete source from the tokens.
Feb 29 2012
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 29 Feb 2012 20:30:43 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 02/29/2012 07:28 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

 On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop.

I did that.

Interesting, I've commented it out https://gist.github.com/1262321#L1559 and get the following. <<< PHOBOS=~/Code/D/DPL/phobos mkdir test_lexer cd test_lexer curl https://raw.github.com/gist/1255439/lexer.d > lexer.d curl https://raw.github.com/gist/1262321/dlexer.d > dlexer.d curl https://raw.github.com/gist/1262321/entity.d > entity.d dmd -O -release -inline dlexer lexer entity wc -l ${PHOBOS}/std/*.d time ./dlexer ${PHOBOS}/std/*.d



Feb 29 2012
prev sibling next sibling parent "Christopher Bergqvist" <spambox0 digitalpoetry.se> writes:
On Wednesday, 29 February 2012 at 16:41:22 UTC, Andrei 
Alexandrescu wrote:
 On 2/28/12 7:16 PM, Christopher Bergqvist wrote:
 What am I failing to pick up on?

Barrier of entry and granularity of approach, I think. Currently if one wants to parse some simple grammar, there are options such as (a) do it by hand, (b) use boost::spirit, or (c) use lex/yacc. Parsing by hand has the obvious disadvantages. Using boost::spirit has a steep learning curve and tends to create very contorted grammar representations, full of representation noise, and scales very poorly. Using lex/yacc is hamfisted - there's an additional build step, generated files to deal with, and the related logistics, which make lex/yacc a viable choice only for "big" grammars. An efficient, integrated parser generator would lower the barrier of entry dramatically - if we play our cards right, even a sprintf specifier string could be parsed simpler and faster using an embedded grammar, instead of painfully writing the recognizer by hand. Parsing config files, XML, JSON, CSV, various custom file formats and many others - all would all be a few lines away. Ideally a user who has a basic understanding of grammars should have an easier time using a small grammar to parse simple custom formats, than writing the parsing code by hand. Andrei

Thanks for your response. The lowered barrier of entry in parsing something like a customized JSON format or config files is nice, and something I could see myself use. I'm still skeptical about the level of "killer-featureness" but I would be glad to be proven wrong.
Feb 29 2012
prev sibling next sibling parent "Martin Nowak" <dawg dawgfoto.de> writes:
On Wed, 29 Feb 2012 21:30:57 +0100, Timon Gehr <timon.gehr gmx.ch> wrote:

 On 02/29/2012 09:03 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 20:30:43 +0100, Timon Gehr <timon.gehr gmx.ch>  
 wrote:

 On 02/29/2012 07:28 PM, Martin Nowak wrote:
 On Wed, 29 Feb 2012 17:41:19 +0100, Timon Gehr <timon.gehr gmx.ch>
 wrote:

 On 02/28/2012 07:46 PM, Martin Nowak wrote:
 https://gist.github.com/1255439 - lexer generator
 https://gist.github.com/1262321 - complete and fast D lexer

Well, it is slower at lexing than DMD at parsing. What is the bottleneck?

No, it's as fast as dmd's lexer. Writing the tokens to stdout takes a lot of time though. Just disable the "writeln(tok);" in the main loop.

I did that.

Interesting, I've commented it out https://gist.github.com/1262321#L1559 and get the following. <<< PHOBOS=~/Code/D/DPL/phobos mkdir test_lexer cd test_lexer curl https://raw.github.com/gist/1255439/lexer.d > lexer.d curl https://raw.github.com/gist/1262321/dlexer.d > dlexer.d curl https://raw.github.com/gist/1262321/entity.d > entity.d dmd -O -release -inline dlexer lexer entity wc -l ${PHOBOS}/std/*.d time ./dlexer ${PHOBOS}/std/*.d




I get 0.160s for lexing using your lexer. Parsing the same file with DMDs parser takes 0.155 seconds. The difference grows with larger files.

Mmh, I've retested and you're right dmd's lexer is about 2x faster. The main overhead stems from using ranges and enforce. Quick profiling shows that 25% is spent in popFront and std.utf.stride. Last time I worked on this I rewrote std.utf.decode to be much faster. But utf characters are still "decoded" twice, once for front and then again for popFront. Also stride uses table lookup and can't be inlined. If switch tables were implemented on x64 one could use them for integral ElementType.
Feb 29 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Feb 29, 2012 at 10:41:22AM -0600, Andrei Alexandrescu wrote:
[...]
 An efficient, integrated parser generator would lower the barrier of
 entry dramatically - if we play our cards right, even a sprintf
 specifier string could be parsed simpler and faster using an embedded
 grammar, instead of painfully writing the recognizer by hand.

I see that std.stdio.writef already parses format strings at compile-time, though the code is somewhat ugly. :) It would be ideal if that can be done just by a series of ENBF/regex declarations.
 Parsing config files, XML, JSON, CSV, various custom file formats and
 many others - all would all be a few lines away. Ideally a user who
 has a basic understanding of grammars should have an easier time using
 a small grammar to parse simple custom formats, than writing the
 parsing code by hand.

This is definitely something worth having. It has always been my dream that an ideal programming language should let you write grammar rules and pretty much autogen the code for you. There shouldn't need to be external utilities with the associated messy build rules, auxiliary files and other such things, esp. if you just need a one-time small parser for a very specific task. T -- Why ask rhetorical questions? -- JC
Feb 29 2012
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
Why do you need grammar rules for json? Just use a custom-defined
struct and pass it to a toJson function like ae's json module. :)
Feb 29 2012
prev sibling next sibling parent "Marco Leise" <Marco.Leise gmx.de> writes:
Am 29.02.2012, 02:30 Uhr, schrieb Piotr Szturmaj <bncrbme jadamspam.pl>:

 CTFE code can be much slower than native one, and I would like to see
 some kind of compiler cache for such code.

I second this. As a fan of clean optimizations this is one of the things I tossed around my head for a while. It could use a cache file or the compiler could be started as a daemon process keeping a memory cache. All code that is called through CTFE would go into the cache, indexed by the internal representation of the function body and parameters. But there are a few open questions, like how seamless this could be integrated. Is it easy to get a hash for function bodies and parameters? How should the cache be limited? N functions, n bytes or maybe one cache per module (together with the .o files)? The latter case would mean that if a.d uses CTFE, that executes code from b.d the results of CTFE would all be cached together with a.o, because that was the entry point. And if there was a module c.d that does the same as a.d it would duplicate the b.d part in its own cache. The benefit is that the cache works with both single module and whole program compilation and it doesn't need any limits. Instead the caches for each module are always refreshed with what was last used in the compilation. In addition to the last compilation, the caches could be aware of versioned compilation. I usually want to compile debug versions and Linux/Windows release versions at least, so I wouldn't want to invalidate the caches. For 32-bit vs. 64-bit I assume it is the best to just cache them separately as it could prove difficult to distinguish two versions of code that uses (void*).sizeof or something else that isn't declared wrapped in a version statement like size_t is.
Feb 29 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--20cf3005dc4033993604ba2fdc84
Content-Type: text/plain; charset=UTF-8

 mixin(Grammar!("Doc <- Node*"
 "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction,
 "OpeningTag <- '<' Identifier '>'", OpeningAction,
 "ClosingTag <-  `</` Identifier '>'", ClosingAction,
 "Text <- (!(OpeningTag / ClosingTag) _)+"));

That looks about right, but still has a fair amount of noise. I think the

Yes, using one string is indeed better. That won't be too difficult to code. But how to associate actions with a rule, in that case? I mean, some rules will have actions, some not. In my case, a parse tree is automatically generated (indeed, it's almost the only thing returned by a parse call, that with recognized string and named captures). I have some additional syntax to 'drop' a node ans such, similar to what you proposed a few posts ago. --20cf3005dc4033993604ba2fdc84 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <p>&gt;&gt; mixin(Grammar!(&quot;Doc &lt;- Node*&quot;<br> &gt;&gt; &quot;Node &lt;- OpeningTag (Text / Node)* ClosingTag&quot;, NodeA= ction,<br> &gt;&gt; &quot;OpeningTag &lt;- &#39;&lt;&#39; Identifier &#39;&gt;&#39;&qu= ot;, OpeningAction,<br> &gt;&gt; &quot;ClosingTag &lt;- =C2=A0`&lt;/` Identifier &#39;&gt;&#39;&quo= t;, ClosingAction,<br> &gt;&gt; &quot;Text &lt;- (!(OpeningTag / ClosingTag) _)+&quot;));<br> &gt;<br> &gt;<br> &gt; That looks about right, but still has a fair amount of noise. I think = the approach of putting the entire grammar in one string is best.</p> <p>Yes, using one string is indeed better. That won&#39;t be too difficult = to code.</p> <p>But how to associate actions with a rule, in that case? I mean, some rul= es will have actions, some not.</p> <p>In my case, a parse tree is automatically generated (indeed, it&#39;s al= most the only thing returned by a parse call, that with recognized string a= nd named captures). I have some additional syntax to &#39;drop&#39; a node = ans such, similar to what you proposed a few posts ago.<br> </p> --20cf3005dc4033993604ba2fdc84--
Mar 01 2012
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Mar 01, 2012 at 04:10:26PM +0100, Philippe Sigaud wrote:
 mixin(Grammar!("Doc <- Node*"
 "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction,
 "OpeningTag <- '<' Identifier '>'", OpeningAction,
 "ClosingTag <-  `</` Identifier '>'", ClosingAction,
 "Text <- (!(OpeningTag / ClosingTag) _)+"));

That looks about right, but still has a fair amount of noise. I think the approach of putting the entire grammar in one string is best.

Yes, using one string is indeed better. That won't be too difficult to code. But how to associate actions with a rule, in that case? I mean, some rules will have actions, some not.

You could maybe just put D code in the grammar string, which gets compiled as a string mixin by CTFE? T -- "A man's wife has more power over him than the state has." -- Ralph Emerson
Mar 01 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--20cf3074d3d259629104ba31afb5
Content-Type: text/plain; charset=UTF-8

 But how to associate actions with a rule, in that case? I mean, some
 rules will have actions, some not.

You could maybe just put D code in the grammar string, which gets compiled as a string mixin by CTFE?

I could, but one of my driving goals while beginning this project a month ao was to use the shiny new lambda syntax directly :) "rule1", o => o "rule2", o => o etc. --20cf3074d3d259629104ba31afb5 Content-Type: text/html; charset=UTF-8 <p>&gt; &gt; But how to associate actions with a rule, in that case? I mean, some<br> &gt; &gt; rules will have actions, some not.<br> &gt;<br> &gt; You could maybe just put D code in the grammar string, which gets<br> &gt; compiled as a string mixin by CTFE?</p> <p>I could, but one of my driving goals while beginning this project a month ao was to use the shiny new lambda syntax directly :)</p> <p>&quot;rule1&quot;, o =&gt; o<br> &quot;rule2&quot;, o =&gt; o<br></p> <p>etc.</p> --20cf3074d3d259629104ba31afb5--
Mar 01 2012
prev sibling next sibling parent reply "F i L" <witte2008 gmail.com> writes:
I'm not sure I follow all the details of what Andrei's suggesting 
and what's being talked about here, this parser/lexer stuff is 
still very new to me, so this may be a bit off-topic. However, I 
thought I'd weigh in on something I was very impressed with about 
the Nimrod language's direct AST access/manipulation.

Nim has a "template" which is very much like D's mixin templates, 
example:

   # Nim
   template foo(b:string) =
     var bar = b

   block main:
     foo("test")
     assert(bar == "test")

and the equivalent in...

   // D
   mixin template foo(string b) {
     auto bar = b;
   }

   void main() {
     mixin foo("test");
     assert(bar == "test");
   }

which is all very straight forward stuff, the cool part comes 
with Nim's macro's. Nim has a two unique types: expr & stmt 
(expression & statement). They're direct AST structures which can 
be passed to template/macro procedures and arbitrarily mutated. 
Example:

   macro foo(s:stmt): stmt =
     result = newNimNode(nnkStmtList)
     for i in 1 .. s.len-1:
       var str = s[i].toStrLit()
       result.add(newCall("echo", str))

   block main:
     foo:
       bar
       baz

the above code prints:
"
   bar
   baz
"

**Some notes: result is what's returned, and the reason you can 
use "foo" with a statement body is because any macro/template 
who's last parameter is type 'stmt' can be called with block 
semantics; similar to how UFCS works with the first parameter.**

The above *might* look like the following in D:

   macro foo(ASTNode[] stmts...) {
     ASTNode[] result;
     foreach (s; stmts) {
       auto str = s.toASTString();
       result ~= new ASTCall!"writeln"(str);
     }
     return result;
   }

   void main() {
     foo {
       bar;
       baz;
     }
   }

This kind of direct AST manipulation + body semantics opens the 
doors for a lot of cool things. If you read through Nim's lib 
documentation you'll notice many of the "language" features are 
actually just Library procedures in the defaultly included system 
module. Which is great because contributions to the *language* 
can be made very easily. Also, the infrastructure to read/write 
AST is no-doubt immensely useful for IDE support and other such 
dev tools.

I'm not a huge fan of everything in Nimrod, but this is something 
they definitely got right, and I think D could gain from their 
experience.
May 27 2012
parent Jacob Carlborg <doob me.com> writes:
On 2012-05-27 22:15, F i L wrote:
 I'm not sure I follow all the details of what Andrei's suggesting and
 what's being talked about here, this parser/lexer stuff is still very
 new to me, so this may be a bit off-topic. However, I thought I'd weigh
 in on something I was very impressed with about the Nimrod language's
 direct AST access/manipulation.

 Nim has a "template" which is very much like D's mixin templates, example:

 # Nim
 template foo(b:string) =
 var bar = b

 block main:
 foo("test")
 assert(bar == "test")

 and the equivalent in...

 // D
 mixin template foo(string b) {
 auto bar = b;
 }

 void main() {
 mixin foo("test");
 assert(bar == "test");
 }

 which is all very straight forward stuff, the cool part comes with Nim's
 macro's. Nim has a two unique types: expr & stmt (expression &
 statement). They're direct AST structures which can be passed to
 template/macro procedures and arbitrarily mutated. Example:

 macro foo(s:stmt): stmt =
 result = newNimNode(nnkStmtList)
 for i in 1 .. s.len-1:
 var str = s[i].toStrLit()
 result.add(newCall("echo", str))

 block main:
 foo:
 bar
 baz

 the above code prints:
 "
 bar
 baz
 "

 **Some notes: result is what's returned, and the reason you can use
 "foo" with a statement body is because any macro/template who's last
 parameter is type 'stmt' can be called with block semantics; similar to
 how UFCS works with the first parameter.**

 The above *might* look like the following in D:

 macro foo(ASTNode[] stmts...) {
 ASTNode[] result;
 foreach (s; stmts) {
 auto str = s.toASTString();
 result ~= new ASTCall!"writeln"(str);
 }
 return result;
 }

 void main() {
 foo {
 bar;
 baz;
 }
 }

 This kind of direct AST manipulation + body semantics opens the doors
 for a lot of cool things. If you read through Nim's lib documentation
 you'll notice many of the "language" features are actually just Library
 procedures in the defaultly included system module. Which is great
 because contributions to the *language* can be made very easily. Also,
 the infrastructure to read/write AST is no-doubt immensely useful for
 IDE support and other such dev tools.

 I'm not a huge fan of everything in Nimrod, but this is something they
 definitely got right, and I think D could gain from their experience.

This is a very cool feature of Nimrod. It allows to move several language features to the library. * synchronized * scope * foreach (possibly) -- /Jacob Carlborg
May 28 2012
prev sibling next sibling parent "John Belmonte" <john neggie.net> writes:
On Thursday, 1 March 2012 at 15:10:36 UTC, Philippe Sigaud wrote:
 mixin(Grammar!("Doc <- Node*"
 "Node <- OpeningTag (Text / Node)* ClosingTag", NodeAction,
 "OpeningTag <- '<' Identifier '>'", OpeningAction,
 "ClosingTag <-  `</` Identifier '>'", ClosingAction,
 "Text <- (!(OpeningTag / ClosingTag) _)+"));

That looks about right, but still has a fair amount of noise. I think the

Yes, using one string is indeed better. That won't be too difficult to code.

I'm wondering if people have seen LPeg. It's a Lua library, but the design is interesting in that patterns are first class objects which can be composed with operator overloading. http://www.inf.puc-rio.br/~roberto/lpeg/
May 27 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Sun, May 27, 2012 at 11:13 PM, John Belmonte <john neggie.net> wrote:
 I'm wondering if people have seen LPeg. =C2=A0It's a Lua library, but the=

 is interesting in that patterns are first class objects which can be
 composed with operator overloading.

 http://www.inf.puc-rio.br/~roberto/lpeg/

This is exactly the approach followed by C++ Boost::Spirit, with halas the limitations from Algol-language operators and precedence: no postfix '*' (Kleene Star) operator. It seems that lpeg has the same problem. I played with this idea with my own Pegged (https://github.com/PhilippeSigaud/Pegged), but I wasn't quite convinced by the result, exactly for the reason above. Also, when looking at real-world Spirit examples, I was a bit disappointed by the resulting syntax: it's not *that* readable for complicated expressions. In fact, that's exactly why I decided to follow the DSL road with Pegged, so as to obtain exactly the PEG syntax, with the real operators and their standard precedence. Btw, if you're interested in expression templates, I uploaded yesterday a very preliminary project in Github, to construct, and then manipulate, expressions: auto e =3D expr(); // The null expression auto f =3D 2*e + 1- (e~"abc")*3; // f is an expression template that encodes the right-hand side. Then, it's up to the user to define what the expression represents. https://github.com/PhilippeSigaud/Expression-Tree
May 28 2012
prev sibling next sibling parent "John Belmonte" <john neggie.net> writes:
On Monday, 28 May 2012 at 12:27:09 UTC, Philippe Sigaud wrote:
 I played with this idea with my own Pegged
 (https://github.com/PhilippeSigaud/Pegged), but I wasn't quite
 convinced by the result, exactly for the reason above. Also, 
 when
 looking at real-world Spirit examples, I was a bit disappointed 
 by the
 resulting syntax: it's not *that* readable for complicated
 expressions. In fact, that's exactly why I decided to follow 
 the DSL
 road with Pegged, so as to obtain exactly the PEG syntax, with 
 the
 real operators and their standard precedence.

Fair enough. I did notice the following in the markdown PEG though which could benefit from first class patterns: # Parsers for different kinds of block-level HTML content. # This is repetitive due to constraints of PEG grammar. HtmlBlockOpenAddress <- '<' Spnl ("address" / "ADDRESS") Spnl HtmlAttribute* '>' HtmlBlockCloseAddress <- '<' Spnl '/' ("address" / "ADDRESS") Spnl '>' HtmlBlockAddress <- HtmlBlockOpenAddress (HtmlBlockAddress / !HtmlBlockCloseAddress .)* HtmlBlockCloseAddress HtmlBlockOpenBlockquote <- '<' Spnl ("blockquote" / "BLOCKQUOTE") Spnl HtmlAttribute* '>' HtmlBlockCloseBlockquote <- '<' Spnl '/' ("blockquote" / "BLOCKQUOTE") Spnl '>' HtmlBlockBlockquote <- HtmlBlockOpenBlockquote (HtmlBlockBlockquote / !HtmlBlockCloseBlockquote .)* HtmlBlockCloseBlockquote . . .
May 28 2012
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Mon, May 28, 2012 at 11:42 PM, John Belmonte <john neggie.net> wrote:
 Fair enough. =C2=A0I did notice the following in the markdown PEG though =

 could benefit from first class patterns:


 # Parsers for different kinds of block-level HTML content.
 # This is repetitive due to constraints of PEG grammar.

 HtmlBlockOpenAddress <- '<' Spnl ("address" / "ADDRESS") Spnl HtmlAttribu=

 '>'
 HtmlBlockCloseAddress <- '<' Spnl '/' ("address" / "ADDRESS") Spnl '>'
 HtmlBlockAddress <- HtmlBlockOpenAddress (HtmlBlockAddress /
 =C2=A0 !HtmlBlockCloseAddress .)* HtmlBlockCloseAddress

 HtmlBlockOpenBlockquote <- '<' Spnl ("blockquote" / "BLOCKQUOTE") Spnl
 =C2=A0 HtmlAttribute* '>'
 HtmlBlockCloseBlockquote <- '<' Spnl '/' ("blockquote" / "BLOCKQUOTE") Sp=

 '>'
 HtmlBlockBlockquote <- HtmlBlockOpenBlockquote (HtmlBlockBlockquote /
 =C2=A0 !HtmlBlockCloseBlockquote .)* HtmlBlockCloseBlockquote

You're exactly right! Nice catch. I took this PEG from another github project (I hope I put the attribution somewhere?) and that was before Pegged accepted parameterized rules. I could indeed drastically factor the previous code.
May 29 2012
prev sibling parent reply "Ken" <kennethuil gmail.com> writes:
On Tuesday, 28 February 2012 at 07:59:16 UTC, Andrei Alexandrescu 
wrote:
 I'm starting a new thread on this because I think the matter is 
 of strategic importance.

 We all felt for a long time that there's a lot of potential in 
 CTFE, and potential applications have been discussed more than 
 a few times, ranging from formatting strings parsed to DSLs and 
 parser generators.

 Such feats are now approaching fruition because a number of 
 factors converge:

 * Dmitry Olshansky's regex library (now in Phobos) generates 
 efficient D code straight from regexen.

 * The scope and quality of CTFE has improved enormously, making 
 more advanced uses possible and even relatively easy (thanks 
 Don!)

 * Hisayuki Mima implemented a parser generator in only 3000 
 lines of code (sadly, no comments or documentation yet :o))

 * With the occasion of that announcement we also find out 
 Philippe Sigaud has already a competing design and 
 implementation of a parser generator.

 This is the kind of stuff I've had an eye on for the longest 
 time. I'm saying it's of strategic importance because CTFE 
 technology, though not new and already available with some 
 languages, has unique powers when combined with other features 
 of D. With CTFE we get to do things that are quite literally 
 impossible to do in other languages.

 We need to have a easy-to-use, complete, seamless, and 
 efficient lexer-parser generator combo in Phobos, pronto. The 
 lexer itself could use a character-level PEG or a classic 
 automaton, and emit tokens for consumption by a parser 
 generator. The two should work in perfect tandem (no need for 
 glue code). At the end of the day, defining a complete 
 lexer+parser combo for a language should be just a few lines 
 longer than the textual representation of the grammar itself.

 What do you all think? Let's get this project off the ground!


 Thanks,

 Andrei

Great! So what's the next step? Do we wait for the maintainers of one of the CTFE parser gen packages to drop it in the Phobos Review Queue? Do a reimplementation for Phobos? We could attack this in pieces. Start with a lexer/FSA generator (like Ragel but using CTFE) - this will make it much easier to consume many wire protocols, for starters (I found it very easy to make a simple HTTP client using Ragel), and will be quite useful on its own. Then extend it into a lexer for a parser generator.
Jun 01 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/1/12 8:39 AM, Ken wrote:
 Great! So what's the next step? Do we wait for the maintainers of one of
 the CTFE parser gen packages to drop it in the Phobos Review Queue? Do a
 reimplementation for Phobos?

 We could attack this in pieces. Start with a lexer/FSA generator (like
 Ragel but using CTFE) - this will make it much easier to consume many
 wire protocols, for starters (I found it very easy to make a simple HTTP
 client using Ragel), and will be quite useful on its own. Then extend it
 into a lexer for a parser generator.

I think this core strength of the language should be properly supplanted by library support, so I'd be very interested to look at Phobos proposals. The proposals should come with sample grammars of nontrivial size, ideally a parser for the entire D language. There might be things to fix in the compiler, e.g. memory consumption. Andrei
Jun 01 2012