Source Code for Module nltk.ccg.api

  1  # Natural Language Toolkit: CCG Categories 
  2  # 
  3  # Copyright (C) 2001-2011 NLTK Project 
  4  # Author: Graeme Gange <ggange@csse.unimelb.edu.au> 
  5  # URL: <http://www.nltk.org/> 
  6  # For license information, see LICENSE.TXT 
  7   
  8 -class AbstractCCGCategory(object): 
  9      ''' 
 10      Interface for categories in combinatory grammars. 
 11      ''' 
 12       
 13      # Returns true if the category is primitive 
 14 -    def is_primitive(self): 
 15          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 16   
 17      # Returns true if the category is a function application 
 18 -    def is_function(self): 
 19          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 20   
 21      # Returns true if the category is a variable 
 22 -    def is_var(self): 
 23          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 24   
 25      # Takes a set of (var, category) substitutions, and replaces every 
 26      # occurrence of the variable with the corresponding category 
 27 -    def substitute(self,substitutions): 
 28          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 29   
 30      # Determines whether two categories can be unified. 
 31      #  - Returns None if they cannot be unified 
 32      #  - Returns a list of necessary substitutions if they can.''' 
 33 -    def can_unify(self,other): 
 34          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 35       
 36      # Utility functions: comparison, strings and hashing. 
 37 -    def __cmp__(self,other): 
 38          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 39   
 40 -    def __str__(self): 
 41          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 42   
 43 -    def __hash__(self): 
 44          raise AssertionError, 'AbstractCCGCategory is an abstract interface' 
 45   
 46   
 47 -class CCGVar(AbstractCCGCategory): 
 48      ''' 
 49      Class representing a variable CCG category. 
 50      Used for conjunctions (and possibly type-raising, if implemented as a 
 51      unary rule). 
 52      ''' 
 53      _maxID = 0 
 54   
 55 -    def __init__(self, prim_only=False): 
 56          """Initialize a variable (selects a new identifier) 
 57   
 58          @param prim_only: a boolean that determines whether the variable is restricted to primitives  
 59          @type prim_only: C{boolean} 
 60          """ 
 61          self._id = self.new_id() 
 62          self._prim_only = prim_only 
 63       
 64      # A class method allowing generation of unique variable identifiers. 
 65 -    def new_id(cls): 
 66          cls._maxID = cls._maxID + 1 
 67          return cls._maxID - 1 
 68      new_id = classmethod(new_id) 
 69   
 70 -    def is_primitive(self): 
 71          return False 
 72   
 73 -    def is_function(self): 
 74          return False 
 75   
 76 -    def is_var(self): 
 77          return True 
 78       
 79 -    def substitute(self, substitutions): 
 80          """If there is a substitution corresponding to this variable, 
 81          return the substituted category. 
 82          """ 
 83          for (var,cat) in substitutions: 
 84              if var == self: 
 85                   return cat 
 86          return self 
 87   
 88 -    def can_unify(self, other): 
 89          """ If the variable can be replaced with other 
 90          a substitution is returned. 
 91          """ 
 92          if other.is_primitive() or not self._prim_only: 
 93              return [(self,other)] 
 94          return None 
 95   
 96 -    def id(self): 
 97          return self._id 
 98   
 99 -    def __cmp__(self,other): 
