Error Correcting Earley Parser

DRAFT

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

We talked about Earley parsers previously. One of the interesting things about Earley parsers is that it also forms the basis of best known general context-free error correcting parser. A parser is error correcting if it is able to parse corrupt inputs that only partially conform to a given grammar. The particular algorithm we will be examining is the minimum distance error correcting parser by Aho et al.¹.

Covering Grammar

The idea from Aho et al. is to first transform the given grammar into a covering grammar. A grammar $G_2$ covers another grammar $G_1$ if (in essence) all productions in $G_1$ are in $G_2$, and a string that is parsed by $G_1$ is guaranteed to be parsed by $G_2$, and all the parses from $G_1$ are guaranteed to exist in the set of parses from $G_2$.

So, we first construct a covering grammar that can handle any corruption of input, with the additional property that there will be a parse of the corrupt string which contains the minimum number of modifications needed such that if they are applied on the string, it will make it parsed by the original grammar.

First, the prerequisites

Our Grammar

We can also print it.

Checking whether a term is nonterminal

Now, the covering grammar itself. The covering grammar constructed by Aho et al. is fairly straight forward. It handles three possible mutations of the input

The replacement of a terminal symbol by another terminal symbol
The insertion of an extra terminal symbol
Deletion of a terminal symbol

Any number and combinations of these mutations can accumulate in an input. That is, in effect, any string can be considered a mutation of a parsable string, and hence we can expect the covering grammar to parse it.

Next, to make sure that any string is parsable, we first define a nonterminal that is capable of parsing any string. For ease of parsing, let us define a new terminal symbol that stands in for any terminal symbol. This stands for $I$ in Aho’s paper.

We should be able to parse any number of such symbols. So, we define a new nonterminal for that. This stands for $H$ in Aho’s paper.

In a similar fashion, we also need a terminal symbol that will match any except a given terminal symbol. Since this is specific to a terminal symbol, let us make it a method.

Note that both Any_one and Any_not can be made into nonterminal symbols with corresponding definitions if required so that the resulting grammar is fully in the context-free format. We do not do that here because it is easier this way.

How do we check for match between a terminal symbol and a given input symbol?

Checking it

We need to transform our grammar. Essentially, the idea is that for each terminal symbol in the grammar, we add a nonterminal symbol that handles the following possibilities

The terminal is matched exactly as provided with a symbol in input
The symbol that matches terminal is replaced by something else in the input, which means another symbol instead of the expected one
Some junk symbols are present before the symbol that matches the given terminal
The expected symbol was deleted from input string

That is, given a is a terminal symbol, we add the following error productions, where <$ a> is the corresponding nonterminal.

<$ a> -> a
<$ a> -> <$.+> a
<$ a> -> $\epsilon$
<$ a> -> {!a}

For each such correction, we add one penalty. In essence, the following general correction rules get one penalty if they are used. That is, each any character {$.} is a correction, and the count of such any characters is the penalty in these rules.

<$.+> -> <$.+> {$.}
<$.+> -> {$.}

Also, these terminal corrections get one penalty. Again, like above, the penalty here is because of not matching a particular expected character.

<$ a> -> $\epsilon$
<$ a> -> {!a}

Notice that we do not have to add penalty for the junk insertion because that is already been applied by the general corrections.

These are added to the grammar as follows.

We modify the grammar to add this new nonterminal.

Finally, we need to modify the start symbol to let junk symbols after the parse. This is handled by adding a new start symbol as below.

<$start> -> <start>
<$start> -> <start> <$.+>

Next, we extract the nullable keys used in Earley parsing

The column definition is exactly the same as before, but with one crucial difference. When we compare uniqueness of states in add(), we give priority to states with less penalty. That is, if the state being added has a lower penalty than an existing state, it is replaced.

class Column:
    def __init__(self, index, letter):
        self.index, self.letter = index, letter
        self.states, self._unique = [], {}

def __str__(self):
        return "%s chart[%d]\n%s" % (self.letter, self.index, "\n".join(
            str(state) for state in self.states if state.finished()))

