Source Code Cross Referenced for Action.java in  » Parser » Rats-Parser-Generators » xtc » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

001:        /*
002:         * xtc - The eXTensible Compiler
003:         * Copyright (C) 2004-2007 Robert Grimm
004:         *
005:         * This library is free software; you can redistribute it and/or
006:         * modify it under the terms of the GNU Lesser General Public License
007:         * version 2.1 as published by the Free Software Foundation.
008:         *
009:         * This library is distributed in the hope that it will be useful,
010:         * but WITHOUT ANY WARRANTY; without even the implied warranty of
011:         * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
012:         * Lesser General Public License for more details.
013:         *
014:         * You should have received a copy of the GNU Lesser General Public
015:         * License along with this library; if not, write to the Free Software
016:         * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017:         * USA.
018:         */
019:        package xtc.util;
020:
021:        /**
022:         * The interface to all actions.  An action implements a computation
023:         * that takes a single argument and produces a single result.  Both
024:         * argument and result have the same type so that actions can be
025:         * trivially composed with each other.
026:         *
027:         * <p />Actions help in producing a left-recursive AST, even though
028:         * the productions generating the individual AST nodes are
029:         * right-recursive (as left-recursion is generally illegal for
030:         * <i>Rats!</i>' grammars).  The basic idea is to create a {@link Pair
031:         * list} of actions during the right-recursion and then apply the
032:         * actions onto the semantic value of the base case.
033:         *
034:         * <p />To illustrate this use of actions, consider the grammar rule
035:         * for logical and expressions in C:<pre>
036:         *   <i>logical-and-expression</i> :
037:         *     <i>bitwise-or-expression</i>
038:         *     <i>logical-and-expression</i> <b>&&</b> <i>bitwise-or-expression</i>
039:         * </pre>
040:         * Since this grammar rule is left-recursive, it cannot directly be
041:         * converted into the corresponding <i>Rats!</i> production and must
042:         * be rewritten as a right-recursion.  At the same time, the
043:         * corresponding AST should still be left-recursive, as the logical
044:         * and operator is left-associative.
045:         *
046:         * <p />Using actions and {@link xtc.tree.GNode generic nodes} as
047:         * semantic values, the corresponding right-recursive productions can
048:         * be written as follows:<pre>
049:         *   Node LogicalAndExpression =
050:         *     base:BitwiseOrExpression list:LogicalAndExpressionTail*
051:         *       { yyValue = apply(list, base); }
052:         *     ;
053:         *
054:         *   Action&lt;Node&gt; LogicalAndExpressionTail =
055:         *     "&&":Symbol right:BitwiseOrExpression
056:         *       { yyValue = new Action&lt;Node&gt;() {
057:         *           public Node run(Node left) {
058:         *             return GNode.create("LogicalAndExpression", left, right);
059:         *           }};
060:         *       }
061:         *     ;
062:         * </pre>
063:         * The semantic action for the <code>LogicalAndExpression</code>
064:         * production relies on an <code>apply()</code> helper method, which
065:         * can be written as following:<pre>
066:         *   &lt;T&gt; T apply(Pair&lt;Action&lt;T&gt;&gt; actions, T seed) {
067:         *     while (! actions.isEmpty()) {
068:         *       seed    = actions.head().run(seed);
069:         *       actions = actions.tail();
070:         *     }
071:         *     return seed;
072:         *   }
073:         * </pre>
074:         * In detail, the <code>LogicalAndExpressionTail</code> production
075:         * recognizes logical and operators followed by the right operands.
076:         * By using an action as its semantic value, the production delays the
077:         * actual construction of the corresponding generic node.  Once all
078:         * logical and operators and the corresponding bitwise or expressions
079:         * have been parsed, the semantic action for the
080:         * <code>LogicalAndExpression</code> production applies the actions
081:         * and creates a left-recursive AST.  Note that this example assumes
082:         * that the production for bitwise or expressions also has a generic
083:         * node as its semantic value.  Further note that, if there is no
084:         * logical and operator in the input, this example simply passes the
085:         * semantic value of the single bitwise or expression through, which
086:         * is the desired behavior as it leaves the AST unmodified.  Finally,
087:         * note that direct left recursions may appear in generic productions,
088:         * as <i>Rats!</i> automatically transforms them into the
089:         * corresponding right-recursions while also creating left-recursive
090:         * semantic values with the help of actions.
091:         *
092:         * @author Robert Grimm
093:         * @version $Revision: 1.10 $
094:         */
095:        public interface Action<T> {
096:
097:            /**
098:             * Perform this action.
099:             *
100:             * @param arg The argument.
101:             * @return The result.
102:             */
103:            T run(T arg);
104:
105:        }