Add location tracking, syntax error and invalid character reporting

[pitree.git] / README.md

NDCODE project

# PiTree: Specification Language for Abstract Syntax Trees

## Introduction

The πtree program is a companion program to πlex and πyacc. It implements a
specification language for abstract syntax trees. In general you will have a
lexical specification such as `my_language.l`, a grammar specification such
as `my_language.y`, and an AST specification such as `my_language.t`. These
will be compiled by πlex, πyacc, and πtree respectively. Then when you run the
generated lexer/parser it will instantiate classes from the AST specification.

The `my_language.t` AST specification is formatted something like a Lex or
YACC specification. It has three parts, separated by %% lines. The parts are
(i) directives and header information, (ii) the class declarations for the
different objects that can be in an AST, in a C++-like syntax, (iii) free-form
code which is appended to the πtree output and can contain subroutines, etc.
Note that in πtree the free-form section serves a second purpose, which is to
attach methods to the classes declared in the classes section. We do this with
regular Python syntax, including a decorator that we provide for this purpose.

It is possible to define your own class hierarchy to use with πlex and πyacc,
without using πtree. You can either define action code in your Lex and YACC
specification to instantiate the objects (the traditional way), or you can use
πlex and πyacc's markup syntax embedded within the πlex and πyacc rules, to say
what you want generated. If you do it the latter way, then the classes need to
have a constructor defined in a specific way so that πlex or πyacc can easily
pass in the child nodes of the AST and any field values to store in the node.

The reason why it is convenient to use πtree to define the class hierarchy is
(i) πtree automatically declares the right kind of constructor that can take
the child nodes and field values, and deal with them appropriately by either
storing or passing into the superclass's constructor, (ii) πtree automatically
adds serialization/deserialization methods to the class to/from πtree's XML
format. While you could use `pickle` or similar, the XML format is advantageous
because it is human readable. It embeds the original parsed text, with markup
giving class names and field values from your πlex/πyacc/πtree specification.

## Installation

From PyPI we can install πtree by a command like `pip3 install --user pitree`.
This will put a `pitree` executable in `$HOME/.local/bin` where `$HOME` is your
home directory. You need to make sure this is in your path, so if the directory
`$HOME/.local/bin` is being created for the first time, you may wish to log out
and back in again. At least on Debian systems it will then appear in your path.

As well as the `pitree` executable, the `ndcode.pitree` package needs to be
importable from Python, since the first statement of the generated code (from
running the `pitree` executable) will usually be something like `from
ndcode.pitree import element`. With the installation method recommended above,
this module will be placed somewhere like
`$HOME/.local/lib/python3.6/site-packages/pitree-0.0.1-py3.6.egg/ndcode/pitree/element.py`
where it is accessible to the generated code. 

An alternative way, if you have already checked out the source repository from
`https://git.ndcode.org/public/pitree.git` or similar, is to run a command like
`. ./env.sh` in the root of the repository. This will put the current directory
(the root of the repository) into your `PYTHONPATH`. The source files have been
put in a directory `ndcode/pitree` so you can then `import ndcode.pitree.XXX`.
With this method, instead of just `pitree` you must run `ndcode/pitree/cli.py`.
Also, you'll have to run `make` in `ndcode/pitree` before anything will work.

## Tutorial

We are going to define a simple AST for a four-function calculator language.
The leaf nodes of the tree will be literals expressed as strings like '5.0'.
The non-leaf nodes will be operators. The negation operator will have one
child being the expression to negate. The add/subtract/multiply/divide nodes
will have two children being the expressions to add/subtract/multiply/divide.

### Tutorial: defining a tree

Create a file called `calc.t` containing the following:
```
%{
  from ndcode.pitree import element
%}

%%

class Expression;
class LiteralExpression: Expression;
class NegExpression: Expression;
class AddExpression: Expression;
class SubExpression: Expression;
class MulExpression: Expression;
class DivExpression: Expression;
```

The text is free-form like C, whitespace is insignificant, and statements
are delimited by semicolons. We have given a simple directives section that
defines some Python code to be copied to the output before anything else,
here an `import` statement that imports the `ndcode.pitree.element` module.

Then we have defined an abstract class `Expression`, which acts as a superclass
to the literal and operator expression classes. Finally, we have gone ahead and
defined the other classes, using πtree's `:` syntax to denote the superclass.