100          if not isinstance(other,CCGVar): 
101              return -1 
102          return cmp(self._id,other.id()) 
103   
104 -    def __hash__(self): 
105          return hash(self._id) 
106 -    def __str__(self): 
107          return "_var" + str(self._id) 
108    
109 -class Direction: 
110      ''' 
111      Class representing the direction of a function application. 
112      Also contains maintains information as to which combinators 
113      may be used with the category. 
114      ''' 
115 -    def __init__(self,dir,restrictions): 
116          self._dir = dir 
117          self._restrs = restrictions 
118       
119      # Testing the application direction 
120 -    def is_forward(self): 
121          return self._dir == '/' 
122 -    def is_backward(self): 
123          return self._dir == '\\' 
124       
125 -    def dir(self): 
126          return self._dir 
127       
128 -    def restrs(self): 
129          """A list of restrictions on the combinators. 
130          '.' denotes that permuting operations are disallowed 
131          ',' denotes that function composition is disallowed 
132          '_' denotes that the direction has variable restrictions. 
133          (This is redundant in the current implementation of type-raising) 
134          """ 
135          return self._restrs 
136   
137 -    def is_variable(self): 
138          return self._restrs == '_' 
139       
140      # Unification and substitution of variable directions. 
141      # Used only if type-raising is implemented as a unary rule, as it 
142      # must inherit restrictions from the argument category. 
143 -    def can_unify(self,other): 
144          if other.is_variable(): 
145              return [('_',self.restrs())] 
146          elif self.is_variable(): 
147              return [('_',other.restrs())] 
148          else: 
149              if self.restrs() == other.restrs(): 
150                  return [] 
151          return None 
152   
153 -    def substitute(self,subs): 
154          if not self.is_variable(): 
155              return self 
156   
157          for (var, restrs) in subs: 
158              if var is '_': 
159                  return Direction(self._dir,restrs) 
160          return self 
161       
162      # Testing permitted combinators 
163 -    def can_compose(self): 
164          return not ',' in self._restrs  
165       
166 -    def can_cross(self): 
167          return not '.' in self._restrs 
168   
169 -    def __cmp__(self,other): 
170          return cmp((self._dir,self._restrs), (other.dir(),other.restrs())) 
171          return res 
172   
173 -    def __hash__(self): 
174        return hash((self._dir,tuple(self._restrs))) 
175   
176 -    def __str__(self): 
177          r_str = "" 
178          for r in self._restrs: 
179              r_str = r_str + str(r) 
180          return str(self._dir) + r_str 
181       
182      # The negation operator reverses the direction of the application 
183 -    def __neg__(self): 
184          if self._dir == '/': 
185              return Direction('\\',self._restrs) 
186          else: 
187              return Direction('/',self._restrs) 
188   
189   
190 -class PrimitiveCategory(AbstractCCGCategory): 
191      ''' 
192      Class representing primitive categories. 
193      Takes a string representation of the category, and a 
194      list of strings specifying the morphological subcategories. 
195      ''' 
196 -    def __init__(self,categ,restrictions=[]): 
197          self._categ = categ 
198          self._restrs = restrictions 
199   
200 -    def is_primitive(self): 
201          return True 
202   
203 -    def is_function(self): 
204          return False 
205   
206 -    def is_var(self): 
207          return False 
208   
209 -    def restrs(self): 
210          return self._restrs  
211       
212 -    def categ(self): 
213          return self._categ 
214       
215      # Substitution does nothing to a primitive category 
216 -    def substitute(self,subs): 
217          return self 
218   
219      # A primitive can be unified with a class of the same 
220      # base category, given that the other category shares all 
221      # of its subclasses, or with a variable. 
222 -    def can_unify(self,other): 
223          if not other.is_primitive(): 
224              return None 
225          if other.is_var(): 
226              return [(other,self)] 
227          if other.categ() == self.categ(): 
228              for restr in self._restrs: 
229                  if restr not in other.restrs(): 
230                      return None 
231              return [] 
232          return None 
233   
234 -    def __cmp__(self,other): 
235          if not isinstance(other,PrimitiveCategory): 
236              return -1 
237          return cmp((self._categ,self.restrs()), 
238                      (other.categ(),other.restrs())) 
239   
240 -    def __hash__(self): 
241          return hash((self._categ,tuple(self._restrs))) 
242   
243 -    def __str__(self): 
244          if self._restrs == []: 
245              return str(self._categ) 
246          return str(self._categ) + str(self._restrs) 
247   
248 -class FunctionalCategory(AbstractCCGCategory): 
249      ''' 
250      Class that represents a function application category. 
251      Consists of argument and result categories, together with 
252      an application direction. 
253      ''' 
254 -    def __init__(self,res,arg,dir,): 
255          self._res = res 
256          self._arg = arg 
257          self._dir = dir 
258   
259 -    def is_primitive(self): 
260          return False 
261   
262 -    def is_function(self): 
263          return True 
264   
265 -    def is_var(self): 
266          return False 
267       
268      # Substitution returns the category consisting of the 
269      # substitution applied to each of its constituents. 
270 -    def substitute(self,subs): 
271          sub_res = self._res.substitute(subs) 
272          sub_dir = self._dir.substitute(subs) 
273          sub_arg = self._arg.substitute(subs) 
274          return FunctionalCategory(sub_res,sub_arg,self._dir) 
275       
276      # A function can unify with another function, so long as its 
277      # constituents can unify, or with an unrestricted variable. 
278 -    def can_unify(self,other): 
279          if other.is_var(): 
280              return [(other,self)] 
281          if other.is_function(): 
282              sa = self._res.can_unify(other.res()) 
283              sd = self._dir.can_unify(other.dir()) 
284              if sa != None and sd != None: 
285                 sb = self._arg.substitute(sa).can_unify(other.arg().substitute(sa)) 
286                 if sb != None: 
287                     return sa + sb 
288          return None 
289       
290      # Constituent accessors        
291 -    def arg(self): 
292          return self._arg 
293   
294 -    def res(self): 
295          return self._res 
296   
297 -    def dir(self): 
298          return self._dir 
299   
300 -    def __cmp__(self,other): 
301          if not isinstance(other,FunctionalCategory): 
302              return -1 
303          return cmp((self._arg,self._dir,self._res), 
304                      (other.arg(),other.dir(),other.res())) 
305 -    def __hash__(self): 
306          return hash((self._arg,self._dir,self._res)) 
307   
308 -    def __str__(self): 
309          return "(" + str(self._res) + str(self._dir) + str(self._arg) + ")" 
310