| Description: |
It would be useful for the **pt** documentation suite to also include a
collection of recommendations / tips / advice on how to design your
grammar, since things that are equivalent for one perspective may be very
different for another, with a span all the way from "easy" to "infeasible"
for operations that one might not think about early in the work.
In want of such advice, users are likely to seek good practices primarily
by looking at the examples shown in the documentation. Unfortunately, I
have come to realise that some of those practices have notable downsides.
Suggested recommendations
-------------------------
These are in no particular order. Some go against practices in the
existing examples, other elaborate upon practices seen.
### End of file
If the starting expression is supposed to consume the entire input (as
opposed to just a prefix of it) then the end-of-file idiom `!.` should be
placed at the end of the starting expression. What one should *not* do is
bury the `!.` in some `EOF` nonterminal, and then further bury this
nonterminal inside another nonterminal.
**Motivation.**
Changing a grammar from "exactly one Thing" to "starting with a Thing" is
something that one occationally wishes to do, for example because a file
begins with a Thing and is then followed by something else, or because a
file is contains a sequence of Things; there is also the application of
searching for a Thing within a larger file. If the end-of-file constraint
appears as the final item in the starting expression then it is
straightforward to programmatically remove it, but if it is buried inside
a nonterminal a couple of levels down then reliably pulling it out becomes
infeasible.
### Optional items
Don't place optional children both at the start and at the end of a
nonterminal. The problem is not in the parsing — that could still be
unambiguous — but that the resulting AST becomes more cumbersome to
process further. Instead have one inner nonterminal acting as container
for variation on one end and an outer nonterminal containing variation at
the other end.
### Whitespace in nonterminals
Don't include initial or final whitespace in nonterminals from which you
will later need to extract the string representation, such as identifiers.
This saves you from having to strip off that whitespace later.
### Nonterminals for fixed text
Make separate nonterminals for fixed tokens, e.g.
```
PLUS <- "+" ;
MINUS <- "-" ;
TIMES <- "*" ;
```
even if the explicit literal strings, or a character class `[-+*]`,
is far more compact to write than `(PLUS / MINUS / TIMES)`. The reason for
having these nonterminals is they will make the tokens show up as distinct
nodes in the AST, which makes the information on what operation is at hand
far more easily available than if you have to retrieve it from the input
text.
This kind of fixed text nonterminal may, without complicating further
processing, include whitespace and form variations (e.g. both `!=` and `<>`
for inequality); we don't care about the node beyond from what nonterminal
it was made.
An exception is if the operation is apparent from the context, for example
```
Product <- Factor ( TIMES Factor )* ;
```
In this case you don't want separate nodes for the *TIMES*, because they
convey no information beyond what you learn from the *Product* parent.
### Pure choice between alternatives
It is often intuitive to have a nonterminal that is a big choice between
possible forms, e.g.
```
Literal <- IntegerLiteral / RealLiteral / StringLiteral / BooleanLiteral ;
```
However, that gives rise to a *Literal* node in your AST which is rarely
useful, and has always exactly one child. Replacing uses of that
*Literal* nonterminal with its definition would result in a more succint
AST. Of course, if *Literal* is referenced in several different places
in the grammar then that might prove impractical, but it is still worth
considering.
### Nonterminals for semantic nodes
A judicious rearrangement of material can sometimes move the AST closer to
its semantic content. Instead of `Prefix`, where
```
Prefix <- (AND / NOT)? Suffix ;
leaf: AND <- "&" WHITESPACE ;
leaf: NOT <- "!" WHITESPACE ;
```
we could have `(AndPrefix / NotPrefix / Suffix)` where
```
AndPrefix <- "&" WHITESPACE Suffix ;
NotPrefix <- "!" WHITESPACE Suffix ;
```
An *AndPrefix* node in the AST corresponds exactly to applying `&` to the
child parsing expression, whereas a *Prefix* node might correspond to
spplying `&`, applying `!`, or doing nothing — it needs to look at its
first child to tell.
The downside of this transformation is that *Suffix* is another
nonterminal giving rise to nodes that might apply some operation, or might
not. Applying it another step, we arrive at
```
PrimaryStar <- Primary "*" WHITESPACE ;
PrimaryPlus <- Primary "+" WHITESPACE ;
PrimaryOpt <- Primary "?" WHITESPACE ;
AndPrefix <- "&" WHITESPACE
(PrimaryStar/PrimaryPlus/PrimaryOpt/Primary) ;
NotPrefix <- "!" WHITESPACE
(PrimaryStar/PrimaryPlus/PrimaryOpt/Primary) ;
```
and instead of `Prefix` or `(AndPrefix / NotPrefix / Suffix)`, we have to
say `(AndPrefix / NotPrefix / Suffix / PrimaryStar / PrimaryPlus /
PrimaryOpt / Primary)`. The number of choices do not explode — because we
only add variants from different levels, not multiply them — but it's
still fairly bad. :-(
A good thing one may observe in this example is how, while attempting to
match a `PrimaryStar`, the parser will first match a `Primary` and then
memoize how that went, so that the matching of `PrimaryPlus`,
`PrimaryOpt`, and `Primary` will not have to do that work again.
|