Source Code for Module nltk.ccg.combinator

  1  # Natural Language Toolkit: Combinatory Categorial Grammar 
  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  from api import * 
  9   
 10 -class UndirectedBinaryCombinator(object): 
 11      """ 
 12      Abstract class for representing a binary combinator. 
 13      Merely defines functions for checking if the function and argument 
 14      are able to be combined, and what the resulting category is. 
 15       
 16      Note that as no assumptions are made as to direction, the unrestricted 
 17      combinators can perform all backward, forward and crossed variations 
 18      of the combinators; these restrictions must be added in the rule 
 19      class. 
 20      """ 
 21 -    def can_combine(self, function, argument): 
 22          raise AssertionError, 'UndirectedBinaryCombinator is an abstract interface' 
 23   
 24 -    def combine (self,function,argument): 
 25          raise AssertionError, 'UndirectedBinaryCombinator is an abstract interface' 
 26   
 27 -class DirectedBinaryCombinator(object): 
 28      """ 
 29      Wrapper for the undirected binary combinator. 
 30      It takes left and right categories, and decides which is to be 
 31      the function, and which the argument. 
 32      It then decides whether or not they can be combined. 
 33      """ 
 34 -    def can_combine(self, left, right): 
 35          raise AssertionError, 'DirectedBinaryCombinator is an abstract interface' 
 36       
 37 -    def combine(self, left, right): 
 38          raise AssertionError, 'DirectedBinaryCombinator is an abstract interface' 
 39   
 40 -class ForwardCombinator(DirectedBinaryCombinator): 
 41      ''' 
 42      Class representing combinators where the primary functor is on the left. 
 43   
 44      Takes an undirected combinator, and a predicate which adds constraints 
 45      restricting the cases in which it may apply. 
 46      ''' 
 47 -    def __init__(self, combinator, predicate, suffix=''): 
 48          self._combinator = combinator 
 49          self._predicate = predicate 
 50          self._suffix = suffix 
 51       
 52 -    def can_combine(self, left, right): 
 53          return (self._combinator.can_combine(left,right) and 
 54                    self._predicate(left,right)) 
 55   
 56 -    def combine(self, left, right): 
 57          for cat in self._combinator.combine(left,right): 
 58              yield cat 
 59       
 60 -    def __str__(self): 
 61          return '>' + str(self._combinator) + self._suffix 
 62   
 63 -class BackwardCombinator(DirectedBinaryCombinator): 
 64      ''' 
 65      The backward equivalent of the ForwardCombinator class. 
 66      ''' 
 67 -    def __init__(self, combinator, predicate, suffix=''): 
 68          self._combinator = combinator 
 69          self._predicate = predicate 
 70          self._suffix = suffix 
 71   
 72 -    def can_combine(self, left, right): 
 73          return (self._combinator.can_combine(right, left) and 
 74                    self._predicate(left,right)) 
 75 -    def combine(self, left, right): 
 76          for cat in self._combinator.combine(right, left): 
 77              yield cat 
 78   
 79 -    def __str__(self): 
 80          return '<' + str(self._combinator) + self._suffix 
 81           
 82 -class UndirectedFunctionApplication(UndirectedBinaryCombinator): 
 83      """ 
 84      Class representing function application. 
 85      Implements rules of the form: 
 86      X/Y Y -> X (>) 
 87      And the corresponding backwards application rule 
 88      """ 
 89   
 90 -    def can_combine(self, function, argument): 
 91          if not function.is_function(): 
 92              return False 
 93   
 94          return not function.arg().can_unify(argument) is None 
 95   
 96 -    def combine(self,function,argument): 
 97          if not function.is_function(): 
 98              return 
 99           
