GLL Recognizer

gll_shift.py

class Cell(object):
    def __init__(self, L):
        self.L = L
        self.edges = set()
        self.redus = set()

class Chart(object):
    def __init__(self):
        self.cont = []
        self.visit = set()
        self.gss = {}

    def add(self, L, cc):
        ret = (L, cc)
        if ret not in self.visit:
            self.visit.add(ret)
            self.cont.append(ret)

    def create(self, L, cc):
        if L in self.gss:
            cell = self.gss[L]
        else:
            cell = self.gss[L] = Cell(L)
        if cc not in cell.edges:
            cell.edges.add(cc)
            for pool in cell.redus:
                pool.add(L, cc)
        return cell

    def pop(self, cell):
        print 'reduce into', cell.L
        cell.redus.add(self)
        for cc in cell.edges:
            self.add(cell.L, cc)

class Parser(object):
    def __init__(self):
        self.reduc = Chart()
        self.shift = Chart()

    def step(self, token):
        while len(self.reduc.cont):
            L, cc = self.reduc.cont.pop()
            L(self, cc, token)
        self.reduc = self.shift
        self.shift = Chart()
        print "shift", repr(token)

def LS(table, cc, token):
    if token in ("a", "c"):
        table.reduc.add(LS1, cc)
    if token in ("a", "b"):
        table.reduc.add(LS2, cc)
    if token in ("d", None):
        table.reduc.add(LS3, cc)

def LS1(table, cc, token):
    LA(table, table.reduc.create(L1, cc), token)

def L1(table, cc, token):
    LS(table, table.reduc.create(L2, cc), token)

def L2(table, cc, token):
    if token == 'd':
        return table.shift.pop(cc)

def LS2(table, cc, token):
    LB(table, table.reduc.create(L3, cc), token)

def L3(table, cc, token):
    LS(table, table.reduc.create(L4, cc), token)

def L4(table, cc, token):
    return table.reduc.pop(cc)

def LS3(table, cc, token):
    return table.reduc.pop(cc)

def LA(table, cc, token):
    if token in ("a", "c"):
        return table.shift.pop(cc)

def LB(table, cc, token):
    if token in ("a", "b"):
        return table.shift.pop(cc)

def accept(table, cc, token):
    if token is None:
        print 'accept'
    else:
        print 'trunc'

acc = Cell(accept)
acc.edges.add(None)
parser = Parser()
parser.reduc.add(LS, acc)
for token in ["a", "a", "b", "d", None]:
    parser.step(token)
    if len(parser.reduc.cont) == 0 and token is not None:
        raise Exception("syn")
assert len(parser.reduc.cont) == 0
assert len(parser.shift.cont) == 0