parameters: (sent, grammar, tags, start, exhaustive)
return_statement: return (C, goal)
docstring: parse sentence, a list of tokens, optionally with gold tags, and
      produce a chart, either exhaustive or up until the viterbi parse.
docstring_summary: parse sentence, a list of tokens, optionally with gold tags, and
      produce a chart, either exhaustive or up until the viterbi parse.
docstring_tokens: parse sentence a list of tokens optionally with gold tags and produce a chart either exhaustive or up until the viterbi parse .
function: def parse(sent, grammar, tags, start, exhaustive):
      """ parse sentence, a list of tokens, optionally with gold tags, and
      produce a chart, either exhaustive or up until the viterbi parse.
      """
      unary = grammar.unary
      lbinary = grammar.lbinary
      rbinary = grammar.rbinary
      lexical = grammar.lexical
      toid = grammar.toid
      tolabel = grammar.tolabel
      goal = ChartItem(start, (1 << len(sent)) - 1)
      maxA = 0
      blocked = 0
      Cx = [{} for _ in toid]
      C = {}
      A = agenda()
  
      # scan: assign part-of-speech tags
      Epsilon = toid["Epsilon"]
      for i, w in enumerate(sent):
          recognized = False
          for terminal in lexical.get(w, []):
              if not tags or tags[i] == tolabel[terminal.lhs].split("@")[0]:
                  item = ChartItem(terminal.lhs, 1 << i)
                  I = ChartItem(Epsilon, i)
                  z = terminal.prob
                  A[item] = Edge(z, z, z, I, None)
                  C[item] = []
                  recognized = True
          if not recognized and tags and tags[i] in toid:
              item = ChartItem(toid[tags[i]], 1 << i)
              I = ChartItem(Epsilon, i)
              A[item] = Edge(0.0, 0.0, 0.0, I, None)
              C[item] = []
              recognized = True
          elif not recognized:
              print "not covered:", tags[i] if tags else w
              return C, None
  
      # parsing
      while A:
          item, edge = A.popitem()
          C[item].append(edge)
          Cx[item.label][item] = edge
  
          if item == goal:
              if exhaustive: continue
              else: break 
          for rule in unary[item.label]:
              blocked += process_edge(
                  ChartItem(rule.lhs, item.vec),
                  Edge(edge.inside + rule.prob, edge.inside + rule.prob,
                       rule.prob, item, None), A, C, exhaustive)
          for rule in lbinary[item.label]:
              for sibling in Cx[rule.rhs2]:
                  e = Cx[rule.rhs2][sibling]
                  if (item.vec & sibling.vec == 0
                      and concat(rule, item.vec, sibling.vec)):
                      blocked += process_edge(
                          ChartItem(rule.lhs, item.vec ^ sibling.vec),
                          Edge(edge.inside + e.inside + rule.prob,
                               edge.inside + e.inside + rule.prob,
                               rule.prob, item, sibling), A, C, exhaustive)
          for rule in rbinary[item.label]:
              for sibling in Cx[rule.rhs1]:
                  e = Cx[rule.rhs1][sibling]
                  if (sibling.vec & item.vec == 0
                      and concat(rule, sibling.vec, item.vec)):
                      blocked += process_edge(
                          ChartItem(rule.lhs, sibling.vec ^ item.vec),
                          Edge(e.inside + edge.inside + rule.prob,
                               e.inside + edge.inside + rule.prob,
                               rule.prob, sibling, item), A, C, exhaustive)
          if len(A) > maxA: maxA = len(A)
          #if len(A) % 10000 == 0:
          #    print "agenda max %d, now %d, items %d" % (maxA, len(A), len(C))
      stderr.write("agenda max %d, now %d, items %d (%d labels), " % (
                                  maxA, len(A), len(C), len(filter(None, Cx))))
      stderr.write("edges %d, blocked %d\n"
  							% (sum(map(len, C.values())), blocked))
      if goal not in C: goal = None
      return (C, goal)
function_tokens: def parse ( sent , grammar , tags , start , exhaustive ) : unary = grammar . unary lbinary = grammar . lbinary rbinary = grammar . rbinary lexical = grammar . lexical toid = grammar . toid tolabel = grammar . tolabel goal = ChartItem ( start , ( 1 << len ( sent ) ) - 1 ) maxA = 0 blocked = 0 Cx = [ { } for _ in toid ] C = { } A = agenda ( ) # scan: assign part-of-speech tags Epsilon = toid [ "Epsilon" ] for i , w in enumerate ( sent ) : recognized = False for terminal in lexical . get ( w , [ ] ) : if not tags or tags [ i ] == tolabel [ terminal . lhs ] . split ( "@" ) [ 0 ] : item = ChartItem ( terminal . lhs , 1 << i ) I = ChartItem ( Epsilon , i ) z = terminal . prob A [ item ] = Edge ( z , z , z , I , None ) C [ item ] = [ ] recognized = True if not recognized and tags and tags [ i ] in toid : item = ChartItem ( toid [ tags [ i ] ] , 1 << i ) I = ChartItem ( Epsilon , i ) A [ item ] = Edge ( 0.0 , 0.0 , 0.0 , I , None ) C [ item ] = [ ] recognized = True elif not recognized : print "not covered:" , tags [ i ] if tags else w return C , None # parsing while A : item , edge = A . popitem ( ) C [ item ] . append ( edge ) Cx [ item . label ] [ item ] = edge if item == goal : if exhaustive : continue else : break for rule in unary [ item . label ] : blocked += process_edge ( ChartItem ( rule . lhs , item . vec ) , Edge ( edge . inside + rule . prob , edge . inside + rule . prob , rule . prob , item , None ) , A , C , exhaustive ) for rule in lbinary [ item . label ] : for sibling in Cx [ rule . rhs2 ] : e = Cx [ rule . rhs2 ] [ sibling ] if ( item . vec & sibling . vec == 0 and concat ( rule , item . vec , sibling . vec ) ) : blocked += process_edge ( ChartItem ( rule . lhs , item . vec ^ sibling . vec ) , Edge ( edge . inside + e . inside + rule . prob , edge . inside + e . inside + rule . prob , rule . prob , item , sibling ) , A , C , exhaustive ) for rule in rbinary [ item . label ] : for sibling in Cx [ rule . rhs1 ] : e = Cx [ rule . rhs1 ] [ sibling ] if ( sibling . vec & item . vec == 0 and concat ( rule , sibling . vec , item . vec ) ) : blocked += process_edge ( ChartItem ( rule . lhs , sibling . vec ^ item . vec ) , Edge ( e . inside + edge . inside + rule . prob , e . inside + edge . inside + rule . prob , rule . prob , sibling , item ) , A , C , exhaustive ) if len ( A ) > maxA : maxA = len ( A ) #if len(A) % 10000 == 0: #    print "agenda max %d, now %d, items %d" % (maxA, len(A), len(C)) stderr . write ( "agenda max %d, now %d, items %d (%d labels), " % ( maxA , len ( A ) , len ( C ) , len ( filter ( None , Cx ) ) ) ) stderr . write ( "edges %d, blocked %d\n" % ( sum ( map ( len , C . values ( ) ) ) , blocked ) ) if goal not in C : goal = None return ( C , goal )