def add(self, state):
        if state in self._unique:
            if self._unique[state].weight > state.weight:
                # delete from self.states in fill_chart
                state.e_col = self
                self.states.append(state)
                self._unique[state] = state
            return self._unique[state]
        self._unique[state] = state
        self.states.append(state)
        state.e_col = self
        return self._unique[state]

def remove_extra_states(self):
        my_states = []
        for state in self._unique:
            cur_states = [s for s in self.states if s == state]
            if len(cur_states) > 1:
                cur_states = sorted(cur_states, key=lambda s: s.weight)
            my_states.append(cur_states[0])
        self.states = my_states
        return

No changes in the definition of state.

class State:
    def __init__(self, name, expr, dot, s_col, e_col=None):
        self.name, self.expr_, self.dot = name, expr, dot
        self.s_col, self.e_col = s_col, e_col
        self.expr, self.weight = expr

def finished(self):
        return self.dot >= len(self.expr)

def at_dot(self):
        return self.expr[self.dot] if self.dot < len(self.expr) else None

def __str__(self):
        def idx(var):
            return var.index if var else -1

return self.name + ':= ' + ' '.join([
            str(p)
            for p in [*self.expr[:self.dot], '|', *self.expr[self.dot:]]
            ]) + "(%d,%d):%d" % (idx(self.s_col), idx(self.e_col), self.weight)

def copy(self):
        return State(self.name, (self.expr, self.weight), self.dot, self.s_col, self.e_col)

def _t(self):
        return (self.name, self.expr, self.dot, self.s_col.index)

def __hash__(self):
        return hash(self._t())

def __eq__(self, other):
        return self._t() == other._t()

def advance(self):
        return State(self.name, (self.expr, self.weight), self.dot + 1, self.s_col)

Next, the parser itself. We need to make sure that the grammar we use is the updated grammar.

Remaining is almost exactly same as the original Earley parser except for complete() where we have to transfer the penalties to the parent parse.

class EarleyParser(EarleyParser):
    def chart_parse(self, tokens, start, alt):
        chart = [Column(i, tok) for i, tok in enumerate([None, *tokens])]
        chart[0].add(State(start, alt, 0, chart[0]))
        return self.fill_chart(chart)

class EarleyParser(EarleyParser):
    def predict(self, col, sym, state):
        for alt in self._grammar[sym]:
            col.add(State(sym, alt, 0, col))
        if sym in self.epsilon:
            col.add(state.advance())

class EarleyParser(EarleyParser):
    def scan(self, col, state, letter):
        if terminal_match(letter, col.letter):
            s = state.advance()
            s.expr = col.letter
            col.add(s)

class EarleyParser(EarleyParser):
    def complete(self, col, state):
        parent_states = [st for st in state.s_col.states
                 if st.at_dot() == state.name]
        for st in parent_states:
            s = st.advance()
            s.weight += state.weight
            col.add(s)

class EarleyParser(EarleyParser):
    def fill_chart(self, chart):
        for i, col in enumerate(chart):
            for state in col.states:
                if state.finished():
                    self.complete(col, state)
                else:
                    sym = state.at_dot()
                    if sym in self._grammar:
                        self.predict(col, sym, state)
                    else:
                        if i + 1 >= len(chart):
                            continue
                        self.scan(chart[i + 1], state, sym)
            col.remove_extra_states()
            if self.log: print(col, '\n')
        return chart

The extraction of parse trees.

class EarleyParser(EarleyParser):
    def parse_prefix(self, text, start_symbol, alt):
        self.table = self.chart_parse(text, start_symbol, alt)
        for col in reversed(self.table):
            states = [st for st in col.states
                if st.name == start_symbol and st.expr == alt[0] and st.s_col.index == 0
            ]
            if states:
                return col.index, states
        return -1, []

class EarleyParser(EarleyParser):
    def parse_paths(self, named_expr, chart, frm, til):
        def paths(state, start, k, e):
            if not e:
                return [[(state, k)]] if start == frm else []
            else:
                return [[(state, k)] + r
                        for r in self.parse_paths(e, chart, frm, start)]

*expr, var = named_expr
        starts = None
        if var not in self._grammar:
            starts = ([(var, til - len(var),
                        't')] if til > 0 and chart[til].letter == var else [])
        else:
            starts = [(s, s.s_col.index, 'n') for s in chart[til].states
                      if s.finished() and s.name == var]