100          subs = function.arg().can_unify(argument) 
101          if subs is None: 
102              return 
103           
104          yield function.res().substitute(subs) 
105   
106 -    def __str__(self): 
107          return '' 
108   
109   
110  # Predicates for function application. 
111   
112  # Ensures the left functor takes an argument on the right 
113 -def forwardOnly(left,right): 
114      return left.dir().is_forward() 
115   
116  # Ensures the right functor takes an argument on the left 
117 -def backwardOnly(left,right): 
118      return right.dir().is_backward() 
119   
120  # Application combinator instances 
121  ForwardApplication = ForwardCombinator(UndirectedFunctionApplication(), 
122                          forwardOnly) 
123  BackwardApplication = BackwardCombinator(UndirectedFunctionApplication(), 
124                          backwardOnly) 
125   
126   
127 -class UndirectedComposition(UndirectedBinaryCombinator): 
128      """ 
129      Functional composition (harmonic) combinator. 
130      Implements rules of the form 
131      X/Y Y/Z -> X/Z (B>) 
132      And the corresponding backwards and crossed variations. 
133      """ 
134 -    def can_combine(self, function, argument): 
135          # Can only combine two functions, and both functions must 
136          # allow composition. 
137          if not (function.is_function() and argument.is_function()): 
138              return False 
139          if function.dir().can_compose() and argument.dir().can_compose(): 
140              return not function.arg().can_unify(argument.res()) is None 
141          return False 
142   
143 -    def combine(self, function, argument): 
144          if not (function.is_function() and argument.is_function()): 
145              return 
146          if function.dir().can_compose() and argument.dir().can_compose(): 
147              subs = function.arg().can_unify(argument.res()) 
148              if not subs is None: 
149                  yield FunctionalCategory(function.res().substitute(subs), 
150                              argument.arg().substitute(subs),argument.dir()) 
151   
152 -    def __str__(self): 
153          return 'B'    
154   
155  # Predicates for restricting application of straight composition. 
156 -def bothForward(left,right): 
157      return left.dir().is_forward() and right.dir().is_forward() 
158   
159 -def bothBackward(left,right): 
160      return left.dir().is_backward() and right.dir().is_backward() 
161   
162  # Predicates for crossed composition 
163   
164 -def crossedDirs(left,right): 
165      return left.dir().is_forward() and right.dir().is_backward() 
166   
167 -def backwardBxConstraint(left,right): 
168      # The functors must be crossed inwards 
169      if not crossedDirs(left, right): 
170          return False 
171      # Permuting combinators must be allowed 
172      if not left.dir().can_cross() and right.dir().can_cross(): 
173          return False 
174      # The resulting argument category is restricted to be primitive 
175      return left.arg().is_primitive() 
176   
177  # Straight composition combinators 
178  ForwardComposition = ForwardCombinator(UndirectedComposition(), 
179                             forwardOnly) 
180  BackwardComposition = BackwardCombinator(UndirectedComposition(), 
181                             backwardOnly) 
182   
183  # Backward crossed composition 
184  BackwardBx = BackwardCombinator(UndirectedComposition(),backwardBxConstraint, 
185                  suffix='x') 
186   
187   
188 -class UndirectedSubstitution(UndirectedBinaryCombinator): 
189      """ 
190      Substitution (permutation) combinator. 
191      Implements rules of the form 
192      Y/Z (X\Y)/Z -> X/Z (<Sx) 
193      And other variations. 
194      """ 
195 -    def can_combine(self, function, argument): 
196          if function.is_primitive() or argument.is_primitive(): 
197              return False 
198         
199          # These could potentially be moved to the predicates, as the 
200          # constraints may not be general to all languages. 
201          if function.res().is_primitive(): 
202              return False 
203          if not function.arg().is_primitive(): 
204              return False 
205   
206          if not (function.dir().can_compose() and argument.dir().can_compose()): 
207              return False 
208          return (function.res().arg() == argument.res()) and (function.arg() == argument.arg()) 
209      
210 -    def combine(self,function,argument): 
211          if self.can_combine(function,argument): 
212              yield FunctionalCategory(function.res().res(),argument.arg(),argument.dir()) 
213   
214 -    def __str__(self): 
215          return 'S' 
216   
217  # Predicate for forward substitution  
218 -def forwardSConstraint(left, right): 
219      if not bothForward(left, right): 
220          return False 
221      return left.res().dir().is_forward() and left.arg().is_primitive() 
222   
223  # Predicate for backward crossed substitution 
224 -def backwardSxConstraint(left,right): 
225      if not left.dir().can_cross() and right.dir().can_cross(): 
226          return False 
227      if not bothForward(left, right): 
228          return False 
229      return right.res().dir().is_backward() and right.arg().is_primitive() 
230   
231  # Instances of substitution combinators 
232  ForwardSubstitution = ForwardCombinator(UndirectedSubstitution(), 
233                              forwardSConstraint) 
234  BackwardSx = BackwardCombinator(UndirectedSubstitution(), 
235                      backwardSxConstraint,'x') 
236   
237   
238  # Retrieves the left-most functional category. 
239  # ie, (N\N)/(S/NP) => N\N 
240 -def innermostFunction(categ): 
241      while categ.res().is_function(): 
242          categ = categ.res() 
243      return categ 
244   
245 -class UndirectedTypeRaise(UndirectedBinaryCombinator): 
246      ''' 
247      Undirected combinator for type raising. 
248      ''' 
249 -    def can_combine(self,function,arg): 
250          # The argument must be a function. 
251          # The restriction that arg.res() must be a function 
252          # merely reduces redundant type-raising; if arg.res() is 
253          # primitive, we have: 
254          # X Y\X =>(<T) Y/(Y\X) Y\X =>(>) Y 
255          # which is equivalent to 
256          # X Y\X =>(<) Y 
257          if not (arg.is_function() and arg.res().is_function()): 
258                  return False 
259   
260          arg = innermostFunction(arg) 
261   
262          subs = left.can_unify(arg_categ.arg()) 
263          if subs is not None: 
264              return True 
265          return False 
266   
267 -    def combine(self,function,arg): 
268          if not (function.is_primitive() and \ 
269                  arg.is_function() and arg.res().is_function()): 
270              return 
271   
272          # Type-raising matches only the innermost application. 
273          arg = innermostFunction(arg) 
274   
275          subs = function.can_unify(arg.arg()) 
276          if subs is not None: 
277              xcat = arg.res().substitute(subs) 
278              yield FunctionalCategory(xcat, 
279                      FunctionalCategory(xcat,function,arg.dir()), 
280                      -(arg.dir())) 
281       
282 -    def __str__(self): 
283          return 'T' 
284   
285  # Predicates for type-raising 
286  # The direction of the innermost category must be towards 
287  # the primary functor. 
288  # The restriction that the variable must be primitive is not 
289  # common to all versions of CCGs; some authors have other restrictions. 
290 -def forwardTConstraint(left,right): 
291      arg = innermostFunction(right) 
292      return arg.dir().is_backward() and arg.res().is_primitive() 
293   
294 -def backwardTConstraint(left,right): 
295      arg = innermostFunction(left) 
296      return arg.dir().is_forward() and arg.res().is_primitive() 
297   
298  # Instances of type-raising combinators 
299  ForwardT = ForwardCombinator(UndirectedTypeRaise(), forwardTConstraint) 
300  BackwardT = BackwardCombinator(UndirectedTypeRaise(), backwardTConstraint) 
301