Created
May 3, 2015 22:03
-
-
Save cheery/2285d595d7bde2f3e499 to your computer and use it in GitHub Desktop.
GLL Recognizer
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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