featstruct.py 102 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797
  1. # Natural Language Toolkit: Feature Structures
  2. #
  3. # Copyright (C) 2001-2019 NLTK Project
  4. # Author: Edward Loper <edloper@gmail.com>,
  5. # Rob Speer,
  6. # Steven Bird <stevenbird1@gmail.com>
  7. # URL: <http://nltk.sourceforge.net>
  8. # For license information, see LICENSE.TXT
  9. """
  10. Basic data classes for representing feature structures, and for
  11. performing basic operations on those feature structures. A feature
  12. structure is a mapping from feature identifiers to feature values,
  13. where each feature value is either a basic value (such as a string or
  14. an integer), or a nested feature structure. There are two types of
  15. feature structure, implemented by two subclasses of ``FeatStruct``:
  16. - feature dictionaries, implemented by ``FeatDict``, act like
  17. Python dictionaries. Feature identifiers may be strings or
  18. instances of the ``Feature`` class.
  19. - feature lists, implemented by ``FeatList``, act like Python
  20. lists. Feature identifiers are integers.
  21. Feature structures are typically used to represent partial information
  22. about objects. A feature identifier that is not mapped to a value
  23. stands for a feature whose value is unknown (*not* a feature without
  24. a value). Two feature structures that represent (potentially
  25. overlapping) information about the same object can be combined by
  26. unification. When two inconsistent feature structures are unified,
  27. the unification fails and returns None.
  28. Features can be specified using "feature paths", or tuples of feature
  29. identifiers that specify path through the nested feature structures to
  30. a value. Feature structures may contain reentrant feature values. A
  31. "reentrant feature value" is a single feature value that can be
  32. accessed via multiple feature paths. Unification preserves the
  33. reentrance relations imposed by both of the unified feature
  34. structures. In the feature structure resulting from unification, any
  35. modifications to a reentrant feature value will be visible using any
  36. of its feature paths.
  37. Feature structure variables are encoded using the ``nltk.sem.Variable``
  38. class. The variables' values are tracked using a bindings
  39. dictionary, which maps variables to their values. When two feature
  40. structures are unified, a fresh bindings dictionary is created to
  41. track their values; and before unification completes, all bound
  42. variables are replaced by their values. Thus, the bindings
  43. dictionaries are usually strictly internal to the unification process.
  44. However, it is possible to track the bindings of variables if you
  45. choose to, by supplying your own initial bindings dictionary to the
  46. ``unify()`` function.
  47. When unbound variables are unified with one another, they become
  48. aliased. This is encoded by binding one variable to the other.
  49. Lightweight Feature Structures
  50. ==============================
  51. Many of the functions defined by ``nltk.featstruct`` can be applied
  52. directly to simple Python dictionaries and lists, rather than to
  53. full-fledged ``FeatDict`` and ``FeatList`` objects. In other words,
  54. Python ``dicts`` and ``lists`` can be used as "light-weight" feature
  55. structures.
  56. >>> from nltk.featstruct import unify
  57. >>> unify(dict(x=1, y=dict()), dict(a='a', y=dict(b='b'))) # doctest: +SKIP
  58. {'y': {'b': 'b'}, 'x': 1, 'a': 'a'}
  59. However, you should keep in mind the following caveats:
  60. - Python dictionaries & lists ignore reentrance when checking for
  61. equality between values. But two FeatStructs with different
  62. reentrances are considered nonequal, even if all their base
  63. values are equal.
  64. - FeatStructs can be easily frozen, allowing them to be used as
  65. keys in hash tables. Python dictionaries and lists can not.
  66. - FeatStructs display reentrance in their string representations;
  67. Python dictionaries and lists do not.
  68. - FeatStructs may *not* be mixed with Python dictionaries and lists
  69. (e.g., when performing unification).
  70. - FeatStructs provide a number of useful methods, such as ``walk()``
  71. and ``cyclic()``, which are not available for Python dicts and lists.
  72. In general, if your feature structures will contain any reentrances,
  73. or if you plan to use them as dictionary keys, it is strongly
  74. recommended that you use full-fledged ``FeatStruct`` objects.
  75. """
  76. from __future__ import print_function, unicode_literals, division
  77. import re
  78. import copy
  79. from functools import total_ordering
  80. from six import integer_types, string_types
  81. from nltk.internals import read_str, raise_unorderable_types
  82. from nltk.sem.logic import (
  83. Variable,
  84. Expression,
  85. SubstituteBindingsI,
  86. LogicParser,
  87. LogicalExpressionException,
  88. )
  89. from nltk.compat import python_2_unicode_compatible, unicode_repr
  90. ######################################################################
  91. # Feature Structure
  92. ######################################################################
  93. @total_ordering
  94. class FeatStruct(SubstituteBindingsI):
  95. """
  96. A mapping from feature identifiers to feature values, where each
  97. feature value is either a basic value (such as a string or an
  98. integer), or a nested feature structure. There are two types of
  99. feature structure:
  100. - feature dictionaries, implemented by ``FeatDict``, act like
  101. Python dictionaries. Feature identifiers may be strings or
  102. instances of the ``Feature`` class.
  103. - feature lists, implemented by ``FeatList``, act like Python
  104. lists. Feature identifiers are integers.
  105. Feature structures may be indexed using either simple feature
  106. identifiers or 'feature paths.' A feature path is a sequence
  107. of feature identifiers that stand for a corresponding sequence of
  108. indexing operations. In particular, ``fstruct[(f1,f2,...,fn)]`` is
  109. equivalent to ``fstruct[f1][f2]...[fn]``.
  110. Feature structures may contain reentrant feature structures. A
  111. "reentrant feature structure" is a single feature structure
  112. object that can be accessed via multiple feature paths. Feature
  113. structures may also be cyclic. A feature structure is "cyclic"
  114. if there is any feature path from the feature structure to itself.
  115. Two feature structures are considered equal if they assign the
  116. same values to all features, and have the same reentrancies.
  117. By default, feature structures are mutable. They may be made
  118. immutable with the ``freeze()`` method. Once they have been
  119. frozen, they may be hashed, and thus used as dictionary keys.
  120. """
  121. _frozen = False
  122. """:ivar: A flag indicating whether this feature structure is
  123. frozen or not. Once this flag is set, it should never be
  124. un-set; and no further modification should be made to this
  125. feature structue."""
  126. ##////////////////////////////////////////////////////////////
  127. # { Constructor
  128. ##////////////////////////////////////////////////////////////
  129. def __new__(cls, features=None, **morefeatures):
  130. """
  131. Construct and return a new feature structure. If this
  132. constructor is called directly, then the returned feature
  133. structure will be an instance of either the ``FeatDict`` class
  134. or the ``FeatList`` class.
  135. :param features: The initial feature values for this feature
  136. structure:
  137. - FeatStruct(string) -> FeatStructReader().read(string)
  138. - FeatStruct(mapping) -> FeatDict(mapping)
  139. - FeatStruct(sequence) -> FeatList(sequence)
  140. - FeatStruct() -> FeatDict()
  141. :param morefeatures: If ``features`` is a mapping or None,
  142. then ``morefeatures`` provides additional features for the
  143. ``FeatDict`` constructor.
  144. """
  145. # If the FeatStruct constructor is called directly, then decide
  146. # whether to create a FeatDict or a FeatList, based on the
  147. # contents of the `features` argument.
  148. if cls is FeatStruct:
  149. if features is None:
  150. return FeatDict.__new__(FeatDict, **morefeatures)
  151. elif _is_mapping(features):
  152. return FeatDict.__new__(FeatDict, features, **morefeatures)
  153. elif morefeatures:
  154. raise TypeError(
  155. 'Keyword arguments may only be specified '
  156. 'if features is None or is a mapping.'
  157. )
  158. if isinstance(features, string_types):
  159. if FeatStructReader._START_FDICT_RE.match(features):
  160. return FeatDict.__new__(FeatDict, features, **morefeatures)
  161. else:
  162. return FeatList.__new__(FeatList, features, **morefeatures)
  163. elif _is_sequence(features):
  164. return FeatList.__new__(FeatList, features)
  165. else:
  166. raise TypeError('Expected string or mapping or sequence')
  167. # Otherwise, construct the object as normal.
  168. else:
  169. return super(FeatStruct, cls).__new__(cls, features, **morefeatures)
  170. ##////////////////////////////////////////////////////////////
  171. # { Uniform Accessor Methods
  172. ##////////////////////////////////////////////////////////////
  173. # These helper functions allow the methods defined by FeatStruct
  174. # to treat all feature structures as mappings, even if they're
  175. # really lists. (Lists are treated as mappings from ints to vals)
  176. def _keys(self):
  177. """Return an iterable of the feature identifiers used by this
  178. FeatStruct."""
  179. raise NotImplementedError() # Implemented by subclasses.
  180. def _values(self):
  181. """Return an iterable of the feature values directly defined
  182. by this FeatStruct."""
  183. raise NotImplementedError() # Implemented by subclasses.
  184. def _items(self):
  185. """Return an iterable of (fid,fval) pairs, where fid is a
  186. feature identifier and fval is the corresponding feature
  187. value, for all features defined by this FeatStruct."""
  188. raise NotImplementedError() # Implemented by subclasses.
  189. ##////////////////////////////////////////////////////////////
  190. # { Equality & Hashing
  191. ##////////////////////////////////////////////////////////////
  192. def equal_values(self, other, check_reentrance=False):
  193. """
  194. Return True if ``self`` and ``other`` assign the same value to
  195. to every feature. In particular, return true if
  196. ``self[p]==other[p]`` for every feature path *p* such
  197. that ``self[p]`` or ``other[p]`` is a base value (i.e.,
  198. not a nested feature structure).
  199. :param check_reentrance: If True, then also return False if
  200. there is any difference between the reentrances of ``self``
  201. and ``other``.
  202. :note: the ``==`` is equivalent to ``equal_values()`` with
  203. ``check_reentrance=True``.
  204. """
  205. return self._equal(other, check_reentrance, set(), set(), set())
  206. def __eq__(self, other):
  207. """
  208. Return true if ``self`` and ``other`` are both feature structures,
  209. assign the same values to all features, and contain the same
  210. reentrances. I.e., return
  211. ``self.equal_values(other, check_reentrance=True)``.
  212. :see: ``equal_values()``
  213. """
  214. return self._equal(other, True, set(), set(), set())
  215. def __ne__(self, other):
  216. return not self == other
  217. def __lt__(self, other):
  218. if not isinstance(other, FeatStruct):
  219. # raise_unorderable_types("<", self, other)
  220. # Sometimes feature values can be pure strings,
  221. # so we need to be able to compare with non-featstructs:
  222. return self.__class__.__name__ < other.__class__.__name__
  223. else:
  224. return len(self) < len(other)
  225. def __hash__(self):
  226. """
  227. If this feature structure is frozen, return its hash value;
  228. otherwise, raise ``TypeError``.
  229. """
  230. if not self._frozen:
  231. raise TypeError('FeatStructs must be frozen before they ' 'can be hashed.')
  232. try:
  233. return self._hash
  234. except AttributeError:
  235. self._hash = self._calculate_hashvalue(set())
  236. return self._hash
  237. def _equal(
  238. self, other, check_reentrance, visited_self, visited_other, visited_pairs
  239. ):
  240. """
  241. Return True iff self and other have equal values.
  242. :param visited_self: A set containing the ids of all ``self``
  243. feature structures we've already visited.
  244. :param visited_other: A set containing the ids of all ``other``
  245. feature structures we've already visited.
  246. :param visited_pairs: A set containing ``(selfid, otherid)`` pairs
  247. for all pairs of feature structures we've already visited.
  248. """
  249. # If we're the same object, then we're equal.
  250. if self is other:
  251. return True
  252. # If we have different classes, we're definitely not equal.
  253. if self.__class__ != other.__class__:
  254. return False
  255. # If we define different features, we're definitely not equal.
  256. # (Perform len test first because it's faster -- we should
  257. # do profiling to see if this actually helps)
  258. if len(self) != len(other):
  259. return False
  260. if set(self._keys()) != set(other._keys()):
  261. return False
  262. # If we're checking reentrance, then any time we revisit a
  263. # structure, make sure that it was paired with the same
  264. # feature structure that it is now. Note: if check_reentrance,
  265. # then visited_pairs will never contain two pairs whose first
  266. # values are equal, or two pairs whose second values are equal.
  267. if check_reentrance:
  268. if id(self) in visited_self or id(other) in visited_other:
  269. return (id(self), id(other)) in visited_pairs
  270. # If we're not checking reentrance, then we still need to deal
  271. # with cycles. If we encounter the same (self, other) pair a
  272. # second time, then we won't learn anything more by examining
  273. # their children a second time, so just return true.
  274. else:
  275. if (id(self), id(other)) in visited_pairs:
  276. return True
  277. # Keep track of which nodes we've visited.
  278. visited_self.add(id(self))
  279. visited_other.add(id(other))
  280. visited_pairs.add((id(self), id(other)))
  281. # Now we have to check all values. If any of them don't match,
  282. # then return false.
  283. for (fname, self_fval) in self._items():
  284. other_fval = other[fname]
  285. if isinstance(self_fval, FeatStruct):
  286. if not self_fval._equal(
  287. other_fval,
  288. check_reentrance,
  289. visited_self,
  290. visited_other,
  291. visited_pairs,
  292. ):
  293. return False
  294. else:
  295. if self_fval != other_fval:
  296. return False
  297. # Everything matched up; return true.
  298. return True
  299. def _calculate_hashvalue(self, visited):
  300. """
  301. Return a hash value for this feature structure.
  302. :require: ``self`` must be frozen.
  303. :param visited: A set containing the ids of all feature
  304. structures we've already visited while hashing.
  305. """
  306. if id(self) in visited:
  307. return 1
  308. visited.add(id(self))
  309. hashval = 5831
  310. for (fname, fval) in sorted(self._items()):
  311. hashval *= 37
  312. hashval += hash(fname)
  313. hashval *= 37
  314. if isinstance(fval, FeatStruct):
  315. hashval += fval._calculate_hashvalue(visited)
  316. else:
  317. hashval += hash(fval)
  318. # Convert to a 32 bit int.
  319. hashval = int(hashval & 0x7FFFFFFF)
  320. return hashval
  321. ##////////////////////////////////////////////////////////////
  322. # { Freezing
  323. ##////////////////////////////////////////////////////////////
  324. #: Error message used by mutating methods when called on a frozen
  325. #: feature structure.
  326. _FROZEN_ERROR = "Frozen FeatStructs may not be modified."
  327. def freeze(self):
  328. """
  329. Make this feature structure, and any feature structures it
  330. contains, immutable. Note: this method does not attempt to
  331. 'freeze' any feature value that is not a ``FeatStruct``; it
  332. is recommended that you use only immutable feature values.
  333. """
  334. if self._frozen:
  335. return
  336. self._freeze(set())
  337. def frozen(self):
  338. """
  339. Return True if this feature structure is immutable. Feature
  340. structures can be made immutable with the ``freeze()`` method.
  341. Immutable feature structures may not be made mutable again,
  342. but new mutable copies can be produced with the ``copy()`` method.
  343. """
  344. return self._frozen
  345. def _freeze(self, visited):
  346. """
  347. Make this feature structure, and any feature structure it
  348. contains, immutable.
  349. :param visited: A set containing the ids of all feature
  350. structures we've already visited while freezing.
  351. """
  352. if id(self) in visited:
  353. return
  354. visited.add(id(self))
  355. self._frozen = True
  356. for (fname, fval) in sorted(self._items()):
  357. if isinstance(fval, FeatStruct):
  358. fval._freeze(visited)
  359. ##////////////////////////////////////////////////////////////
  360. # { Copying
  361. ##////////////////////////////////////////////////////////////
  362. def copy(self, deep=True):
  363. """
  364. Return a new copy of ``self``. The new copy will not be frozen.
  365. :param deep: If true, create a deep copy; if false, create
  366. a shallow copy.
  367. """
  368. if deep:
  369. return copy.deepcopy(self)
  370. else:
  371. return self.__class__(self)
  372. # Subclasses should define __deepcopy__ to ensure that the new
  373. # copy will not be frozen.
  374. def __deepcopy__(self, memo):
  375. raise NotImplementedError() # Implemented by subclasses.
  376. ##////////////////////////////////////////////////////////////
  377. # { Structural Information
  378. ##////////////////////////////////////////////////////////////
  379. def cyclic(self):
  380. """
  381. Return True if this feature structure contains itself.
  382. """
  383. return self._find_reentrances({})[id(self)]
  384. def walk(self):
  385. """
  386. Return an iterator that generates this feature structure, and
  387. each feature structure it contains. Each feature structure will
  388. be generated exactly once.
  389. """
  390. return self._walk(set())
  391. def _walk(self, visited):
  392. """
  393. Return an iterator that generates this feature structure, and
  394. each feature structure it contains.
  395. :param visited: A set containing the ids of all feature
  396. structures we've already visited while freezing.
  397. """
  398. raise NotImplementedError() # Implemented by subclasses.
  399. def _walk(self, visited):
  400. if id(self) in visited:
  401. return
  402. visited.add(id(self))
  403. yield self
  404. for fval in self._values():
  405. if isinstance(fval, FeatStruct):
  406. for elt in fval._walk(visited):
  407. yield elt
  408. # Walk through the feature tree. The first time we see a feature
  409. # value, map it to False (not reentrant). If we see a feature
  410. # value more than once, then map it to True (reentrant).
  411. def _find_reentrances(self, reentrances):
  412. """
  413. Return a dictionary that maps from the ``id`` of each feature
  414. structure contained in ``self`` (including ``self``) to a
  415. boolean value, indicating whether it is reentrant or not.
  416. """
  417. if id(self) in reentrances:
  418. # We've seen it more than once.
  419. reentrances[id(self)] = True
  420. else:
  421. # This is the first time we've seen it.
  422. reentrances[id(self)] = False
  423. # Recurse to contained feature structures.
  424. for fval in self._values():
  425. if isinstance(fval, FeatStruct):
  426. fval._find_reentrances(reentrances)
  427. return reentrances
  428. ##////////////////////////////////////////////////////////////
  429. # { Variables & Bindings
  430. ##////////////////////////////////////////////////////////////
  431. def substitute_bindings(self, bindings):
  432. """:see: ``nltk.featstruct.substitute_bindings()``"""
  433. return substitute_bindings(self, bindings)
  434. def retract_bindings(self, bindings):
  435. """:see: ``nltk.featstruct.retract_bindings()``"""
  436. return retract_bindings(self, bindings)
  437. def variables(self):
  438. """:see: ``nltk.featstruct.find_variables()``"""
  439. return find_variables(self)
  440. def rename_variables(self, vars=None, used_vars=(), new_vars=None):
  441. """:see: ``nltk.featstruct.rename_variables()``"""
  442. return rename_variables(self, vars, used_vars, new_vars)
  443. def remove_variables(self):
  444. """
  445. Return the feature structure that is obtained by deleting
  446. any feature whose value is a ``Variable``.
  447. :rtype: FeatStruct
  448. """
  449. return remove_variables(self)
  450. ##////////////////////////////////////////////////////////////
  451. # { Unification
  452. ##////////////////////////////////////////////////////////////
  453. def unify(self, other, bindings=None, trace=False, fail=None, rename_vars=True):
  454. return unify(self, other, bindings, trace, fail, rename_vars)
  455. def subsumes(self, other):
  456. """
  457. Return True if ``self`` subsumes ``other``. I.e., return true
  458. If unifying ``self`` with ``other`` would result in a feature
  459. structure equal to ``other``.
  460. """
  461. return subsumes(self, other)
  462. ##////////////////////////////////////////////////////////////
  463. # { String Representations
  464. ##////////////////////////////////////////////////////////////
  465. def __repr__(self):
  466. """
  467. Display a single-line representation of this feature structure,
  468. suitable for embedding in other representations.
  469. """
  470. return self._repr(self._find_reentrances({}), {})
  471. def _repr(self, reentrances, reentrance_ids):
  472. """
  473. Return a string representation of this feature structure.
  474. :param reentrances: A dictionary that maps from the ``id`` of
  475. each feature value in self, indicating whether that value
  476. is reentrant or not.
  477. :param reentrance_ids: A dictionary mapping from each ``id``
  478. of a feature value to a unique identifier. This is modified
  479. by ``repr``: the first time a reentrant feature value is
  480. displayed, an identifier is added to ``reentrance_ids`` for it.
  481. """
  482. raise NotImplementedError()
  483. # Mutation: disable if frozen.
  484. _FROZEN_ERROR = "Frozen FeatStructs may not be modified."
  485. _FROZEN_NOTICE = "\n%sIf self is frozen, raise ValueError."
  486. def _check_frozen(method, indent=''):
  487. """
  488. Given a method function, return a new method function that first
  489. checks if ``self._frozen`` is true; and if so, raises ``ValueError``
  490. with an appropriate message. Otherwise, call the method and return
  491. its result.
  492. """
  493. def wrapped(self, *args, **kwargs):
  494. if self._frozen:
  495. raise ValueError(_FROZEN_ERROR)
  496. else:
  497. return method(self, *args, **kwargs)
  498. wrapped.__name__ = method.__name__
  499. wrapped.__doc__ = (method.__doc__ or '') + (_FROZEN_NOTICE % indent)
  500. return wrapped
  501. ######################################################################
  502. # Feature Dictionary
  503. ######################################################################
  504. @python_2_unicode_compatible
  505. class FeatDict(FeatStruct, dict):
  506. """
  507. A feature structure that acts like a Python dictionary. I.e., a
  508. mapping from feature identifiers to feature values, where a feature
  509. identifier can be a string or a ``Feature``; and where a feature value
  510. can be either a basic value (such as a string or an integer), or a nested
  511. feature structure. A feature identifiers for a ``FeatDict`` is
  512. sometimes called a "feature name".
  513. Two feature dicts are considered equal if they assign the same
  514. values to all features, and have the same reentrances.
  515. :see: ``FeatStruct`` for information about feature paths, reentrance,
  516. cyclic feature structures, mutability, freezing, and hashing.
  517. """
  518. def __init__(self, features=None, **morefeatures):
  519. """
  520. Create a new feature dictionary, with the specified features.
  521. :param features: The initial value for this feature
  522. dictionary. If ``features`` is a ``FeatStruct``, then its
  523. features are copied (shallow copy). If ``features`` is a
  524. dict, then a feature is created for each item, mapping its
  525. key to its value. If ``features`` is a string, then it is
  526. processed using ``FeatStructReader``. If ``features`` is a list of
  527. tuples ``(name, val)``, then a feature is created for each tuple.
  528. :param morefeatures: Additional features for the new feature
  529. dictionary. If a feature is listed under both ``features`` and
  530. ``morefeatures``, then the value from ``morefeatures`` will be
  531. used.
  532. """
  533. if isinstance(features, string_types):
  534. FeatStructReader().fromstring(features, self)
  535. self.update(**morefeatures)
  536. else:
  537. # update() checks the types of features.
  538. self.update(features, **morefeatures)
  539. # ////////////////////////////////////////////////////////////
  540. # { Dict methods
  541. # ////////////////////////////////////////////////////////////
  542. _INDEX_ERROR = str("Expected feature name or path. Got %r.")
  543. def __getitem__(self, name_or_path):
  544. """If the feature with the given name or path exists, return
  545. its value; otherwise, raise ``KeyError``."""
  546. if isinstance(name_or_path, (string_types, Feature)):
  547. return dict.__getitem__(self, name_or_path)
  548. elif isinstance(name_or_path, tuple):
  549. try:
  550. val = self
  551. for fid in name_or_path:
  552. if not isinstance(val, FeatStruct):
  553. raise KeyError # path contains base value
  554. val = val[fid]
  555. return val
  556. except (KeyError, IndexError):
  557. raise KeyError(name_or_path)
  558. else:
  559. raise TypeError(self._INDEX_ERROR % name_or_path)
  560. def get(self, name_or_path, default=None):
  561. """If the feature with the given name or path exists, return its
  562. value; otherwise, return ``default``."""
  563. try:
  564. return self[name_or_path]
  565. except KeyError:
  566. return default
  567. def __contains__(self, name_or_path):
  568. """Return true if a feature with the given name or path exists."""
  569. try:
  570. self[name_or_path]
  571. return True
  572. except KeyError:
  573. return False
  574. def has_key(self, name_or_path):
  575. """Return true if a feature with the given name or path exists."""
  576. return name_or_path in self
  577. def __delitem__(self, name_or_path):
  578. """If the feature with the given name or path exists, delete
  579. its value; otherwise, raise ``KeyError``."""
  580. if self._frozen:
  581. raise ValueError(_FROZEN_ERROR)
  582. if isinstance(name_or_path, (string_types, Feature)):
  583. return dict.__delitem__(self, name_or_path)
  584. elif isinstance(name_or_path, tuple):
  585. if len(name_or_path) == 0:
  586. raise ValueError("The path () can not be set")
  587. else:
  588. parent = self[name_or_path[:-1]]
  589. if not isinstance(parent, FeatStruct):
  590. raise KeyError(name_or_path) # path contains base value
  591. del parent[name_or_path[-1]]
  592. else:
  593. raise TypeError(self._INDEX_ERROR % name_or_path)
  594. def __setitem__(self, name_or_path, value):
  595. """Set the value for the feature with the given name or path
  596. to ``value``. If ``name_or_path`` is an invalid path, raise
  597. ``KeyError``."""
  598. if self._frozen:
  599. raise ValueError(_FROZEN_ERROR)
  600. if isinstance(name_or_path, (string_types, Feature)):
  601. return dict.__setitem__(self, name_or_path, value)
  602. elif isinstance(name_or_path, tuple):
  603. if len(name_or_path) == 0:
  604. raise ValueError("The path () can not be set")
  605. else:
  606. parent = self[name_or_path[:-1]]
  607. if not isinstance(parent, FeatStruct):
  608. raise KeyError(name_or_path) # path contains base value
  609. parent[name_or_path[-1]] = value
  610. else:
  611. raise TypeError(self._INDEX_ERROR % name_or_path)
  612. clear = _check_frozen(dict.clear)
  613. pop = _check_frozen(dict.pop)
  614. popitem = _check_frozen(dict.popitem)
  615. setdefault = _check_frozen(dict.setdefault)
  616. def update(self, features=None, **morefeatures):
  617. if self._frozen:
  618. raise ValueError(_FROZEN_ERROR)
  619. if features is None:
  620. items = ()
  621. elif hasattr(features, 'items') and callable(features.items):
  622. items = features.items()
  623. elif hasattr(features, '__iter__'):
  624. items = features
  625. else:
  626. raise ValueError('Expected mapping or list of tuples')
  627. for key, val in items:
  628. if not isinstance(key, (string_types, Feature)):
  629. raise TypeError('Feature names must be strings')
  630. self[key] = val
  631. for key, val in morefeatures.items():
  632. if not isinstance(key, (string_types, Feature)):
  633. raise TypeError('Feature names must be strings')
  634. self[key] = val
  635. ##////////////////////////////////////////////////////////////
  636. # { Copying
  637. ##////////////////////////////////////////////////////////////
  638. def __deepcopy__(self, memo):
  639. memo[id(self)] = selfcopy = self.__class__()
  640. for (key, val) in self._items():
  641. selfcopy[copy.deepcopy(key, memo)] = copy.deepcopy(val, memo)
  642. return selfcopy
  643. ##////////////////////////////////////////////////////////////
  644. # { Uniform Accessor Methods
  645. ##////////////////////////////////////////////////////////////
  646. def _keys(self):
  647. return self.keys()
  648. def _values(self):
  649. return self.values()
  650. def _items(self):
  651. return self.items()
  652. ##////////////////////////////////////////////////////////////
  653. # { String Representations
  654. ##////////////////////////////////////////////////////////////
  655. def __str__(self):
  656. """
  657. Display a multi-line representation of this feature dictionary
  658. as an FVM (feature value matrix).
  659. """
  660. return '\n'.join(self._str(self._find_reentrances({}), {}))
  661. def _repr(self, reentrances, reentrance_ids):
  662. segments = []
  663. prefix = ''
  664. suffix = ''
  665. # If this is the first time we've seen a reentrant structure,
  666. # then assign it a unique identifier.
  667. if reentrances[id(self)]:
  668. assert id(self) not in reentrance_ids
  669. reentrance_ids[id(self)] = repr(len(reentrance_ids) + 1)
  670. # sorting note: keys are unique strings, so we'll never fall
  671. # through to comparing values.
  672. for (fname, fval) in sorted(self.items()):
  673. display = getattr(fname, 'display', None)
  674. if id(fval) in reentrance_ids:
  675. segments.append('%s->(%s)' % (fname, reentrance_ids[id(fval)]))
  676. elif (
  677. display == 'prefix'
  678. and not prefix
  679. and isinstance(fval, (Variable, string_types))
  680. ):
  681. prefix = '%s' % fval
  682. elif display == 'slash' and not suffix:
  683. if isinstance(fval, Variable):
  684. suffix = '/%s' % fval.name
  685. else:
  686. suffix = '/%s' % unicode_repr(fval)
  687. elif isinstance(fval, Variable):
  688. segments.append('%s=%s' % (fname, fval.name))
  689. elif fval is True:
  690. segments.append('+%s' % fname)
  691. elif fval is False:
  692. segments.append('-%s' % fname)
  693. elif isinstance(fval, Expression):
  694. segments.append('%s=<%s>' % (fname, fval))
  695. elif not isinstance(fval, FeatStruct):
  696. segments.append('%s=%s' % (fname, unicode_repr(fval)))
  697. else:
  698. fval_repr = fval._repr(reentrances, reentrance_ids)
  699. segments.append('%s=%s' % (fname, fval_repr))
  700. # If it's reentrant, then add on an identifier tag.
  701. if reentrances[id(self)]:
  702. prefix = '(%s)%s' % (reentrance_ids[id(self)], prefix)
  703. return '%s[%s]%s' % (prefix, ', '.join(segments), suffix)
  704. def _str(self, reentrances, reentrance_ids):
  705. """
  706. :return: A list of lines composing a string representation of
  707. this feature dictionary.
  708. :param reentrances: A dictionary that maps from the ``id`` of
  709. each feature value in self, indicating whether that value
  710. is reentrant or not.
  711. :param reentrance_ids: A dictionary mapping from each ``id``
  712. of a feature value to a unique identifier. This is modified
  713. by ``repr``: the first time a reentrant feature value is
  714. displayed, an identifier is added to ``reentrance_ids`` for
  715. it.
  716. """
  717. # If this is the first time we've seen a reentrant structure,
  718. # then tack on an id string.
  719. if reentrances[id(self)]:
  720. assert id(self) not in reentrance_ids
  721. reentrance_ids[id(self)] = repr(len(reentrance_ids) + 1)
  722. # Special case: empty feature dict.
  723. if len(self) == 0:
  724. if reentrances[id(self)]:
  725. return ['(%s) []' % reentrance_ids[id(self)]]
  726. else:
  727. return ['[]']
  728. # What's the longest feature name? Use this to align names.
  729. maxfnamelen = max(len("%s" % k) for k in self.keys())
  730. lines = []
  731. # sorting note: keys are unique strings, so we'll never fall
  732. # through to comparing values.
  733. for (fname, fval) in sorted(self.items()):
  734. fname = ("%s" % fname).ljust(maxfnamelen)
  735. if isinstance(fval, Variable):
  736. lines.append('%s = %s' % (fname, fval.name))
  737. elif isinstance(fval, Expression):
  738. lines.append('%s = <%s>' % (fname, fval))
  739. elif isinstance(fval, FeatList):
  740. fval_repr = fval._repr(reentrances, reentrance_ids)
  741. lines.append('%s = %s' % (fname, unicode_repr(fval_repr)))
  742. elif not isinstance(fval, FeatDict):
  743. # It's not a nested feature structure -- just print it.
  744. lines.append('%s = %s' % (fname, unicode_repr(fval)))
  745. elif id(fval) in reentrance_ids:
  746. # It's a feature structure we've seen before -- print
  747. # the reentrance id.
  748. lines.append('%s -> (%s)' % (fname, reentrance_ids[id(fval)]))
  749. else:
  750. # It's a new feature structure. Separate it from
  751. # other values by a blank line.
  752. if lines and lines[-1] != '':
  753. lines.append('')
  754. # Recursively print the feature's value (fval).
  755. fval_lines = fval._str(reentrances, reentrance_ids)
  756. # Indent each line to make room for fname.
  757. fval_lines = [(' ' * (maxfnamelen + 3)) + l for l in fval_lines]
  758. # Pick which line we'll display fname on, & splice it in.
  759. nameline = (len(fval_lines) - 1) // 2
  760. fval_lines[nameline] = (
  761. fname + ' =' + fval_lines[nameline][maxfnamelen + 2 :]
  762. )
  763. # Add the feature structure to the output.
  764. lines += fval_lines
  765. # Separate FeatStructs by a blank line.
  766. lines.append('')
  767. # Get rid of any excess blank lines.
  768. if lines[-1] == '':
  769. lines.pop()
  770. # Add brackets around everything.
  771. maxlen = max(len(line) for line in lines)
  772. lines = ['[ %s%s ]' % (line, ' ' * (maxlen - len(line))) for line in lines]
  773. # If it's reentrant, then add on an identifier tag.
  774. if reentrances[id(self)]:
  775. idstr = '(%s) ' % reentrance_ids[id(self)]
  776. lines = [(' ' * len(idstr)) + l for l in lines]
  777. idline = (len(lines) - 1) // 2
  778. lines[idline] = idstr + lines[idline][len(idstr) :]
  779. return lines
  780. ######################################################################
  781. # Feature List
  782. ######################################################################
  783. class FeatList(FeatStruct, list):
  784. """
  785. A list of feature values, where each feature value is either a
  786. basic value (such as a string or an integer), or a nested feature
  787. structure.
  788. Feature lists may contain reentrant feature values. A "reentrant
  789. feature value" is a single feature value that can be accessed via
  790. multiple feature paths. Feature lists may also be cyclic.
  791. Two feature lists are considered equal if they assign the same
  792. values to all features, and have the same reentrances.
  793. :see: ``FeatStruct`` for information about feature paths, reentrance,
  794. cyclic feature structures, mutability, freezing, and hashing.
  795. """
  796. def __init__(self, features=()):
  797. """
  798. Create a new feature list, with the specified features.
  799. :param features: The initial list of features for this feature
  800. list. If ``features`` is a string, then it is paresd using
  801. ``FeatStructReader``. Otherwise, it should be a sequence
  802. of basic values and nested feature structures.
  803. """
  804. if isinstance(features, string_types):
  805. FeatStructReader().fromstring(features, self)
  806. else:
  807. list.__init__(self, features)
  808. # ////////////////////////////////////////////////////////////
  809. # { List methods
  810. # ////////////////////////////////////////////////////////////
  811. _INDEX_ERROR = "Expected int or feature path. Got %r."
  812. def __getitem__(self, name_or_path):
  813. if isinstance(name_or_path, integer_types):
  814. return list.__getitem__(self, name_or_path)
  815. elif isinstance(name_or_path, tuple):
  816. try:
  817. val = self
  818. for fid in name_or_path:
  819. if not isinstance(val, FeatStruct):
  820. raise KeyError # path contains base value
  821. val = val[fid]
  822. return val
  823. except (KeyError, IndexError):
  824. raise KeyError(name_or_path)
  825. else:
  826. raise TypeError(self._INDEX_ERROR % name_or_path)
  827. def __delitem__(self, name_or_path):
  828. """If the feature with the given name or path exists, delete
  829. its value; otherwise, raise ``KeyError``."""
  830. if self._frozen:
  831. raise ValueError(_FROZEN_ERROR)
  832. if isinstance(name_or_path, (integer_types, slice)):
  833. return list.__delitem__(self, name_or_path)
  834. elif isinstance(name_or_path, tuple):
  835. if len(name_or_path) == 0:
  836. raise ValueError("The path () can not be set")
  837. else:
  838. parent = self[name_or_path[:-1]]
  839. if not isinstance(parent, FeatStruct):
  840. raise KeyError(name_or_path) # path contains base value
  841. del parent[name_or_path[-1]]
  842. else:
  843. raise TypeError(self._INDEX_ERROR % name_or_path)
  844. def __setitem__(self, name_or_path, value):
  845. """Set the value for the feature with the given name or path
  846. to ``value``. If ``name_or_path`` is an invalid path, raise
  847. ``KeyError``."""
  848. if self._frozen:
  849. raise ValueError(_FROZEN_ERROR)
  850. if isinstance(name_or_path, (integer_types, slice)):
  851. return list.__setitem__(self, name_or_path, value)
  852. elif isinstance(name_or_path, tuple):
  853. if len(name_or_path) == 0:
  854. raise ValueError("The path () can not be set")
  855. else:
  856. parent = self[name_or_path[:-1]]
  857. if not isinstance(parent, FeatStruct):
  858. raise KeyError(name_or_path) # path contains base value
  859. parent[name_or_path[-1]] = value
  860. else:
  861. raise TypeError(self._INDEX_ERROR % name_or_path)
  862. # __delslice__ = _check_frozen(list.__delslice__, ' ')
  863. # __setslice__ = _check_frozen(list.__setslice__, ' ')
  864. __iadd__ = _check_frozen(list.__iadd__)
  865. __imul__ = _check_frozen(list.__imul__)
  866. append = _check_frozen(list.append)
  867. extend = _check_frozen(list.extend)
  868. insert = _check_frozen(list.insert)
  869. pop = _check_frozen(list.pop)
  870. remove = _check_frozen(list.remove)
  871. reverse = _check_frozen(list.reverse)
  872. sort = _check_frozen(list.sort)
  873. ##////////////////////////////////////////////////////////////
  874. # { Copying
  875. ##////////////////////////////////////////////////////////////
  876. def __deepcopy__(self, memo):
  877. memo[id(self)] = selfcopy = self.__class__()
  878. selfcopy.extend(copy.deepcopy(fval, memo) for fval in self)
  879. return selfcopy
  880. ##////////////////////////////////////////////////////////////
  881. # { Uniform Accessor Methods
  882. ##////////////////////////////////////////////////////////////
  883. def _keys(self):
  884. return list(range(len(self)))
  885. def _values(self):
  886. return self
  887. def _items(self):
  888. return enumerate(self)
  889. ##////////////////////////////////////////////////////////////
  890. # { String Representations
  891. ##////////////////////////////////////////////////////////////
  892. # Special handling for: reentrances, variables, expressions.
  893. def _repr(self, reentrances, reentrance_ids):
  894. # If this is the first time we've seen a reentrant structure,
  895. # then assign it a unique identifier.
  896. if reentrances[id(self)]:
  897. assert id(self) not in reentrance_ids
  898. reentrance_ids[id(self)] = repr(len(reentrance_ids) + 1)
  899. prefix = '(%s)' % reentrance_ids[id(self)]
  900. else:
  901. prefix = ''
  902. segments = []
  903. for fval in self:
  904. if id(fval) in reentrance_ids:
  905. segments.append('->(%s)' % reentrance_ids[id(fval)])
  906. elif isinstance(fval, Variable):
  907. segments.append(fval.name)
  908. elif isinstance(fval, Expression):
  909. segments.append('%s' % fval)
  910. elif isinstance(fval, FeatStruct):
  911. segments.append(fval._repr(reentrances, reentrance_ids))
  912. else:
  913. segments.append('%s' % unicode_repr(fval))
  914. return '%s[%s]' % (prefix, ', '.join(segments))
  915. ######################################################################
  916. # Variables & Bindings
  917. ######################################################################
  918. def substitute_bindings(fstruct, bindings, fs_class='default'):
  919. """
  920. Return the feature structure that is obtained by replacing each
  921. variable bound by ``bindings`` with its binding. If a variable is
  922. aliased to a bound variable, then it will be replaced by that
  923. variable's value. If a variable is aliased to an unbound
  924. variable, then it will be replaced by that variable.
  925. :type bindings: dict(Variable -> any)
  926. :param bindings: A dictionary mapping from variables to values.
  927. """
  928. if fs_class == 'default':
  929. fs_class = _default_fs_class(fstruct)
  930. fstruct = copy.deepcopy(fstruct)
  931. _substitute_bindings(fstruct, bindings, fs_class, set())
  932. return fstruct
  933. def _substitute_bindings(fstruct, bindings, fs_class, visited):
  934. # Visit each node only once:
  935. if id(fstruct) in visited:
  936. return
  937. visited.add(id(fstruct))
  938. if _is_mapping(fstruct):
  939. items = fstruct.items()
  940. elif _is_sequence(fstruct):
  941. items = enumerate(fstruct)
  942. else:
  943. raise ValueError('Expected mapping or sequence')
  944. for (fname, fval) in items:
  945. while isinstance(fval, Variable) and fval in bindings:
  946. fval = fstruct[fname] = bindings[fval]
  947. if isinstance(fval, fs_class):
  948. _substitute_bindings(fval, bindings, fs_class, visited)
  949. elif isinstance(fval, SubstituteBindingsI):
  950. fstruct[fname] = fval.substitute_bindings(bindings)
  951. def retract_bindings(fstruct, bindings, fs_class='default'):
  952. """
  953. Return the feature structure that is obtained by replacing each
  954. feature structure value that is bound by ``bindings`` with the
  955. variable that binds it. A feature structure value must be
  956. identical to a bound value (i.e., have equal id) to be replaced.
  957. ``bindings`` is modified to point to this new feature structure,
  958. rather than the original feature structure. Feature structure
  959. values in ``bindings`` may be modified if they are contained in
  960. ``fstruct``.
  961. """
  962. if fs_class == 'default':
  963. fs_class = _default_fs_class(fstruct)
  964. (fstruct, new_bindings) = copy.deepcopy((fstruct, bindings))
  965. bindings.update(new_bindings)
  966. inv_bindings = dict((id(val), var) for (var, val) in bindings.items())
  967. _retract_bindings(fstruct, inv_bindings, fs_class, set())
  968. return fstruct
  969. def _retract_bindings(fstruct, inv_bindings, fs_class, visited):
  970. # Visit each node only once:
  971. if id(fstruct) in visited:
  972. return
  973. visited.add(id(fstruct))
  974. if _is_mapping(fstruct):
  975. items = fstruct.items()
  976. elif _is_sequence(fstruct):
  977. items = enumerate(fstruct)
  978. else:
  979. raise ValueError('Expected mapping or sequence')
  980. for (fname, fval) in items:
  981. if isinstance(fval, fs_class):
  982. if id(fval) in inv_bindings:
  983. fstruct[fname] = inv_bindings[id(fval)]
  984. _retract_bindings(fval, inv_bindings, fs_class, visited)
  985. def find_variables(fstruct, fs_class='default'):
  986. """
  987. :return: The set of variables used by this feature structure.
  988. :rtype: set(Variable)
  989. """
  990. if fs_class == 'default':
  991. fs_class = _default_fs_class(fstruct)
  992. return _variables(fstruct, set(), fs_class, set())
  993. def _variables(fstruct, vars, fs_class, visited):
  994. # Visit each node only once:
  995. if id(fstruct) in visited:
  996. return
  997. visited.add(id(fstruct))
  998. if _is_mapping(fstruct):
  999. items = fstruct.items()
  1000. elif _is_sequence(fstruct):
  1001. items = enumerate(fstruct)
  1002. else:
  1003. raise ValueError('Expected mapping or sequence')
  1004. for (fname, fval) in items:
  1005. if isinstance(fval, Variable):
  1006. vars.add(fval)
  1007. elif isinstance(fval, fs_class):
  1008. _variables(fval, vars, fs_class, visited)
  1009. elif isinstance(fval, SubstituteBindingsI):
  1010. vars.update(fval.variables())
  1011. return vars
  1012. def rename_variables(
  1013. fstruct, vars=None, used_vars=(), new_vars=None, fs_class='default'
  1014. ):
  1015. """
  1016. Return the feature structure that is obtained by replacing
  1017. any of this feature structure's variables that are in ``vars``
  1018. with new variables. The names for these new variables will be
  1019. names that are not used by any variable in ``vars``, or in
  1020. ``used_vars``, or in this feature structure.
  1021. :type vars: set
  1022. :param vars: The set of variables that should be renamed.
  1023. If not specified, ``find_variables(fstruct)`` is used; i.e., all
  1024. variables will be given new names.
  1025. :type used_vars: set
  1026. :param used_vars: A set of variables whose names should not be
  1027. used by the new variables.
  1028. :type new_vars: dict(Variable -> Variable)
  1029. :param new_vars: A dictionary that is used to hold the mapping
  1030. from old variables to new variables. For each variable *v*
  1031. in this feature structure:
  1032. - If ``new_vars`` maps *v* to *v'*, then *v* will be
  1033. replaced by *v'*.
  1034. - If ``new_vars`` does not contain *v*, but ``vars``
  1035. does contain *v*, then a new entry will be added to
  1036. ``new_vars``, mapping *v* to the new variable that is used
  1037. to replace it.
  1038. To consistently rename the variables in a set of feature
  1039. structures, simply apply rename_variables to each one, using
  1040. the same dictionary:
  1041. >>> from nltk.featstruct import FeatStruct
  1042. >>> fstruct1 = FeatStruct('[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]')
  1043. >>> fstruct2 = FeatStruct('[subj=[agr=[number=?z,gender=?y]], obj=[agr=[number=?z,gender=?y]]]')
  1044. >>> new_vars = {} # Maps old vars to alpha-renamed vars
  1045. >>> fstruct1.rename_variables(new_vars=new_vars)
  1046. [obj=[agr=[gender=?y2]], subj=[agr=[gender=?y2]]]
  1047. >>> fstruct2.rename_variables(new_vars=new_vars)
  1048. [obj=[agr=[gender=?y2, number=?z2]], subj=[agr=[gender=?y2, number=?z2]]]
  1049. If new_vars is not specified, then an empty dictionary is used.
  1050. """
  1051. if fs_class == 'default':
  1052. fs_class = _default_fs_class(fstruct)
  1053. # Default values:
  1054. if new_vars is None:
  1055. new_vars = {}
  1056. if vars is None:
  1057. vars = find_variables(fstruct, fs_class)
  1058. else:
  1059. vars = set(vars)
  1060. # Add our own variables to used_vars.
  1061. used_vars = find_variables(fstruct, fs_class).union(used_vars)
  1062. # Copy ourselves, and rename variables in the copy.
  1063. return _rename_variables(
  1064. copy.deepcopy(fstruct), vars, used_vars, new_vars, fs_class, set()
  1065. )
  1066. def _rename_variables(fstruct, vars, used_vars, new_vars, fs_class, visited):
  1067. if id(fstruct) in visited:
  1068. return
  1069. visited.add(id(fstruct))
  1070. if _is_mapping(fstruct):
  1071. items = fstruct.items()
  1072. elif _is_sequence(fstruct):
  1073. items = enumerate(fstruct)
  1074. else:
  1075. raise ValueError('Expected mapping or sequence')
  1076. for (fname, fval) in items:
  1077. if isinstance(fval, Variable):
  1078. # If it's in new_vars, then rebind it.
  1079. if fval in new_vars:
  1080. fstruct[fname] = new_vars[fval]
  1081. # If it's in vars, pick a new name for it.
  1082. elif fval in vars:
  1083. new_vars[fval] = _rename_variable(fval, used_vars)
  1084. fstruct[fname] = new_vars[fval]
  1085. used_vars.add(new_vars[fval])
  1086. elif isinstance(fval, fs_class):
  1087. _rename_variables(fval, vars, used_vars, new_vars, fs_class, visited)
  1088. elif isinstance(fval, SubstituteBindingsI):
  1089. # Pick new names for any variables in `vars`
  1090. for var in fval.variables():
  1091. if var in vars and var not in new_vars:
  1092. new_vars[var] = _rename_variable(var, used_vars)
  1093. used_vars.add(new_vars[var])
  1094. # Replace all variables in `new_vars`.
  1095. fstruct[fname] = fval.substitute_bindings(new_vars)
  1096. return fstruct
  1097. def _rename_variable(var, used_vars):
  1098. name, n = re.sub('\d+$', '', var.name), 2
  1099. if not name:
  1100. name = '?'
  1101. while Variable('%s%s' % (name, n)) in used_vars:
  1102. n += 1
  1103. return Variable('%s%s' % (name, n))
  1104. def remove_variables(fstruct, fs_class='default'):
  1105. """
  1106. :rtype: FeatStruct
  1107. :return: The feature structure that is obtained by deleting
  1108. all features whose values are ``Variables``.
  1109. """
  1110. if fs_class == 'default':
  1111. fs_class = _default_fs_class(fstruct)
  1112. return _remove_variables(copy.deepcopy(fstruct), fs_class, set())
  1113. def _remove_variables(fstruct, fs_class, visited):
  1114. if id(fstruct) in visited:
  1115. return
  1116. visited.add(id(fstruct))
  1117. if _is_mapping(fstruct):
  1118. items = list(fstruct.items())
  1119. elif _is_sequence(fstruct):
  1120. items = list(enumerate(fstruct))
  1121. else:
  1122. raise ValueError('Expected mapping or sequence')
  1123. for (fname, fval) in items:
  1124. if isinstance(fval, Variable):
  1125. del fstruct[fname]
  1126. elif isinstance(fval, fs_class):
  1127. _remove_variables(fval, fs_class, visited)
  1128. return fstruct
  1129. ######################################################################
  1130. # Unification
  1131. ######################################################################
  1132. @python_2_unicode_compatible
  1133. class _UnificationFailure(object):
  1134. def __repr__(self):
  1135. return 'nltk.featstruct.UnificationFailure'
  1136. UnificationFailure = _UnificationFailure()
  1137. """A unique value used to indicate unification failure. It can be
  1138. returned by ``Feature.unify_base_values()`` or by custom ``fail()``
  1139. functions to indicate that unificaiton should fail."""
  1140. # The basic unification algorithm:
  1141. # 1. Make copies of self and other (preserving reentrance)
  1142. # 2. Destructively unify self and other
  1143. # 3. Apply forward pointers, to preserve reentrance.
  1144. # 4. Replace bound variables with their values.
  1145. def unify(
  1146. fstruct1,
  1147. fstruct2,
  1148. bindings=None,
  1149. trace=False,
  1150. fail=None,
  1151. rename_vars=True,
  1152. fs_class='default',
  1153. ):
  1154. """
  1155. Unify ``fstruct1`` with ``fstruct2``, and return the resulting feature
  1156. structure. This unified feature structure is the minimal
  1157. feature structure that contains all feature value assignments from both
  1158. ``fstruct1`` and ``fstruct2``, and that preserves all reentrancies.
  1159. If no such feature structure exists (because ``fstruct1`` and
  1160. ``fstruct2`` specify incompatible values for some feature), then
  1161. unification fails, and ``unify`` returns None.
  1162. Bound variables are replaced by their values. Aliased
  1163. variables are replaced by their representative variable
  1164. (if unbound) or the value of their representative variable
  1165. (if bound). I.e., if variable *v* is in ``bindings``,
  1166. then *v* is replaced by ``bindings[v]``. This will
  1167. be repeated until the variable is replaced by an unbound
  1168. variable or a non-variable value.
  1169. Unbound variables are bound when they are unified with
  1170. values; and aliased when they are unified with variables.
  1171. I.e., if variable *v* is not in ``bindings``, and is
  1172. unified with a variable or value *x*, then
  1173. ``bindings[v]`` is set to *x*.
  1174. If ``bindings`` is unspecified, then all variables are
  1175. assumed to be unbound. I.e., ``bindings`` defaults to an
  1176. empty dict.
  1177. >>> from nltk.featstruct import FeatStruct
  1178. >>> FeatStruct('[a=?x]').unify(FeatStruct('[b=?x]'))
  1179. [a=?x, b=?x2]
  1180. :type bindings: dict(Variable -> any)
  1181. :param bindings: A set of variable bindings to be used and
  1182. updated during unification.
  1183. :type trace: bool
  1184. :param trace: If true, generate trace output.
  1185. :type rename_vars: bool
  1186. :param rename_vars: If True, then rename any variables in
  1187. ``fstruct2`` that are also used in ``fstruct1``, in order to
  1188. avoid collisions on variable names.
  1189. """
  1190. # Decide which class(es) will be treated as feature structures,
  1191. # for the purposes of unification.
  1192. if fs_class == 'default':
  1193. fs_class = _default_fs_class(fstruct1)
  1194. if _default_fs_class(fstruct2) != fs_class:
  1195. raise ValueError(
  1196. "Mixing FeatStruct objects with Python "
  1197. "dicts and lists is not supported."
  1198. )
  1199. assert isinstance(fstruct1, fs_class)
  1200. assert isinstance(fstruct2, fs_class)
  1201. # If bindings are unspecified, use an empty set of bindings.
  1202. user_bindings = bindings is not None
  1203. if bindings is None:
  1204. bindings = {}
  1205. # Make copies of fstruct1 and fstruct2 (since the unification
  1206. # algorithm is destructive). Do it all at once, to preserve
  1207. # reentrance links between fstruct1 and fstruct2. Copy bindings
  1208. # as well, in case there are any bound vars that contain parts
  1209. # of fstruct1 or fstruct2.
  1210. (fstruct1copy, fstruct2copy, bindings_copy) = copy.deepcopy(
  1211. (fstruct1, fstruct2, bindings)
  1212. )
  1213. # Copy the bindings back to the original bindings dict.
  1214. bindings.update(bindings_copy)
  1215. if rename_vars:
  1216. vars1 = find_variables(fstruct1copy, fs_class)
  1217. vars2 = find_variables(fstruct2copy, fs_class)
  1218. _rename_variables(fstruct2copy, vars1, vars2, {}, fs_class, set())
  1219. # Do the actual unification. If it fails, return None.
  1220. forward = {}
  1221. if trace:
  1222. _trace_unify_start((), fstruct1copy, fstruct2copy)
  1223. try:
  1224. result = _destructively_unify(
  1225. fstruct1copy, fstruct2copy, bindings, forward, trace, fail, fs_class, ()
  1226. )
  1227. except _UnificationFailureError:
  1228. return None
  1229. # _destructively_unify might return UnificationFailure, e.g. if we
  1230. # tried to unify a mapping with a sequence.
  1231. if result is UnificationFailure:
  1232. if fail is None:
  1233. return None
  1234. else:
  1235. return fail(fstruct1copy, fstruct2copy, ())
  1236. # Replace any feature structure that has a forward pointer
  1237. # with the target of its forward pointer.
  1238. result = _apply_forwards(result, forward, fs_class, set())
  1239. if user_bindings:
  1240. _apply_forwards_to_bindings(forward, bindings)
  1241. # Replace bound vars with values.
  1242. _resolve_aliases(bindings)
  1243. _substitute_bindings(result, bindings, fs_class, set())
  1244. # Return the result.
  1245. if trace:
  1246. _trace_unify_succeed((), result)
  1247. if trace:
  1248. _trace_bindings((), bindings)
  1249. return result
  1250. class _UnificationFailureError(Exception):
  1251. """An exception that is used by ``_destructively_unify`` to abort
  1252. unification when a failure is encountered."""
  1253. def _destructively_unify(
  1254. fstruct1, fstruct2, bindings, forward, trace, fail, fs_class, path
  1255. ):
  1256. """
  1257. Attempt to unify ``fstruct1`` and ``fstruct2`` by modifying them
  1258. in-place. If the unification succeeds, then ``fstruct1`` will
  1259. contain the unified value, the value of ``fstruct2`` is undefined,
  1260. and forward[id(fstruct2)] is set to fstruct1. If the unification
  1261. fails, then a _UnificationFailureError is raised, and the
  1262. values of ``fstruct1`` and ``fstruct2`` are undefined.
  1263. :param bindings: A dictionary mapping variables to values.
  1264. :param forward: A dictionary mapping feature structures ids
  1265. to replacement structures. When two feature structures
  1266. are merged, a mapping from one to the other will be added
  1267. to the forward dictionary; and changes will be made only
  1268. to the target of the forward dictionary.
  1269. ``_destructively_unify`` will always 'follow' any links
  1270. in the forward dictionary for fstruct1 and fstruct2 before
  1271. actually unifying them.
  1272. :param trace: If true, generate trace output
  1273. :param path: The feature path that led us to this unification
  1274. step. Used for trace output.
  1275. """
  1276. # If fstruct1 is already identical to fstruct2, we're done.
  1277. # Note: this, together with the forward pointers, ensures
  1278. # that unification will terminate even for cyclic structures.
  1279. if fstruct1 is fstruct2:
  1280. if trace:
  1281. _trace_unify_identity(path, fstruct1)
  1282. return fstruct1
  1283. # Set fstruct2's forward pointer to point to fstruct1; this makes
  1284. # fstruct1 the canonical copy for fstruct2. Note that we need to
  1285. # do this before we recurse into any child structures, in case
  1286. # they're cyclic.
  1287. forward[id(fstruct2)] = fstruct1
  1288. # Unifying two mappings:
  1289. if _is_mapping(fstruct1) and _is_mapping(fstruct2):
  1290. for fname in fstruct1:
  1291. if getattr(fname, 'default', None) is not None:
  1292. fstruct2.setdefault(fname, fname.default)
  1293. for fname in fstruct2:
  1294. if getattr(fname, 'default', None) is not None:
  1295. fstruct1.setdefault(fname, fname.default)
  1296. # Unify any values that are defined in both fstruct1 and
  1297. # fstruct2. Copy any values that are defined in fstruct2 but
  1298. # not in fstruct1 to fstruct1. Note: sorting fstruct2's
  1299. # features isn't actually necessary; but we do it to give
  1300. # deterministic behavior, e.g. for tracing.
  1301. for fname, fval2 in sorted(fstruct2.items()):
  1302. if fname in fstruct1:
  1303. fstruct1[fname] = _unify_feature_values(
  1304. fname,
  1305. fstruct1[fname],
  1306. fval2,
  1307. bindings,
  1308. forward,
  1309. trace,
  1310. fail,
  1311. fs_class,
  1312. path + (fname,),
  1313. )
  1314. else:
  1315. fstruct1[fname] = fval2
  1316. return fstruct1 # Contains the unified value.
  1317. # Unifying two sequences:
  1318. elif _is_sequence(fstruct1) and _is_sequence(fstruct2):
  1319. # If the lengths don't match, fail.
  1320. if len(fstruct1) != len(fstruct2):
  1321. return UnificationFailure
  1322. # Unify corresponding values in fstruct1 and fstruct2.
  1323. for findex in range(len(fstruct1)):
  1324. fstruct1[findex] = _unify_feature_values(
  1325. findex,
  1326. fstruct1[findex],
  1327. fstruct2[findex],
  1328. bindings,
  1329. forward,
  1330. trace,
  1331. fail,
  1332. fs_class,
  1333. path + (findex,),
  1334. )
  1335. return fstruct1 # Contains the unified value.
  1336. # Unifying sequence & mapping: fail. The failure function
  1337. # doesn't get a chance to recover in this case.
  1338. elif (_is_sequence(fstruct1) or _is_mapping(fstruct1)) and (
  1339. _is_sequence(fstruct2) or _is_mapping(fstruct2)
  1340. ):
  1341. return UnificationFailure
  1342. # Unifying anything else: not allowed!
  1343. raise TypeError('Expected mappings or sequences')
  1344. def _unify_feature_values(
  1345. fname, fval1, fval2, bindings, forward, trace, fail, fs_class, fpath
  1346. ):
  1347. """
  1348. Attempt to unify ``fval1`` and and ``fval2``, and return the
  1349. resulting unified value. The method of unification will depend on
  1350. the types of ``fval1`` and ``fval2``:
  1351. 1. If they're both feature structures, then destructively
  1352. unify them (see ``_destructively_unify()``.
  1353. 2. If they're both unbound variables, then alias one variable
  1354. to the other (by setting bindings[v2]=v1).
  1355. 3. If one is an unbound variable, and the other is a value,
  1356. then bind the unbound variable to the value.
  1357. 4. If one is a feature structure, and the other is a base value,
  1358. then fail.
  1359. 5. If they're both base values, then unify them. By default,
  1360. this will succeed if they are equal, and fail otherwise.
  1361. """
  1362. if trace:
  1363. _trace_unify_start(fpath, fval1, fval2)
  1364. # Look up the "canonical" copy of fval1 and fval2
  1365. while id(fval1) in forward:
  1366. fval1 = forward[id(fval1)]
  1367. while id(fval2) in forward:
  1368. fval2 = forward[id(fval2)]
  1369. # If fval1 or fval2 is a bound variable, then
  1370. # replace it by the variable's bound value. This
  1371. # includes aliased variables, which are encoded as
  1372. # variables bound to other variables.
  1373. fvar1 = fvar2 = None
  1374. while isinstance(fval1, Variable) and fval1 in bindings:
  1375. fvar1 = fval1
  1376. fval1 = bindings[fval1]
  1377. while isinstance(fval2, Variable) and fval2 in bindings:
  1378. fvar2 = fval2
  1379. fval2 = bindings[fval2]
  1380. # Case 1: Two feature structures (recursive case)
  1381. if isinstance(fval1, fs_class) and isinstance(fval2, fs_class):
  1382. result = _destructively_unify(
  1383. fval1, fval2, bindings, forward, trace, fail, fs_class, fpath
  1384. )
  1385. # Case 2: Two unbound variables (create alias)
  1386. elif isinstance(fval1, Variable) and isinstance(fval2, Variable):
  1387. if fval1 != fval2:
  1388. bindings[fval2] = fval1
  1389. result = fval1
  1390. # Case 3: An unbound variable and a value (bind)
  1391. elif isinstance(fval1, Variable):
  1392. bindings[fval1] = fval2
  1393. result = fval1
  1394. elif isinstance(fval2, Variable):
  1395. bindings[fval2] = fval1
  1396. result = fval2
  1397. # Case 4: A feature structure & a base value (fail)
  1398. elif isinstance(fval1, fs_class) or isinstance(fval2, fs_class):
  1399. result = UnificationFailure
  1400. # Case 5: Two base values
  1401. else:
  1402. # Case 5a: Feature defines a custom unification method for base values
  1403. if isinstance(fname, Feature):
  1404. result = fname.unify_base_values(fval1, fval2, bindings)
  1405. # Case 5b: Feature value defines custom unification method
  1406. elif isinstance(fval1, CustomFeatureValue):
  1407. result = fval1.unify(fval2)
  1408. # Sanity check: unify value should be symmetric
  1409. if isinstance(fval2, CustomFeatureValue) and result != fval2.unify(fval1):
  1410. raise AssertionError(
  1411. 'CustomFeatureValue objects %r and %r disagree '
  1412. 'about unification value: %r vs. %r'
  1413. % (fval1, fval2, result, fval2.unify(fval1))
  1414. )
  1415. elif isinstance(fval2, CustomFeatureValue):
  1416. result = fval2.unify(fval1)
  1417. # Case 5c: Simple values -- check if they're equal.
  1418. else:
  1419. if fval1 == fval2:
  1420. result = fval1
  1421. else:
  1422. result = UnificationFailure
  1423. # If either value was a bound variable, then update the
  1424. # bindings. (This is really only necessary if fname is a
  1425. # Feature or if either value is a CustomFeatureValue.)
  1426. if result is not UnificationFailure:
  1427. if fvar1 is not None:
  1428. bindings[fvar1] = result
  1429. result = fvar1
  1430. if fvar2 is not None and fvar2 != fvar1:
  1431. bindings[fvar2] = result
  1432. result = fvar2
  1433. # If we unification failed, call the failure function; it
  1434. # might decide to continue anyway.
  1435. if result is UnificationFailure:
  1436. if fail is not None:
  1437. result = fail(fval1, fval2, fpath)
  1438. if trace:
  1439. _trace_unify_fail(fpath[:-1], result)
  1440. if result is UnificationFailure:
  1441. raise _UnificationFailureError
  1442. # Normalize the result.
  1443. if isinstance(result, fs_class):
  1444. result = _apply_forwards(result, forward, fs_class, set())
  1445. if trace:
  1446. _trace_unify_succeed(fpath, result)
  1447. if trace and isinstance(result, fs_class):
  1448. _trace_bindings(fpath, bindings)
  1449. return result
  1450. def _apply_forwards_to_bindings(forward, bindings):
  1451. """
  1452. Replace any feature structure that has a forward pointer with
  1453. the target of its forward pointer (to preserve reentrancy).
  1454. """
  1455. for (var, value) in bindings.items():
  1456. while id(value) in forward:
  1457. value = forward[id(value)]
  1458. bindings[var] = value
  1459. def _apply_forwards(fstruct, forward, fs_class, visited):
  1460. """
  1461. Replace any feature structure that has a forward pointer with
  1462. the target of its forward pointer (to preserve reentrancy).
  1463. """
  1464. # Follow our own forwards pointers (if any)
  1465. while id(fstruct) in forward:
  1466. fstruct = forward[id(fstruct)]
  1467. # Visit each node only once:
  1468. if id(fstruct) in visited:
  1469. return
  1470. visited.add(id(fstruct))
  1471. if _is_mapping(fstruct):
  1472. items = fstruct.items()
  1473. elif _is_sequence(fstruct):
  1474. items = enumerate(fstruct)
  1475. else:
  1476. raise ValueError('Expected mapping or sequence')
  1477. for fname, fval in items:
  1478. if isinstance(fval, fs_class):
  1479. # Replace w/ forwarded value.
  1480. while id(fval) in forward:
  1481. fval = forward[id(fval)]
  1482. fstruct[fname] = fval
  1483. # Recurse to child.
  1484. _apply_forwards(fval, forward, fs_class, visited)
  1485. return fstruct
  1486. def _resolve_aliases(bindings):
  1487. """
  1488. Replace any bound aliased vars with their binding; and replace
  1489. any unbound aliased vars with their representative var.
  1490. """
  1491. for (var, value) in bindings.items():
  1492. while isinstance(value, Variable) and value in bindings:
  1493. value = bindings[var] = bindings[value]
  1494. def _trace_unify_start(path, fval1, fval2):
  1495. if path == ():
  1496. print('\nUnification trace:')
  1497. else:
  1498. fullname = '.'.join("%s" % n for n in path)
  1499. print(' ' + '| ' * (len(path) - 1) + '|')
  1500. print(' ' + '| ' * (len(path) - 1) + '| Unify feature: %s' % fullname)
  1501. print(' ' + '| ' * len(path) + ' / ' + _trace_valrepr(fval1))
  1502. print(' ' + '| ' * len(path) + '|\\ ' + _trace_valrepr(fval2))
  1503. def _trace_unify_identity(path, fval1):
  1504. print(' ' + '| ' * len(path) + '|')
  1505. print(' ' + '| ' * len(path) + '| (identical objects)')
  1506. print(' ' + '| ' * len(path) + '|')
  1507. print(' ' + '| ' * len(path) + '+-->' + unicode_repr(fval1))
  1508. def _trace_unify_fail(path, result):
  1509. if result is UnificationFailure:
  1510. resume = ''
  1511. else:
  1512. resume = ' (nonfatal)'
  1513. print(' ' + '| ' * len(path) + '| |')
  1514. print(' ' + 'X ' * len(path) + 'X X <-- FAIL' + resume)
  1515. def _trace_unify_succeed(path, fval1):
  1516. # Print the result.
  1517. print(' ' + '| ' * len(path) + '|')
  1518. print(' ' + '| ' * len(path) + '+-->' + unicode_repr(fval1))
  1519. def _trace_bindings(path, bindings):
  1520. # Print the bindings (if any).
  1521. if len(bindings) > 0:
  1522. binditems = sorted(bindings.items(), key=lambda v: v[0].name)
  1523. bindstr = '{%s}' % ', '.join(
  1524. '%s: %s' % (var, _trace_valrepr(val)) for (var, val) in binditems
  1525. )
  1526. print(' ' + '| ' * len(path) + ' Bindings: ' + bindstr)
  1527. def _trace_valrepr(val):
  1528. if isinstance(val, Variable):
  1529. return '%s' % val
  1530. else:
  1531. return '%s' % unicode_repr(val)
  1532. def subsumes(fstruct1, fstruct2):
  1533. """
  1534. Return True if ``fstruct1`` subsumes ``fstruct2``. I.e., return
  1535. true if unifying ``fstruct1`` with ``fstruct2`` would result in a
  1536. feature structure equal to ``fstruct2.``
  1537. :rtype: bool
  1538. """
  1539. return fstruct2 == unify(fstruct1, fstruct2)
  1540. def conflicts(fstruct1, fstruct2, trace=0):
  1541. """
  1542. Return a list of the feature paths of all features which are
  1543. assigned incompatible values by ``fstruct1`` and ``fstruct2``.
  1544. :rtype: list(tuple)
  1545. """
  1546. conflict_list = []
  1547. def add_conflict(fval1, fval2, path):
  1548. conflict_list.append(path)
  1549. return fval1
  1550. unify(fstruct1, fstruct2, fail=add_conflict, trace=trace)
  1551. return conflict_list
  1552. ######################################################################
  1553. # Helper Functions
  1554. ######################################################################
  1555. def _is_mapping(v):
  1556. return hasattr(v, '__contains__') and hasattr(v, 'keys')
  1557. def _is_sequence(v):
  1558. return (
  1559. hasattr(v, '__iter__')
  1560. and hasattr(v, '__len__')
  1561. and not isinstance(v, string_types)
  1562. )
  1563. def _default_fs_class(obj):
  1564. if isinstance(obj, FeatStruct):
  1565. return FeatStruct
  1566. if isinstance(obj, (dict, list)):
  1567. return (dict, list)
  1568. else:
  1569. raise ValueError(
  1570. 'To unify objects of type %s, you must specify '
  1571. 'fs_class explicitly.' % obj.__class__.__name__
  1572. )
  1573. ######################################################################
  1574. # FeatureValueSet & FeatureValueTuple
  1575. ######################################################################
  1576. class SubstituteBindingsSequence(SubstituteBindingsI):
  1577. """
  1578. A mixin class for sequence clases that distributes variables() and
  1579. substitute_bindings() over the object's elements.
  1580. """
  1581. def variables(self):
  1582. return [elt for elt in self if isinstance(elt, Variable)] + sum(
  1583. [
  1584. list(elt.variables())
  1585. for elt in self
  1586. if isinstance(elt, SubstituteBindingsI)
  1587. ],
  1588. [],
  1589. )
  1590. def substitute_bindings(self, bindings):
  1591. return self.__class__([self.subst(v, bindings) for v in self])
  1592. def subst(self, v, bindings):
  1593. if isinstance(v, SubstituteBindingsI):
  1594. return v.substitute_bindings(bindings)
  1595. else:
  1596. return bindings.get(v, v)
  1597. @python_2_unicode_compatible
  1598. class FeatureValueTuple(SubstituteBindingsSequence, tuple):
  1599. """
  1600. A base feature value that is a tuple of other base feature values.
  1601. FeatureValueTuple implements ``SubstituteBindingsI``, so it any
  1602. variable substitutions will be propagated to the elements
  1603. contained by the set. A ``FeatureValueTuple`` is immutable.
  1604. """
  1605. def __repr__(self): # [xx] really use %s here?
  1606. if len(self) == 0:
  1607. return '()'
  1608. return '(%s)' % ', '.join('%s' % (b,) for b in self)
  1609. @python_2_unicode_compatible
  1610. class FeatureValueSet(SubstituteBindingsSequence, frozenset):
  1611. """
  1612. A base feature value that is a set of other base feature values.
  1613. FeatureValueSet implements ``SubstituteBindingsI``, so it any
  1614. variable substitutions will be propagated to the elements
  1615. contained by the set. A ``FeatureValueSet`` is immutable.
  1616. """
  1617. def __repr__(self): # [xx] really use %s here?
  1618. if len(self) == 0:
  1619. return '{/}' # distinguish from dict.
  1620. # n.b., we sort the string reprs of our elements, to ensure
  1621. # that our own repr is deterministic.
  1622. return '{%s}' % ', '.join(sorted('%s' % (b,) for b in self))
  1623. __str__ = __repr__
  1624. @python_2_unicode_compatible
  1625. class FeatureValueUnion(SubstituteBindingsSequence, frozenset):
  1626. """
  1627. A base feature value that represents the union of two or more
  1628. ``FeatureValueSet`` or ``Variable``.
  1629. """
  1630. def __new__(cls, values):
  1631. # If values contains FeatureValueUnions, then collapse them.
  1632. values = _flatten(values, FeatureValueUnion)
  1633. # If the resulting list contains no variables, then
  1634. # use a simple FeatureValueSet instead.
  1635. if sum(isinstance(v, Variable) for v in values) == 0:
  1636. values = _flatten(values, FeatureValueSet)
  1637. return FeatureValueSet(values)
  1638. # If we contain a single variable, return that variable.
  1639. if len(values) == 1:
  1640. return list(values)[0]
  1641. # Otherwise, build the FeatureValueUnion.
  1642. return frozenset.__new__(cls, values)
  1643. def __repr__(self):
  1644. # n.b., we sort the string reprs of our elements, to ensure
  1645. # that our own repr is deterministic. also, note that len(self)
  1646. # is guaranteed to be 2 or more.
  1647. return '{%s}' % '+'.join(sorted('%s' % (b,) for b in self))
  1648. @python_2_unicode_compatible
  1649. class FeatureValueConcat(SubstituteBindingsSequence, tuple):
  1650. """
  1651. A base feature value that represents the concatenation of two or
  1652. more ``FeatureValueTuple`` or ``Variable``.
  1653. """
  1654. def __new__(cls, values):
  1655. # If values contains FeatureValueConcats, then collapse them.
  1656. values = _flatten(values, FeatureValueConcat)
  1657. # If the resulting list contains no variables, then
  1658. # use a simple FeatureValueTuple instead.
  1659. if sum(isinstance(v, Variable) for v in values) == 0:
  1660. values = _flatten(values, FeatureValueTuple)
  1661. return FeatureValueTuple(values)
  1662. # If we contain a single variable, return that variable.
  1663. if len(values) == 1:
  1664. return list(values)[0]
  1665. # Otherwise, build the FeatureValueConcat.
  1666. return tuple.__new__(cls, values)
  1667. def __repr__(self):
  1668. # n.b.: len(self) is guaranteed to be 2 or more.
  1669. return '(%s)' % '+'.join('%s' % (b,) for b in self)
  1670. def _flatten(lst, cls):
  1671. """
  1672. Helper function -- return a copy of list, with all elements of
  1673. type ``cls`` spliced in rather than appended in.
  1674. """
  1675. result = []
  1676. for elt in lst:
  1677. if isinstance(elt, cls):
  1678. result.extend(elt)
  1679. else:
  1680. result.append(elt)
  1681. return result
  1682. ######################################################################
  1683. # Specialized Features
  1684. ######################################################################
  1685. @total_ordering
  1686. @python_2_unicode_compatible
  1687. class Feature(object):
  1688. """
  1689. A feature identifier that's specialized to put additional
  1690. constraints, default values, etc.
  1691. """
  1692. def __init__(self, name, default=None, display=None):
  1693. assert display in (None, 'prefix', 'slash')
  1694. self._name = name # [xx] rename to .identifier?
  1695. self._default = default # [xx] not implemented yet.
  1696. self._display = display
  1697. if self._display == 'prefix':
  1698. self._sortkey = (-1, self._name)
  1699. elif self._display == 'slash':
  1700. self._sortkey = (1, self._name)
  1701. else:
  1702. self._sortkey = (0, self._name)
  1703. @property
  1704. def name(self):
  1705. """The name of this feature."""
  1706. return self._name
  1707. @property
  1708. def default(self):
  1709. """Default value for this feature."""
  1710. return self._default
  1711. @property
  1712. def display(self):
  1713. """Custom display location: can be prefix, or slash."""
  1714. return self._display
  1715. def __repr__(self):
  1716. return '*%s*' % self.name
  1717. def __lt__(self, other):
  1718. if isinstance(other, string_types):
  1719. return True
  1720. if not isinstance(other, Feature):
  1721. raise_unorderable_types("<", self, other)
  1722. return self._sortkey < other._sortkey
  1723. def __eq__(self, other):
  1724. return type(self) == type(other) and self._name == other._name
  1725. def __ne__(self, other):
  1726. return not self == other
  1727. def __hash__(self):
  1728. return hash(self._name)
  1729. # ////////////////////////////////////////////////////////////
  1730. # These can be overridden by subclasses:
  1731. # ////////////////////////////////////////////////////////////
  1732. def read_value(self, s, position, reentrances, parser):
  1733. return parser.read_value(s, position, reentrances)
  1734. def unify_base_values(self, fval1, fval2, bindings):
  1735. """
  1736. If possible, return a single value.. If not, return
  1737. the value ``UnificationFailure``.
  1738. """
  1739. if fval1 == fval2:
  1740. return fval1
  1741. else:
  1742. return UnificationFailure
  1743. class SlashFeature(Feature):
  1744. def read_value(self, s, position, reentrances, parser):
  1745. return parser.read_partial(s, position, reentrances)
  1746. class RangeFeature(Feature):
  1747. RANGE_RE = re.compile('(-?\d+):(-?\d+)')
  1748. def read_value(self, s, position, reentrances, parser):
  1749. m = self.RANGE_RE.match(s, position)
  1750. if not m:
  1751. raise ValueError('range', position)
  1752. return (int(m.group(1)), int(m.group(2))), m.end()
  1753. def unify_base_values(self, fval1, fval2, bindings):
  1754. if fval1 is None:
  1755. return fval2
  1756. if fval2 is None:
  1757. return fval1
  1758. rng = max(fval1[0], fval2[0]), min(fval1[1], fval2[1])
  1759. if rng[1] < rng[0]:
  1760. return UnificationFailure
  1761. return rng
  1762. SLASH = SlashFeature('slash', default=False, display='slash')
  1763. TYPE = Feature('type', display='prefix')
  1764. ######################################################################
  1765. # Specialized Feature Values
  1766. ######################################################################
  1767. @total_ordering
  1768. class CustomFeatureValue(object):
  1769. """
  1770. An abstract base class for base values that define a custom
  1771. unification method. The custom unification method of
  1772. ``CustomFeatureValue`` will be used during unification if:
  1773. - The ``CustomFeatureValue`` is unified with another base value.
  1774. - The ``CustomFeatureValue`` is not the value of a customized
  1775. ``Feature`` (which defines its own unification method).
  1776. If two ``CustomFeatureValue`` objects are unified with one another
  1777. during feature structure unification, then the unified base values
  1778. they return *must* be equal; otherwise, an ``AssertionError`` will
  1779. be raised.
  1780. Subclasses must define ``unify()``, ``__eq__()`` and ``__lt__()``.
  1781. Subclasses may also wish to define ``__hash__()``.
  1782. """
  1783. def unify(self, other):
  1784. """
  1785. If this base value unifies with ``other``, then return the
  1786. unified value. Otherwise, return ``UnificationFailure``.
  1787. """
  1788. raise NotImplementedError('abstract base class')
  1789. def __eq__(self, other):
  1790. raise NotImplementedError('abstract base class')
  1791. def __ne__(self, other):
  1792. return not self == other
  1793. def __lt__(self, other):
  1794. raise NotImplementedError('abstract base class')
  1795. def __hash__(self):
  1796. raise TypeError('%s objects or unhashable' % self.__class__.__name__)
  1797. ######################################################################
  1798. # Feature Structure Reader
  1799. ######################################################################
  1800. class FeatStructReader(object):
  1801. def __init__(
  1802. self,
  1803. features=(SLASH, TYPE),
  1804. fdict_class=FeatStruct,
  1805. flist_class=FeatList,
  1806. logic_parser=None,
  1807. ):
  1808. self._features = dict((f.name, f) for f in features)
  1809. self._fdict_class = fdict_class
  1810. self._flist_class = flist_class
  1811. self._prefix_feature = None
  1812. self._slash_feature = None
  1813. for feature in features:
  1814. if feature.display == 'slash':
  1815. if self._slash_feature:
  1816. raise ValueError('Multiple features w/ display=slash')
  1817. self._slash_feature = feature
  1818. if feature.display == 'prefix':
  1819. if self._prefix_feature:
  1820. raise ValueError('Multiple features w/ display=prefix')
  1821. self._prefix_feature = feature
  1822. self._features_with_defaults = [
  1823. feature for feature in features if feature.default is not None
  1824. ]
  1825. if logic_parser is None:
  1826. logic_parser = LogicParser()
  1827. self._logic_parser = logic_parser
  1828. def fromstring(self, s, fstruct=None):
  1829. """
  1830. Convert a string representation of a feature structure (as
  1831. displayed by repr) into a ``FeatStruct``. This process
  1832. imposes the following restrictions on the string
  1833. representation:
  1834. - Feature names cannot contain any of the following:
  1835. whitespace, parentheses, quote marks, equals signs,
  1836. dashes, commas, and square brackets. Feature names may
  1837. not begin with plus signs or minus signs.
  1838. - Only the following basic feature value are supported:
  1839. strings, integers, variables, None, and unquoted
  1840. alphanumeric strings.
  1841. - For reentrant values, the first mention must specify
  1842. a reentrance identifier and a value; and any subsequent
  1843. mentions must use arrows (``'->'``) to reference the
  1844. reentrance identifier.
  1845. """
  1846. s = s.strip()
  1847. value, position = self.read_partial(s, 0, {}, fstruct)
  1848. if position != len(s):
  1849. self._error(s, 'end of string', position)
  1850. return value
  1851. _START_FSTRUCT_RE = re.compile(r'\s*(?:\((\d+)\)\s*)?(\??[\w-]+)?(\[)')
  1852. _END_FSTRUCT_RE = re.compile(r'\s*]\s*')
  1853. _SLASH_RE = re.compile(r'/')
  1854. _FEATURE_NAME_RE = re.compile(r'\s*([+-]?)([^\s\(\)<>"\'\-=\[\],]+)\s*')
  1855. _REENTRANCE_RE = re.compile(r'\s*->\s*')
  1856. _TARGET_RE = re.compile(r'\s*\((\d+)\)\s*')
  1857. _ASSIGN_RE = re.compile(r'\s*=\s*')
  1858. _COMMA_RE = re.compile(r'\s*,\s*')
  1859. _BARE_PREFIX_RE = re.compile(r'\s*(?:\((\d+)\)\s*)?(\??[\w-]+\s*)()')
  1860. # This one is used to distinguish fdicts from flists:
  1861. _START_FDICT_RE = re.compile(
  1862. r'(%s)|(%s\s*(%s\s*(=|->)|[+-]%s|\]))'
  1863. % (
  1864. _BARE_PREFIX_RE.pattern,
  1865. _START_FSTRUCT_RE.pattern,
  1866. _FEATURE_NAME_RE.pattern,
  1867. _FEATURE_NAME_RE.pattern,
  1868. )
  1869. )
  1870. def read_partial(self, s, position=0, reentrances=None, fstruct=None):
  1871. """
  1872. Helper function that reads in a feature structure.
  1873. :param s: The string to read.
  1874. :param position: The position in the string to start parsing.
  1875. :param reentrances: A dictionary from reentrance ids to values.
  1876. Defaults to an empty dictionary.
  1877. :return: A tuple (val, pos) of the feature structure created by
  1878. parsing and the position where the parsed feature structure ends.
  1879. :rtype: bool
  1880. """
  1881. if reentrances is None:
  1882. reentrances = {}
  1883. try:
  1884. return self._read_partial(s, position, reentrances, fstruct)
  1885. except ValueError as e:
  1886. if len(e.args) != 2:
  1887. raise
  1888. self._error(s, *e.args)
  1889. def _read_partial(self, s, position, reentrances, fstruct=None):
  1890. # Create the new feature structure
  1891. if fstruct is None:
  1892. if self._START_FDICT_RE.match(s, position):
  1893. fstruct = self._fdict_class()
  1894. else:
  1895. fstruct = self._flist_class()
  1896. # Read up to the open bracket.
  1897. match = self._START_FSTRUCT_RE.match(s, position)
  1898. if not match:
  1899. match = self._BARE_PREFIX_RE.match(s, position)
  1900. if not match:
  1901. raise ValueError('open bracket or identifier', position)
  1902. position = match.end()
  1903. # If there as an identifier, record it.
  1904. if match.group(1):
  1905. identifier = match.group(1)
  1906. if identifier in reentrances:
  1907. raise ValueError('new identifier', match.start(1))
  1908. reentrances[identifier] = fstruct
  1909. if isinstance(fstruct, FeatDict):
  1910. fstruct.clear()
  1911. return self._read_partial_featdict(s, position, match, reentrances, fstruct)
  1912. else:
  1913. del fstruct[:]
  1914. return self._read_partial_featlist(s, position, match, reentrances, fstruct)
  1915. def _read_partial_featlist(self, s, position, match, reentrances, fstruct):
  1916. # Prefix features are not allowed:
  1917. if match.group(2):
  1918. raise ValueError('open bracket')
  1919. # Bare prefixes are not allowed:
  1920. if not match.group(3):
  1921. raise ValueError('open bracket')
  1922. # Build a list of the features defined by the structure.
  1923. while position < len(s):
  1924. # Check for the close bracket.
  1925. match = self._END_FSTRUCT_RE.match(s, position)
  1926. if match is not None:
  1927. return fstruct, match.end()
  1928. # Reentances have the form "-> (target)"
  1929. match = self._REENTRANCE_RE.match(s, position)
  1930. if match:
  1931. position = match.end()
  1932. match = self._TARGET_RE.match(s, position)
  1933. if not match:
  1934. raise ValueError('identifier', position)
  1935. target = match.group(1)
  1936. if target not in reentrances:
  1937. raise ValueError('bound identifier', position)
  1938. position = match.end()
  1939. fstruct.append(reentrances[target])
  1940. # Anything else is a value.
  1941. else:
  1942. value, position = self._read_value(0, s, position, reentrances)
  1943. fstruct.append(value)
  1944. # If there's a close bracket, handle it at the top of the loop.
  1945. if self._END_FSTRUCT_RE.match(s, position):
  1946. continue
  1947. # Otherwise, there should be a comma
  1948. match = self._COMMA_RE.match(s, position)
  1949. if match is None:
  1950. raise ValueError('comma', position)
  1951. position = match.end()
  1952. # We never saw a close bracket.
  1953. raise ValueError('close bracket', position)
  1954. def _read_partial_featdict(self, s, position, match, reentrances, fstruct):
  1955. # If there was a prefix feature, record it.
  1956. if match.group(2):
  1957. if self._prefix_feature is None:
  1958. raise ValueError('open bracket or identifier', match.start(2))
  1959. prefixval = match.group(2).strip()
  1960. if prefixval.startswith('?'):
  1961. prefixval = Variable(prefixval)
  1962. fstruct[self._prefix_feature] = prefixval
  1963. # If group 3 is empty, then we just have a bare prefix, so
  1964. # we're done.
  1965. if not match.group(3):
  1966. return self._finalize(s, match.end(), reentrances, fstruct)
  1967. # Build a list of the features defined by the structure.
  1968. # Each feature has one of the three following forms:
  1969. # name = value
  1970. # name -> (target)
  1971. # +name
  1972. # -name
  1973. while position < len(s):
  1974. # Use these variables to hold info about each feature:
  1975. name = value = None
  1976. # Check for the close bracket.
  1977. match = self._END_FSTRUCT_RE.match(s, position)
  1978. if match is not None:
  1979. return self._finalize(s, match.end(), reentrances, fstruct)
  1980. # Get the feature name's name
  1981. match = self._FEATURE_NAME_RE.match(s, position)
  1982. if match is None:
  1983. raise ValueError('feature name', position)
  1984. name = match.group(2)
  1985. position = match.end()
  1986. # Check if it's a special feature.
  1987. if name[0] == '*' and name[-1] == '*':
  1988. name = self._features.get(name[1:-1])
  1989. if name is None:
  1990. raise ValueError('known special feature', match.start(2))
  1991. # Check if this feature has a value already.
  1992. if name in fstruct:
  1993. raise ValueError('new name', match.start(2))
  1994. # Boolean value ("+name" or "-name")
  1995. if match.group(1) == '+':
  1996. value = True
  1997. if match.group(1) == '-':
  1998. value = False
  1999. # Reentrance link ("-> (target)")
  2000. if value is None:
  2001. match = self._REENTRANCE_RE.match(s, position)
  2002. if match is not None:
  2003. position = match.end()
  2004. match = self._TARGET_RE.match(s, position)
  2005. if not match:
  2006. raise ValueError('identifier', position)
  2007. target = match.group(1)
  2008. if target not in reentrances:
  2009. raise ValueError('bound identifier', position)
  2010. position = match.end()
  2011. value = reentrances[target]
  2012. # Assignment ("= value").
  2013. if value is None:
  2014. match = self._ASSIGN_RE.match(s, position)
  2015. if match:
  2016. position = match.end()
  2017. value, position = self._read_value(name, s, position, reentrances)
  2018. # None of the above: error.
  2019. else:
  2020. raise ValueError('equals sign', position)
  2021. # Store the value.
  2022. fstruct[name] = value
  2023. # If there's a close bracket, handle it at the top of the loop.
  2024. if self._END_FSTRUCT_RE.match(s, position):
  2025. continue
  2026. # Otherwise, there should be a comma
  2027. match = self._COMMA_RE.match(s, position)
  2028. if match is None:
  2029. raise ValueError('comma', position)
  2030. position = match.end()
  2031. # We never saw a close bracket.
  2032. raise ValueError('close bracket', position)
  2033. def _finalize(self, s, pos, reentrances, fstruct):
  2034. """
  2035. Called when we see the close brace -- checks for a slash feature,
  2036. and adds in default values.
  2037. """
  2038. # Add the slash feature (if any)
  2039. match = self._SLASH_RE.match(s, pos)
  2040. if match:
  2041. name = self._slash_feature
  2042. v, pos = self._read_value(name, s, match.end(), reentrances)
  2043. fstruct[name] = v
  2044. ## Add any default features. -- handle in unficiation instead?
  2045. # for feature in self._features_with_defaults:
  2046. # fstruct.setdefault(feature, feature.default)
  2047. # Return the value.
  2048. return fstruct, pos
  2049. def _read_value(self, name, s, position, reentrances):
  2050. if isinstance(name, Feature):
  2051. return name.read_value(s, position, reentrances, self)
  2052. else:
  2053. return self.read_value(s, position, reentrances)
  2054. def read_value(self, s, position, reentrances):
  2055. for (handler, regexp) in self.VALUE_HANDLERS:
  2056. match = regexp.match(s, position)
  2057. if match:
  2058. handler_func = getattr(self, handler)
  2059. return handler_func(s, position, reentrances, match)
  2060. raise ValueError('value', position)
  2061. def _error(self, s, expected, position):
  2062. lines = s.split('\n')
  2063. while position > len(lines[0]):
  2064. position -= len(lines.pop(0)) + 1 # +1 for the newline.
  2065. estr = (
  2066. 'Error parsing feature structure\n '
  2067. + lines[0]
  2068. + '\n '
  2069. + ' ' * position
  2070. + '^ '
  2071. + 'Expected %s' % expected
  2072. )
  2073. raise ValueError(estr)
  2074. # ////////////////////////////////////////////////////////////
  2075. # { Value Readers
  2076. # ////////////////////////////////////////////////////////////
  2077. #: A table indicating how feature values should be processed. Each
  2078. #: entry in the table is a pair (handler, regexp). The first entry
  2079. #: with a matching regexp will have its handler called. Handlers
  2080. #: should have the following signature::
  2081. #:
  2082. #: def handler(s, position, reentrances, match): ...
  2083. #:
  2084. #: and should return a tuple (value, position), where position is
  2085. #: the string position where the value ended. (n.b.: order is
  2086. #: important here!)
  2087. VALUE_HANDLERS = [
  2088. ('read_fstruct_value', _START_FSTRUCT_RE),
  2089. ('read_var_value', re.compile(r'\?[a-zA-Z_][a-zA-Z0-9_]*')),
  2090. ('read_str_value', re.compile("[uU]?[rR]?(['\"])")),
  2091. ('read_int_value', re.compile(r'-?\d+')),
  2092. ('read_sym_value', re.compile(r'[a-zA-Z_][a-zA-Z0-9_]*')),
  2093. (
  2094. 'read_app_value',
  2095. re.compile(r'<(app)\((\?[a-z][a-z]*)\s*,' r'\s*(\?[a-z][a-z]*)\)>'),
  2096. ),
  2097. # ('read_logic_value', re.compile(r'<([^>]*)>')),
  2098. # lazily match any character after '<' until we hit a '>' not preceded by '-'
  2099. ('read_logic_value', re.compile(r'<(.*?)(?<!-)>')),
  2100. ('read_set_value', re.compile(r'{')),
  2101. ('read_tuple_value', re.compile(r'\(')),
  2102. ]
  2103. def read_fstruct_value(self, s, position, reentrances, match):
  2104. return self.read_partial(s, position, reentrances)
  2105. def read_str_value(self, s, position, reentrances, match):
  2106. return read_str(s, position)
  2107. def read_int_value(self, s, position, reentrances, match):
  2108. return int(match.group()), match.end()
  2109. # Note: the '?' is included in the variable name.
  2110. def read_var_value(self, s, position, reentrances, match):
  2111. return Variable(match.group()), match.end()
  2112. _SYM_CONSTS = {'None': None, 'True': True, 'False': False}
  2113. def read_sym_value(self, s, position, reentrances, match):
  2114. val, end = match.group(), match.end()
  2115. return self._SYM_CONSTS.get(val, val), end
  2116. def read_app_value(self, s, position, reentrances, match):
  2117. """Mainly included for backwards compat."""
  2118. return self._logic_parser.parse('%s(%s)' % match.group(2, 3)), match.end()
  2119. def read_logic_value(self, s, position, reentrances, match):
  2120. try:
  2121. try:
  2122. expr = self._logic_parser.parse(match.group(1))
  2123. except LogicalExpressionException:
  2124. raise ValueError()
  2125. return expr, match.end()
  2126. except ValueError:
  2127. raise ValueError('logic expression', match.start(1))
  2128. def read_tuple_value(self, s, position, reentrances, match):
  2129. return self._read_seq_value(
  2130. s, position, reentrances, match, ')', FeatureValueTuple, FeatureValueConcat
  2131. )
  2132. def read_set_value(self, s, position, reentrances, match):
  2133. return self._read_seq_value(
  2134. s, position, reentrances, match, '}', FeatureValueSet, FeatureValueUnion
  2135. )
  2136. def _read_seq_value(
  2137. self, s, position, reentrances, match, close_paren, seq_class, plus_class
  2138. ):
  2139. """
  2140. Helper function used by read_tuple_value and read_set_value.
  2141. """
  2142. cp = re.escape(close_paren)
  2143. position = match.end()
  2144. # Special syntax fo empty tuples:
  2145. m = re.compile(r'\s*/?\s*%s' % cp).match(s, position)
  2146. if m:
  2147. return seq_class(), m.end()
  2148. # Read values:
  2149. values = []
  2150. seen_plus = False
  2151. while True:
  2152. # Close paren: return value.
  2153. m = re.compile(r'\s*%s' % cp).match(s, position)
  2154. if m:
  2155. if seen_plus:
  2156. return plus_class(values), m.end()
  2157. else:
  2158. return seq_class(values), m.end()
  2159. # Read the next value.
  2160. val, position = self.read_value(s, position, reentrances)
  2161. values.append(val)
  2162. # Comma or looking at close paren
  2163. m = re.compile(r'\s*(,|\+|(?=%s))\s*' % cp).match(s, position)
  2164. if not m:
  2165. raise ValueError("',' or '+' or '%s'" % cp, position)
  2166. if m.group(1) == '+':
  2167. seen_plus = True
  2168. position = m.end()
  2169. ######################################################################
  2170. # { Demo
  2171. ######################################################################
  2172. def display_unification(fs1, fs2, indent=' '):
  2173. # Print the two input feature structures, side by side.
  2174. fs1_lines = ("%s" % fs1).split('\n')
  2175. fs2_lines = ("%s" % fs2).split('\n')
  2176. if len(fs1_lines) > len(fs2_lines):
  2177. blankline = '[' + ' ' * (len(fs2_lines[0]) - 2) + ']'
  2178. fs2_lines += [blankline] * len(fs1_lines)
  2179. else:
  2180. blankline = '[' + ' ' * (len(fs1_lines[0]) - 2) + ']'
  2181. fs1_lines += [blankline] * len(fs2_lines)
  2182. for (fs1_line, fs2_line) in zip(fs1_lines, fs2_lines):
  2183. print(indent + fs1_line + ' ' + fs2_line)
  2184. print(indent + '-' * len(fs1_lines[0]) + ' ' + '-' * len(fs2_lines[0]))
  2185. linelen = len(fs1_lines[0]) * 2 + 3
  2186. print(indent + '| |'.center(linelen))
  2187. print(indent + '+-----UNIFY-----+'.center(linelen))
  2188. print(indent + '|'.center(linelen))
  2189. print(indent + 'V'.center(linelen))
  2190. bindings = {}
  2191. result = fs1.unify(fs2, bindings)
  2192. if result is None:
  2193. print(indent + '(FAILED)'.center(linelen))
  2194. else:
  2195. print(
  2196. '\n'.join(indent + l.center(linelen) for l in ("%s" % result).split('\n'))
  2197. )
  2198. if bindings and len(bindings.bound_variables()) > 0:
  2199. print(repr(bindings).center(linelen))
  2200. return result
  2201. def interactive_demo(trace=False):
  2202. import random, sys
  2203. HELP = '''
  2204. 1-%d: Select the corresponding feature structure
  2205. q: Quit
  2206. t: Turn tracing on or off
  2207. l: List all feature structures
  2208. ?: Help
  2209. '''
  2210. print(
  2211. '''
  2212. This demo will repeatedly present you with a list of feature
  2213. structures, and ask you to choose two for unification. Whenever a
  2214. new feature structure is generated, it is added to the list of
  2215. choices that you can pick from. However, since this can be a
  2216. large number of feature structures, the demo will only print out a
  2217. random subset for you to choose between at a given time. If you
  2218. want to see the complete lists, type "l". For a list of valid
  2219. commands, type "?".
  2220. '''
  2221. )
  2222. print('Press "Enter" to continue...')
  2223. sys.stdin.readline()
  2224. fstruct_strings = [
  2225. '[agr=[number=sing, gender=masc]]',
  2226. '[agr=[gender=masc, person=3]]',
  2227. '[agr=[gender=fem, person=3]]',
  2228. '[subj=[agr=(1)[]], agr->(1)]',
  2229. '[obj=?x]',
  2230. '[subj=?x]',
  2231. '[/=None]',
  2232. '[/=NP]',
  2233. '[cat=NP]',
  2234. '[cat=VP]',
  2235. '[cat=PP]',
  2236. '[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]',
  2237. '[gender=masc, agr=?C]',
  2238. '[gender=?S, agr=[gender=?S,person=3]]',
  2239. ]
  2240. all_fstructs = [
  2241. (i, FeatStruct(fstruct_strings[i])) for i in range(len(fstruct_strings))
  2242. ]
  2243. def list_fstructs(fstructs):
  2244. for i, fstruct in fstructs:
  2245. print()
  2246. lines = ("%s" % fstruct).split('\n')
  2247. print('%3d: %s' % (i + 1, lines[0]))
  2248. for line in lines[1:]:
  2249. print(' ' + line)
  2250. print()
  2251. while True:
  2252. # Pick 5 feature structures at random from the master list.
  2253. MAX_CHOICES = 5
  2254. if len(all_fstructs) > MAX_CHOICES:
  2255. fstructs = sorted(random.sample(all_fstructs, MAX_CHOICES))
  2256. else:
  2257. fstructs = all_fstructs
  2258. print('_' * 75)
  2259. print('Choose two feature structures to unify:')
  2260. list_fstructs(fstructs)
  2261. selected = [None, None]
  2262. for (nth, i) in (('First', 0), ('Second', 1)):
  2263. while selected[i] is None:
  2264. print(
  2265. (
  2266. '%s feature structure (1-%d,q,t,l,?): '
  2267. % (nth, len(all_fstructs))
  2268. ),
  2269. end=' ',
  2270. )
  2271. try:
  2272. input = sys.stdin.readline().strip()
  2273. if input in ('q', 'Q', 'x', 'X'):
  2274. return
  2275. if input in ('t', 'T'):
  2276. trace = not trace
  2277. print(' Trace = %s' % trace)
  2278. continue
  2279. if input in ('h', 'H', '?'):
  2280. print(HELP % len(fstructs))
  2281. continue
  2282. if input in ('l', 'L'):
  2283. list_fstructs(all_fstructs)
  2284. continue
  2285. num = int(input) - 1
  2286. selected[i] = all_fstructs[num][1]
  2287. print()
  2288. except:
  2289. print('Bad sentence number')
  2290. continue
  2291. if trace:
  2292. result = selected[0].unify(selected[1], trace=1)
  2293. else:
  2294. result = display_unification(selected[0], selected[1])
  2295. if result is not None:
  2296. for i, fstruct in all_fstructs:
  2297. if repr(result) == repr(fstruct):
  2298. break
  2299. else:
  2300. all_fstructs.append((len(all_fstructs), result))
  2301. print('\nType "Enter" to continue unifying; or "q" to quit.')
  2302. input = sys.stdin.readline().strip()
  2303. if input in ('q', 'Q', 'x', 'X'):
  2304. return
  2305. def demo(trace=False):
  2306. """
  2307. Just for testing
  2308. """
  2309. # import random
  2310. # processor breaks with values like '3rd'
  2311. fstruct_strings = [
  2312. '[agr=[number=sing, gender=masc]]',
  2313. '[agr=[gender=masc, person=3]]',
  2314. '[agr=[gender=fem, person=3]]',
  2315. '[subj=[agr=(1)[]], agr->(1)]',
  2316. '[obj=?x]',
  2317. '[subj=?x]',
  2318. '[/=None]',
  2319. '[/=NP]',
  2320. '[cat=NP]',
  2321. '[cat=VP]',
  2322. '[cat=PP]',
  2323. '[subj=[agr=[gender=?y]], obj=[agr=[gender=?y]]]',
  2324. '[gender=masc, agr=?C]',
  2325. '[gender=?S, agr=[gender=?S,person=3]]',
  2326. ]
  2327. all_fstructs = [FeatStruct(fss) for fss in fstruct_strings]
  2328. # MAX_CHOICES = 5
  2329. # if len(all_fstructs) > MAX_CHOICES:
  2330. # fstructs = random.sample(all_fstructs, MAX_CHOICES)
  2331. # fstructs.sort()
  2332. # else:
  2333. # fstructs = all_fstructs
  2334. for fs1 in all_fstructs:
  2335. for fs2 in all_fstructs:
  2336. print(
  2337. "\n*******************\nfs1 is:\n%s\n\nfs2 is:\n%s\n\nresult is:\n%s"
  2338. % (fs1, fs2, unify(fs1, fs2))
  2339. )
  2340. if __name__ == '__main__':
  2341. demo()
  2342. __all__ = [
  2343. 'FeatStruct',
  2344. 'FeatDict',
  2345. 'FeatList',
  2346. 'unify',
  2347. 'subsumes',
  2348. 'conflicts',
  2349. 'Feature',
  2350. 'SlashFeature',
  2351. 'RangeFeature',
  2352. 'SLASH',
  2353. 'TYPE',
  2354. 'FeatStructReader',
  2355. ]