Note that `Expression` has an implicit superclass of `element.Element`, using
the `element` module imported in the directives section. Hence, some `element`
module always needs to be imported (but you can use your own `element` module).

### Tutorial: compiling the tree

To compile this specification, run a command like `pitree --python calc.t`.
By default this creates an output file called `t_def.py`. (Similarly, πlex
defaults to creating `lex_yy.py` and πyacc defaults to creating `y_tab.py`,
behaviour which is inherited from the C versions of the tools). The name
`t_def.py` stands for "Tree Definition". You can also specify your own output
file name using `-o`, for example `pitree --python -o calc_def.py calc.t`.

Let us now have a quick look at the generated output, it is pretty simple:
```
# ... copyright stuff (omitted for brevity) ...

import json

# GENERATE SECTION1 BEGIN
from ndcode.pitree import element
# GENERATE END

# GENERATE SECTION2 BEGIN
class Expression(element.Element):
  tag = 'Expression'
class LiteralExpression(Expression):
  tag = 'LiteralExpression'
class NegExpression(Expression):
  tag = 'NegExpression'
class AddExpression(Expression):
  tag = 'AddExpression'
class SubExpression(Expression):
  tag = 'SubExpression'
class MulExpression(Expression):
  tag = 'MulExpression'
class DivExpression(Expression):
  tag = 'DivExpression'
tag_to_class = {
  'Expression': Expression,
  'LiteralExpression': LiteralExpression,
  'NegExpression': NegExpression,
  'AddExpression': AddExpression,
  'SubExpression': SubExpression,
  'MulExpression': MulExpression,
  'DivExpression': DivExpression
}
# GENERATE END

def method(_class):
  def decorator(func):
    setattr(_class, func.__name__, func)
    return func
  return decorator

# GENERATE SECTION3 BEGIN
# GENERATE END
```

The wanted classes are just defined as regular Python classes, and there is
a small amount of stuff to support serializing/deserializing. The `tag` field
of each class is for serializing and converts a class to a textual name, the
`tag_to_class` dictionary is for deserializing and goes the other way. The
`method` function is a decorator, and will be discussed later in the tutorial.
You can insert arbitary code in the SECTION1 and SECTION3 parts of the output.

The `json` import is not referenced in this particular example, but in later
examples it will be used in the generated code to serialize and deserialize
Python native types such as `str`, `int` and so on. This is a bit lazy on our
part, since we know what type is being serialized/deserialized, so we could
generate more specific code to do this, but the `json` way is easier for now.

### Tutorial: serializing the tree

Let us now create a short program which imports and uses the example tree
definition from above. Create a script `serialize.py` containing the following:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def

expression = t_def.AddExpression(
  children = [
    t_def.MulExpression(
      children = [
        t_def.LiteralExpression(text = ['5']),
        t_def.LiteralExpression(text = ['2'])
      ]
    ),
    t_def.LiteralExpression(text = ['7'])
  ]
)
element.serialize(expression, sys.stdout)
```

Make it executable, `chmod a+x ./serialize.py`. For the remaining scripts in
the tutorial, we'll assume that you know to do this step, or that you will run
the scripts via the `python3` command if you prefer them not to be executable.

This program programmatically constructs a simple AST for the calculator
expression `5 * 2 + 7`, and then serializes it to `sys.stdout` for inspection.

Basically all the heavy lifting is done in the `ndcode.pitree.element` module,
via a combination of the utility routine `element.serialize()`, and supporting
methods that we have defined on the superclass `ndcode.pitree.element.Element`.

Run this and redirect the output to a file, e.g. `./serialize.py >expr.xml`.
You should get a file containing something like:
```
<root>
  <AddExpression ref="0"><MulExpression><LiteralExpression>5</LiteralExpression><LiteralExpression>2</LiteralExpression></MulExpression><LiteralExpression>7</LiteralExpression></AddExpression>
