Skip to content

Instantly share code, notes, and snippets.

@cheery
Created May 3, 2015 22:03
Show Gist options
  • Save cheery/2285d595d7bde2f3e499 to your computer and use it in GitHub Desktop.
Save cheery/2285d595d7bde2f3e499 to your computer and use it in GitHub Desktop.
GLL Recognizer
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment