Hello,
I'm currently writing a PEG matching/parsing library in and for D. This is
rather to learn the language better, but it will be published anyway. (Tell me
whether there are already, could not find any.)
One key characteristic is: instead of using a meta-grammar (an enhanced dialect
of PEG) to write a grammar which then needs to be translated into a parser, one
defines the parser directly in D, using Pattern types like Literal, Choice,
Option, etc. For instance:
auto sign = new Option(new Klass("+-"));
auto digits = new String(new Klass("0-9"));
auto integer = new Tuple(sign, digits);
writeln(integer.match("-321"));
// should write: "integer:(sign:- digits:321)"
In other words: the grammar is the parser. A big advantage is one needs not
learn and master a new langage. A big drawback is the grammar is verbose -- but
that's ok for me.
Another advantage is one can often express the grammar more elegantly, or solve
difficult issues, by using D features inside the grammar:
lDelim = Character("<"); lDelim = Character(">");
Node tagSection(name) {return Tuple(lDelim, Literal(name), rDelim);)}
boldSection = tagSection("b");
(This defines a kind of super-pattern. Also solves the problem that tags must
match -- no need to keep a stack of open tags.)
I'm facing a 2 issues, 1 about design, 1 about implementation.
First, you may find it weird that I call "Tuple" what is usually named
"Sequence". Actually, a sequence of predefined elements in text, like above,
correspond to tuple fields. The result is a composite node, each child of which
is a node matched by a sub-pattern. Hope you see what I mean.
"Sequence" would be misleading: in fact, repetitive patterns yield sequences
(arrays) of nodes. For instance:
digits = OneOrMore(digit);
writeln(digits.match("321"));
// should write: "digits:[digit:3 digit:2 digit:1]"
For this reason, a TupleNode presently holds an associative array of children
nodes, each indexed by the pattern that yielded it. I find this rather
sensible, and rich in terms of semantics (but see also below). As a result,
when traversing an AST, one can access tuple node fields by key (instead of by
index number), which is imo nicer and more expressive. What do you think?
One issue happens when several fields of the tuple actually are of the same
kind:
addition = new Tuple(operand, PLUS, operand);
In fact, the pattern operand here determines the format of each operand without
telling apart their distinct *roles*. This issue breaks the above dsign, since
both operands would go to the same entry of the associative array. The user
must thus write eg:
rightOperand = leftOperand.copy();
addition = new Tuple(leftOperand, PLUS, rightOperand);
So, I need to make a choice:
1. Keep this design, which forces users to copy patterns in such cases.
2. Let it down, make nodes generated by Tuple patterns hold a plain array
of chil nodes.
3. Have tuple nodes hold both an plain array and an associative array.
4. ???
I'm currently for option 1., because it make the grammar clearer, even if it
requires one more line from the user.
Second, I would like node output (toString) to show pattern *names*, like in
the examples.
Do you find this useful? In my practice, it seems a priceles feature, even if
it makes output more verbose. It especially helps a lot in setting up correct
grammars, commonly a difficult task. Unnamed results miss semantic information.
What do you think?
Nodes presently hold a ref to their pattern, right. But I cannot find a way for
the patterns to know their own names ;-) I do not want the user to have to name
them manually, since they already give the needed information in definitions.
But the said info seems inaccessible at runtime.
One apparent solution would be write the grammar itself in an associative array
of (name:pattern) pairs, then traverse it to set the names on the patterns
themselves. But this does not work because hogher-level patterns need to
reference lower-level ones.
Another approach would be to explore the current scope (symbol table). That's
what I do win dynamic languages. Is this possible in D?
Can you imagine another solution? (Note: .stringof is not a solution, I guess,
since this.stringof yields "this"!)
This feature is also highly useful when writing out patterns themselves:
subpatterns are called by their names. For instance, integer shows as "(sign
digits)". The only alternative is to fully expand subpatterns, and
subsubpattern.., which quickly leads to unreadable mess like regexes. The same
advantage helps in having clear match failure error messages: the failing
pattern shows in a readible manner.
It would also give an alternative for tuple nodes: keys could be pattern names
instead of patterns themselves; which is more flexible since a tree can then be
traversed by a routine lying in a scope where pattern definitions are not
available (eg the parser can be written in a module).
Thank you,
Denis
-- -- -- -- -- -- --
vit esse estrany ☣
spir.wikidot.com