--- jupytext: formats: md:myst text_representation: extension: .md format_name: myst kernelspec: display_name: Python 3 language: python name: python3 --- (sec:derivation-tree)= # Derivation Tree Reference ```{code-cell} :tags: ["remove-input", "remove-output"] from myst_nb import glue from fandango.language.tree import DerivationTree from fandango.language.symbols import NonTerminal t = DerivationTree(NonTerminal('a string')) number_of_methods = len(dir(t)) + len(dir(str)) glue("number_of_methods", number_of_methods) ``` Fandango constraints make use of _symbols_ (anything enclosed in `<...>`) to express desired or required properties of generated inputs. During evaluation, any `` returns a _derivation tree_ representing the composition of the produced or parsed string. This derivation tree has a type of `DerivationTree`, as do all subtrees. `DerivationTree` objects support *{glue:}`number_of_methods` functions, methods, and operators* directly; after converting `DerivationTree` objects into standard Python types such as `str`, the entire Python ecosystem is available. ```{mermaid} classDiagram class DerivationTree{ to_string(encoding: str = "latin-1") str bytes() str to_bytes(encoding: str = "utf-8") str to_int(encoding: str = "utf-8") str should_be_serialized() bool contains_bits() bool to_bits(encoding: str = "utf-8") str is_terminal() bool is_nonterminal() bool getitem(n: int) DerivationTree getitem(n: int, s: slice) DerivationTree children() list[DerivationTree] children_values() list[TreeValue] descendants() list[DerivationTree] descendant_values() list[TreeValue] parent() DerivationTree | None, sources() list[DerivationTree] __eq__(DerivationTree | str | bytes | int) bool __ne__(DerivationTree | str | bytes | int) bool to_bits() str to_grammar() str to_tree() str __repr__() str __str__() str } click DerivationTree href "#" "Fandango DerivationTree class" ``` (sec:derivation-tree-structure)= ## Derivation Tree Structure Let's have a look at the structure of a derivation tree. Consider this derivation tree from the [ISO 8601 date and time grammar](ISO8601.md): :::{margin} Note that nonterminals can be empty strings, such as the second child of ``. ::: ```{code-cell} :tags: ["remove-input"] from Tree import Tree tree = Tree('', Tree('', Tree('', Tree('', Tree('', Tree(''), Tree('', Tree('2')), Tree('', Tree('0')), Tree('', Tree('2')), Tree('', Tree('5')) ), Tree('-'), Tree('', Tree('10')), Tree('-'), Tree('', Tree('27')) )), Tree('') )) tree.visualize() ``` The elements of the tree are designated as follows: Node : Any connected element of a tree. Child : An immediate descendant of a node. In the above tree, the `` node has one child, ``. Descendant : A child of a node, or a descendant of one of its children. `` is a descendant of ``. All nodes (except the root node) are descendants of the root node. Parent : The parent of a node $N$ is the node that has $N$ as a child. `` is the parent of ``. Root : The node without parent; typically ``. Terminal Symbol : A node with at least one child. Nonterminal Symbol : A node without children. Concatenating all terminal symbols (using `str()`) in a derivation tree yields the string represented. For the above tree, this would be `2025-10-27`. ## Evaluating Derivation Trees To write constraints, you may want to serialize derivation trees into standard Python types such as `str`ings, `bytes`, or `int`s. To do so, simply call `str()`, `bytes()`, or `int()` respectively. Internally, the serialization is done in `str` objects as long as the subtree only contains string values, and in `bytes` otherwise. During concatenation, strings are converted to bytes in with `utf-8` encoding, for conversion from bytes to strings, `latin-1` is used to prevent breaking non-utf-8 strings. If you would like to convert them using utf-8, you can call `.to_string("utf-8")`. Concatenation of non-bit types with bit types always triggers Fandango to convert the remaining trailing bits into `bytes` (with the first bit being the most significant). If the number of trailing bits isn't a multiple of 8, Fandango will throw an error. `int()` on a subtree consisting only of strings will attempt to parse the string as a number. If the tree consists of bits only, it will be converted to a number with the first bit being the most significant. Bytes are converted to strings and then treated accordingly. ```{deprecated} 1.0 Previous versions of Fandango automatically converted certain values — this no longer works to prevent accidental mistakes while writing constraints. ``` ```{tip} It is generally unwise to rely on the type of the internal representation of linearized `DerivationTree` values as these may change with future expansions of Fandango. Use functions directly implemented on them (`.startswith("Hello")`), or explicitly convert them to a base type in Python instead (`str()`). ``` ## General `DerivationTree` Functions These functions are available for all `DerivationTree` objects, regardless of the type they evaluate into. ### Converters Since any `` has the type `DerivationTree`, one must convert it first into a standard Python type before passing it as argument to a standard Python function. `str() -> str` : Convert `` into a Unicode string. Byte strings in `` are converted using `latin-1` encoding. `.to_string(encoding: str = "latin-1") -> str` : More flexible alternative to `str()` `bytes() -> bytes` : Convert `` into a byte string. Unicode strings in `` are converted using `utf-8` encoding. `.to_bytes(encoding: str = "utf-8") -> bytes` : More flexible alternative to `bytes()` `int() -> int` : Convert `` into an integer, like the Python `int()` function. `` must be exclusively bits, or a Unicode string or byte string representing an integer literal. `.to_int(encoding: str = "utf-8") -> int` : More flexible alternative to `int()` `.should_be_serialized_to_bytes() -> bool` : Returns `True` if the sub-tree contains bits or bytes and thus is natively serialized to bytes `.contains_bits() -> bool` : Returns `True` if the sub-tree contains bits `.contains_bytes() -> bool` : Returns `True` if the sub-tree contains bytes `.to_bits(encoding: str = "utf-8") -> int` : Provides a bitwise representation of the input, in a string of `0`s and `1`s `.is_terminal() -> bool` : True if `` is a terminal node. `.is_nonterminal() -> bool` : True if `` is a nonterminal node. ### Accessing Children `len() -> int` : Return the number of children of ``. ```{important} To access the length of the _string_ represented by ``, use `len(str())`. ``` `[n] -> DerivationTree` : Access the `n`th child of ``, as a `DerivationTree`. `[0]` is the first child; `[-1]` is the last child. ```{important} To access the `n`th _character_ of ``, use `str()[n]`. ``` `[start:stop] -> DerivationTree` : Return a new `DerivationTree` which has the children `[start]` to `[stop-1]` as children. If `start` is omitted, children start from the beginning; if `stop` is omitted, children go up to the end, including the last one. `.children() -> list[DerivationTree]` : Return a list containing all children of ``. `.children_values() -> list[TreeValue]` : Return a list containing the values of all children of ``. ```{note} `TreeValue` objects can be converted into standard Python objects with `str()`, `bytes()`, or `int().` Alternatively, use the same base functionality from `str`, `bytes`, and `int` on them directly that is [implemented on entire `DerivationTree`s](sec:derivation-tree-direct-access-functions). ``` ` in ` : Return True if ` == CHILD` for any of the children of ``. `VALUE in ` : Return True if `VALUE == CHILD.value()` for any of the children of ``. ### Accessing Descendants `.descendants() -> list[DerivationTree]` : Return a list containing all descendants of ``; that is, all children and their transitive children. `.descendant_values() -> list[TreeValue]` : Return a list containing the values of all descendants of ``; that is, the values of all children and their transitive children. ```{note} `TreeValue` objects can be converted into standard Python objects with `str()`, `bytes()`, or `int().` Alternatively, use the same base functionality from `str`, `bytes`, and `int` on them directly that is [implemented on entire `DerivationTree`s](sec:derivation-tree-direct-access-functions). ``` ### Accessing Parents `.parent() -> Optional[DerivationTree]` : Return the parent of the current node, or `None` for the root node. ### Accessing Sources `.sources() -> list[DerivationTree]` : Return a list containing all sources of ``. Sources are symbols used in generator expressions out of which the value of `` was created; see [the section on data conversions](sec:conversion) for details. ### Comparisons ` == ` : Returns True if both trees have the same structure and all nodes have the same values. ` == VALUE` : Returns True if `.value() == VALUE` — requires the types to match ` != ` : Returns True if both trees have a different structure or any nodes have different values. ` != VALUE` : Inverse of ` == VALUE`. To compare values with `<`, `>`, `<=`, `>=`, etc., explicitly convert them to the type you would like to use for comparison first. ### Debugging See the [section on output formats](sec:formats) for details on these representations. `.to_bits() -> str` : Return a bit representation (`0` and `1` characters) of ``. `.to_grammar() -> str` : Return a grammar-like representation of ``. `.to_tree() -> str` : Return a tree representation of ``, using `Tree(...)` constructors. `repr() -> str` : Return the internal representation of ``, as a `DerivationTree` constructor that can be evaluated as a Python expression. (sec:derivation-tree-direct-access-functions)= ## Type-Specific Functions The bulk of available functions comes from the Python standard library. The vast majority of methods implemented on `str`, `bytes`, and `int` are also implemented on `DerivationTree`s: * If a method is only implemented on one of the three base types, the `DerivationTree` internally is first transformed into that type (using `str()` etc.). * If a method is implemented on multiple base types, but they always have different signatures (such as `.startswith`, which takes a `str` if called on a `str`, and `bytes` if called on `bytes`), the `DerivationTree` is transformed into the appropriate base type. * If a method is implemented on multiple base types, and there is no way to distinguish based on the signatures, the method is invoked on the underlying type. This is not recommended as these methods rely on knowledge of the type of the internal representation (which may change in the future). Simply convert the tree to the desired base type first (`str().upper()`).