com.singularsys.jep.configurableparser
Class ShuntingYard

java.lang.Object
  extended by 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
static class ShuntingYard.ShuntingYardGrammarParserFactory
          Factory creating new ShuntingYard instances.
 
Field Summary
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
ShuntingYard(Jep jep, java.util.List<GrammarMatcher> gm)
           
 
Method Summary
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 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  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)
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 - iterator with the list of tokens
Returns:
the generated parser tree
Throws:
ParseException

parseSubExpression

public Node parseSubExpression()
                        throws ParseException
Callback function used by GrammerMatchers

Specified by:
parseSubExpression in interface GrammarParser
Returns:
the root node of the matched sub expression.
Throws:
ParseException

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

prefixSuffix

protected void prefixSuffix()
                     throws ParseException
A prefix() optionally followed by suffix operators.

Throws:
ParseException

prefix

protected void prefix()
               throws ParseException
Matches identifies, numbers, prefix operators and plugged in grammar matchers.

Throws:
ParseException

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


Copyright © 2010 Singular Systems http://www.singularsys.com/jep