Initial GLR stack.
-class GraphStructuredStack(object):
+class GLRStack(object):
"""
A data structure representing a forkable stack from Tomita's paper.
+
+ Attributes:
+ heads(list of GLRStackNode)
"""
+ def __init__(self):
+ self.heads = []
+ def reduce(self, head, production):
+ """Executes reduce operation for the given head and production.
-class PackedParseForestNode(object):
- """This is a node in the Tomita's packed parse forest."""
+ Reduces given head by the production determined by the given token.
+ Creates new head. Remove action from current head. If head has no more
+ actions it is removed from heads list. The given token shall be the
+ only token ahead of the new head. Try to merge new head if the same
+ head exists. Execute reduce semantic action.
+ """
+ def shift(self, position, state):
+ """Execute shift operation at the given position to the given state.
-class NonTerminal(PackedParseForestNode):
- pass
+ Shift token determined by the given state from input at given position
+ and create the new head. Parents will be all nodes that had shift
+ action with the given state at the given position.
+ """
-class Terminal(PackedParseForestNode):
- pass
+class GLRStackNode(object):
+ """
+ Attributes:
+ state(LRState):
+ position(int):
+ parents_production(dict): { production: parent GLRStackNode}
+ Each stack node might have multiple parents.
+ tokens_ahead(list of Token)
+ actions(list of lists of Action): Possible actions for each token.
+ """
+ def __init__(self, state, position):
+ self.state = state
+ self.position = position
+ self.parents_production = {}
+ self.tokens_ahead = []
+ self.actions = []
