def RING_SUM(a, b):
if "." in a:
a_except_upsilon = [] + a
a_except_upsilon.remove(".")
return a_except_upsilon + b
else:
return a
def UNION(a, b):
for e in b:
if e in a:
pass
else:
a.append(e)
a.sort()
return a
def PRINT_FIRST(rules):
firstDict = {}
# step 1
for rule in rules:
var, eq, stmt = rule.split()
firstDict[var] = []
print firstDict
# step 2
for rule in rules:
var, eq, stmt = rule.split()
if stmt[0] in TERMINAL:
firstDict[var] = UNION(firstDict[var], [stmt[0]])
print firstDict
# step 3
while True:
oldRepr = repr(firstDict)
for rule in rules:
var, eq, stmt = rule.split()
if stmt[0] in TERMINAL:
pass
else:
oldFirst = firstDict[var]
addFirst = firstDict[stmt[0]]
for next in stmt[1:]:
addFirst = RING_SUM(addFirst, firstDict.get(next, [next]))
newFirst = UNION(oldFirst, addFirst)
print "update", var, newFirst
firstDict[var] = newFirst
newRepr = repr(firstDict)
if oldRepr == newRepr:
break
firstDict = firstDict
print firstDict
rules = [
"E = TX",
"X = +TX",
"X = .",
"T = FY",
"Y = *FY",
"Y = .",
"F = (E)",
"F = a",
]
PRINT_FIRST(rules)
결과
{'Y': [], 'X': [], 'E': [], 'T': [], 'F': []}
{'Y': ['*', '.'], 'X': ['+', '.'], 'E': [], 'T': [], 'F': ['(', 'a']}
update E []
update T ['(', 'a']
update E ['(', 'a']
update T ['(', 'a']
update E ['(', 'a']
update T ['(', 'a']
{'Y': ['*', '.'], 'X': ['+', '.'], 'E': ['(', 'a'], 'T': ['(', 'a'], 'F': ['(', 'a']}
(0) 
(0)
python 을 좋아하는 게임 프로그래머
