Last change
on this file since 252 was 252, checked in by Rick van der Zwet, 14 years ago |
Helper script for assignment 1 :-(
|
-
Property svn:executable
set to
*
|
File size:
1.4 KB
|
Line | |
---|
1 | #!/usr/bin/env python
|
---|
2 | #
|
---|
3 | # Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm.
|
---|
4 | #
|
---|
5 |
|
---|
6 |
|
---|
7 | # Word to search for
|
---|
8 | w = 'cabab'
|
---|
9 |
|
---|
10 | # CNF
|
---|
11 | cnf = {
|
---|
12 | 'S' : ['AB','b'],
|
---|
13 | 'A' : ['CB', 'AA','a'],
|
---|
14 | 'B' : ['AS', 'b'],
|
---|
15 | 'C' : ['BS', 'c'],
|
---|
16 | }
|
---|
17 |
|
---|
18 | def irange(i,j):
|
---|
19 | """ Return i till and including(!) j """
|
---|
20 | return range(i,j+1)
|
---|
21 |
|
---|
22 | n = len(w)
|
---|
23 | r = [[[]]*(n+1) for x in irange(0,n)]
|
---|
24 |
|
---|
25 |
|
---|
26 |
|
---|
27 |
|
---|
28 | def printr():
|
---|
29 | print 'i\\textbackslash j &',
|
---|
30 | for i in irange(1,n):
|
---|
31 | print "%-10s &" % i,
|
---|
32 | print "\\\\ \\hline \\hline"
|
---|
33 |
|
---|
34 |
|
---|
35 | for i in irange(1,n):
|
---|
36 | print "%17i &" % i,
|
---|
37 | for j in irange(1,n):
|
---|
38 | if r[i][j] == [None]:
|
---|
39 | item = "@"
|
---|
40 | else:
|
---|
41 | item = ",".join(r[i][j]),
|
---|
42 | print "%-10s &" % item,
|
---|
43 | print "\\\\ \\hline"
|
---|
44 |
|
---|
45 | def to_r(i,j,k):
|
---|
46 | if k not in r[i][j]:
|
---|
47 | if r[i][j] == [None]:
|
---|
48 | r[i][j] = [k]
|
---|
49 | else:
|
---|
50 | r[i][j] = r[i][j] + [k]
|
---|
51 |
|
---|
52 | def from_r(i,j):
|
---|
53 | return r[i][j]
|
---|
54 |
|
---|
55 | def letter(i):
|
---|
56 | return w[i-1]
|
---|
57 |
|
---|
58 |
|
---|
59 | # Initial productions (leafs)
|
---|
60 | for i in irange(1,n):
|
---|
61 | for k,v in cnf.iteritems():
|
---|
62 | if letter(i) in v:
|
---|
63 | to_r(i,i,k)
|
---|
64 |
|
---|
65 | # Longer length Productions
|
---|
66 | for d in irange(1,n-1):
|
---|
67 | for i in irange(1,n-d):
|
---|
68 | j = i + d
|
---|
69 | to_r(i,j,None)
|
---|
70 | for k in irange(i,j-1):
|
---|
71 | for y,z in cnf.iteritems():
|
---|
72 | # Iterate over all YX rules
|
---|
73 | for x in [w for w in z if len(w) == 2]:
|
---|
74 | if x[0] in from_r(i,k) and x[1] in from_r(k+1,j):
|
---|
75 | to_r(i,j,y)
|
---|
76 |
|
---|
77 |
|
---|
78 | printr()
|
---|
Note:
See
TracBrowser
for help on using the repository browser.