</root>
```

The `<root>` and `</root>` tags and the `ref="0"` attribute are added by the
serializer, to support the attachment of arbitrary structures to AST nodes,
such as from semantic analysis. We will not consider such use for now. But note
that when deserializing, the node returned is the one with the `ref="0"` on it.

We have deliberately not indented this in the normal XML way, for reasons that
should become clear further in the tutorial. If we do indent it manually, it
becomes more obvious that this expression is nested like `(5 * 2) + 7`, e.g.:
```
<root>
  <AddExpression ref="0">
    <MulExpression>
      <LiteralExpression>5</LiteralExpression>
      <LiteralExpression>2</LiteralExpression>
    </MulExpression>
    <LiteralExpression>7</LiteralExpression>
  </AddExpression>
</root>
```

### Tutorial: methods on the tree

What we will do now is create a method to perform the requested calculation,
e.g. with the above example tree, it would add 5 and 2, then multiply by 7.

We are going to do this in an object-oriented manner, by defining a method
`evaluate()` on the `Expression` class. This method will be specialized in the
leaf class `LiteralExpression` and the non-leaf classes like `NegExpression`,
so that each class knows how to evaluate itself. For the leaf class this means
creating a number to operate on, for the non-leaf classes this means evaluating
the child nodes and then operating on these results by negation, addition, etc.

We will define these methods in a slightly unconventional way, by attaching
them to the class after the class has been defined. This serves two purposes,
(i) the code generator for classes is simplified since it does not need to
worry about our methods, (ii) our methods can be grouped by method name rather
than by class name, making it easy to see how each class evaluates itself. The
point ii makes our Python code look a bit like Haskell pattern matching code.

To try it, add a free-form section to `calc.t` beginning with `%%`, as follows:
```
%%

@method(Expression)
def evaluate(self):
  raise NotImplementedError
@method(LiteralExpression)
def evaluate(self):
  return float(self.text[0])
@method(NegExpression)
def evaluate(self):
  return -self.children[0].evaluate()
@method(AddExpression)
def evaluate(self):
  return self.children[0].evaluate() + self.children[1].evaluate()
@method(SubExpression)
def evaluate(self):
  return self.children[0].evaluate() - self.children[1].evaluate()
@method(MulExpression)
def evaluate(self):
  return self.children[0].evaluate() * self.children[1].evaluate()
@method(DivExpression)
def evaluate(self):
  return self.children[0].evaluate() / self.children[1].evaluate()
del evaluate
```

The same-named function `evaluate()` is defined a number of times, using the
`@method` decorator to attach the different definitions to different classes.
Unfortunately the `def` statement doesn't know that the decorator has put the
function elsewhere, so it also defines the function in the `t_def` module. To
clean up, we therefore do `del evaluate` after we've done all of the attaching.

In the leaf node method, we refer to text stored in the node by `self.text[0]`.
In the non-leaf node methods, we refer to the child nodes by `self.children[0]`
for the first child, `self.children[1]` for the second child and so on. The
methods simply assume that the correct number of children are present: 0 for
`LiteralExpression`, 1 for `NegExpression`, 2 for `AddExpression` and the rest.

Note that following best Python practice, the abstract class `Expression` also
gets a definition of the method, which raises `NotImplementedError`. It serves
as a catch-all, in case we forget to define it on one of the derived classes.

Don't forget to recompile the tree definition, by `pitree --python calc.t`.
Then, to test the new method, create a script `evaluate.py` as follows:
```
#!/usr/bin/env python3

import t_def

expression = t_def.AddExpression(
  children = [
    t_def.MulExpression(
      children = [
        t_def.LiteralExpression(text = ['5']),
        t_def.LiteralExpression(text = ['2'])
      ]
    ),
    t_def.LiteralExpression(text = ['7'])
  ]
)
print(expression.evaluate())
```
Running `./evaluate.py` should show the answer of evaluating the tree, `17.0`.

### Tutorial: deserializing the tree

To support deserialization, we have to add a tiny bit of boilerplate code to
our tree definition `calc.t` in the free-form section, as follows:
```
def factory(tag, *args, **kwargs):
  return tag_to_class[tag](*args, **kwargs)
```

What this does is, given a tag name and a set of constructor arguments, calls
the appropriate constructor to create the requested node, e.g. it constructs a
`LiteralExpression` when `tag` is set to `'LiteralExpression'`, and so on.

The reason we do this here (instead of doing it automatically in the generated
code) is for expandability. For example, we can define a larger language which
uses `calc.t` as a mini-language for some of its subtrees, with a more complex
factory that can use the `calc.t` factory as a subfactory for particular nodes.

Don't forget to recompile the tree definition, by `pitree --python calc.t`.
Then, to test the deserializer, create a script `deserialize.py` as follows:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def

expression = element.deserialize(sys.stdin, t_def.factory)
print(expression.evaluate())
```

