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 FIRST(rules):
firstDict = {}
# step 1
for rule in rules:
var, eq, stmt = rule.split()
firstDict[var] = []
# step 2
for rule in rules:
var, eq, stmt = rule.split()
if stmt[0] in TERMINAL:
firstDict[var] = UNION(firstDict[var], [stmt[0]])
# 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)
firstDict[var] = newFirst
newRepr = repr(firstDict)
if oldRepr == newRepr:
break
return firstDict
def UNION_EXCEPT_UPSILON(a, b):
if "." in b:
b_except_upsilon = [] + b
b_except_upsilon.remove(".")
return UNION(a, b_except_upsilon)
else:
return UNION(a, b)
def PRINT_FOLLOW(rules):
firstDict = FIRST(rules)
followDict = {}
# step1 시작 심벌만 $ 로 초기화
for idx, rule in enumerate(rules):
var, eq, stmt = rule.split()
if idx == 0:
followDict[var] = ["$"]
else:
followDict[var] = []
print followDict
# step 2 A = ?BN 모양을 찾은 다음
# FOLLOW(B) 에 입실론_제외_FIRST(N) 을 합한다
for rule in rules:
var, eq, stmt = rule.split()
for nonTerminal in firstDict:
nonTerminalPos = stmt.find(nonTerminal)
if nonTerminalPos >= 0:
nonTerminalNextPos = nonTerminalPos + 1
if nonTerminalNextPos < len(stmt):
nextChar = stmt[nonTerminalNextPos]
nextFirst = firstDict.get(nextChar, [nextChar])
if "." == nextFirst:
pass
else:
followDict[nonTerminal] = UNION_EXCEPT_UPSILON(followDict[nonTerminal], nextFirst)
print followDict
# step 3 A = B or
# A = ?B or
# A = ?BN 이고 FIRST(N) 에 입실론이 있을 경우
# FOLLOW(B) 에 FOLLOW(A) 를 합한다
while True:
oldRepr = repr(followDict)
for rule in rules:
var, eq, stmt = rule.split()
for nonTerminal in firstDict:
nonTerminalPos = stmt.find(nonTerminal)
if nonTerminalPos >= 0:
nonTerminalNextPos = nonTerminalPos + 1
if nonTerminalNextPos < len(stmt):
nextChar = stmt[nonTerminalNextPos]
nextFirst = firstDict.get(nextChar, [nextChar])
if "." in nextFirst:
#print "upsilon in follow"
pass
else:
continue
else:
#print "not exist follow"
pass
followDict[nonTerminal] = UNION(followDict[nonTerminal], followDict[var])
newRepr = repr(followDict)
if oldRepr == newRepr:
break
print followDict
rules = [
"E = TX",
"X = +TX",
"X = .",
"T = FY",
"Y = *FY",
"Y = .",
"F = (E)",
"F = a",
]
PRINT_FOLLOW(rules)
결과
{'Y': [], 'X': [], 'E': ['$'], 'T': [], 'F': []}
{'Y': [], 'X': [], 'E': ['$', ')'], 'T': ['+'], 'F': ['*']}
{'Y': ['$', ')', '+'], 'X': ['$', ')'], 'E': ['$', ')'], 'T': ['$', ')', '+'], 'F': ['$', ')', '*', '+']}
Hit any key to close this window...
(0) 
(0)
python 을 좋아하는 게임 프로그래머
