Package com.singularsys.jep.configurableparser

Class ShuntingYard

java.lang.Object

com.singularsys.jep.configurableparser.ShuntingYard

All Implemented Interfaces:

GrammarParser

Direct Known Subclasses:

LineNumberingShuntingYard

public class ShuntingYard
extends java.lang.Object
implements GrammarParser

An operator precedence parser based on the shunting yard algorithm.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	ShuntingYard.PrefixRes	Return result of following methods.
static class	ShuntingYard.ShuntingYardGrammarParserFactory	Factory creating new ShuntingYard instances.

Field Summary

Fields

Modifier and Type	Field	Description
protected static boolean	DUMP
protected static Operator	implicitMul
protected Lookahead2Iterator<Token>	it
protected Jep	jep
protected java.util.List<GrammarMatcher>	matchers
protected NodeFactory	nf
protected java.util.Stack<Node>	nodes
protected java.util.Stack<Operator>	ops
protected static Operator	sentinel

Constructor Summary

Constructors

Constructor	Description
ShuntingYard(Jep jep, java.util.List<GrammarMatcher> gm)	Normal constructor, itterator set in parse(Iterator)

Method Summary

Modifier and Type	Method	Description
protected boolean	compareOps(Operator op1, Operator op2)	Compare operators based on their precedence and associativity.
protected void	dumpState(java.lang.String msg)
protected void	expression()	Match prefixSuffix() optionally followed by a binary or ternary operator or an implicit multiplication.
Lookahead2Iterator<Token>	getIterator()
Node	parse(java.util.Iterator<Token> input)	Main entry point, construct tree from sequence of tokens.
Node	parsePrefixSuffix()	Callback function used by GrammerMatchers where the matcher expects a simple number, variable, or function call with optional, prefix or suffix operator.
Node	parseSubExpression()	Callback function used by GrammerMatchers
protected void	popOp()	Pops an operator off the Operator stack, and creates a new node.
protected void	prefix()	Matches identifies, numbers, prefix operators and plugged in grammar matchers.
protected void	prefixSuffix()	A prefix() optionally followed by suffix operators.
protected ShuntingYard.PrefixRes	prefixSuffixUnchecked()	Attempt to match a prefix optionally followed by suffix operators.
protected ShuntingYard.PrefixRes	prefixUnchecked()	Matches identifies, numbers, prefix operators and plugged in grammar matchers.
protected void	pushOp(Operator op, Token tok)	The pushOp function is worth some explanation Say 1+2*3 is parsed.
void	setIterator(Lookahead2Iterator<Token> it)	Set the iterator used by the GrammarParser.parseSubExpression()

Methods inherited from class java.lang.Object

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

Field Detail

DUMP

protected static final boolean DUMP

See Also:

Constant Field Values

ops

protected java.util.Stack<Operator> ops

nodes

protected java.util.Stack<Node> nodes

it

protected Lookahead2Iterator<Token> it

matchers

protected java.util.List<GrammarMatcher> matchers

jep

protected Jep jep

sentinel

protected static final Operator sentinel

implicitMul

protected static final Operator implicitMul

nf

protected NodeFactory nf

Constructor Detail

ShuntingYard

public ShuntingYard(Jep jep,
                    java.util.List<GrammarMatcher> gm)

Normal constructor, itterator set in parse(Iterator)

Parameters:

jep - Jep instance

gm - list of grammar rules

Method Detail

parse

public Node parse(java.util.Iterator<Token> input)
           throws ParseException

Main entry point, construct tree from sequence of tokens.

Specified by:

parse in interface GrammarParser

Parameters:

input - stream of tokens

Returns:

constructed tree

Throws:

ParseException - if the input cannot be parsed

parseSubExpression

public Node parseSubExpression()
                        throws ParseException

Callback function used by GrammerMatchers

Specified by:

parseSubExpression in interface GrammarParser

Returns:

node tree

Throws:

ParseException - if the input cannot be parsed

expression

protected void expression()
                   throws ParseException

Match prefixSuffix() optionally followed by a binary or ternary operator or an implicit multiplication. Consumes tokens and pushes operators found onto to the stack.

Throws:

ParseException

parsePrefixSuffix

public Node parsePrefixSuffix()
                       throws ParseException

Callback function used by GrammerMatchers where the matcher expects a simple number, variable, or function call with optional, prefix or suffix operator.

Specified by:

parsePrefixSuffix in interface GrammarParser

Returns:

node tree or null if parsing failed to match

Throws:

ParseException - if the input cannot be parsed

prefixSuffix

protected void prefixSuffix()
                     throws ParseException

A prefix() optionally followed by suffix operators.

Throws:

ParseException

prefixSuffixUnchecked

protected ShuntingYard.PrefixRes prefixSuffixUnchecked()
                                                throws ParseException

Attempt to match a prefix optionally followed by suffix operators.

Returns:

code indicating state of parsing

Throws:

ParseException - if node construction fails

Since:

3.5

prefixUnchecked

protected ShuntingYard.PrefixRes prefixUnchecked()
                                          throws ParseException

Matches identifies, numbers, prefix operators and plugged in grammar matchers.

Returns:

code indicating state of parsing

Throws:

ParseException - if node construction fails

Since:

3.5

prefix

protected void prefix()
               throws ParseException

Matches identifies, numbers, prefix operators and plugged in grammar matchers. Wrapper function around the prefixUnchecked()

Throws:

ParseException - if input fails to match or error construction node tree

pushOp

protected void pushOp(Operator op,
                      Token tok)
               throws ParseException

The pushOp function is worth some explanation Say 1+2*3 is parsed. First + is pushed onto the stack, then * is pushed. For 1*2+3. * is pushed, when + is encountered * has tighter precedence so it and the top two elements from the node stack are popped, the result computed and pushed on the node stack. Special cases -1+2 [uminus,+],[1] -> [+],[-1] -> [+],[-1,2] -> [],[(-1)+2] -1^2 [uminus,^],[1] -> [uminus,^],[1] -> [uminus,^],[1,2] -> [uminus],[1^2] -> [],[-(1^2)] 1^-2 [^],[1] -> [^,uminus],[1] ->[^,uminus],[1,2] -> [^],[1,(-2)] ->[],[1^(-2)]

Parameters:

op -

tok - Token operator came from

Throws:

ParseException

compareOps

protected boolean compareOps(Operator op1,
                             Operator op2)

Compare operators based on their precedence and associativity.

Parameters:

op1 -

op2 -

Returns:

true if op1 has a lower precedence than op2, or equal precedence and a left assoc op, etc.

popOp

protected void popOp()
              throws ParseException

Pops an operator off the Operator stack, and creates a new node. The children of the node are poped off the node stack and the result is pushed onto the node stack.

Throws:

ParseException

dumpState

protected void dumpState(java.lang.String msg)

getIterator

public Lookahead2Iterator<Token> getIterator()

setIterator

public void setIterator(Lookahead2Iterator<Token> it)

Description copied from interface: GrammarParser

Set the iterator used by the GrammarParser.parseSubExpression()

Specified by:

setIterator in interface GrammarParser

Parameters:

it - the iterator