If you still have the `expr.xml` file that you created when testing the
serializer, you can now feed it to the deserializer by running a command like
`./deserialize.py <expr.xml`. It will deserialize, then evaluate the `17.0`.
This is quite powerful, as it makes an existing XML file become "intelligent".

### Tutorial: fields on a node

Suppose we want to cut down the number of different classes in the tree. We now
want to have a `UnaryExpression` class to cover all unary operators, including
the former `NegExpression`, and a `BinaryExpression` class to cover all binary
operators, including the former `AddExpression` and so on. We will keep track
of which kind of operator is requested, by storing it in a field on the node.
We use "field" to mean the same as Python instance variables or XML attributes.

To avoid confusion we'll call the field `unary_operator` for `UnaryExpression`
and `binary_operator` for `BinaryExpression`. For simplicity's sake we'll make
the field contain a Python `str`, even though in it would be more efficient to
make it an `int` containing an enumeration value. πtree supports a fairly rich
type system, subject to types being declared upfront (not Duck typing). We can
have `str`, `int`, `bool`, `list(str)` and so on. It's best to think of this in
a C++-like way, so `list(str)` is similar to `std::vector<std::string>`, etc.

Here is a revised tree definition `calc1.t` using fields, including a factory
to support the deserializer, and an appropriately updated `evaluate()` method:
```
%{
  from ndcode.pitree import element
%}

%%

class Expression;
class LiteralExpression: Expression;
class UnaryExpression: Expression {
  str unary_operator;
};
class BinaryExpression: Expression {
  str binary_operator;
};

%%

def factory(tag, *args, **kwargs):
  return tag_to_class[tag](*args, **kwargs)

@method(Expression)
def evaluate(self):
  raise NotImplementedError
@method(LiteralExpression)
def evaluate(self):
  return float(self.text[0])
@method(UnaryExpression)
def evaluate(self):
  value = self.children[0].evaluate()
  if self.unary_operator == '-':
    return -value
  raise NotImplementedError
@method(BinaryExpression)
def evaluate(self):
  value0 = self.children[0].evaluate()
  value1 = self.children[1].evaluate()
  if self.binary_operator == '+':
    return value0 + value1
  if self.binary_operator == '-':
    return value0 - value1
  if self.binary_operator == '*':
    return value0 * value1
  if self.binary_operator == '/':
    return value0 / value1
  raise NotImplementedError
del evaluate
```

Whilst this is a bit of a contrived example, it illustrates how sometimes an
attribute on a node can be more compact than defining a set of classes for the
different node types. Here it allows some common code, the evaluation of the
child nodes, to be expressed just once for unary and once for binary operators.

To avoid confusion let us compile this to `t_def1.py` instead of `t_def.py`.
Run `pitree --python -o t_def1.py calc1.t`. Then, create an `evaluate1.py`:
```
#!/usr/bin/env python3

import t_def1

expression = t_def1.BinaryExpression(
  binary_operator = '+',
  children = [
    t_def1.BinaryExpression(
      binary_operator = '*',
      children = [
        t_def1.LiteralExpression(text = ['5']),
        t_def1.LiteralExpression(text = ['2'])
      ]
    ),
    t_def1.LiteralExpression(text = ['7'])
  ]
)
print(expression.evaluate())
```

To test the serialization with fields, create a `serialize1.py` as follows:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def1

expression = t_def1.BinaryExpression(
  binary_operator = '+',
  children = [
    t_def1.BinaryExpression(
      binary_operator = '*',
      children = [
        t_def1.LiteralExpression(text = ['5']),
        t_def1.LiteralExpression(text = ['2'])
      ]
    ),
    t_def1.LiteralExpression(text = ['7'])
  ]
)
element.serialize(expression, sys.stdout)
```

Running `./serialize1.py >tree1.xml` should produce output in which the field
values `unary_operator` and `binary_operator` are stored in XML attributes:
```
<root>
  <BinaryExpression binary_operator="&quot;+&quot;" ref="0"><BinaryExpression binary_operator="&quot;*&quot;"><LiteralExpression>5</LiteralExpression><LiteralExpression>2</LiteralExpression></BinaryExpression><LiteralExpression>7</LiteralExpression></BinaryExpression>
