Grammalecte  Hex Artifact Content

Artifact 11706e17f59b866a8064df5fe5fdb71cd29ee18d07cce4f8d6a01cbb98c7ed6e:


0000: 23 21 70 79 74 68 6f 6e 33 0a 0a 22 22 22 0a 52  #!python3..""".R
0010: 55 4c 45 20 47 52 41 50 48 20 42 55 49 4c 44 45  ULE GRAPH BUILDE
0020: 52 0a 22 22 22 0a 0a 23 20 62 79 20 4f 6c 69 76  R."""..# by Oliv
0030: 69 65 72 20 52 2e 0a 23 20 4c 69 63 65 6e 73 65  ier R..# License
0040: 3a 20 4d 50 4c 20 32 0a 0a 69 6d 70 6f 72 74 20  : MPL 2..import 
0050: 72 65 0a 69 6d 70 6f 72 74 20 74 72 61 63 65 62  re.import traceb
0060: 61 63 6b 0a 0a 0a 0a 63 6c 61 73 73 20 44 41 52  ack....class DAR
0070: 47 3a 0a 20 20 20 20 22 22 22 44 49 52 45 43 54  G:.    """DIRECT
0080: 20 41 43 59 43 4c 49 43 20 52 55 4c 45 20 47 52   ACYCLIC RULE GR
0090: 41 50 48 22 22 22 0a 20 20 20 20 23 20 54 68 69  APH""".    # Thi
00a0: 73 20 63 6f 64 65 20 69 73 20 69 6e 73 70 69 72  s code is inspir
00b0: 65 64 20 66 72 6f 6d 20 53 74 65 76 65 20 48 61  ed from Steve Ha
00c0: 6e 6f 76 e2 80 99 73 20 44 41 57 47 2c 20 32 30  nov...s DAWG, 20
00d0: 31 31 2e 20 28 68 74 74 70 3a 2f 2f 73 74 65 76  11. (http://stev
00e0: 65 68 61 6e 6f 76 2e 63 61 2f 62 6c 6f 67 2f 69  ehanov.ca/blog/i
00f0: 6e 64 65 78 2e 70 68 70 3f 69 64 3d 31 31 35 29  ndex.php?id=115)
0100: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69 6e 69 74  ..    def __init
0110: 5f 5f 20 28 73 65 6c 66 2c 20 6c 52 75 6c 65 2c  __ (self, lRule,
0120: 20 73 4c 61 6e 67 43 6f 64 65 29 3a 0a 20 20 20   sLangCode):.   
0130: 20 20 20 20 20 70 72 69 6e 74 28 22 20 3e 20 44       print(" > D
0140: 69 72 65 63 74 20 41 63 79 63 6c 69 63 20 52 75  irect Acyclic Ru
0150: 6c 65 20 47 72 61 70 68 20 28 44 41 52 47 29 22  le Graph (DARG)"
0160: 2c 20 65 6e 64 3d 22 20 22 29 0a 0a 20 20 20 20  , end=" ")..    
0170: 20 20 20 20 23 20 50 72 65 70 61 72 69 6e 67 20      # Preparing 
0180: 44 41 52 47 0a 20 20 20 20 20 20 20 20 73 65 6c  DARG.        sel
0190: 66 2e 73 4c 61 6e 67 43 6f 64 65 20 3d 20 73 4c  f.sLangCode = sL
01a0: 61 6e 67 43 6f 64 65 0a 20 20 20 20 20 20 20 20  angCode.        
01b0: 73 65 6c 66 2e 6e 52 75 6c 65 20 3d 20 6c 65 6e  self.nRule = len
01c0: 28 6c 52 75 6c 65 29 0a 20 20 20 20 20 20 20 20  (lRule).        
01d0: 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75  self.aPreviousRu
01e0: 6c 65 20 3d 20 5b 5d 0a 20 20 20 20 20 20 20 20  le = [].        
01f0: 4e 6f 64 65 2e 72 65 73 65 74 4e 65 78 74 49 64  Node.resetNextId
0200: 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  ().        self.
0210: 6f 52 6f 6f 74 20 3d 20 4e 6f 64 65 28 29 0a 20  oRoot = Node(). 
0220: 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e 63         self.lUnc
0230: 68 65 63 6b 65 64 4e 6f 64 65 73 20 3d 20 5b 5d  heckedNodes = []
0240: 20 20 23 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65    # list of node
0250: 73 20 74 68 61 74 20 68 61 76 65 20 6e 6f 74 20  s that have not 
0260: 62 65 65 6e 20 63 68 65 63 6b 65 64 20 66 6f 72  been checked for
0270: 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e 0a 20 20   duplication..  
0280: 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d 69 6e 69        self.lMini
0290: 6d 69 7a 65 64 4e 6f 64 65 73 20 3d 20 7b 7d 20  mizedNodes = {} 
02a0: 20 23 20 6c 69 73 74 20 6f 66 20 75 6e 69 71 75   # list of uniqu
02b0: 65 20 6e 6f 64 65 73 20 74 68 61 74 20 68 61 76  e nodes that hav
02c0: 65 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20 66  e been checked f
02d0: 6f 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e 0a  or duplication..
02e0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 4e 6f          self.nNo
02f0: 64 65 20 3d 20 30 0a 20 20 20 20 20 20 20 20 73  de = 0.        s
0300: 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a 0a 20 20  elf.nArc = 0..  
0310: 20 20 20 20 20 20 23 20 62 75 69 6c 64 0a 20 20        # build.  
0320: 20 20 20 20 20 20 6c 52 75 6c 65 2e 73 6f 72 74        lRule.sort
0330: 28 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20 61  ().        for a
0340: 52 75 6c 65 20 69 6e 20 6c 52 75 6c 65 3a 0a 20  Rule in lRule:. 
0350: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
0360: 69 6e 73 65 72 74 28 61 52 75 6c 65 29 0a 20 20  insert(aRule).  
0370: 20 20 20 20 20 20 73 65 6c 66 2e 66 69 6e 69 73        self.finis
0380: 68 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66  h().        self
0390: 2e 63 6f 75 6e 74 4e 6f 64 65 73 28 29 0a 20 20  .countNodes().  
03a0: 20 20 20 20 20 20 73 65 6c 66 2e 63 6f 75 6e 74        self.count
03b0: 41 72 63 73 28 29 0a 20 20 20 20 20 20 20 20 73  Arcs().        s
03c0: 65 6c 66 2e 64 69 73 70 6c 61 79 49 6e 66 6f 28  elf.displayInfo(
03d0: 29 0a 0a 20 20 20 20 23 20 42 55 49 4c 44 20 44  )..    # BUILD D
03e0: 41 52 47 0a 20 20 20 20 64 65 66 20 69 6e 73 65  ARG.    def inse
03f0: 72 74 20 28 73 65 6c 66 2c 20 61 52 75 6c 65 29  rt (self, aRule)
0400: 3a 0a 20 20 20 20 20 20 20 20 22 69 6e 73 65 72  :.        "inser
0410: 74 20 61 20 6e 65 77 20 72 75 6c 65 20 28 74 6f  t a new rule (to
0420: 6b 65 6e 73 20 6d 75 73 74 20 62 65 20 69 6e 73  kens must be ins
0430: 65 72 74 65 64 20 69 6e 20 6f 72 64 65 72 29 22  erted in order)"
0440: 0a 20 20 20 20 20 20 20 20 69 66 20 61 52 75 6c  .        if aRul
0450: 65 20 3c 20 73 65 6c 66 2e 61 50 72 65 76 69 6f  e < self.aPrevio
0460: 75 73 52 75 6c 65 3a 0a 20 20 20 20 20 20 20 20  usRule:.        
0470: 20 20 20 20 65 78 69 74 28 22 23 20 45 72 72 6f      exit("# Erro
0480: 72 3a 20 74 6f 6b 65 6e 73 20 6d 75 73 74 20 62  r: tokens must b
0490: 65 20 69 6e 73 65 72 74 65 64 20 69 6e 20 6f 72  e inserted in or
04a0: 64 65 72 2e 22 29 0a 0a 20 20 20 20 20 20 20 20  der.")..        
04b0: 23 20 66 69 6e 64 20 63 6f 6d 6d 6f 6e 20 70 72  # find common pr
04c0: 65 66 69 78 20 62 65 74 77 65 65 6e 20 77 6f 72  efix between wor
04d0: 64 20 61 6e 64 20 70 72 65 76 69 6f 75 73 20 77  d and previous w
04e0: 6f 72 64 0a 20 20 20 20 20 20 20 20 6e 43 6f 6d  ord.        nCom
04f0: 6d 6f 6e 50 72 65 66 69 78 20 3d 20 30 0a 20 20  monPrefix = 0.  
0500: 20 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20 72        for i in r
0510: 61 6e 67 65 28 6d 69 6e 28 6c 65 6e 28 61 52 75  ange(min(len(aRu
0520: 6c 65 29 2c 20 6c 65 6e 28 73 65 6c 66 2e 61 50  le), len(self.aP
0530: 72 65 76 69 6f 75 73 52 75 6c 65 29 29 29 3a 0a  reviousRule))):.
0540: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 61              if a
0550: 52 75 6c 65 5b 69 5d 20 21 3d 20 73 65 6c 66 2e  Rule[i] != self.
0560: 61 50 72 65 76 69 6f 75 73 52 75 6c 65 5b 69 5d  aPreviousRule[i]
0570: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
0580: 20 20 62 72 65 61 6b 0a 20 20 20 20 20 20 20 20    break.        
0590: 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69      nCommonPrefi
05a0: 78 20 2b 3d 20 31 0a 0a 20 20 20 20 20 20 20 20  x += 1..        
05b0: 23 20 43 68 65 63 6b 20 74 68 65 20 6c 55 6e 63  # Check the lUnc
05c0: 68 65 63 6b 65 64 4e 6f 64 65 73 20 66 6f 72 20  heckedNodes for 
05d0: 72 65 64 75 6e 64 61 6e 74 20 6e 6f 64 65 73 2c  redundant nodes,
05e0: 20 70 72 6f 63 65 65 64 69 6e 67 20 66 72 6f 6d   proceeding from
05f0: 20 6c 61 73 74 0a 20 20 20 20 20 20 20 20 23 20   last.        # 
0600: 6f 6e 65 20 64 6f 77 6e 20 74 6f 20 74 68 65 20  one down to the 
0610: 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78 20 73 69  common prefix si
0620: 7a 65 2e 20 54 68 65 6e 20 74 72 75 6e 63 61 74  ze. Then truncat
0630: 65 20 74 68 65 20 6c 69 73 74 20 61 74 20 74 68  e the list at th
0640: 61 74 20 70 6f 69 6e 74 2e 0a 20 20 20 20 20 20  at point..      
0650: 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a 65    self._minimize
0660: 28 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 29 0a  (nCommonPrefix).
0670: 0a 20 20 20 20 20 20 20 20 23 20 61 64 64 20 74  .        # add t
0680: 68 65 20 73 75 66 66 69 78 2c 20 73 74 61 72 74  he suffix, start
0690: 69 6e 67 20 66 72 6f 6d 20 74 68 65 20 63 6f 72  ing from the cor
06a0: 72 65 63 74 20 6e 6f 64 65 20 6d 69 64 2d 77 61  rect node mid-wa
06b0: 79 20 74 68 72 6f 75 67 68 20 74 68 65 20 67 72  y through the gr
06c0: 61 70 68 0a 20 20 20 20 20 20 20 20 69 66 20 6c  aph.        if l
06d0: 65 6e 28 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b  en(self.lUncheck
06e0: 65 64 4e 6f 64 65 73 29 20 3d 3d 20 30 3a 0a 20  edNodes) == 0:. 
06f0: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
0700: 20 3d 20 73 65 6c 66 2e 6f 52 6f 6f 74 0a 20 20   = self.oRoot.  
0710: 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20        else:.    
0720: 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20          oNode = 
0730: 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e  self.lUncheckedN
0740: 6f 64 65 73 5b 2d 31 5d 5b 32 5d 0a 0a 20 20 20  odes[-1][2]..   
0750: 20 20 20 20 20 69 54 6f 6b 65 6e 20 3d 20 6e 43       iToken = nC
0760: 6f 6d 6d 6f 6e 50 72 65 66 69 78 0a 20 20 20 20  ommonPrefix.    
0770: 20 20 20 20 66 6f 72 20 73 54 6f 6b 65 6e 20 69      for sToken i
0780: 6e 20 61 52 75 6c 65 5b 6e 43 6f 6d 6d 6f 6e 50  n aRule[nCommonP
0790: 72 65 66 69 78 3a 5d 3a 0a 20 20 20 20 20 20 20  refix:]:.       
07a0: 20 20 20 20 20 6f 4e 65 78 74 4e 6f 64 65 20 3d       oNextNode =
07b0: 20 4e 6f 64 65 28 29 0a 20 20 20 20 20 20 20 20   Node().        
07c0: 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72 63 73 5b      oNode.dArcs[
07d0: 73 54 6f 6b 65 6e 5d 20 3d 20 6f 4e 65 78 74 4e  sToken] = oNextN
07e0: 6f 64 65 0a 20 20 20 20 20 20 20 20 20 20 20 20  ode.            
07f0: 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e  self.lUncheckedN
0800: 6f 64 65 73 2e 61 70 70 65 6e 64 28 28 6f 4e 6f  odes.append((oNo
0810: 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f 4e 65 78  de, sToken, oNex
0820: 74 4e 6f 64 65 29 29 0a 20 20 20 20 20 20 20 20  tNode)).        
0830: 20 20 20 20 69 66 20 69 54 6f 6b 65 6e 20 3d 3d      if iToken ==
0840: 20 28 6c 65 6e 28 61 52 75 6c 65 29 20 2d 20 32   (len(aRule) - 2
0850: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ):.             
0860: 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e 61 6c 20     oNode.bFinal 
0870: 3d 20 54 72 75 65 0a 20 20 20 20 20 20 20 20 20  = True.         
0880: 20 20 20 69 54 6f 6b 65 6e 20 2b 3d 20 31 0a 20     iToken += 1. 
0890: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
08a0: 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a 20 20 20   = oNextNode.   
08b0: 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e 61       oNode.bFina
08c0: 6c 20 3d 20 54 72 75 65 0a 20 20 20 20 20 20 20  l = True.       
08d0: 20 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52   self.aPreviousR
08e0: 75 6c 65 20 3d 20 61 52 75 6c 65 0a 0a 20 20 20  ule = aRule..   
08f0: 20 64 65 66 20 66 69 6e 69 73 68 20 28 73 65 6c   def finish (sel
0900: 66 29 3a 0a 20 20 20 20 20 20 20 20 22 6d 69 6e  f):.        "min
0910: 69 6d 69 7a 65 20 75 6e 63 68 65 63 6b 65 64 20  imize unchecked 
0920: 6e 6f 64 65 73 22 0a 20 20 20 20 20 20 20 20 73  nodes".        s
0930: 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a 65 28 30 29  elf._minimize(0)
0940: 0a 0a 20 20 20 20 64 65 66 20 5f 6d 69 6e 69 6d  ..    def _minim
0950: 69 7a 65 20 28 73 65 6c 66 2c 20 64 6f 77 6e 54  ize (self, downT
0960: 6f 29 3a 0a 20 20 20 20 20 20 20 20 23 20 70 72  o):.        # pr
0970: 6f 63 65 65 64 20 66 72 6f 6d 20 74 68 65 20 6c  oceed from the l
0980: 65 61 66 20 75 70 20 74 6f 20 61 20 63 65 72 74  eaf up to a cert
0990: 61 69 6e 20 70 6f 69 6e 74 0a 20 20 20 20 20 20  ain point.      
09a0: 20 20 66 6f 72 20 69 20 69 6e 20 72 61 6e 67 65    for i in range
09b0: 28 20 6c 65 6e 28 73 65 6c 66 2e 6c 55 6e 63 68  ( len(self.lUnch
09c0: 65 63 6b 65 64 4e 6f 64 65 73 29 2d 31 2c 20 64  eckedNodes)-1, d
09d0: 6f 77 6e 54 6f 2d 31 2c 20 2d 31 20 29 3a 0a 20  ownTo-1, -1 ):. 
09e0: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
09f0: 2c 20 73 54 6f 6b 65 6e 2c 20 6f 43 68 69 6c 64  , sToken, oChild
0a00: 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6c 55 6e 63  Node = self.lUnc
0a10: 68 65 63 6b 65 64 4e 6f 64 65 73 5b 69 5d 0a 20  heckedNodes[i]. 
0a20: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 6f 43             if oC
0a30: 68 69 6c 64 4e 6f 64 65 20 69 6e 20 73 65 6c 66  hildNode in self
0a40: 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73  .lMinimizedNodes
0a50: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
0a60: 20 20 23 20 72 65 70 6c 61 63 65 20 74 68 65 20    # replace the 
0a70: 63 68 69 6c 64 20 77 69 74 68 20 74 68 65 20 70  child with the p
0a80: 72 65 76 69 6f 75 73 6c 79 20 65 6e 63 6f 75 6e  reviously encoun
0a90: 74 65 72 65 64 20 6f 6e 65 0a 20 20 20 20 20 20  tered one.      
0aa0: 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e            oNode.
0ab0: 64 41 72 63 73 5b 73 54 6f 6b 65 6e 5d 20 3d 20  dArcs[sToken] = 
0ac0: 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e  self.lMinimizedN
0ad0: 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f 64 65 5d  odes[oChildNode]
0ae0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73  .            els
0af0: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  e:.             
0b00: 20 20 20 23 20 61 64 64 20 74 68 65 20 73 74 61     # add the sta
0b10: 74 65 20 74 6f 20 74 68 65 20 6d 69 6e 69 6d 69  te to the minimi
0b20: 7a 65 64 20 6e 6f 64 65 73 2e 0a 20 20 20 20 20  zed nodes..     
0b30: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
0b40: 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 5b  lMinimizedNodes[
0b50: 6f 43 68 69 6c 64 4e 6f 64 65 5d 20 3d 20 6f 43  oChildNode] = oC
0b60: 68 69 6c 64 4e 6f 64 65 0a 20 20 20 20 20 20 20  hildNode.       
0b70: 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65       self.lUnche
0b80: 63 6b 65 64 4e 6f 64 65 73 2e 70 6f 70 28 29 0a  ckedNodes.pop().
0b90: 0a 20 20 20 20 64 65 66 20 63 6f 75 6e 74 4e 6f  .    def countNo
0ba0: 64 65 73 20 28 73 65 6c 66 29 3a 0a 20 20 20 20  des (self):.    
0bb0: 20 20 20 20 22 63 6f 75 6e 74 20 6e 6f 64 65 73      "count nodes
0bc0: 20 77 69 74 68 69 6e 20 74 68 65 20 77 68 6f 6c   within the whol
0bd0: 65 20 67 72 61 70 68 22 0a 20 20 20 20 20 20 20  e graph".       
0be0: 20 73 65 6c 66 2e 6e 4e 6f 64 65 20 3d 20 6c 65   self.nNode = le
0bf0: 6e 28 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65  n(self.lMinimize
0c00: 64 4e 6f 64 65 73 29 0a 0a 20 20 20 20 64 65 66  dNodes)..    def
0c10: 20 63 6f 75 6e 74 41 72 63 73 20 28 73 65 6c 66   countArcs (self
0c20: 29 3a 0a 20 20 20 20 20 20 20 20 22 63 6f 75 6e  ):.        "coun
0c30: 74 20 61 72 63 73 20 77 69 74 68 69 6e 20 74 68  t arcs within th
0c40: 65 20 77 68 6f 6c 65 20 67 72 61 70 68 22 0a 20  e whole graph". 
0c50: 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 41 72 63         self.nArc
0c60: 20 3d 20 30 0a 20 20 20 20 20 20 20 20 66 6f 72   = 0.        for
0c70: 20 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c   oNode in self.l
0c80: 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a  MinimizedNodes:.
0c90: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
0ca0: 2e 6e 41 72 63 20 2b 3d 20 6c 65 6e 28 6f 4e 6f  .nArc += len(oNo
0cb0: 64 65 2e 64 41 72 63 73 29 0a 0a 20 20 20 20 64  de.dArcs)..    d
0cc0: 65 66 20 64 69 73 70 6c 61 79 49 6e 66 6f 20 28  ef displayInfo (
0cd0: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
0ce0: 64 69 73 70 6c 61 79 20 69 6e 66 6f 72 6d 61 74  display informat
0cf0: 69 6f 6e 73 20 61 62 6f 75 74 20 74 68 65 20 72  ions about the r
0d00: 75 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20 20  ule graph".     
0d10: 20 20 20 70 72 69 6e 74 28 22 3a 20 7b 3a 3e 31     print(": {:>1
0d20: 30 2c 7d 20 72 75 6c 65 73 2c 20 20 7b 3a 3e 31  0,} rules,  {:>1
0d30: 30 2c 7d 20 6e 6f 64 65 73 2c 20 20 7b 3a 3e 31  0,} nodes,  {:>1
0d40: 30 2c 7d 20 61 72 63 73 22 2e 66 6f 72 6d 61 74  0,} arcs".format
0d50: 28 73 65 6c 66 2e 6e 52 75 6c 65 2c 20 73 65 6c  (self.nRule, sel
0d60: 66 2e 6e 4e 6f 64 65 2c 20 73 65 6c 66 2e 6e 41  f.nNode, self.nA
0d70: 72 63 29 29 0a 0a 20 20 20 20 64 65 66 20 63 72  rc))..    def cr
0d80: 65 61 74 65 47 72 61 70 68 20 28 73 65 6c 66 29  eateGraph (self)
0d90: 3a 0a 20 20 20 20 20 20 20 20 22 63 72 65 61 74  :.        "creat
0da0: 65 20 74 68 65 20 67 72 61 70 68 20 61 73 20 61  e the graph as a
0db0: 20 64 69 63 74 69 6f 6e 61 72 79 22 0a 20 20 20   dictionary".   
0dc0: 20 20 20 20 20 64 47 72 61 70 68 20 3d 20 7b 20       dGraph = { 
0dd0: 30 3a 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e 67 65  0: self.oRoot.ge
0de0: 74 4e 6f 64 65 41 73 44 69 63 74 28 29 20 7d 0a  tNodeAsDict() }.
0df0: 20 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f 64          for oNod
0e00: 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d  e in self.lMinim
0e10: 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20  izedNodes:.     
0e20: 20 20 20 20 20 20 20 73 48 61 73 68 49 64 20 3d         sHashId =
0e30: 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28   oNode.__hash__(
0e40: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  ).            if
0e50: 20 73 48 61 73 68 49 64 20 6e 6f 74 20 69 6e 20   sHashId not in 
0e60: 64 47 72 61 70 68 3a 0a 20 20 20 20 20 20 20 20  dGraph:.        
0e70: 20 20 20 20 20 20 20 20 64 47 72 61 70 68 5b 73          dGraph[s
0e80: 48 61 73 68 49 64 5d 20 3d 20 6f 4e 6f 64 65 2e  HashId] = oNode.
0e90: 67 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29 0a  getNodeAsDict().
0ea0: 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65              else
0eb0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
0ec0: 20 20 70 72 69 6e 74 28 22 45 72 72 6f 72 2e 20    print("Error. 
0ed0: 44 6f 75 62 6c 65 20 6e 6f 64 65 e2 80 a6 20 73  Double node... s
0ee0: 61 6d 65 20 69 64 3a 20 22 2c 20 73 48 61 73 68  ame id: ", sHash
0ef0: 49 64 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  Id).            
0f00: 20 20 20 20 70 72 69 6e 74 28 73 74 72 28 6f 4e      print(str(oN
0f10: 6f 64 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63  ode.getNodeAsDic
0f20: 74 28 29 29 29 0a 20 20 20 20 20 20 20 20 64 47  t())).        dG
0f30: 72 61 70 68 20 3d 20 73 65 6c 66 2e 5f 72 65 77  raph = self._rew
0f40: 72 69 74 65 4b 65 79 73 4f 66 44 41 52 47 28 64  riteKeysOfDARG(d
0f50: 47 72 61 70 68 29 0a 20 20 20 20 20 20 20 20 73  Graph).        s
0f60: 65 6c 66 2e 5f 63 68 65 63 6b 52 65 67 65 78 65  elf._checkRegexe
0f70: 73 28 64 47 72 61 70 68 29 0a 20 20 20 20 20 20  s(dGraph).      
0f80: 20 20 72 65 74 75 72 6e 20 64 47 72 61 70 68 0a    return dGraph.
0f90: 0a 20 20 20 20 64 65 66 20 5f 72 65 77 72 69 74  .    def _rewrit
0fa0: 65 4b 65 79 73 4f 66 44 41 52 47 20 28 73 65 6c  eKeysOfDARG (sel
0fb0: 66 2c 20 64 47 72 61 70 68 29 3a 0a 20 20 20 20  f, dGraph):.    
0fc0: 20 20 20 20 22 6b 65 79 73 20 6f 66 20 44 41 52      "keys of DAR
0fd0: 47 20 61 72 65 20 6c 6f 6e 67 20 6e 75 6d 62 65  G are long numbe
0fe0: 72 73 20 28 68 61 73 68 65 73 29 3a 20 74 68 69  rs (hashes): thi
0ff0: 73 20 66 75 6e 63 74 69 6f 6e 20 72 65 70 6c 61  s function repla
1000: 63 65 20 74 68 65 73 65 20 68 61 73 68 65 73 20  ce these hashes 
1010: 77 69 74 68 20 73 6d 61 6c 6c 65 72 20 6e 75 6d  with smaller num
1020: 62 65 72 73 20 28 74 6f 20 72 65 64 75 63 65 20  bers (to reduce 
1030: 73 74 6f 72 69 6e 67 20 73 69 7a 65 29 22 0a 20  storing size)". 
1040: 20 20 20 20 20 20 20 23 20 63 72 65 61 74 65 20         # create 
1050: 74 72 61 6e 73 6c 61 74 69 6f 6e 20 64 69 63 74  translation dict
1060: 69 6f 6e 61 72 79 0a 20 20 20 20 20 20 20 20 64  ionary.        d
1070: 4b 65 79 54 72 61 6e 73 20 3d 20 7b 7d 0a 20 20  KeyTrans = {}.  
1080: 20 20 20 20 20 20 66 6f 72 20 69 2c 20 6e 4b 65        for i, nKe
1090: 79 20 69 6e 20 65 6e 75 6d 65 72 61 74 65 28 64  y in enumerate(d
10a0: 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20  Graph):.        
10b0: 20 20 20 20 64 4b 65 79 54 72 61 6e 73 5b 6e 4b      dKeyTrans[nK
10c0: 65 79 5d 20 3d 20 69 0a 20 20 20 20 20 20 20 20  ey] = i.        
10d0: 23 20 72 65 70 6c 61 63 65 20 6b 65 79 73 0a 20  # replace keys. 
10e0: 20 20 20 20 20 20 20 64 4e 65 77 47 72 61 70 68         dNewGraph
10f0: 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 66 6f   = {}.        fo
1100: 72 20 6e 4b 65 79 2c 20 64 56 61 6c 20 69 6e 20  r nKey, dVal in 
1110: 64 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a 0a  dGraph.items():.
1120: 20 20 20 20 20 20 20 20 20 20 20 20 64 4e 65 77              dNew
1130: 47 72 61 70 68 5b 64 4b 65 79 54 72 61 6e 73 5b  Graph[dKeyTrans[
1140: 6e 4b 65 79 5d 5d 20 3d 20 64 56 61 6c 0a 20 20  nKey]] = dVal.  
1150: 20 20 20 20 20 20 66 6f 72 20 6e 4b 65 79 2c 20        for nKey, 
1160: 64 56 61 6c 20 69 6e 20 64 47 72 61 70 68 2e 69  dVal in dGraph.i
1170: 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20  tems():.        
1180: 20 20 20 20 66 6f 72 20 73 41 72 63 2c 20 76 61      for sArc, va
1190: 6c 20 69 6e 20 64 56 61 6c 2e 69 74 65 6d 73 28  l in dVal.items(
11a0: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ):.             
11b0: 20 20 20 69 66 20 74 79 70 65 28 76 61 6c 29 20     if type(val) 
11c0: 69 73 20 69 6e 74 3a 0a 20 20 20 20 20 20 20 20  is int:.        
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 64 56 61 6c              dVal
11e0: 5b 73 41 72 63 5d 20 3d 20 64 4b 65 79 54 72 61  [sArc] = dKeyTra
11f0: 6e 73 5b 76 61 6c 5d 0a 20 20 20 20 20 20 20 20  ns[val].        
1200: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
1210: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1220: 20 20 66 6f 72 20 73 41 72 63 2c 20 6e 4b 65 79    for sArc, nKey
1230: 20 69 6e 20 76 61 6c 2e 69 74 65 6d 73 28 29 3a   in val.items():
1240: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1250: 20 20 20 20 20 20 20 20 20 76 61 6c 5b 73 41 72           val[sAr
1260: 63 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b 6e  c] = dKeyTrans[n
1270: 4b 65 79 5d 0a 20 20 20 20 20 20 20 20 72 65 74  Key].        ret
1280: 75 72 6e 20 64 4e 65 77 47 72 61 70 68 0a 0a 20  urn dNewGraph.. 
1290: 20 20 20 64 65 66 20 5f 63 68 65 63 6b 52 65 67     def _checkReg
12a0: 65 78 65 73 20 28 73 65 6c 66 2c 20 64 47 72 61  exes (self, dGra
12b0: 70 68 29 3a 0a 20 20 20 20 20 20 20 20 22 63 68  ph):.        "ch
12c0: 65 63 6b 20 76 61 6c 69 64 69 74 79 20 6f 66 20  eck validity of 
12d0: 72 65 67 65 78 65 73 22 0a 20 20 20 20 20 20 20  regexes".       
12e0: 20 61 52 65 67 65 78 20 3d 20 73 65 74 28 29 0a   aRegex = set().
12f0: 20 20 20 20 20 20 20 20 66 6f 72 20 6e 4b 65 79          for nKey
1300: 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61 70 68  , dVal in dGraph
1310: 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20  .items():.      
1320: 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f 76 61        if "<re_va
1330: 6c 75 65 3e 22 20 69 6e 20 64 56 61 6c 3a 0a 20  lue>" in dVal:. 
1340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
1350: 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64 56 61  or sRegex in dVa
1360: 6c 5b 22 3c 72 65 5f 76 61 6c 75 65 3e 22 5d 3a  l["<re_value>"]:
1370: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1380: 20 20 20 20 20 69 66 20 73 52 65 67 65 78 20 6e       if sRegex n
1390: 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a 20 20  ot in aRegex:.  
13a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13b0: 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68 65 63        self._chec
13c0: 6b 52 65 67 65 78 28 73 52 65 67 65 78 29 0a 20  kRegex(sRegex). 
13d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
13e0: 20 20 20 20 20 20 20 61 52 65 67 65 78 2e 61 64         aRegex.ad
13f0: 64 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  d(sRegex).      
1400: 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f 6d 6f        if "<re_mo
1410: 72 70 68 3e 22 20 69 6e 20 64 56 61 6c 3a 0a 20  rph>" in dVal:. 
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
1430: 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64 56 61  or sRegex in dVa
1440: 6c 5b 22 3c 72 65 5f 6d 6f 72 70 68 3e 22 5d 3a  l["<re_morph>"]:
1450: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1460: 20 20 20 20 20 69 66 20 73 52 65 67 65 78 20 6e       if sRegex n
1470: 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a 20 20  ot in aRegex:.  
1480: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1490: 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68 65 63        self._chec
14a0: 6b 52 65 67 65 78 28 73 52 65 67 65 78 29 0a 20  kRegex(sRegex). 
14b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
14c0: 20 20 20 20 20 20 20 61 52 65 67 65 78 2e 61 64         aRegex.ad
14d0: 64 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  d(sRegex).      
14e0: 20 20 61 52 65 67 65 78 2e 63 6c 65 61 72 28 29    aRegex.clear()
14f0: 0a 0a 20 20 20 20 64 65 66 20 5f 63 68 65 63 6b  ..    def _check
1500: 52 65 67 65 78 20 28 73 65 6c 66 2c 20 73 52 65  Regex (self, sRe
1510: 67 65 78 29 3a 0a 20 20 20 20 20 20 20 20 23 70  gex):.        #p
1520: 72 69 6e 74 28 73 52 65 67 65 78 29 0a 20 20 20  rint(sRegex).   
1530: 20 20 20 20 20 69 66 20 22 c2 ac 22 20 69 6e 20       if ".." in 
1540: 73 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20 20  sRegex:.        
1550: 20 20 20 20 73 50 61 74 74 65 72 6e 2c 20 73 4e      sPattern, sN
1560: 65 67 50 61 74 74 65 72 6e 20 3d 20 73 52 65 67  egPattern = sReg
1570: 65 78 2e 73 70 6c 69 74 28 22 c2 ac 22 29 0a 20  ex.split(".."). 
1580: 20 20 20 20 20 20 20 20 20 20 20 74 72 79 3a 0a             try:.
1590: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15a0: 69 66 20 6e 6f 74 20 73 4e 65 67 50 61 74 74 65  if not sNegPatte
15b0: 72 6e 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  rn:.            
15c0: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 23          print("#
15d0: 20 57 61 72 6e 69 6e 67 21 20 45 6d 70 74 79 20   Warning! Empty 
15e0: 6e 65 67 70 61 74 74 65 72 6e 3a 22 2c 20 73 52  negpattern:", sR
15f0: 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20 20  egex).          
1600: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
1610: 28 73 50 61 74 74 65 72 6e 29 0a 20 20 20 20 20  (sPattern).     
1620: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 73 4e             if sN
1630: 65 67 50 61 74 74 65 72 6e 20 21 3d 20 22 2a 22  egPattern != "*"
1640: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1650: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
1660: 28 73 4e 65 67 50 61 74 74 65 72 6e 29 0a 20 20  (sNegPattern).  
1670: 20 20 20 20 20 20 20 20 20 20 65 78 63 65 70 74            except
1680: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1690: 20 20 70 72 69 6e 74 28 22 23 20 45 72 72 6f 72    print("# Error
16a0: 2e 20 57 72 6f 6e 67 20 72 65 67 65 78 3a 22 2c  . Wrong regex:",
16b0: 20 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20   sRegex).       
16c0: 20 20 20 20 20 20 20 20 20 65 78 69 74 28 29 0a           exit().
16d0: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
16e0: 20 20 20 20 20 20 20 20 20 20 74 72 79 3a 0a 20            try:. 
16f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69                 i
1700: 66 20 6e 6f 74 20 73 52 65 67 65 78 3a 0a 20 20  f not sRegex:.  
1710: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1720: 20 20 70 72 69 6e 74 28 22 23 20 57 61 72 6e 69    print("# Warni
1730: 6e 67 21 20 45 6d 70 74 79 20 70 61 74 74 65 72  ng! Empty patter
1740: 6e 3a 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20  n:", sRegex).   
1750: 20 20 20 20 20 20 20 20 20 20 20 20 20 72 65 2e               re.
1760: 63 6f 6d 70 69 6c 65 28 73 52 65 67 65 78 29 0a  compile(sRegex).
1770: 20 20 20 20 20 20 20 20 20 20 20 20 65 78 63 65              exce
1780: 70 74 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  pt:.            
1790: 20 20 20 20 70 72 69 6e 74 28 22 23 20 45 72 72      print("# Err
17a0: 6f 72 2e 20 57 72 6f 6e 67 20 72 65 67 65 78 3a  or. Wrong regex:
17b0: 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20 20 20  ", sRegex).     
17c0: 20 20 20 20 20 20 20 20 20 20 20 65 78 69 74 28             exit(
17d0: 29 0a 0a 0a 63 6c 61 73 73 20 4e 6f 64 65 3a 0a  )...class Node:.
17e0: 20 20 20 20 22 22 22 4e 6f 64 65 20 6f 66 20 74      """Node of t
17f0: 68 65 20 72 75 6c 65 20 67 72 61 70 68 22 22 22  he rule graph"""
1800: 0a 0a 20 20 20 20 4e 65 78 74 49 64 20 3d 20 30  ..    NextId = 0
1810: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69 6e 69 74  ..    def __init
1820: 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  __ (self):.     
1830: 20 20 20 73 65 6c 66 2e 69 20 3d 20 4e 6f 64 65     self.i = Node
1840: 2e 4e 65 78 74 49 64 0a 20 20 20 20 20 20 20 20  .NextId.        
1850: 4e 6f 64 65 2e 4e 65 78 74 49 64 20 2b 3d 20 31  Node.NextId += 1
1860: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62 46  .        self.bF
1870: 69 6e 61 6c 20 3d 20 46 61 6c 73 65 0a 20 20 20  inal = False.   
1880: 20 20 20 20 20 73 65 6c 66 2e 64 41 72 63 73 20       self.dArcs 
1890: 3d 20 7b 7d 20 20 20 20 20 20 20 20 20 20 23 20  = {}          # 
18a0: 6b 65 79 3a 20 61 72 63 20 76 61 6c 75 65 3b 20  key: arc value; 
18b0: 76 61 6c 75 65 3a 20 61 20 6e 6f 64 65 0a 0a 20  value: a node.. 
18c0: 20 20 20 40 63 6c 61 73 73 6d 65 74 68 6f 64 0a     @classmethod.
18d0: 20 20 20 20 64 65 66 20 72 65 73 65 74 4e 65 78      def resetNex
18e0: 74 49 64 20 28 63 6c 73 29 3a 0a 20 20 20 20 20  tId (cls):.     
18f0: 20 20 20 22 72 65 73 65 74 20 74 6f 20 30 20 74     "reset to 0 t
1900: 68 65 20 6e 6f 64 65 20 63 6f 75 6e 74 65 72 22  he node counter"
1910: 0a 20 20 20 20 20 20 20 20 63 6c 73 2e 4e 65 78  .        cls.Nex
1920: 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64 65 66  tId = 0..    def
1930: 20 5f 5f 73 74 72 5f 5f 20 28 73 65 6c 66 29 3a   __str__ (self):
1940: 0a 20 20 20 20 20 20 20 20 23 20 43 61 75 74 69  .        # Cauti
1950: 6f 6e 21 20 74 68 69 73 20 66 75 6e 63 74 69 6f  on! this functio
1960: 6e 20 69 73 20 75 73 65 64 20 66 6f 72 20 68 61  n is used for ha
1970: 73 68 69 6e 67 20 61 6e 64 20 63 6f 6d 70 61 72  shing and compar
1980: 69 73 6f 6e 21 0a 20 20 20 20 20 20 20 20 63 46  ison!.        cF
1990: 69 6e 61 6c 20 3d 20 22 31 22 20 20 69 66 20 73  inal = "1"  if s
19a0: 65 6c 66 2e 62 46 69 6e 61 6c 20 20 65 6c 73 65  elf.bFinal  else
19b0: 20 22 30 22 0a 20 20 20 20 20 20 20 20 6c 20 3d   "0".        l =
19c0: 20 5b 63 46 69 6e 61 6c 5d 0a 20 20 20 20 20 20   [cFinal].      
19d0: 20 20 66 6f 72 20 28 6b 65 79 2c 20 6f 4e 6f 64    for (key, oNod
19e0: 65 29 20 69 6e 20 73 65 6c 66 2e 64 41 72 63 73  e) in self.dArcs
19f0: 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20  .items():.      
1a00: 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 73        l.append(s
1a10: 74 72 28 6b 65 79 29 29 0a 20 20 20 20 20 20 20  tr(key)).       
1a20: 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 73 74       l.append(st
1a30: 72 28 6f 4e 6f 64 65 2e 69 29 29 0a 20 20 20 20  r(oNode.i)).    
1a40: 20 20 20 20 72 65 74 75 72 6e 20 22 5f 22 2e 6a      return "_".j
1a50: 6f 69 6e 28 6c 29 0a 0a 20 20 20 20 64 65 66 20  oin(l)..    def 
1a60: 5f 5f 68 61 73 68 5f 5f 20 28 73 65 6c 66 29 3a  __hash__ (self):
1a70: 0a 20 20 20 20 20 20 20 20 23 20 55 73 65 64 20  .        # Used 
1a80: 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20 70 79  as a key in a py
1a90: 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72 79 2e  thon dictionary.
1aa0: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
1ab0: 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29 2e 5f  self.__str__()._
1ac0: 5f 68 61 73 68 5f 5f 28 29 0a 0a 20 20 20 20 64  _hash__()..    d
1ad0: 65 66 20 5f 5f 65 71 5f 5f 20 28 73 65 6c 66 2c  ef __eq__ (self,
1ae0: 20 6f 74 68 65 72 29 3a 0a 20 20 20 20 20 20 20   other):.       
1af0: 20 23 20 55 73 65 64 20 61 73 20 61 20 6b 65 79   # Used as a key
1b00: 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64 69 63   in a python dic
1b10: 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20 20 20  tionary..       
1b20: 20 23 20 4e 6f 64 65 73 20 61 72 65 20 65 71 75   # Nodes are equ
1b30: 69 76 61 6c 65 6e 74 20 69 66 20 74 68 65 79 20  ivalent if they 
1b40: 68 61 76 65 20 69 64 65 6e 74 69 63 61 6c 20 61  have identical a
1b50: 72 63 73 2c 20 61 6e 64 20 65 61 63 68 20 69 64  rcs, and each id
1b60: 65 6e 74 69 63 61 6c 20 61 72 63 20 6c 65 61 64  entical arc lead
1b70: 73 20 74 6f 20 69 64 65 6e 74 69 63 61 6c 20 73  s to identical s
1b80: 74 61 74 65 73 2e 0a 20 20 20 20 20 20 20 20 72  tates..        r
1b90: 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73 74 72  eturn self.__str
1ba0: 5f 5f 28 29 20 3d 3d 20 6f 74 68 65 72 2e 5f 5f  __() == other.__
1bb0: 73 74 72 5f 5f 28 29 0a 0a 20 20 20 20 64 65 66  str__()..    def
1bc0: 20 67 65 74 4e 6f 64 65 41 73 44 69 63 74 20 28   getNodeAsDict (
1bd0: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
1be0: 72 65 74 75 72 6e 73 20 74 68 65 20 6e 6f 64 65  returns the node
1bf0: 20 61 73 20 61 20 64 69 63 74 69 6f 6e 61 72 79   as a dictionary
1c00: 20 73 74 72 75 63 74 75 72 65 22 0a 20 20 20 20   structure".    
1c10: 20 20 20 20 64 4e 6f 64 65 20 3d 20 7b 7d 0a 20      dNode = {}. 
1c20: 20 20 20 20 20 20 20 64 52 65 56 61 6c 75 65 20         dReValue 
1c30: 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 52 65  = {}.        dRe
1c40: 4d 6f 72 70 68 20 3d 20 7b 7d 0a 20 20 20 20 20  Morph = {}.     
1c50: 20 20 20 64 52 75 6c 65 20 3d 20 7b 7d 0a 20 20     dRule = {}.  
1c60: 20 20 20 20 20 20 64 4c 65 6d 6d 61 20 3d 20 7b        dLemma = {
1c70: 7d 0a 20 20 20 20 20 20 20 20 64 4d 65 74 61 20  }.        dMeta 
1c80: 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 54 61  = {}.        dTa
1c90: 67 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 66  g = {}.        f
1ca0: 6f 72 20 73 41 72 63 2c 20 6f 4e 6f 64 65 20 69  or sArc, oNode i
1cb0: 6e 20 73 65 6c 66 2e 64 41 72 63 73 2e 69 74 65  n self.dArcs.ite
1cc0: 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20  ms():.          
1cd0: 20 20 69 66 20 73 41 72 63 2e 73 74 61 72 74 73    if sArc.starts
1ce0: 77 69 74 68 28 22 40 22 29 20 61 6e 64 20 6c 65  with("@") and le
1cf0: 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20  n(sArc) > 1:.   
1d00: 20 20 20 20 20 20 20 20 20 20 20 20 20 64 52 65               dRe
1d10: 4d 6f 72 70 68 5b 73 41 72 63 5b 31 3a 5d 5d 20  Morph[sArc[1:]] 
1d20: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
1d30: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
1d40: 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74 73 77  lif sArc.startsw
1d50: 69 74 68 28 22 7e 22 29 20 61 6e 64 20 6c 65 6e  ith("~") and len
1d60: 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20  (sArc) > 1:.    
1d70: 20 20 20 20 20 20 20 20 20 20 20 20 64 52 65 56              dReV
1d80: 61 6c 75 65 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d  alue[sArc[1:]] =
1d90: 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28   oNode.__hash__(
1da0: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c  ).            el
1db0: 69 66 20 73 41 72 63 2e 73 74 61 72 74 73 77 69  if sArc.startswi
1dc0: 74 68 28 22 3e 22 29 20 61 6e 64 20 6c 65 6e 28  th(">") and len(
1dd0: 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20 20  sArc) > 1:.     
1de0: 20 20 20 20 20 20 20 20 20 20 20 64 4c 65 6d 6d             dLemm
1df0: 61 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e  a[sArc[1:]] = oN
1e00: 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20  ode.__hash__(). 
1e10: 20 20 20 20 20 20 20 20 20 20 20 65 6c 69 66 20             elif 
1e20: 73 41 72 63 2e 73 74 61 72 74 73 77 69 74 68 28  sArc.startswith(
1e30: 22 2a 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72  "*") and len(sAr
1e40: 63 29 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20  c) > 1:.        
1e50: 20 20 20 20 20 20 20 20 64 4d 65 74 61 5b 73 41          dMeta[sA
1e60: 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e  rc[1:]] = oNode.
1e70: 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20  __hash__().     
1e80: 20 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63         elif sArc
1e90: 2e 73 74 61 72 74 73 77 69 74 68 28 22 2f 22 29  .startswith("/")
1ea0: 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e   and len(sArc) >
1eb0: 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20   1:.            
1ec0: 20 20 20 20 64 54 61 67 5b 73 41 72 63 5b 31 3a      dTag[sArc[1:
1ed0: 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73  ]] = oNode.__has
1ee0: 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20  h__().          
1ef0: 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72    elif sArc.star
1f00: 74 73 77 69 74 68 28 22 23 23 22 29 3a 0a 20 20  tswith("##"):.  
1f10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 52                dR
1f20: 75 6c 65 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20  ule[sArc[1:]] = 
1f30: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
1f40: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73  .            els
1f50: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  e:.             
1f60: 20 20 20 64 4e 6f 64 65 5b 73 41 72 63 5d 20 3d     dNode[sArc] =
1f70: 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28   oNode.__hash__(
1f80: 29 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65  ).        if dRe
1f90: 56 61 6c 75 65 3a 0a 20 20 20 20 20 20 20 20 20  Value:.         
1fa0: 20 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 76 61     dNode["<re_va
1fb0: 6c 75 65 3e 22 5d 20 3d 20 64 52 65 56 61 6c 75  lue>"] = dReValu
1fc0: 65 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65  e.        if dRe
1fd0: 4d 6f 72 70 68 3a 0a 20 20 20 20 20 20 20 20 20  Morph:.         
1fe0: 20 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 6d 6f     dNode["<re_mo
1ff0: 72 70 68 3e 22 5d 20 3d 20 64 52 65 4d 6f 72 70  rph>"] = dReMorp
2000: 68 0a 20 20 20 20 20 20 20 20 69 66 20 64 4c 65  h.        if dLe
2010: 6d 6d 61 3a 0a 20 20 20 20 20 20 20 20 20 20 20  mma:.           
2020: 20 64 4e 6f 64 65 5b 22 3c 6c 65 6d 6d 61 73 3e   dNode["<lemmas>
2030: 22 5d 20 3d 20 64 4c 65 6d 6d 61 0a 20 20 20 20  "] = dLemma.    
2040: 20 20 20 20 69 66 20 64 54 61 67 3a 0a 20 20 20      if dTag:.   
2050: 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22           dNode["
2060: 3c 74 61 67 73 3e 22 5d 20 3d 20 64 54 61 67 0a  <tags>"] = dTag.
2070: 20 20 20 20 20 20 20 20 69 66 20 64 4d 65 74 61          if dMeta
2080: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e  :.            dN
2090: 6f 64 65 5b 22 3c 6d 65 74 61 3e 22 5d 20 3d 20  ode["<meta>"] = 
20a0: 64 4d 65 74 61 0a 20 20 20 20 20 20 20 20 69 66  dMeta.        if
20b0: 20 64 52 75 6c 65 3a 0a 20 20 20 20 20 20 20 20   dRule:.        
20c0: 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72 75 6c 65      dNode["<rule
20d0: 73 3e 22 5d 20 3d 20 64 52 75 6c 65 0a 20 20 20  s>"] = dRule.   
20e0: 20 20 20 20 20 23 69 66 20 73 65 6c 66 2e 62 46       #if self.bF
20f0: 69 6e 61 6c 3a 0a 20 20 20 20 20 20 20 20 23 20  inal:.        # 
2100: 20 20 20 64 4e 6f 64 65 5b 22 3c 66 69 6e 61 6c     dNode["<final
2110: 3e 22 5d 20 3d 20 31 0a 20 20 20 20 20 20 20 20  >"] = 1.        
2120: 72 65 74 75 72 6e 20 64 4e 6f 64 65 0a           return dNode.