return [p for s, start, k in starts for p in paths(s, start, k, expr)]

class EarleyParser(EarleyParser):
    def forest(self, s, kind, chart):
        return self.parse_forest(chart, s) if kind == 'n' else (s, [])

def parse_forest(self, chart, state):
        pathexprs = self.parse_paths(state.expr, chart, state.s_col.index,
                                     state.e_col.index) if state.expr else []
        return state.name, [[(v, k, chart) for v, k in reversed(pathexpr)]
                            for pathexpr in pathexprs]

class EarleyParser(EarleyParser):
    def parse_on(self, text, start_symbol):
        self._grammar = add_start(self._grammar, start_symbol)
        print_g(self._grammar)

for alt in self._grammar[start_symbol]:
            cursor, states = self.parse_prefix(text, start_symbol, alt)
            start = next((s for s in states if s.finished()), None)

if cursor < len(text) or not start:
                #raise SyntaxError("at " + repr(text[cursor:]))
                continue
            forest = self.parse_forest(self.table, start)
            print('weight = ', str(start))
            yield forest

Now, we can use a simple extractor to extract one of the error correcting parses with lowest penalties.

class SimpleExtractor:
    def __init__(self, parser, text, start_symbol):
        parser._grammar = add_start(parser._grammar, start_symbol)
        self.parser = parser
        cursor, states = parser.parse_prefix(text, start_symbol, parser._grammar[start_symbol][0])
        start = next((s for s in states if s.finished()), None)
        if cursor < len(text) or not start:
            raise SyntaxError("at " + repr(cursor))
        self.my_forest = parser.parse_forest(parser.table, start)

def extract_a_node(self, forest_node):
        name, paths = forest_node
        if not paths:
            return ((name, 0, 1), []), (name, [])
        cur_path, i, l = self.choose_path(paths)
        child_nodes = []
        pos_nodes = []
        for s, kind, chart in cur_path:
            f = self.parser.forest(s, kind, chart)
            postree, ntree = self.extract_a_node(f)
            child_nodes.append(ntree)
            pos_nodes.append(postree)

return ((name, i, l), pos_nodes), (name, child_nodes)

def choose_path(self, arr):
        l = len(arr)
        i = random.randrange(l)
        res = sorted([(self.cost_of_path(a),a) for a in arr], key=lambda a: a[0])
        return res[0][1], None, None

def cost_of_path(self, p):
        states = [s for s,kind,chart in p if kind == 'n']
        return sum([s.weight for s in states])

def extract_a_tree(self):
        pos_tree, parse_tree = self.extract_a_node(self.my_forest)
        return parse_tree

class O:
    def __init__(self, **keys): self.__dict__.update(keys)
    def __repr__(self): return str(self.__dict__)

Options = O(F='|', L='+', V='|', H='-', NL='\n')

def format_newlines(prefix, formatted_node):
    replacement = ''.join([Options.NL, '\n', prefix])
    return formatted_node.replace('\n', replacement)

def format_tree(node, format_node, get_children, prefix=''):
    children = list(get_children(node))
    next_prefix = ''.join([prefix, Options.V, '   '])
    for child in children[:-1]:
        fml = format_newlines(next_prefix, format_node(child))
        yield ''.join([prefix, Options.F, Options.H, Options.H, ' ', fml])
        tree = format_tree(child, format_node, get_children, next_prefix)
        for result in tree:
            yield result
    if children:
        last_prefix = ''.join([prefix, '    '])
        fml = format_newlines(last_prefix, format_node(children[-1]))
        yield ''.join([prefix, Options.L, Options.H, Options.H, ' ', fml])
        tree = format_tree(children[-1], format_node, get_children, last_prefix)
        for result in tree:
            yield result

def format_parsetree(node,
          format_node=lambda x: repr(x[0]),
          get_children=lambda x: x[1]):
    lines = I.chain([format_node(node)], format_tree(node, format_node, get_children), [''],)
    return '\n'.join(lines)

Alfred V. Aho and Thomas G. Peterson, A Minimum Distance Error-Correcting Parser for Context-Free Languages, SIAM Journal on Computing, 1972 https://doi.org/10.1137/0201022 ↩