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=""+"" ref="0"><BinaryExpression binary_operator=""*""><LiteralExpression>5</LiteralExpression><LiteralExpression>2</LiteralExpression></BinaryExpression><LiteralExpression>7</LiteralExpression></BinaryExpression>
+</root>
+
+Note that `"` 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.
public / pitree.git / commitdiff