| The interface to all actions. An action implements a computation
that takes a single argument and produces a single result. Both
argument and result have the same type so that actions can be
trivially composed with each other.
Actions help in producing a left-recursive AST, even though
the productions generating the individual AST nodes are
right-recursive (as left-recursion is generally illegal for
Rats!' grammars). The basic idea is to create a
Pairlist of actions during the right-recursion and then apply the
actions onto the semantic value of the base case.
To illustrate this use of actions, consider the grammar rule
for logical and expressions in C:
logical-and-expression :
bitwise-or-expression
logical-and-expression && bitwise-or-expression
Since this grammar rule is left-recursive, it cannot directly be
converted into the corresponding Rats! production and must
be rewritten as a right-recursion. At the same time, the
corresponding AST should still be left-recursive, as the logical
and operator is left-associative.
Using actions and
xtc.tree.GNode generic nodes as
semantic values, the corresponding right-recursive productions can
be written as follows:
Node LogicalAndExpression =
base:BitwiseOrExpression list:LogicalAndExpressionTail*
{ yyValue = apply(list, base); }
;
Action<Node> LogicalAndExpressionTail =
"&&":Symbol right:BitwiseOrExpression
{ yyValue = new Action<Node>() {
public Node run(Node left) {
return GNode.create("LogicalAndExpression", left, right);
}};
}
;
The semantic action for the LogicalAndExpression
production relies on an apply() helper method, which
can be written as following:
<T> T apply(Pair<Action<T>> actions, T seed) {
while (! actions.isEmpty()) {
seed = actions.head().run(seed);
actions = actions.tail();
}
return seed;
}
In detail, the LogicalAndExpressionTail production
recognizes logical and operators followed by the right operands.
By using an action as its semantic value, the production delays the
actual construction of the corresponding generic node. Once all
logical and operators and the corresponding bitwise or expressions
have been parsed, the semantic action for the
LogicalAndExpression production applies the actions
and creates a left-recursive AST. Note that this example assumes
that the production for bitwise or expressions also has a generic
node as its semantic value. Further note that, if there is no
logical and operator in the input, this example simply passes the
semantic value of the single bitwise or expression through, which
is the desired behavior as it leaves the AST unmodified. Finally,
note that direct left recursions may appear in generic productions,
as Rats! automatically transforms them into the
corresponding right-recursions while also creating left-recursive
semantic values with the help of actions.
author:
Robert Grimm
version:
$Revision: 1.10 $ |