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

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

      • stack

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

      • buffer

        protected final java.lang.String buffer

      • pos

        protected int pos

      • labels

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

      • accepted

        protected boolean accepted

      • error

        protected int error

      • got

        protected java.lang.String got

      • id

        protected final int id

    • Constructor Detail

      • AssemblyParseMachine

        public AssemblyParseMachine​(AssemblyParser parser,
                            java.lang.String input,
                            int pos,
                            AssemblyParseToken lastTok,
                            java.util.Map<java.lang.String,​java.lang.Long> labels)
        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
        labels - a map of valid tokens to number for numeric terminals

    • 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