# Algorytm Cooke'a-Youngera-Kasamiego # # Programy wypisuje na standardowe wyjście plik HTML-owy, w którym pokazano # poszczególne kroki algorytmu. # # Wojciech Muła, 27.03.2004 def parse(string): try: string.index('->') except: raise "Nie zdefiniowano produkcji. Źródło błędu: '%s'." % (R) tmp = string.split('->', 2) f = tmp[0].strip(); t = [i.strip() for i in tmp[1].split('|')] if len(f) > 1: raise "Z lewej strony może występować tylko jeden symbol." if not f.isupper(): raise "Z lewej strony może występować wyłącznie jeden symbol nietermianlny." for i in t: if len(i) == 1 and not i.lower(): raise "Spodziewano się symbolu terminalnego. Źródło błędu: '%s'." % i if len(i) > 2: raise "Po prawej stronie mogą być słowa o długości 1 albo 2. Źródło błędu: '%s'." % i if len(i) == 2 and (not i[0].isupper() or not i[1].isupper()): raise "Spodziewano się słowa złożonego z dwóch symbli nieterminalnych. Źródło błędu: '%s'." % i return f, t def lookup(P, string): result = [] for i in P: result = result + [i for x in P[i] if x==string] return result def uniq(L): res = {} for i in L: res[i] = 0 return res.keys() def CYK(x, rules_list, start_symbol='S'): n = len(x); # parsowanie reguł P = {} for i in rules_list: f,t = parse(i) P[f] = t tmp = uniq("".join([i+"".join(P[i]) for i in P])) l = [i for i in tmp if i.islower()] l.sort() u = [i for i in tmp if i.isupper()] u.remove(start_symbol) u.sort() u = [start_symbol] + u print "
G = <{%s}, {%s}, P, %s>
" % (", ".join(u+l), ", ".join(l), start_symbol) print "

P:

" k = P.keys() k.remove(start_symbol) k.sort() k = [start_symbol] + k for i in k: print "%s → %s
" % (i, "|".join(P[i])) print "
x = %s
" % x V = {} print "

Pierwsza część algorytmu

" print "" print "

Druga część algorytmu

" # druga część algorytmu (zagnieżdżone pętle) print "" # tabelka print '' for j in xrange(1,n+1): print "" for i in xrange(1,n+1): if V.has_key((i,j)): if len(V[(i,j)]): p = ",".join(V[(i,j)]) else: p = "-" r = i >= n-j+1 t = j == 1 print '' % (t,r,p), else: print '', print "" for i in xrange(1,n+1): if V.has_key((i,j)): r = i >= n-j+1 p = '' % (r,i,j) else: p = '' print p, print "
%s
V%d%d
" if start_symbol in V[(1,n)]: print "

Ponieważ %s ∈ V1%d, zatem słowo %s należy do języka L(G)." % (start_symbol, n, x) else: print "

Słowo %s nie należy do języka." % x if __name__ == "__main__": import sys def help(): print "-f=file - zbiór reguł produkcji" print "-w=word - słowo które sprawdzamy" print "-s=S - symbol startowy (domyślnie 'S')" print "-h - to co teraz czytasz" file = "" word = "" start = "S" for i in sys.argv: if i=="-h": help() sys.exit() if i.startswith("-f="): file = i[3:] if i.startswith("-w="): word = i[3:] if i.startswith("-s="): start = i[3:4] if file=="": print "Podaj nazwę pliku." sys.exit(1) if word=="": print "Podaj słowo które ma zostać sprawdzone." sys.exit(1) try: file = open(file, "r") rules = [line[:-1] for line in file.readlines()] file.close() print '' print '' print '' print '\t' print '\t' print '\t' print '\tSprawdzenie czy %s należy do języka' % word print '' print '' CYK(word, rules, start) print "" print "" except: print "Error:", sys.exc_info()[1] sys.exit(2)