Open-source image
open-source
Hime logo

Table of content

Tree Actions

This page explains the mechanism of tree actions that are able to modify the Abstact Syntax Trees produced by the parsers. Hime supports the specification of two simple actions, the drop action and the promote action.

Abstract syntax tree

Parsers generated by Hime are designed to output an Abstract Syntax Tree (AST) corresponding to the parsed input. The structure of the produced AST is similar to those produced by other tools. Given a rule a -> x y z;, the parser will produce for this rule a tree node a with x, y and z as children nodes:

Tree A(X Y Z)

The general rule to keep in mind is that for any syntactic rule, the parser produces a sub-tree with the head as top node and symbols in the rule's body as direct children of this node. Consequently, for the rule a -> x y* z;, produced AST will have a as top node and then x, multiple instances of y and finally z as children of this node:

Tree A(X Y Y Y Z)

Drop tree action

The drop action specifies the node on which it is applied will simply be removed from the AST along with all its children. The drop action is specified using !. For example, the rule a -> x y! z; will produce ASTs with a as top node and only x and z as children. The drop action may be applied to a complete group in a rule's body. For example, the rule a -> x (c|d*)! z; will produce the same ASTs as the previous example. This DOES NOT change the semantic of the rule, this only drop potential c and d nodes from the AST after them being recognized by the parser in the input.

Promote tree action

The promote action specifies that a particular symbol in the rule's body must become the top node of the produced AST for the rule, instead of the rule's head. The promote action is noted ^. Multiple promote actions may be specified in the body of a rule. In addition, this action may also be applied on a whole group in the body. See hereafter:

Single Promote Action

a -> x y^ z ;

This rule first produces:

Tree A(X Y Z)

Applying the promote actions it becomes:

Tree Y(X Z)

Multiple Promote Actions

When multiple promote actions are found, they are applied sequentially from left to right:

a -> x y^ z^ ;

This rule first produces:

Tree A(X Y Z)

Applying the first promote action it becomes:

Tree A(X Y Z)

Applying the second promote action it becomes:

Tree A(X Y Z)

Chaining Promote Actions

Promote actions are applied bottom-up in the AST as follow:

a -> x y^ ;
y -> u v^ w ;

These rules will originally produce:

Tree A(X Y Z)

Applying the first promote action it becomes:

Tree A(X Y Z)

Applying the second promote action it becomes:

Tree A(X Y Z)

Sub-Rule tree action

The sub-rule tree action has an effect opposite to the promote tree action ; it has the effect of lowering nodes in the tree structure. Contrary to the other tree actions, it does not apply to single symbols in a grammar rules but to a complete part of the rule's body. It is expressed as follow:

e -> a { x y z } b ;

Note the use of the curly brackets in the rule's body. It delimits the effect of the sub-rule action. The effect itself is to puts the AST nodes corresponding to the symbols within the curly brackets below a generated AST node. This generated AST node will be given the special ε symbol, i.e. the terminal symbol that denotes the absence of symbols. For the rule abobe, the resulting AST will be:

Tree E(A EPS(X Y Z) B)

One way to think of this tree action is to image that the curly brackets define the body of an anonymous syntactic rule