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 inparse(Iterator)
-
Method Summary
All Methods Instance Methods Concrete Methods 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 GrammerMatchersprotected 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 theGrammarParser.parseSubExpression()
-
-
-
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 inparse(Iterator)
- Parameters:
jep
- Jep instancegm
- 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 interfaceGrammarParser
- 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 interfaceGrammarParser
- 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 interfaceGrammarParser
- 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 theprefixUnchecked()
- 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 theGrammarParser.parseSubExpression()
- Specified by:
setIterator
in interfaceGrammarParser
- Parameters:
it
- the iterator
-
-