Here are the first few stages from the Earley parsing page on wikipedia.S(0):  2 + 3 * 4    (1)  P   S         (0)    # start rule    (2)  S   S + M     (0)    # predict from (1)    (3)  S   M         (0)    # predict from (1)    (4)  M   M * T     (0)    # predict from (3)    (5)  M   T         (0)    # predict from (3)    (6)  T   number    (0)    # predict from (5)S(1): 2  + 3 * 4    (1)  T  number     (0)    # scan from S(0)(6)    (2)  M  T          (0)    # complete from (1) and S(0)(5)    (3)  M  M  * T     (0)    # complete from (2) and S(0)(4)    (4)  S  M          (0)    # complete from (2) and S(0)(3)    (5)  S  S  + M     (0)    # complete from (4) and S(0)(2)    (6)  P  S          (0)    # complete from (4) and S(0)(1)S(2): 2 +  3 * 4    (1)  S  S +  M     (0)    # scan from S(1)(5)    (2)  M   M * T     (2)    # predict from (1)    (3)  M   T         (2)    # predict from (1)    (4)  T   number    (2)    # predict from (3)I've already got the algorithm written, and debugPrintState seems to be showing the correct Earley states.Here is the code, you can use it if you want:from cf_grammar import ruleSymbols, varNameclass SPPFNode:     # Shared Packed Parse Forest    stringSpaces = 5    def __init__(self, symbol, input_start, input_end, parent=None):        self._parent = parent        self._symbol = symbol        self._start = input_start        self._end = input_end        self._children = []    @property    def parent(self):        return self._parent    @property    def children(self):        return list(self._children)    @property    def symbol(self):        return self._symbol    @property    def inputStart(self):        return self._start    @property    def inputEnd(self):        return self._end    def addChild(self, node):        if node is not None:            self._children.append(node)    def insertChild(self, index, node):        if node is not None:            self._children.insert(index, node)    def toString(self, spaces=None):        if spaces is None:            spaces = 0        space_str = ''        for k in range(0, spaces):            space_str += ' '        string = '(' + ' + self._symbol + ' + ', ' + str(self.inputStart) + ', ' + str(self.inputEnd) + ')\n'        for child in self._children:            string += space_str + '|\n'            string += space_str + '+--'            string += child.toString(spaces=spaces + self.stringSpaces)        return string    def __str__(self):        return self.toString()class EarleyParser:    POS, RULE, ORIG, NODE = range(4)    dummyStart = '0'    def __init__(self, grammar):        self._grammar = dict(grammar)        self._grammar[self.dummyStart] = None        self._state = None        self._pos = None        self._input = None    def parse(self, string, start):        assert (len(string) > 0)        self._initState(start)        self._input = string        for k in range(0, len(string) + 1):            while True:                state_len = len(self._state[k])                for var, states in list(self._state[k].items()):                    for state in states:                        if not self._finished(state):                            if self._nextSymbolIsVar(state):                                var1 = self._varAtPos(state[self.POS], state[self.RULE])                                self._predict(k, var1)                            elif k < len(self._input):                                self._scan(k, self._input[k], state[self.NODE])                        else:                            self._complete(k, var, state[self.ORIG], state[self.NODE])                if len(self._state[k]) == state_len:                    break              # If the states in the state set stabilize, then there's nothing more to do            if len(self._state) == k:   # If no new state set was added                break        return self._sppForest()    def debugPrintState(self, where=None):        if where is not None:            print(where)        for k in range(0, len(self._state)):            print('\tS(' + str(k) + '):')            for var, states in self._state[k].items():                print('\t\t' + var + ':')                for state in states:                    print('\t\t\t' + str(state))        print('\n')    def _sppForest(self):        if len(self._state) != len(self._input) + 1:            return []        forest = []        state_set = self._state[-1]        for states in state_set.values():            for state in states:                pos, rule, orig, node = state                if pos == len(rule) and orig == 0:                    forest.append(node)        return forest    def _predict(self, k, var):        rules = self._grammar[var]        for rule in rules:            symbols = ruleSymbols(rule)            self._addState(k, var, (0, symbols, k, None))     def _scan(self, k, a, node):        for var, states in self._state[k].items():            for i in range(0, len(states)):                state = states[i]                pos1, rule1, orig1, node1 = state                if pos1 < len(rule1) and rule1[pos1] == a:                    if node1 is None:                        node1 = SPPFNode(symbol=a, input_start=k, input_end=k+1)                        states[i] = (state[self.POS], state[self.RULE], state[self.ORIG], node1)                    if node is None:                        node = SPPFNode(symbol=var, input_start=-1, input_end=-1)                    node.addChild(node1)                    print('scan: ')                    print(node)                    self._addState(k+1, var, (pos1+1, rule1, orig1, node))    def _complete(self, k, var, orig, node):        for var1, states in self._state[orig].items():            for state in states:                pos1, rule1, orig1, node1 = state                var2 = self._varAtPos(pos1, rule1)                if var2 == var:                    node2 = SPPFNode(symbol=var, input_start=-1, input_end=-1)                    node2.addChild(node)                    node2.addChild(node1)                    print('complete: ')                    print(node2)                    self._addState(k, var1, (pos1+1, rule1, orig1, node2))    def _finished(self, state):        if state[self.POS] < len(state[self.RULE]):            return False        return True    def _addState(self, k, var, state):        if var != self.dummyStart:            if k >= len(self._state):                self._state.append({})            if var not in self._state[k]:                self._state[k][var] = [state]            else:                for state1 in self._state[k][var]:                    if state1[self.POS] == state[self.POS] and \                       state1[self.RULE] == state[self.RULE] and \                       state1[self.ORIG] == state[self.ORIG]:                        return                self._state[k][var].append(state)                 # Only add states not added, per wikipedia article    def _nextSymbolIsVar(self, state):        pos, rule, orig, node = state        if pos < len(rule):            var = varName(rule[pos])            if var:  return True        return False    def _varAtPos(self, pos, rule):        if pos < len(rule):            var = varName(rule[pos])            if var:                return var        return None    def _initState(self, start_rule):        self._pos = 0        self._state = []        dummy_rule = ('{'+ start_rule + '}',)        self._grammar[self.dummyStart] = dummy_rule        state_set = {self.dummyStart: [(0, dummy_rule, 0, None)]}        self._state.append(state_set)        # The parser is seedd with S(0) consisting of only the top-level ruleif __name__ == '__main__':    from led_ux_grammar import grammar, debugGrammar    EarleyParser.dummyStart = 'P'    parser = EarleyParser(debugGrammar)    forest = parser.parse('2+3*4', start='S')    for tree in forest:        print(tree)However, it's hard for me to see how to construct the nodes as I build up the states using the algorithm.I don't need for you to read my code, just show me a 2 level tree given the first few stages above.If you want to run the code, here is the grammar in another file:debugGrammar = {    'S' : ['{S}+{M}', '{M}'],    'M' : ['{M}*{T}', '{T}'],    'T' : ['1', '2', '3', '4'],}And some utility functions for working with the grammar (cf_grammar.py):def charRange(begin, end):    return [chr(x) for x in range(ord(begin), ord(end) + 1)]def ruleSymbols(rule):    symbols = []    k = 0    while k < len(rule):        c = rule[k]        if c == '{':            end = rule.find('}', k) + 1            sym = rule[k:end]            symbols.append(sym)            k = end        else:            symbols.append(c)            k += 1    return tuple(symbols)def varName(symbol):    if len(symbol) >= 3 and symbol[0] == '{' and symbol[-1] == '}':        return symbol[1:-1]    return Nonedef terminal(symbol):    if len(symbol > 0):        if symbol[0] != '{':            return symbol        elif varName(symbol):            return None        else:            return None      # Error in grammar spec    return ''
What should the SPPF forest look like as this Earley parsing example progresses?
algorithms;trees;parsers