Abstract Syntax Tree
APM builds the AST for you while it parses. Every syntac action becomes a node with its units beneath it, and that default is what most grammars want.
A := B . C; # A, with B and C as its children, in that order
When the shape you want is not the shape the grammar had to be written in, an AST map says what to build instead.
Writing a map
A map is -> followed by the shape, and the body it maps must be in
parentheses:
(<body>) -> (<map>)
Inside the map you name the units of the body. Their order in the map is their order in the tree, whatever order the body matched them in:
stmt := (name . number) -> (number name); # number first in the tree
Anything you leave out is discarded:
paren := ("(" . expr . ")") -> (expr); # the brackets do not survive
A map never changes what was matched. It only decides what is kept and where it hangs.
Making one a parent
A: (B C) keeps A as a node and puts B and C underneath it instead of
beside it. A parent can itself be a child, so this nests:
pair := (name . number) -> (name: (number));
deep := (a . b . c) -> (a: (b: (c)));
A name means every unit of that name
This is the rule the whole map works by, and it is worth saying plainly: a name in a map means every unit of that name in the body, and they all go to the same place.
X := (A . A . B) -> (B: (A));
Over a a b, both As land under B. A counter is the same idea — one
instruction making many nodes, all going to the one slot.
Used as a parent, the name still means all of them, so the most recent one is the one that takes the children:
X := (A . A . B) -> (A: (B)); # the second A is B's parent
That is not a mistake to be reported. If you meant one of them in particular, label it.
Reaching into a choice
A map can name something that only one alternative produces:
X := (A . (B | C) . D) -> (A: (C)); # C when C matched; nothing when B did
Or it can name the choice itself, when either side is wanted in the same place. This is the form to reach for when a symbol appears in every alternative:
X := (A . (B | C) . D) -> (A: ((B|C)) D); # whichever one matched
Writing (B|C) says “the thing this choice produced”, so the map does not have
to be written twice.
[A] — lift a node’s children
Square brackets ascend: whatever A held takes A’s place, and A itself
is dropped. It moves one level; what those children held stays put.
Given P := A . B; the difference is:
X := (P . C) -> (C: (P)); # (X (C (P (A) (B)))) P stays
X := (P . C) -> (C: ([P])); # (X (C (A) (B))) P goes, A and B arrive
X := (P . C) -> ([P] C); # (X (A) (B) (C)) at the top
X := (P . C) -> (C [P]); # (X (C) (A) (B)) keeping its place
An ascended node keeps the position it had among its siblings; only the level goes. This is how you flatten one wrapper that the grammar needed but the tree does not.
[A] as a parent
[A]: (X) lifts A’s children as above, and X hangs under the last of
them — the same rule a repeated name follows, where the children go to the last
one. Given P := A . B;:
X := (P . C) -> ([P]: (C)); # (X (A) (B (C))) C under the last thing P held
If A held nothing, there is nothing for X to hang on, so X ascends
with it: it lands where A would have gone, beside A’s siblings. That is the
natural shape for a header that is a charseq:
Section := (SectionHeader LineBreak (SectionItem)*)
-> ([SectionHeader]: ([SectionItem]));
node("Name") — a node nothing matched
Every other entry in a map points at something the body already produced. This one is made because the map asks for it.
made := (name => texvar v) -> (name node("Extra", v));
Once made it is a node like any other: it can be a parent, it can be a child, and it nests.
wrap := (a . b) -> (node("Group"): (a b)); # a made node as the parent
The second argument names a variable, and the text that variable holds becomes the node’s value — a span of the input, like every other node’s value. Nothing anywhere invents text. Without it you get a node with a name and no value.
Because the node is emitted at the end of the body, a variable it reads has already been written by the time it runs.
node("Name", C) — renaming what a unit made
When the second argument is a unit of the body rather than a variable, no
new node is made: the node C made is the one placed, renamed. It keeps its
span and its children, and goes where the node() stands.
Section := (SectionHeader LineBreak (SectionItem)*)
-> (node("SectionH", SectionHeader): ([SectionItem]));
Every section comes out as a SectionH holding its header’s text, with the
items under it. As a parent, the renamed node keeps the children it already
had, and what the map hangs under it follows them.
Anything a map can name can be renamed: a rule, a label, a literal, a character block, a linked call.
If C did not match — it sits in an alternative that was not taken — nothing is placed.
A plain name must be one or the other: a name that is both a unit of the body and a variable is refused (
E-astmap-node-both), and so is one that is neither (E-astmap-undef).node("Name", [C])is not accepted. Renaming the root of what C made is already whatnode("Name", C)does.
Everything is reachable
A map names a maker the way it is written. An action by its name, a literal by itself, a character block by the block text, a linked call by the whole qualified name:
X := (<a:z> . B) -> (B: (<a:z>));
Y := (javascript::stmt . B) -> (B: (javascript::stmt));
There is no kind of maker a map cannot point at.
Note
A character block only makes a node when ast-node-char is on — see
Config Settings. A map can name it either way, but with
that setting off there is no node to place.
Labels — telling two of the same apart
A plain name already means all of them, so you only need a label when two units of one name must go to different places. A label is written in single quotes, directly against the unit with no space:
swap := ('a'name . 'b'name) -> ('b' 'a');
A labelled unit answers only to its label, which is what leaves the plain name free for the other one. Labels exist only for the map they appear in and never reach the parser.
Note
A map that says exactly what the body already says is fine. It is dropped, and costs nothing:
z := (A . B) -> (A B); # the same as writing no map at all
Deleting one entry from a map is an ordinary edit, and the moment before the next keystroke should not be an error.
Important
A map may place each thing once. Naming the same unit in two places is refused — a node has one parent, and a map that asked for two would have to copy it.
'h'X — what a left-recursive rule has built
In a rule that calls itself on the left, the leading self-reference is cut by the machine — it has to be, or the rule would never terminate. A label on it names what the rule has built so far, and the parent takes it as its first child:
p := ('h'p . "[" . n . "]" | n) -> (node("index"): ('h' n) | n);
Over 1[2][3]:
index
├── index
│ ├── n "1"
│ └── n "2"
└── n "3"
The accumulated side is always the first child. A map that wants it somewhere else is asking for a fold, and a fold is what a binding power table is for.
Side roots — root_node and >>
Some nodes belong to the whole parse rather than to the place they matched: comments a formatter has to keep, declarations a symbol table wants together. A side root collects them.
root_node comments;
declares one. An action sends nodes to it with >>, after its map if it has
one:
item := (stmt . comment?) >> comments:(comment); # comment goes to the root
note := (hash . text) >> comments; # everything note makes goes
>> root:(...)sends what it names. It is a map of its own, read against the same body: anything it names leaves the tree, and what the map hangs under that stays under it. Without a->, everything it does not name stays where it would have been.>> rootwith no map sends everything the body makes. The action itself stays where it was, with no children — so it stands alone: a->or another>>beside it is an error (E-root-map).One unit goes to one place — the tree or one root — never two (
E-astmap-twice).
The result holds each root that got anything as a node of its own after the parse’s roots, in the order the roots were declared, with its nodes in the order they appear in the input:
item ...
comments
├── comment "# first"
└── comment "# second"
A node is only sent once its attempt succeeds. An alternative that matched a comment and then failed sends nothing, exactly as its nodes never reach the tree.
Renaming with node_id
A node is named after the action that made it. node_id changes the name it is
saved under, while the grammar goes on calling the action by its label.
node_id {
perm_unit: "perm",
ident_node: "identifier",
};
The reason this exists: when the name you want is a keyword. Every word the
language spells out is reserved, so no action can be called
perm, char or end. Label the action something else and use node_id to
save it under the name you actually wanted.
APM’s own grammar does exactly that — its rule for a permutation is labelled
perm_unit and saved as perm.
The saved name must be a usable identifier — letters, digits and underscore, not starting with a digit. Whatever reads the tree will have to write that name in its own source, so a name with a space or a dash in it is refused.
Each action may be renamed once, and no two actions may end up saved under the same name.
See also
Whether literals become nodes at all, and whether adjacent ones merge, is settled by Config Settings — worth reading before you reach for a map, because several shapes are a config change rather than a rewrite.