xtc.parser
Class DirectLeftRecurser

java.lang.Object
  xtc.tree.Visitor
      xtc.parser.DirectLeftRecurser

public class DirectLeftRecurser
extends Visitor

Visitor to transform direct left-recursions into equivalent right-recursions. As a practical matter, this visitor transforms only void, text-only, token-level, and generic productions. For generic productions, it builds on actions to ensure that the resulting right-recursive productions preserve the structure of the original productions' semantic values. In particular, left-associative data structures remain left-associative, even after transformation. This visitor requires that all nested choices that do not appear as the last element in a sequence have been lifted. It also assumes that the entire grammar is contained in a single module.

This visitor may report errors to the user.

Version:

$Revision: 1.82 $

Author:

Robert Grimm

Field Summary

protected Analyzer	analyzer The analyzer utility.
protected AST	ast The type operations.
protected java.util.List<Binding>	children The list of variables representing the children of the generic node to be created.
protected boolean	hasConstant The flag for whether the grammar has the constant attribute.
protected boolean	hasParseTree The flag for whether the grammar has the parseTree attribute.
protected boolean	isGeneric The flag for whether we are transforming a generic production.
protected boolean	isTextOnly The flag for whether we are transforming a text-only production.
protected boolean	isToken The flag for whether we are transforming a token-level production.
protected boolean	isTopLevel Flag for whether the current element is the top-level element of a production.
protected boolean	isVoid The flag for whether we are transforming a void production.
protected java.util.List<NodeMarker>	markers The list of node markers.
protected FullProduction	pTail The new tail production.
protected Runtime	runtime The runtime.
protected Binding	seed The binding for the seed value.
protected boolean	seenChoice Flag for whether we have processed an ordered choice.
protected int	state The current state.
static int	STATE_BASE The flag for processing the base case.
static int	STATE_RECURSION The flag for processing the recursive case.
protected java.lang.String	varAction The name of the action's argument.

Constructor Summary

DirectLeftRecurser(Runtime runtime, Analyzer analyzer, AST ast)
Create a new direct left-recurser.

Method Summary

protected Binding	bind(Element e) Create a binding for the specified element.
static boolean	isBase(Sequence s, FullProduction p) Determine whether the specified sequence represents a base case for a direct left-recursion.
static boolean	isRecursive(Sequence s, FullProduction p) Determine whether the specified sequence is directly left-recursive.
static boolean	isTransformable(FullProduction p) Determine whether the specified production contains a direct left-recursion that is transformable into the corresponding right-recursion by this visitor.
Element	visit(Binding b) Visit the specified binding.
Element	visit(Element e) Visit the specified element.
void	visit(FullProduction p) Visit the specified production.
void	visit(Module m) Process the specified grammar.
Element	visit(NodeMarker m) Visit the specified node marker.
Element	visit(NonTerminal nt) Visit the specified nonterminal.
Element	visit(NullLiteral l) Visit the specified null literal.
Element	visit(Option o) Visit the specified option.
Element	visit(OrderedChoice c) Visit the specified ordered choice.
Element	visit(ParseTreeNode n) Visit the specified parse tree node.
Element	visit(Repetition r) Visit the specified repetition.
Element	visit(Sequence s) Visit the specified sequence.
Element	visit(StringLiteral l) Visit the specified string literal.
Element	visit(StringMatch m) Visit the specified string match.

Methods inherited from class xtc.tree.Visitor

dispatch, equals, hashCode, iterate, map, mapInPlace, unableToVisit, visit

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

Field Detail

STATE_RECURSION

public static final int STATE_RECURSION

The flag for processing the recursive case.

See Also:

Constant Field Values

STATE_BASE

public static final int STATE_BASE

The flag for processing the base case.

See Also:

Constant Field Values

runtime

protected final Runtime runtime

The runtime.

analyzer

protected final Analyzer analyzer

The analyzer utility.

ast

protected final AST ast

The type operations.

isVoid

protected boolean isVoid

The flag for whether we are transforming a void production.

isTextOnly

protected boolean isTextOnly

The flag for whether we are transforming a text-only production.

isToken

protected boolean isToken

The flag for whether we are transforming a token-level production.

isGeneric

protected boolean isGeneric

The flag for whether we are transforming a generic production.

hasConstant

protected boolean hasConstant

The flag for whether the grammar has the constant attribute.

hasParseTree

protected boolean hasParseTree

The flag for whether the grammar has the parseTree attribute.

state

protected int state

The current state.

isTopLevel

protected boolean isTopLevel

Flag for whether the current element is the top-level element of a production.

seenChoice

protected boolean seenChoice

Flag for whether we have processed an ordered choice.

children

protected java.util.List<Binding> children

The list of variables representing the children of the generic node to be created.

markers

protected java.util.List<NodeMarker> markers

The list of node markers.

pTail

protected FullProduction pTail

The new tail production.

seed

protected Binding seed

The binding for the seed value.

varAction

protected java.lang.String varAction

The name of the action's argument.

Constructor Detail

DirectLeftRecurser

public DirectLeftRecurser(Runtime runtime,
                          Analyzer analyzer,
                          AST ast)

Create a new direct left-recurser.

Parameters:

runtime - The runtime.

analyzer - The analyzer utility.

ast - The type operations.

Method Detail

bind

protected Binding bind(Element e)

Create a binding for the specified element. This method also adds the name of the bound variable to the end of the list of children.

Parameters:

e - The element to bind.

Returns:

The corresponding binding.

visit

public void visit(Module m)

Process the specified grammar.

visit

public void visit(FullProduction p)

Visit the specified production.

visit

public Element visit(OrderedChoice c)

Visit the specified ordered choice.

visit

public Element visit(Repetition r)

Visit the specified repetition.

visit

public Element visit(Option o)

Visit the specified option.

visit

public Element visit(Sequence s)

Visit the specified sequence.

visit

public Element visit(Binding b)

Visit the specified binding.

visit

public Element visit(StringMatch m)

Visit the specified string match.

visit

public Element visit(NonTerminal nt)

Visit the specified nonterminal.

visit

public Element visit(StringLiteral l)

Visit the specified string literal.

visit

public Element visit(ParseTreeNode n)

Visit the specified parse tree node.

visit

public Element visit(NullLiteral l)

Visit the specified null literal.

visit

public Element visit(NodeMarker m)

Visit the specified node marker.

visit

public Element visit(Element e)

Visit the specified element. This method provides the default implementation for repetitions, options, predicates, voided elements, character terminals, (parser) actions, and value elements.

isTransformable

public static boolean isTransformable(FullProduction p)

Determine whether the specified production contains a direct left-recursion that is transformable into the corresponding right-recursion by this visitor. Note that, for a production to be transformable, all direct left-recursions must precede the corresponding base cases. Further nore that this method assumes that the specified production's element is an ordered choice of sequences.

Parameters:

p - The production.

Returns:

true if the production is transformable by this visitor.

isRecursive

public static boolean isRecursive(Sequence s,
                                  FullProduction p)

Determine whether the specified sequence is directly left-recursive. The specified sequence must be a top-level alternative of the specified production, which, in turn, must be transformable.

Parameters:

s - The sequence.

p - The production.

Returns:

true if the specified sequence is directly left-recursive.

isBase

public static boolean isBase(Sequence s,
                             FullProduction p)

Determine whether the specified sequence represents a base case for a direct left-recursion. The specified sequence must be a top-level alternative for the specified production, which, in turn, must be transformable.

Parameters:

s - The sequence.

p - The production.

Returns:

true if the specified sequence is a base case for the direct left-recursion.