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

Class AssemblyParseMachine

java.lang.Object
ghidra.app.plugin.assembler.sleigh.parse.AssemblyParseMachine
All Implemented Interfaces:
Comparable<AssemblyParseMachine>
public class AssemblyParseMachine extends Object implements 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 Details

  • Constructor Details

    • AssemblyParseMachine

      public AssemblyParseMachine(AssemblyParser parser, String input, int pos, AssemblyParseToken lastTok, AssemblyNumericSymbols symbols)
      Construct a new parse state
      Parameters:
      parser - the parser driving this machine
      input - the full input line
      pos - the position in the line identifying the next characters to parse
      lastTok -
      symbols -

  • Method Details

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object that)
      Overrides:
      equals in class Object

    • compareTo

      public int compareTo(AssemblyParseMachine that)
      Specified by:
      compareTo in interface Comparable<AssemblyParseMachine>

    • 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, Set<AssemblyParseMachine> results, Deque<AssemblyParseMachine> visited)
      Perform a given action and continue parsing, exhausting all results after the action

      The visited list prevents infinite loops or stack overflows resulting from consuming epsilon and going to the same state. Such loops may involve many states.

      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

    • consume

      protected void consume(AssemblyTerminal t, AssemblyParseToken tok, Set<AssemblyParseMachine> results, 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, 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 String toString()
      Overrides:
      toString in class Object

    • exhaust

      protected void exhaust(Set<AssemblyParseMachine> results, 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 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