Name Rascal/Libraries/Prelude/ParseTree/implode

Synopsis Implode a parse tree according to a given (ADT) type.

Function &T<:value implode(type[&T<:value] t, Tree tree)

Usage import ParseTree;

Description Given a grammar for a language, its sentences can be parsed and the result is a parse tree (or more precisely a value of type Tree). For many applications this is sufficient and the results are achieved by traversing and matching them using concrete patterns.

In other cases, the further processing of parse trees is better done in a more abstract form. The abstract syntax for a language is a data type that is used to represent programs in the language in an abstract form. Abstract syntax has the following properties:

• It is "abstract" in the sense that it does not contain textual details such as parentheses, layout, and the like.
• While a language has one grammar (also known as, concrete syntax) it may have several abstract syntaxes for different purposes: type analysis, code generation, etc.

The function implode bridges the gap between parse tree and abstract syntax tree. Given a parse tree and a Rascal type it traverses them simultaneously and constructs an abstract syntax tree (a value of the given type) as follows:

1. Literals, layout and empty (i.e. ()) nodes are skipped.
2. Regular */+ lists are imploded to lists or sets depending on what is expected in the ADT.
3. Ambiguities are imploded to sets.
4. If the expected type is str the tree is unparsed into a string. This happens for both lexical and context-free parse trees.
5. If a tree's production has no label and a single AST (i.e. non-layout, non-literal) argument (for instance, an injection), the tree node is skipped, and implosion continues with the lone argument. The same applies to bracket productions, even if they are labeled.
6. If a tree's production has no label, but more than one argument, the tree is imploded to a tuple (provided this conforms to the ADT).
7. Optionals are imploded to booleans if this is expected in the ADT. This also works for optional literals, as shown in the example below.
8. An optional is imploded to a list with zero or one argument, iff a list type is expected.
9. If the argument of an optional tree has a production with no label, containing a single list, then this list is spliced into the optional list.
10. For trees with (cons-)labeled productions, the corresponding constructor in the ADT corresponding to the non-terminal of the production is found in order to make the AST.
11. If the provided type is node, (cons-)labeled trees will be imploded to untyped nodes. This means that any subtrees below it will be untyped nodes (if there is a label), tuples of nodes (if a label is absent), and strings for lexicals.
12. Unlabeled lexicals are imploded to str, int, real, bool depending on the expected type in the ADT. To implode lexical into types other than str, the PDB parse functions for integers and doubles are used. Boolean lexicals should match "true" or "false". NB: lexicals are imploded this way, even if they are ambiguous.
13. If a lexical tree has a cons label, the tree imploded to a constructor with that name and a single string-valued argument containing the tree's yield.

An IllegalArgument exception is thrown if during implosion a tree is encountered that cannot be imploded to the expected type in the ADT. As explained above, this function assumes that the ADT type names correspond to syntax non-terminal names, and constructor names correspond to production labels. Labels of production arguments do not have to match with labels in ADT constructors.

Finally, source location annotations are propagated as annotations on constructor ASTs. To access them, the user is required to explicitly declare a location annotation on all ADTs used in implosion. In other words, for every ADT type T, add:

anno loc T@location;

Examples

Example for rule 5

Given the grammar

syntax IDTYPE = Id ":" Type;
syntax Decls = decls: "declare" {IDTYPE ","}* ";";

Decls will be imploded as:

data Decls = decls(list[tuple[str,Type]]);

(assuming Id is a lexical non-terminal).

Example for rule 6

Given the grammar

syntax Formal = formal: "VAR"? {Id ","}+ ":" Type;

The corresponding ADT could be:

data Formal = formal(bool, list[str], Type);

Example for rule 8

Given the grammar

syntax Tag = "[" {Modifier ","}* "]";
syntax Decl = decl: Tag? Signature Body;

In this case, a Decl is imploded into the following ADT:

data Decl = decl(list[Modifier], Signature, Body);  

Example for rule 9

Given the grammar

syntax Exp = left add: Exp "+" Exp;

Can be imploded into:

data Exp = add(Exp, Exp);

[Edit] | [New Subconcept] | [Recompile Course] | [Warnings]