fork download
copy 
  1. import collections
  2.  
  3. def build(CNF):
  4.     G = collections.defaultdict(list)
  5.     for left, right in CNF:
  6.         G[right].append(left)
  7.     return G
  8.  
  9. def cky(G, W):
  10.     T = [[[] for j in range(len(W)+1)] for i in range(len(W))]
  11.     for j in range(1, len(W)+1):
  12.         T[j-1][j] += G.get(W[j-1], [])
  13.         print "[%d,%d]: %r" % (j-1, j, G.get(W[j-1]))
  14.         for i in range(j-2, -1, -1):
  15.             for k in range(i+1, j):
  16.                 for x in T[i][k]:
  17.                     for y in T[k][j]:
  18.                         T[i][j] += G.get((x,y), [])
  19.                         print "[%d,%d]: %r      = ( %s[%d,%d] + %s[%d,%d] )" % (i,j,G.get((x,y)),x,i,k,y,k,j)
  20.     return T
  21.  
  22. if __name__ == '__main__':
  23.     CNF = (
  24.         ('S', ('NP','VP')),
  25.         ('NP', ('CD','NP')),
  26.         ('NP', ('UN','NP')),
  27.         ('NP', ('NN','ADJP')),
  28.         ('VP', ('VP','NP')),
  29.         ('VP', ('ADVP','VB')),
  30.         ('NP', 'Nam'),
  31.         ('NN', 'xe'), 
  32.         ('CD', 'mot'),
  33.         ('VB', 'mua'),
  34.         ('ADJP', 'moi'),
  35.         ('ADVP', 'moi'),
  36.         ('UN', 'chiec'),
  37.     )
  38.     G = build(CNF)
  39.     n = 'Nam','moi','mua','mot','chiec','xe','moi'
  40.     T = cky(G, n)
  41.     print n
  42.     for l in range(0, len(n)):
  43.         T[l][0] = l
  44.     for l in range(0, len(n)):
  45.             print T[l]
  46.  
Success #stdin #stdout 0s 23688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0,1]: ['NP']
[1,2]: ['ADJP', 'ADVP']
[0,2]: None      = ( NP[0,1] + ADJP[1,2] )
[0,2]: None      = ( NP[0,1] + ADVP[1,2] )
[2,3]: ['VB']
[1,3]: None      = ( ADJP[1,2] + VB[2,3] )
[1,3]: ['VP']      = ( ADVP[1,2] + VB[2,3] )
[0,3]: ['S']      = ( NP[0,1] + VP[1,3] )
[3,4]: ['CD']
[2,4]: None      = ( VB[2,3] + CD[3,4] )
[1,4]: None      = ( VP[1,3] + CD[3,4] )
[0,4]: None      = ( S[0,3] + CD[3,4] )
[4,5]: ['UN']
[3,5]: None      = ( CD[3,4] + UN[4,5] )
[5,6]: ['NN']
[4,6]: None      = ( UN[4,5] + NN[5,6] )
[6,7]: ['ADJP', 'ADVP']
[5,7]: ['NP']      = ( NN[5,6] + ADJP[6,7] )
[5,7]: None      = ( NN[5,6] + ADVP[6,7] )
[4,7]: ['NP']      = ( UN[4,5] + NP[5,7] )
[3,7]: ['NP']      = ( CD[3,4] + NP[4,7] )
[2,7]: None      = ( VB[2,3] + NP[3,7] )
[1,7]: ['VP']      = ( VP[1,3] + NP[3,7] )
[0,7]: ['S']      = ( NP[0,1] + VP[1,7] )
[0,7]: None      = ( S[0,3] + NP[3,7] )
('Nam', 'moi', 'mua', 'mot', 'chiec', 'xe', 'moi')
[0, ['NP'], [], ['S'], [], [], [], ['S']]
[1, [], ['ADJP', 'ADVP'], ['VP'], [], [], [], ['VP']]
[2, [], [], ['VB'], [], [], [], []]
[3, [], [], [], ['CD'], [], [], ['NP']]
[4, [], [], [], [], ['UN'], [], ['NP']]
[5, [], [], [], [], [], ['NN'], ['NP']]
[6, [], [], [], [], [], [], ['ADJP', 'ADVP']]
https://ideone.com/jQqlcB
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!