Tcl Library Source Code

View Ticket
Login
Ticket UUID: dd79d8540e1468e7c32a8579efb31ac0545cfe8
Title: More documentation: How to write your grammar
Type: RFE Version:
Submitter: lars_h_again Created on: 2024-01-21 22:02:44
Subsystem: pt (parsetools) Assigned To: nobody
Priority: 5 Medium Severity: Minor
Status: Open Last Modified: 2024-01-21 22:02:44
Resolution: None Closed By: nobody
    Closed on:
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.