Class AssemblyParseMachine
- java.lang.Object
-
- ghidra.app.plugin.assembler.sleigh.parse.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 Summary
Fields Modifier and Type Field Description protected boolean
accepted
protected java.lang.String
buffer
protected int
error
protected java.util.Collection<AssemblyTerminal>
expected
protected java.lang.String
got
protected int
id
protected java.util.Map<java.lang.String,java.lang.Long>
labels
protected AssemblyParseToken
lastTok
protected java.util.List<java.lang.Integer>
output
protected AssemblyParser
parser
protected int
pos
protected java.util.Stack<java.lang.Integer>
stack
protected java.util.Stack<AssemblyParseTreeNode>
treeStack
-
Constructor Summary
Constructors Constructor Description 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
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
compareTo(AssemblyParseMachine that)
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 parsingAssemblyParseMachine
copy()
Duplicate this machine state This is used extensively when branchingprotected 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 actionboolean
equals(java.lang.Object that)
java.util.Set<AssemblyParseMachine>
exhaust()
Parse (or continue parsing) all possible trees from this machine stateprotected void
exhaust(java.util.Set<AssemblyParseMachine> results, java.util.Deque<AssemblyParseMachine> visited)
Parse (or continue parsing) all possible trees from this machine stateprotected 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.AssemblyParseBranch
getTree()
If in the accepted state, get the resulting parse tree for this machineint
hashCode()
java.lang.String
toString()
-
-
-
Field Detail
-
parser
protected final AssemblyParser parser
-
output
protected final java.util.List<java.lang.Integer> output
-
stack
protected final java.util.Stack<java.lang.Integer> stack
-
treeStack
protected final java.util.Stack<AssemblyParseTreeNode> treeStack
-
buffer
protected final java.lang.String buffer
-
pos
protected int pos
-
lastTok
protected AssemblyParseToken lastTok
-
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
-
expected
protected java.util.Collection<AssemblyTerminal> expected
-
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 machineinput
- the full input linepos
- the position in the line identifying the next characters to parselabels
- a map of valid tokens to number for numeric terminals
-
-
Method Detail
-
hashCode
public int hashCode()
- Overrides:
hashCode
in classjava.lang.Object
-
equals
public boolean equals(java.lang.Object that)
- Overrides:
equals
in classjava.lang.Object
-
compareTo
public int compareTo(AssemblyParseMachine that)
- Specified by:
compareTo
in interfacejava.lang.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, 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 actiontok
- the token given by the terminal (column) of the entry containing this actionresults
- 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 terminaltok
- the corresponding tokenresults
- a place to store all the parsing resultsvisited
- 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 checkvisited
- 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 classjava.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 resultsvisited
- 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
-
-