</root>

Note that `&quot;` in the above represents `'`, and hence the value stored for
`binary_operator` is actually `'+'` or `'*'` rather than `+` or `*` directly.
The reason for this, is that if the type of the field were say `list(str)`
rather than `str`, it would be necessary to quote the strings in order to be
able to separate the list items. In the future, we might try to quote only if
needed, to produce a more readable file. For now we use Python's `json` module.

The deserializer test program for the new format using fields, is the same as
`deserialize.py` with `t_def` changed to `t_def1`. It prints `17.0` as before.

### Tutorial: storing the whitespace

An important part of the XML serialization process is that it the AST stores
the original parsed text within it, which can be recovered either by stripping
the serialized XML output of all tags, or by calling `element.to_text()` on an
in-memory tree. When in memory, this text is stored in the `text` array of each
node. We saw previously, how leaf nodes can get their text by `self.text[0]`.

Logically, the contents of a node is its fields, and the interleaving of its
text and its children, starting and ending with text. So there is always one
more entry in the `text` array than the `children` array. For example, suppose
a node has 2 children, e.g. the `AddExpression` or `BinaryExpression` nodes
seen in the previous examples. Then it will have 3 pieces of text. Its internal
structure can be summarized `text[0] children[0] text[1] children[1] text[2]`.

We will now show a revised `serialize2.py` which stores some text in the nodes:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def

expression = t_def.AddExpression(
  text = ['', ' + ', ''],
  children = [
    t_def.MulExpression(
      text = ['', ' * ', ''],
      children = [
        t_def.LiteralExpression(text = ['5']),
        t_def.LiteralExpression(text = ['2'])
      ]
    ),
    t_def.LiteralExpression(text = ['7'])
  ]
)
element.serialize(expression, sys.stdout)
```

This would generate the following serialized output:
```
<root>
  <AddExpression ref="0"><MulExpression><LiteralExpression>5</LiteralExpression> * <LiteralExpression>2</LiteralExpression></MulExpression> + <LiteralExpression>7</LiteralExpression></AddExpression>
</root>
```

If we either strip the tags from the XML output (only the `AddExpression` node)
or add a line like `print(element.to_text(expression))` in the test program,
then we can see the stripped version is `5 * 2 + 7` which is more satisfying
than `527` which would have been printed by the earlier versions without text.

Suppose we use πlex, πyacc, and πtree in integrated fashion to parse general
computer languages such as C. Then the text-storage facility is used in leaf
nodes to store things like identifiers, constants and such, and in non-leaf
nodes mainly to store the whitespace separators between tokens. So for example,
a source code formatter can run over the tree adjusting the inter-token space.

Interestingly though, much of the incoming syntax can also be treated as
inter-token space, because it is redundant in respect of the structure imposed
by the AST. For example, suppose the original expression was `5 * (2 + 7)`.
Since the AST already encodes that the `+` node is nested inside the `*` node,
the parentheses are effectively whitespace from the viewpoint of the AST.

To see how this works, consider this `serialize3.py` which uses parentheses:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def

expression = t_def.MulExpression(
  text = ['', ' * (', ')'],
  children = [
    t_def.LiteralExpression(text = ['5']),
    t_def.AddExpression(
      text = ['', ' + ', ''],
      children = [
        t_def.LiteralExpression(text = ['2']),
        t_def.LiteralExpression(text = ['7'])
      ]
    )
  ]
)
element.serialize(expression, sys.stdout)
```

This produces output like:
```
<root>
  <MulExpression ref="0"><LiteralExpression>5</LiteralExpression> * (<AddExpression><LiteralExpression>2</LiteralExpression> + <LiteralExpression>7</LiteralExpression></AddExpression>)</MulExpression>
</root>
```

Whilst it is irrelevant whether the `(` and `)` characters appear inside the
`AddExpression` tags or not, we have placed them outside. This is because in
the parsing stage an `AddExpression` would be recognized first, followed by a
notional `ParenthesesExpression` that contains the parentheses, but does not
actually generate any markup. Using πyacc we can control the markup precisely.

