ret = []
for production in productions:
if '|' in production:
head = production[:len("N -> ")]
ret += [head + sub.strip() + "$" for sub in production[len(head):].split('|')]
else:
ret += [production + "$"]
return ret
def GetLR0(production):
head = production[:len("N -> ")]
tail = production[len(head):-1] # except $
items = [head + tail[:pos] + '.' + tail[pos:] + '$'
for pos in range(len(tail))]
return items
def GetNewStartProduction(productions):
return '0 -> %c$' % productions[0][0]
def GetMarkSymbol(item):
pos = item.find('.')
return item[pos + 1]
def IsNonterminal(symbol):
return symbol.isupper()
def Closure(item, productions):
# add self
ret = [item]
markSymbol = GetMarkSymbol(item)
if IsNonterminal(markSymbol) and markSymbol[0] != item[0]:
relationProductions = [production
for production in productions
if production[0] == markSymbol]
# add relation production closures
relationClosures = [Closure(GetLR0(production)[0], productions)
for production in relationProductions]
for relationClosure in relationClosures:
ret += relationClosure
return ret
def Goto(items, nextToken, productions):
movableItems = [item
for item in items
if item[item.find('.') + 1] == nextToken]
nextItems = []
ret = []
for item in movableItems:
curPos = item.find('.')
nextPos = curPos + 1
nextItem = item[:curPos] + item[nextPos] + '.' + item[nextPos + 1:]
ret += Closure(nextItem, productions)
return ret
def GetMarkSymbols(items):
markSymbols = [GetMarkSymbol(item) for item in items]
ret = []
for markSymbol in markSymbols:
if markSymbol in ret:
pass
else:
ret.append(markSymbol)
return ret
class Node:
index = 0
def __init__(self, items, productions, gotoList):
gotoList.append(self)
self.name = "I%d" % (Node.index)
Node.index += 1
self.items = items
self.nextTokens = [markSymbol
for markSymbol in GetMarkSymbols(items)
if markSymbol != '$']
print self.name, self.items
def FindSameNode(self, items, gotoList):
for node in gotoList:
if node.items == items:
return node
return None
def MakeChildren(self, stack, productions, gotoList):
print self.name, "MakeChildren"
gotos = [(nextToken, Goto(self.items, nextToken, productions))
for nextToken in self.nextTokens]
self.children = []
for nextToken, goto in gotos:
sameNode = self.FindSameNode(goto, gotoList)
if sameNode:
print "FoundSameNode! Redirect[%s]: %s" % (sameNode.name, goto)
self.children.append((nextToken, sameNode))
else:
child = Node(goto, productions, gotoList)
self.children.append((nextToken, child))
stack.append(child)
#raw_input()
def MakeTransitionGraph(productions):
gotoList = []
productions = SplitProductions(productions)
productions = [GetNewStartProduction(productions)] + productions
newStartProduction = GetLR0(productions[0])[0]
print productions
argmentedProductions = Closure(newStartProduction, productions)
rootNode = Node(argmentedProductions, productions, gotoList)
stack = [rootNode]
while stack:
parent = stack.pop(0)
parent.MakeChildren(stack, productions, gotoList)
return rootNode
"""
productions = [
"E -> E+T | T",
"T -> T*F | F",
"F -> (E) | a",
]
"""
productions = [
"S -> (L) | a",
"L -> L,S | S",
]
print "-" * 80
MakeTransitionGraph(productions)
결과보기
more..
(0) 
(0)
python 을 좋아하는 게임 프로그래머
