Shaping Trees

A PEGO grammar does two jobs: it decides which input is valid, and it decides what tree you get back. This guide is about the tree that every grammar produces without any extra work and how to shape it with captures, atomic (#atomic), discard (-) and hidden rules (_name). Declaring Types describes the typed nodes of a grammar, and Actions shows how to replace the tree with a typed AST built by actions.

The guide complements the normative chapters Rule Expressions, Type System and Actions; read them for the exact rules. Here the focus is on how and why to use each feature. For operator expressions (foldl chains versus Operators Rule Declaration Statements), see the companion guide Operators Rule.

Every grammar and output below was produced by running it. To follow along, put each grammar in the file named on its first line and run the command shown, using either the installed tool or go run ./cmd/pego from a checkout:

go install github.com/ornew/pego/cmd/pego@latest

pego parse -g <grammar> -s <rule> -i '<input>' -f sexpr parses the input with the start rule <rule> (default main), which must match the whole input, and prints the tree.

#Reading a Tree

Start with the smallest grammar that has some structure:

// assign.pego
@start
rule main = ^^ assign $$
rule assign = name ws "=" ws value ";"
rule name = [a-z]+
rule value = number / name
rule number = [0-9]+
rule ws = " "*

pego parse -g assign.pego -f sexpr -i 'ab = 12;'

((["a" "b"] [" "] "=" [" "] ["1" "2"] ";"))

The sexpr format is a compact notation for values:

Reading the output above from the inside out: name is the repetition [a-z]+, so it is a list of one string node per letter (shown as ["a" "b"]). ws is also a list (of spaces), and value is number, so the node is the list of digits. assign is a sequence, so a tuple of its six valued elements; and main wraps that in another tuple, because ^^ and $$ have no value and the sequence therefore has a single element.

Source information adds the rule that produced each node and the names of the captures. It is off by default, because most programs do not need it; ask for it with -source-info (pego.WithSourceInfo() in Go):

pego parse -g assign.pego -f sexpr -source-info -i 'ab = 12;'

((["a" "b"]@name [" "]@ws "=" [" "]@ws ["1" "2"]@number ";")@assign)@main

x@name means that the node x is the value of the rule name. Only the value of a rule is labeled: the elements of a tuple that come from literals, like the "=" above, are not.

The default JSON format carries the same information and adds positions. Here is a rule with an optional element:

// optional.pego
@start
rule main = name ("," name)?
rule name = [a-z]+ #atomic

pego parse -g optional.pego -i 'a'

{
  "start": 0,
  "end": 1,
  "value": [
    {
      "start": 0,
      "end": 1,
      "value": "a"
    },
    null
  ]
}

#The Default Tree

If a rule has no action, its value is determined by the shape of the Rule Expression alone. The rules are short enough to memorize:

A sequence with no valued element has the unit () as its value.

Three consequences are worth knowing before you write any action.

One value per rule, and rule names. A rule produces exactly one value. With source information, a node that a rule creates in its own body is labeled with the rule's name; a node that comes from another rule keeps that rule's label.

// cst.pego
@start(default)
rule seq = "y" "z"
@start
rule alt = "x" / "y" "z"
rule one = "x"
@start
rule same = one
@start
rule rep = "x"*
@start
rule opt = "x"?
@start
rule cap = k:"x" "y"

pego parse -g cst.pego -s seq -f sexpr -source-info -i 'yz'
pego parse -g cst.pego -s alt -f sexpr -source-info -i 'x'
pego parse -g cst.pego -s alt -f sexpr -source-info -i 'yz'
pego parse -g cst.pego -s same -f sexpr -source-info -i 'x'
pego parse -g cst.pego -s rep -f sexpr -source-info -i 'xxx'
pego parse -g cst.pego -s opt -f sexpr -source-info -i 'x'
pego parse -g cst.pego -s cap -f sexpr -source-info -i 'xy'

("y" "z")@seq
"x"@alt
("y" "z")@alt
"x"@one
["x" "x" "x"]@rep
"x"@opt
(k:"x" "y")@cap

same yields the node labeled @one, not @same. The choice alt yields a string node or a tuple depending on the alternative, which is why it is called transparent (the reasoning is in design record 002). In cap, the capture k names the first element of the tuple; see Captures.

Only valued elements are in the tuple. In "(" expr ")" the two parentheses are elements of the tuple, next to the expression. To keep them out, discard them with -; do the same for whitespace and separators.

The start rule must consume the whole input. Remaining input is a syntax error ("expected end of input"), so the start rule needs no $$ for that. What it does need is to consume trailing whitespace and comments explicitly.

#Shaping the Tree

#Atomic and Discard

a #atomic matches a and produces one string node holding the matched text, instead of the tree of a. Use it for tokens: a number is one node, not a list of digits. -a matches a and produces nothing. Use it for input the syntax needs but the tree does not:

// shape.pego
@start
rule main = ^^ assign $$
rule assign = name -ws -"=" -ws value -";"
rule name = [a-z]+ #atomic
rule value = number / name
rule number = [0-9]+ #atomic
rule ws = " "*

pego parse -g shape.pego -f sexpr -source-info -i 'ab = 12;'

(("ab"@name "12"@number)@assign)@main

Compare this with the tree in Reading a Tree: the same input now yields a tuple of just two string nodes (inside the tuple of main). Both operators suppress construction, so they are also cheaper (see Performance Guidelines). Because captures are meaningless inside them, (k:"x" "y") #atomic and -(k:"x" "y") are compile errors.

#Captures

A capture label:a gives the value of a a name that actions and predicates can use as $label. Without an action, a capture does not change the value of the rule; it only names an element of it, which source information shows as label: before the element. A capture removes nothing from the tuple.

// capture.pego
@start(default)
rule pair = k:name -ws -"=" -ws v:value -";"
rule name = [a-z]+ #atomic
rule value = number / name
rule number = [0-9]+ #atomic
rule ws = " "*
@start
rule list = name ("," n:name)*
@start
rule list2 = name (-"," n:name)*

pego parse -g capture.pego -s pair -f sexpr -source-info -i 'ab = 12;'
pego parse -g capture.pego -s list -f sexpr -source-info -i 'a,b,c'
pego parse -g capture.pego -s list2 -f sexpr -source-info -i 'a,b,c'

(k:"ab"@name v:"12"@number)@pair
("a"@name [("," n:"b"@name) ("," n:"c"@name)])@list
("a"@name [(n:"b"@name) (n:"c"@name)])@list2

Note how k and v label the two elements of the tuple. A capture inside a repetition belongs to the scope of one iteration: each element of the list is a tuple that carries the capture n. If the iteration's value is not a tuple the engine wraps it in one, so that the capture has somewhere to live. This is what makes $rest in foldl($first, $rest, (acc, i) => ... i.$n ...) work (see the recipes).

Two details matter in practice:

• A capture that did not match (inside ? or in only some alternatives of a choice) is nil, and its type is optional (*T).
• A captured value keeps its whole subtree. If you capture a repetition such as rest:(ws "," ws x:ident)*, every whitespace node inside it stays in the value, because you may inspect it with x[i] or text later. Discard the parts you do not need inside the capture, punctuation included: rest:(-ws -"," -ws x:ident)*.

#Hidden Rules

A rule whose name begins with _ is hidden: it lets you share part of a grammar without adding a level to the tree. A visible rule makes a node, so a call of it nests its elements one level deeper. A hidden rule without an action makes no node of its own: its elements are spliced into the sequence that calls it, as if its expression were written there as a group.

// hidden.pego
@start(default)
rule shown = "(" items ")"
rule items = [a-z] ("," [a-z])*
@start
rule hidden = "(" _items ")"
rule _items = [a-z] ("," [a-z])*

pego parse -g hidden.pego -s shown -f sexpr -source-info -i '(a,b,c)'
pego parse -g hidden.pego -s hidden -f sexpr -source-info -i '(a,b,c)'

("(" ("a" [("," "b") ("," "c")])@items ")")@shown
("(" "a" [("," "b") ("," "c")] ")")@hidden

shown has a node @items inside its tuple; in hidden the first letter and the list of the rest are elements of the tuple of hidden itself. A hidden rule is still a rule at run time (memoized, recursive, with its own cut and recovery scope), but it is not an entry point, adds no type to the AST and does not expose its captures to the caller. The exact rules are in Hidden Rules; Actions describes the hidden rules that inline actions create.

#Unwrapping the Root

A start rule such as main = ^^ expr $$ wraps the real result in a tuple. When you build an AST, return the value you want instead:

@start
rule main Expr = e:expr $$ => $e

This is the idiom of the calculator example.

#Using the Tree From Go

Parser.Parse returns a *pego.Node, which is opaque: Kind() says whether it is a string node, a tuple, a list, an error value or a struct, and the methods that fit the kind read it: Start() and End(), Text(), Len(), Elem(i) and Elems(), Field(name) and Fields() for the fields of a struct, and Value(). Rule() and the capture names are there only if the parser was compiled with pego.WithSourceInfo(). Reading values is covered in Reading Trees, walking the tree and selecting nodes by position in Walking Trees, and the node model is defined in Nodes and Values.

#Performance Guidelines

PEGO builds values only where something can observe them. To reduce allocations, help the engine identify what your grammar does not need:

1. Discard trivia inside captured expressions with -x: rest:(-ws -"," -ws v:value)*. The engine cannot drop it automatically, because a captured value exposes its whole subtree.
2. Use #atomic for tokens. Their bodies are matched without building values: an identifier is one node instead of one node per character.

How much do they matter? Parsing one 140 KB list of 20,000 identifiers separated by " , " with the default backend allocated, measured around a single Parse call with runtime.MemStats:

These choices matter most when a grammar captures many repeated values. Measure your own input and inspect the resulting tree to ensure that discarding text does not remove information your application needs.

If you only need to know whether the input is valid, use pego parse -check (pego.RecognizeOnly()): it builds no values and runs no actions.

#Troubleshooting

#Related Topics

• Declaring Types: struct and join types.
• Actions: building the tree yourself, and the hidden rules behind inline actions.
• Rule Expressions: the expressions that the tree is made of.
• Reading Trees: reading the result in Go.