Another time this occurs is when recognizing keyword-delimited structures such
as `for (declaration; expression; expression) statement` in C. In the AST this
would appear as a `ForStatement` class with 4 children: the declaration, the
two expressions and the statement. The keyword `for` and all delimeters are
treated as whitespace, since `ForStatement` already implies the keyword `for`.

### Tutorial: leading and trailing whitespace

In order to be able to store the contents of a source file exactly (plus the
markup that results from recognizing its lexical and grammatical structure),
we need to be able to store the leading and trailing whitespace. To do this,
we will define a root AST node called `AST`. Furthermore, a πtree convention is
to use inner classes for node types that are expected to appear inside others.

Therefore we will create a `calc4.t` with this modification, as follows:
```
%{
  from ndcode.pitree import element
%}

%%

class AST {
  class Expression;
  class LiteralExpression: Expression;
  class NegExpression: Expression;
  class AddExpression: Expression;
  class SubExpression: Expression;
  class MulExpression: Expression;
  class DivExpression: Expression;
};
```

Whilst Python does not have good inner class support in the same way as Java,
it does allow them. Apart from the lexical nesting, the inner classes are
treated as independent from their outer class. We just define them as inner
classes by convention, as it cleans up the namespace and tends to group them.

Compile this with `pitree --python -o t_def4.py calc4.t` and then create an
example `serialize4.py` that has leading and trailing whitespace as follows:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def4

expression = t_def4.AST(
  text = ['/* calculator source file */\n\n', '\n'],
  children = [
    t_def4.AST.MulExpression(
      text = ['', ' * (', ')'],
      children = [
        t_def4.AST.LiteralExpression(text = ['5']),
        t_def4.AST.AddExpression(
          text = ['', ' + ', ''],
          children = [
            t_def4.AST.LiteralExpression(text = ['2']),
            t_def4.AST.LiteralExpression(text = ['7'])
          ]
        )
      ]
    )
  ]
)
element.serialize(expression, sys.stdout)
```

This serializes as follows:
```
<root>
  <AST ref="0">/* calculator source file */

<AST_MulExpression><AST_LiteralExpression>5</AST_LiteralExpression> * (<AST_AddExpression><AST_LiteralExpression>2</AST_LiteralExpression> + <AST_LiteralExpression>7</AST_LiteralExpression></AST_AddExpression>)</AST_MulExpression>
</AST>
</root>
```

Now, the `AST` tag contains a leading comment (treated as whitespace) and some
newlines, then the real AST content (its root is an `AST_MulExpression`), and
finally a trailing newline between the real AST and the end of the `AST` tag.

Note that inner classes must be prefixed with their outer class name at every
reference, e.g. `t_def.AST.MulExpression` in the Python code, and are stored
with underscores in the serialized output, e.g. `AST_MulExpression`. In future
it might be possible to generate the XML without the fully qualified names, for
example just `<MulExpression>...</MulExpression` when inside `<AST>...</AST>`.

### Tutorial: semantic analysis and markup

Another important feature of the serialization format is that arbitrary objects
can be attached to a node, subject to those objects being declared to πtree and
following the ordinary πtree conventions. As well as πtree objects, we can also
attach many Python intrinsic types, such as numbers, strings, lists, and so on.

To attach πtree objects to a node, you simply declare a field of type `ref`.
Whereas basic field types like `int` or `list(int)` store the corresponding
Python intrinsic types, fields of type `ref` store Python references, provided
they refer to a πtree object. Aggregates like `list(ref)` are also available.

Such attached πtree objects are serialized by reference rather than by direct
nesting in the XML file, so that multiple pointers to the same object generate
multiple references to that object rather than multiple copies. Deserialization
reverses the process to reproduce the original structure of Python references.
The `None` value is allowed and will be serialized and deserialized correctly.

Note that for the sake of readability in the generated XML, Python intrinsics
such as lists are not stored by reference, and neither are child nodes. Thus,
they cannot be multiple, and care should be taken to ensure that multiple
pointers to those kinds of objects do not occur in the tree. An exception to
this is, you can attach a reference to a subtree that also has a parent node,
provided there is at most one parent node (the serializer relies upon this).

The following example is based on `calc4.t`, but there are now two kinds of
literal nodes, `IntLiteralExpression` and `FloatLiteralExpression`. Every
expression has a `type` (declared on the base class `Expression` to ensure it
is always present), which refers to either a `IntType` or `FloatType` object.

We'll also create `UnaryExpression` and `BinaryExpression` classes to put the
semantic analysis code on, to take advantage that the semantic analysis does
not really care which operators are involved specifically. The `DivExpression`
will override the default semantic analysis to always generate a `FloatType`.

Create the basic `calc5.t` defining the needed class hierarchy, as follows:
```
%{
  from ndcode.pitree import element
%}

