I eventually decided to take on implementing PEG parser generator for Dao, as ybabel proposed some time ago. It's an unusual functionality, and some aspects of it would be better discussed beforehand, which is why I'm starting this topic.

First of all, a short intro about what PEG is and how it can be used.

PEG, Parsing Expression Grammar, is a simple BNF-like notation to define a parser. The syntax and semantics are explained well in the Wikipedia article , so I just give example from it which I'll use further. It's a simplest grammar for arithmetic expressions: When and why use PEG parser? PEG is much more flexible than regular expressions due to its recursion capability. Thus it becomes possible to parse complex-structured text data, code of existing and, most interesting, your own programming and markup languages etc. And that's not all mere theory: PEG is already adapted for most mainstream languages (see the incomplete list at the packrat/PEG page ).

Now, here is what I've come with regarding PEG support in Dao.

First, we need grammar mapping on Dao syntax. The original PEG syntax is certainly nice, but using it as text would require special parser and greatly complicate the implementation (higher error-proneness should also be taken into account). So it seems suitable to simply reuse ordinary language elements. The resulting Dao-based syntax I've thought up looks like this (same grammar as above): Here is description of the semantics:

1. grammar => named tuple;
2. terminal symbol => Dao regex string;
3. non-terminal symbol (as a reference) => enum, "$id";
4. grouping => tuple, "(e1, e2, ...)";
5. ordered choice => list, "{e1, e2, ...}";
6. quantifiers "*", "+" and "?" => tuples "0:", "1:" and "0:1";
7. predicates "&" and "!" => integers 1 and 0.

That may be not the best variant, any other ideas regarding the syntax are welcomed.

BTW, there is one interesting aspect about the Dao-based syntax I propose -- the grammar is supposed to be used "as is", without translation into some internal structures. Thus it should be possible and safe to alter the grammar on the fly , after the corresponding parser has been created (but not add or remove rules). Not sure how it can be useful (and can it be at all), but that may be worth taking into account.

Regarding the actual implementation: for now I suppose it will be a usual C module with parser class. The class's constructor will take the grammar and pre-process it -- resolve references, compile regexes and check basic restrictions (I already wrote some code for that). No changes should be made to the grammar representation, so you'll be able to alter it any time like an ordinary composition of Dao values. Upon running the parser it's engine (packrat implementation, I suppose) will "walk" the grammar preserving the ability to detect new errors on the fly.

The question which interests me most is what output the parser should produce. Should it be just an AST mapped to Dao data structures, or perhaps it can be organized in more sophisticated and suitable way? There is probably a wide area of various possibilities to consider.

Should someone come around any interesting ideas about PEG in Dao, write down your thoughts here and thereby prevent me from deciding everything alone! :)