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 and 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 and 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 and Description
    `ShuntingYard(Jep jep, java.util.List<GrammarMatcher> gm)` Normal constructor, itterator set in `parse(Iterator)`

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and 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()` 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

      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

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