Package ghidra.app.plugin.assembler.sleigh.parse

Class AssemblyParseMachine

  • All Implemented Interfaces:
    java.lang.Comparable<AssemblyParseMachine>
    public class AssemblyParseMachine
extends java.lang.Object
implements java.lang.Comparable<AssemblyParseMachine>
    A class that implements the LALR(1) parsing algorithm Instances of this class store a parse state. In order to work correctly, the class must be given a properly-constructed Action/Goto table. This implementation is somewhat unconventional. First, instead of strictly tokenizing and then parsing, each terminal is given the opportunity to match a token in the input. If none match, it results in a syntax error (equivalent to the token type having an empty cell in the classical algorithm). If more than one match, the parser branches. Also, because a single cell may also contain multiple actions, the parser could branch again. Thus, if a sentence is ambiguous, this algorithm will identify all possible parse trees, including ones where the input is tokenized differently than in other trees.

    • Field Detail

      • output NEW

        protected final java.util.List<java.lang.Integer> output

      • stack NEW

        protected final java.util.Stack<java.lang.Integer> stack

      • buffer NEW

        protected final java.lang.String buffer

      • pos NEW

        protected int pos

      • labels NEW

        protected final java.util.Map<java.lang.String,​java.lang.Long> labels

      • accepted NEW

        protected boolean accepted

      • error NEW

        protected int error

      • got NEW

        protected java.lang.String got

      • id NEW

        protected final int id

Constructor Detail

  • Method Detail

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class java.lang.Object

    • equals

      public boolean equals​(java.lang.Object that)
      Overrides:
      equals in class java.lang.Object

    • copy

      public AssemblyParseMachine copy()
      Duplicate this machine state This is used extensively when branching
      Returns:
      the duplicate

    • doAction

      protected void doAction​(AssemblyParseActionGotoTable.Action a,
                        AssemblyParseToken tok,
                        java.util.Set<AssemblyParseMachine> results,
                        java.util.Deque<AssemblyParseMachine> visited)
      Perform a given action and continue parsing, exhausting all results after the action
      Parameters:
      a - the action
      tok - the token given by the terminal (column) of the entry containing this action
      results - a place to store all the parsing results (each must be accept or error state)
      visited - a collection of machine states already visited The visited "collection" prevents infinite loops or stack overflows resulting from "consuming" epsilon and going to the same state. Such loops may involve many states. It is also defined as a map here for debugging purposes, so that when a loop is detected, we can print the ID of the first visit.

    • consume

      protected void consume​(AssemblyTerminal t,
                       AssemblyParseToken tok,
                       java.util.Set<AssemblyParseMachine> results,
                       java.util.Deque<AssemblyParseMachine> visited)
      Consume a given terminal (and corresponding token) and continue parsing
      Parameters:
      t - the terminal
      tok - the corresponding token
      results - a place to store all the parsing results
      visited - a collection of machine states already visited

    • findLoop

      protected static AssemblyParseMachine findLoop​(AssemblyParseMachine machine,
                                               java.util.Collection<AssemblyParseMachine> visited)
      Look for previous machine states having the same stack and position This would imply we have gone in a loop without consuming anything. We need to prune.
      Parameters:
      machine - the machine state to check
      visited - the stack of previous machine states
      Returns:
      if there is a loop, the machine state proving it, null otherwise

    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object

    • exhaust

      protected void exhaust​(java.util.Set<AssemblyParseMachine> results,
                       java.util.Deque<AssemblyParseMachine> visited)
      Parse (or continue parsing) all possible trees from this machine state
      Parameters:
      results - a place to store all the parsing results
      visited - a collection of machine states already visited

    • exhaust

      public java.util.Set<AssemblyParseMachine> exhaust()
      Parse (or continue parsing) all possible trees from this machine state
      Returns:
      the set of all possible trees and errors

    • getTree

      public AssemblyParseBranch getTree()
      If in the accepted state, get the resulting parse tree for this machine
      Returns:
      the parse tree