%%

class Type;
class IntType: Type;
class FloatType: Type;

class AST {
  class Expression {
    ref type;
  };
  class IntLiteralExpression: Expression;
  class FloatLiteralExpression: Expression;
  class UnaryExpression: Expression;
  class NegExpression: UnaryExpression;
  class BinaryExpression: Expression;
  class AddExpression: BinaryExpression;
  class SubExpression: BinaryExpression;
  class MulExpression: BinaryExpression;
  class DivExpression: BinaryExpression;
};
```

Add a free-form section beginning with `%%` and a `semantic_analysis()` method:
```
%%

@method(AST.Expression)
def semantic_analysis(self):
  raise NotImplementedError
@method(AST.IntLiteralExpression)
def semantic_analysis(self):
  self.type = IntType()
@method(AST.FloatLiteralExpression)
def semantic_analysis(self):
  self.type = FloatType()
@method(AST.UnaryExpression)
def semantic_analysis(self):
  self.children[0].semantic_analysis()
  self.type = self.children[0].type
@method(AST.BinaryExpression)
def semantic_analysis(self):
  self.children[0].semantic_analysis()
  self.children[1].semantic_analysis()
  self.type = (
    self.children[0].type
  if isinstance(self.children[0].type, FloatType) else
    self.children[1].type
  )
@method(AST.DivExpression)
def semantic_analysis(self):
  self.children[0].semantic_analysis()
  self.children[1].semantic_analysis()
  self.type = FloatType()
```

Compile this to `t_def5.py` by `pitree --python -o t_def5.py calc5.t`, and then
create the corresponding test program `serialize5.py` containing the following:
```
#!/usr/bin/env python3

from ndcode.pitree import element
import sys
import t_def5

expression = t_def5.AST(
  text = ['/* calculator source file */\n\n', '\n'],
  children = [
    t_def5.AST.MulExpression(
      text = ['', ' * (', ')'],
      children = [
        t_def5.AST.IntLiteralExpression(text = ['5']),
        t_def5.AST.AddExpression(
          text = ['', ' + ', ''],
          children = [
            t_def5.AST.IntLiteralExpression(text = ['2']),
            t_def5.AST.FloatLiteralExpression(text = ['7.5'])
          ]
        )
      ]
    )
  ]
)
expression.children[0].semantic_analysis()
element.serialize(expression, sys.stdout)
```

Running this should produce output like
```
<root>
  <AST ref="0">/* calculator source file */

<AST_MulExpression type="3"><AST_IntLiteralExpression type="1">5</AST_IntLiteralExpression> * (<AST_AddExpression type="3"><AST_IntLiteralExpression type="2">2</AST_IntLiteralExpression> + <AST_FloatLiteralExpression type="3">7.5</AST_FloatLiteralExpression></AST_AddExpression>)</AST_MulExpression>
</AST>
  <IntType ref="1" />
  <IntType ref="2" />
  <FloatType ref="3" />
</root>
```

We can see that the `type` attribute of each expression node in the XML gives
an integer, which is a reference to one of the `IntType` or `FloatType` objects
later in the file. The `IntType` and `FloatType` objects are unparented with
respect to the AST, and thus appear as children of the `<root>...</root>` node.

We can also see that due to some optimization in the `semantic_analysis()`
method of the `BinaryExpression` class, which reuses the type of either the
left child or the right child as appropriate, many of the type references are
the same. This makes it fairly cheap to add the semantic information to a node.

The efficiency of this approach is highlighted for semantic analysis with more
complicated type systems, for example in C we can have "int", "pointer to int",
"pointer to pointer to int", "array of int" and so on. There can be a lot of
reuse, e.g. consider the "address of" operator in C -- the "address of" node
has a type of a "pointer to" node, containing a reference to the child's type.