Grammalecte  Hex Artifact Content

Artifact 9b17f8d6af4b1eb3f79615b282e0f3525ebbe200a1f6c119d8586f1d4ba73c8f:


0000: 22 22 22 0a 52 55 4c 45 20 47 52 41 50 48 20 42  """.RULE GRAPH B
0010: 55 49 4c 44 45 52 0a 22 22 22 0a 0a 23 20 62 79  UILDER."""..# by
0020: 20 4f 6c 69 76 69 65 72 20 52 2e 0a 23 20 4c 69   Olivier R..# Li
0030: 63 65 6e 73 65 3a 20 4d 50 4c 20 32 0a 0a 69 6d  cense: MPL 2..im
0040: 70 6f 72 74 20 72 65 0a 0a 0a 63 6c 61 73 73 20  port re...class 
0050: 44 41 52 47 3a 0a 20 20 20 20 22 22 22 44 49 52  DARG:.    """DIR
0060: 45 43 54 20 41 43 59 43 4c 49 43 20 52 55 4c 45  ECT ACYCLIC RULE
0070: 20 47 52 41 50 48 22 22 22 0a 20 20 20 20 23 20   GRAPH""".    # 
0080: 54 68 69 73 20 63 6f 64 65 20 69 73 20 69 6e 73  This code is ins
0090: 70 69 72 65 64 20 66 72 6f 6d 20 53 74 65 76 65  pired from Steve
00a0: 20 48 61 6e 6f 76 e2 80 99 73 20 44 41 57 47 2c   Hanov...s DAWG,
00b0: 20 32 30 31 31 2e 20 28 68 74 74 70 3a 2f 2f 73   2011. (http://s
00c0: 74 65 76 65 68 61 6e 6f 76 2e 63 61 2f 62 6c 6f  tevehanov.ca/blo
00d0: 67 2f 69 6e 64 65 78 2e 70 68 70 3f 69 64 3d 31  g/index.php?id=1
00e0: 31 35 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69  15)..    def __i
00f0: 6e 69 74 5f 5f 20 28 73 65 6c 66 2c 20 6c 52 75  nit__ (self, lRu
0100: 6c 65 2c 20 73 4c 61 6e 67 43 6f 64 65 29 3a 0a  le, sLangCode):.
0110: 20 20 20 20 20 20 20 20 23 20 50 72 65 70 61 72          # Prepar
0120: 69 6e 67 20 44 41 52 47 0a 20 20 20 20 20 20 20  ing DARG.       
0130: 20 73 65 6c 66 2e 73 4c 61 6e 67 43 6f 64 65 20   self.sLangCode 
0140: 3d 20 73 4c 61 6e 67 43 6f 64 65 0a 20 20 20 20  = sLangCode.    
0150: 20 20 20 20 73 65 6c 66 2e 6e 52 75 6c 65 20 3d      self.nRule =
0160: 20 6c 65 6e 28 6c 52 75 6c 65 29 0a 20 20 20 20   len(lRule).    
0170: 20 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f      self.aPrevio
0180: 75 73 52 75 6c 65 20 3d 20 5b 5d 0a 20 20 20 20  usRule = [].    
0190: 20 20 20 20 4e 6f 64 65 2e 72 65 73 65 74 4e 65      Node.resetNe
01a0: 78 74 49 64 28 29 0a 20 20 20 20 20 20 20 20 73  xtId().        s
01b0: 65 6c 66 2e 6f 52 6f 6f 74 20 3d 20 4e 6f 64 65  elf.oRoot = Node
01c0: 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  ().        self.
01d0: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20  lUncheckedNodes 
01e0: 3d 20 5b 5d 20 20 23 20 6c 69 73 74 20 6f 66 20  = []  # list of 
01f0: 6e 6f 64 65 73 20 74 68 61 74 20 68 61 76 65 20  nodes that have 
0200: 6e 6f 74 20 62 65 65 6e 20 63 68 65 63 6b 65 64  not been checked
0210: 20 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f 6e   for duplication
0220: 2e 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c  ..        self.l
0230: 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 20 3d  MinimizedNodes =
0240: 20 7b 7d 20 20 23 20 6c 69 73 74 20 6f 66 20 75   {}  # list of u
0250: 6e 69 71 75 65 20 6e 6f 64 65 73 20 74 68 61 74  nique nodes that
0260: 20 68 61 76 65 20 62 65 65 6e 20 63 68 65 63 6b   have been check
0270: 65 64 20 66 6f 72 20 64 75 70 6c 69 63 61 74 69  ed for duplicati
0280: 6f 6e 2e 0a 20 20 20 20 20 20 20 20 73 65 6c 66  on..        self
0290: 2e 6e 4e 6f 64 65 20 3d 20 30 0a 20 20 20 20 20  .nNode = 0.     
02a0: 20 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30     self.nArc = 0
02b0: 0a 0a 20 20 20 20 20 20 20 20 23 20 62 75 69 6c  ..        # buil
02c0: 64 0a 20 20 20 20 20 20 20 20 6c 52 75 6c 65 2e  d.        lRule.
02d0: 73 6f 72 74 28 29 0a 20 20 20 20 20 20 20 20 66  sort().        f
02e0: 6f 72 20 61 52 75 6c 65 20 69 6e 20 6c 52 75 6c  or aRule in lRul
02f0: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 73  e:.            s
0300: 65 6c 66 2e 69 6e 73 65 72 74 28 61 52 75 6c 65  elf.insert(aRule
0310: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 66  ).        self.f
0320: 69 6e 69 73 68 28 29 0a 20 20 20 20 20 20 20 20  inish().        
0330: 73 65 6c 66 2e 63 6f 75 6e 74 4e 6f 64 65 73 28  self.countNodes(
0340: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 63  ).        self.c
0350: 6f 75 6e 74 41 72 63 73 28 29 0a 0a 20 20 20 20  ountArcs()..    
0360: 23 20 42 55 49 4c 44 20 44 41 52 47 0a 20 20 20  # BUILD DARG.   
0370: 20 64 65 66 20 69 6e 73 65 72 74 20 28 73 65 6c   def insert (sel
0380: 66 2c 20 61 52 75 6c 65 29 3a 0a 20 20 20 20 20  f, aRule):.     
0390: 20 20 20 22 69 6e 73 65 72 74 20 61 20 6e 65 77     "insert a new
03a0: 20 72 75 6c 65 20 28 74 6f 6b 65 6e 73 20 6d 75   rule (tokens mu
03b0: 73 74 20 62 65 20 69 6e 73 65 72 74 65 64 20 69  st be inserted i
03c0: 6e 20 6f 72 64 65 72 29 22 0a 20 20 20 20 20 20  n order)".      
03d0: 20 20 69 66 20 61 52 75 6c 65 20 3c 20 73 65 6c    if aRule < sel
03e0: 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 3a  f.aPreviousRule:
03f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 78 69  .            exi
0400: 74 28 22 23 20 45 72 72 6f 72 3a 20 74 6f 6b 65  t("# Error: toke
0410: 6e 73 20 6d 75 73 74 20 62 65 20 69 6e 73 65 72  ns must be inser
0420: 74 65 64 20 69 6e 20 6f 72 64 65 72 2e 22 29 0a  ted in order.").
0430: 0a 20 20 20 20 20 20 20 20 23 20 66 69 6e 64 20  .        # find 
0440: 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78 20 62 65  common prefix be
0450: 74 77 65 65 6e 20 77 6f 72 64 20 61 6e 64 20 70  tween word and p
0460: 72 65 76 69 6f 75 73 20 77 6f 72 64 0a 20 20 20  revious word.   
0470: 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66       nCommonPref
0480: 69 78 20 3d 20 30 0a 20 20 20 20 20 20 20 20 66  ix = 0.        f
0490: 6f 72 20 69 20 69 6e 20 72 61 6e 67 65 28 6d 69  or i in range(mi
04a0: 6e 28 6c 65 6e 28 61 52 75 6c 65 29 2c 20 6c 65  n(len(aRule), le
04b0: 6e 28 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73  n(self.aPrevious
04c0: 52 75 6c 65 29 29 29 3a 0a 20 20 20 20 20 20 20  Rule))):.       
04d0: 20 20 20 20 20 69 66 20 61 52 75 6c 65 5b 69 5d       if aRule[i]
04e0: 20 21 3d 20 73 65 6c 66 2e 61 50 72 65 76 69 6f   != self.aPrevio
04f0: 75 73 52 75 6c 65 5b 69 5d 3a 0a 20 20 20 20 20  usRule[i]:.     
0500: 20 20 20 20 20 20 20 20 20 20 20 62 72 65 61 6b             break
0510: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e 43 6f  .            nCo
0520: 6d 6d 6f 6e 50 72 65 66 69 78 20 2b 3d 20 31 0a  mmonPrefix += 1.
0530: 0a 20 20 20 20 20 20 20 20 23 20 43 68 65 63 6b  .        # Check
0540: 20 74 68 65 20 6c 55 6e 63 68 65 63 6b 65 64 4e   the lUncheckedN
0550: 6f 64 65 73 20 66 6f 72 20 72 65 64 75 6e 64 61  odes for redunda
0560: 6e 74 20 6e 6f 64 65 73 2c 20 70 72 6f 63 65 65  nt nodes, procee
0570: 64 69 6e 67 20 66 72 6f 6d 20 6c 61 73 74 0a 20  ding from last. 
0580: 20 20 20 20 20 20 20 23 20 6f 6e 65 20 64 6f 77         # one dow
0590: 6e 20 74 6f 20 74 68 65 20 63 6f 6d 6d 6f 6e 20  n to the common 
05a0: 70 72 65 66 69 78 20 73 69 7a 65 2e 20 54 68 65  prefix size. The
05b0: 6e 20 74 72 75 6e 63 61 74 65 20 74 68 65 20 6c  n truncate the l
05c0: 69 73 74 20 61 74 20 74 68 61 74 20 70 6f 69 6e  ist at that poin
05d0: 74 2e 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  t..        self.
05e0: 5f 6d 69 6e 69 6d 69 7a 65 28 6e 43 6f 6d 6d 6f  _minimize(nCommo
05f0: 6e 50 72 65 66 69 78 29 0a 0a 20 20 20 20 20 20  nPrefix)..      
0600: 20 20 23 20 61 64 64 20 74 68 65 20 73 75 66 66    # add the suff
0610: 69 78 2c 20 73 74 61 72 74 69 6e 67 20 66 72 6f  ix, starting fro
0620: 6d 20 74 68 65 20 63 6f 72 72 65 63 74 20 6e 6f  m the correct no
0630: 64 65 20 6d 69 64 2d 77 61 79 20 74 68 72 6f 75  de mid-way throu
0640: 67 68 20 74 68 65 20 67 72 61 70 68 0a 20 20 20  gh the graph.   
0650: 20 20 20 20 20 69 66 20 6e 6f 74 20 73 65 6c 66       if not self
0660: 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73  .lUncheckedNodes
0670: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  :.            oN
0680: 6f 64 65 20 3d 20 73 65 6c 66 2e 6f 52 6f 6f 74  ode = self.oRoot
0690: 0a 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20  .        else:. 
06a0: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
06b0: 20 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b   = self.lUncheck
06c0: 65 64 4e 6f 64 65 73 5b 2d 31 5d 5b 32 5d 0a 0a  edNodes[-1][2]..
06d0: 20 20 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 3d          iToken =
06e0: 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 0a 20   nCommonPrefix. 
06f0: 20 20 20 20 20 20 20 66 6f 72 20 73 54 6f 6b 65         for sToke
0700: 6e 20 69 6e 20 61 52 75 6c 65 5b 6e 43 6f 6d 6d  n in aRule[nComm
0710: 6f 6e 50 72 65 66 69 78 3a 5d 3a 0a 20 20 20 20  onPrefix:]:.    
0720: 20 20 20 20 20 20 20 20 6f 4e 65 78 74 4e 6f 64          oNextNod
0730: 65 20 3d 20 4e 6f 64 65 28 29 0a 20 20 20 20 20  e = Node().     
0740: 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72         oNode.dAr
0750: 63 73 5b 73 54 6f 6b 65 6e 5d 20 3d 20 6f 4e 65  cs[sToken] = oNe
0760: 78 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20 20  xtNode.         
0770: 20 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b     self.lUncheck
0780: 65 64 4e 6f 64 65 73 2e 61 70 70 65 6e 64 28 28  edNodes.append((
0790: 6f 4e 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f  oNode, sToken, o
07a0: 4e 65 78 74 4e 6f 64 65 29 29 0a 20 20 20 20 20  NextNode)).     
07b0: 20 20 20 20 20 20 20 69 66 20 69 54 6f 6b 65 6e         if iToken
07c0: 20 3d 3d 20 28 6c 65 6e 28 61 52 75 6c 65 29 20   == (len(aRule) 
07d0: 2d 20 32 29 3a 0a 20 20 20 20 20 20 20 20 20 20  - 2):.          
07e0: 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e        oNode.bFin
07f0: 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20 20 20  al = True.      
0800: 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 2b 3d 20        iToken += 
0810: 31 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  1.            oN
0820: 6f 64 65 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a  ode = oNextNode.
0830: 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46          oNode.bF
0840: 69 6e 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20  inal = True.    
0850: 20 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f      self.aPrevio
0860: 75 73 52 75 6c 65 20 3d 20 61 52 75 6c 65 0a 0a  usRule = aRule..
0870: 20 20 20 20 64 65 66 20 66 69 6e 69 73 68 20 28      def finish (
0880: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
0890: 6d 69 6e 69 6d 69 7a 65 20 75 6e 63 68 65 63 6b  minimize uncheck
08a0: 65 64 20 6e 6f 64 65 73 22 0a 20 20 20 20 20 20  ed nodes".      
08b0: 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a 65    self._minimize
08c0: 28 30 29 0a 0a 20 20 20 20 64 65 66 20 5f 6d 69  (0)..    def _mi
08d0: 6e 69 6d 69 7a 65 20 28 73 65 6c 66 2c 20 64 6f  nimize (self, do
08e0: 77 6e 54 6f 29 3a 0a 20 20 20 20 20 20 20 20 23  wnTo):.        #
08f0: 20 70 72 6f 63 65 65 64 20 66 72 6f 6d 20 74 68   proceed from th
0900: 65 20 6c 65 61 66 20 75 70 20 74 6f 20 61 20 63  e leaf up to a c
0910: 65 72 74 61 69 6e 20 70 6f 69 6e 74 0a 20 20 20  ertain point.   
0920: 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20 72 61       for i in ra
0930: 6e 67 65 28 20 6c 65 6e 28 73 65 6c 66 2e 6c 55  nge( len(self.lU
0940: 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 29 2d 31  ncheckedNodes)-1
0950: 2c 20 64 6f 77 6e 54 6f 2d 31 2c 20 2d 31 20 29  , downTo-1, -1 )
0960: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  :.            oN
0970: 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f 43 68  ode, sToken, oCh
0980: 69 6c 64 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6c  ildNode = self.l
0990: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 5b 69  UncheckedNodes[i
09a0: 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  ].            if
09b0: 20 6f 43 68 69 6c 64 4e 6f 64 65 20 69 6e 20 73   oChildNode in s
09c0: 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f  elf.lMinimizedNo
09d0: 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20 20 20  des:.           
09e0: 20 20 20 20 20 23 20 72 65 70 6c 61 63 65 20 74       # replace t
09f0: 68 65 20 63 68 69 6c 64 20 77 69 74 68 20 74 68  he child with th
0a00: 65 20 70 72 65 76 69 6f 75 73 6c 79 20 65 6e 63  e previously enc
0a10: 6f 75 6e 74 65 72 65 64 20 6f 6e 65 0a 20 20 20  ountered one.   
0a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f               oNo
0a30: 64 65 2e 64 41 72 63 73 5b 73 54 6f 6b 65 6e 5d  de.dArcs[sToken]
0a40: 20 3d 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a   = self.lMinimiz
0a50: 65 64 4e 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f  edNodes[oChildNo
0a60: 64 65 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20  de].            
0a70: 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20  else:.          
0a80: 20 20 20 20 20 20 23 20 61 64 64 20 74 68 65 20        # add the 
0a90: 73 74 61 74 65 20 74 6f 20 74 68 65 20 6d 69 6e  state to the min
0aa0: 69 6d 69 7a 65 64 20 6e 6f 64 65 73 2e 0a 20 20  imized nodes..  
0ab0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65                se
0ac0: 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64  lf.lMinimizedNod
0ad0: 65 73 5b 6f 43 68 69 6c 64 4e 6f 64 65 5d 20 3d  es[oChildNode] =
0ae0: 20 6f 43 68 69 6c 64 4e 6f 64 65 0a 20 20 20 20   oChildNode.    
0af0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e          self.lUn
0b00: 63 68 65 63 6b 65 64 4e 6f 64 65 73 2e 70 6f 70  checkedNodes.pop
0b10: 28 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e  ()..    def coun
0b20: 74 4e 6f 64 65 73 20 28 73 65 6c 66 29 3a 0a 20  tNodes (self):. 
0b30: 20 20 20 20 20 20 20 22 63 6f 75 6e 74 20 6e 6f         "count no
0b40: 64 65 73 20 77 69 74 68 69 6e 20 74 68 65 20 77  des within the w
0b50: 68 6f 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20  hole graph".    
0b60: 20 20 20 20 73 65 6c 66 2e 6e 4e 6f 64 65 20 3d      self.nNode =
0b70: 20 6c 65 6e 28 73 65 6c 66 2e 6c 4d 69 6e 69 6d   len(self.lMinim
0b80: 69 7a 65 64 4e 6f 64 65 73 29 0a 0a 20 20 20 20  izedNodes)..    
0b90: 64 65 66 20 63 6f 75 6e 74 41 72 63 73 20 28 73  def countArcs (s
0ba0: 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22 63  elf):.        "c
0bb0: 6f 75 6e 74 20 61 72 63 73 20 77 69 74 68 69 6e  ount arcs within
0bc0: 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61 70 68   the whole graph
0bd0: 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e  ".        self.n
0be0: 41 72 63 20 3d 20 6c 65 6e 28 73 65 6c 66 2e 6f  Arc = len(self.o
0bf0: 52 6f 6f 74 2e 64 41 72 63 73 29 0a 20 20 20 20  Root.dArcs).    
0c00: 20 20 20 20 66 6f 72 20 6f 4e 6f 64 65 20 69 6e      for oNode in
0c10: 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64   self.lMinimized
0c20: 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20  Nodes:.         
0c30: 20 20 20 73 65 6c 66 2e 6e 41 72 63 20 2b 3d 20     self.nArc += 
0c40: 6c 65 6e 28 6f 4e 6f 64 65 2e 64 41 72 63 73 29  len(oNode.dArcs)
0c50: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 73 74 72 5f  ..    def __str_
0c60: 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20  _ (self):.      
0c70: 20 20 22 64 69 73 70 6c 61 79 20 69 6e 66 6f 72    "display infor
0c80: 6d 61 74 69 6f 6e 73 20 61 62 6f 75 74 20 74 68  mations about th
0c90: 65 20 72 75 6c 65 20 67 72 61 70 68 22 0a 20 20  e rule graph".  
0ca0: 20 20 20 20 20 20 72 65 74 75 72 6e 20 22 20 3e        return " >
0cb0: 20 44 41 52 47 3a 20 7b 3a 3e 31 30 2c 7d 20 72   DARG: {:>10,} r
0cc0: 75 6c 65 73 2c 20 20 7b 3a 3e 31 30 2c 7d 20 6e  ules,  {:>10,} n
0cd0: 6f 64 65 73 2c 20 20 7b 3a 3e 31 30 2c 7d 20 61  odes,  {:>10,} a
0ce0: 72 63 73 22 2e 66 6f 72 6d 61 74 28 73 65 6c 66  rcs".format(self
0cf0: 2e 6e 52 75 6c 65 2c 20 73 65 6c 66 2e 6e 4e 6f  .nRule, self.nNo
0d00: 64 65 2c 20 73 65 6c 66 2e 6e 41 72 63 29 0a 0a  de, self.nArc)..
0d10: 20 20 20 20 64 65 66 20 63 72 65 61 74 65 47 72      def createGr
0d20: 61 70 68 20 28 73 65 6c 66 29 3a 0a 20 20 20 20  aph (self):.    
0d30: 20 20 20 20 22 63 72 65 61 74 65 20 74 68 65 20      "create the 
0d40: 67 72 61 70 68 20 61 73 20 61 20 64 69 63 74 69  graph as a dicti
0d50: 6f 6e 61 72 79 22 0a 20 20 20 20 20 20 20 20 64  onary".        d
0d60: 47 72 61 70 68 20 3d 20 7b 20 30 3a 20 73 65 6c  Graph = { 0: sel
0d70: 66 2e 6f 52 6f 6f 74 2e 67 65 74 4e 6f 64 65 41  f.oRoot.getNodeA
0d80: 73 44 69 63 74 28 29 20 7d 0a 20 20 20 20 20 20  sDict() }.      
0d90: 20 20 66 6f 72 20 6f 4e 6f 64 65 20 69 6e 20 73    for oNode in s
0da0: 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f  elf.lMinimizedNo
0db0: 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20 20 20  des:.           
0dc0: 20 73 48 61 73 68 49 64 20 3d 20 6f 4e 6f 64 65   sHashId = oNode
0dd0: 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20  .__hash__().    
0de0: 20 20 20 20 20 20 20 20 69 66 20 73 48 61 73 68          if sHash
0df0: 49 64 20 6e 6f 74 20 69 6e 20 64 47 72 61 70 68  Id not in dGraph
0e00: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
0e10: 20 20 64 47 72 61 70 68 5b 73 48 61 73 68 49 64    dGraph[sHashId
0e20: 5d 20 3d 20 6f 4e 6f 64 65 2e 67 65 74 4e 6f 64  ] = oNode.getNod
0e30: 65 41 73 44 69 63 74 28 29 0a 20 20 20 20 20 20  eAsDict().      
0e40: 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20        else:.    
0e50: 20 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e              prin
0e60: 74 28 22 45 72 72 6f 72 2e 20 44 6f 75 62 6c 65  t("Error. Double
0e70: 20 6e 6f 64 65 e2 80 a6 20 73 61 6d 65 20 69 64   node... same id
0e80: 3a 20 22 2c 20 73 48 61 73 68 49 64 29 0a 20 20  : ", sHashId).  
0e90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72                pr
0ea0: 69 6e 74 28 73 74 72 28 6f 4e 6f 64 65 2e 67 65  int(str(oNode.ge
0eb0: 74 4e 6f 64 65 41 73 44 69 63 74 28 29 29 29 0a  tNodeAsDict())).
0ec0: 20 20 20 20 20 20 20 20 64 47 72 61 70 68 20 3d          dGraph =
0ed0: 20 73 65 6c 66 2e 5f 72 65 77 72 69 74 65 4b 65   self._rewriteKe
0ee0: 79 73 4f 66 44 41 52 47 28 64 47 72 61 70 68 29  ysOfDARG(dGraph)
0ef0: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f 73  .        self._s
0f00: 6f 72 74 41 63 74 69 6f 6e 73 28 64 47 72 61 70  ortActions(dGrap
0f10: 68 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  h).        self.
0f20: 5f 63 68 65 63 6b 52 65 67 65 78 65 73 28 64 47  _checkRegexes(dG
0f30: 72 61 70 68 29 0a 20 20 20 20 20 20 20 20 72 65  raph).        re
0f40: 74 75 72 6e 20 64 47 72 61 70 68 0a 0a 20 20 20  turn dGraph..   
0f50: 20 64 65 66 20 5f 72 65 77 72 69 74 65 4b 65 79   def _rewriteKey
0f60: 73 4f 66 44 41 52 47 20 28 73 65 6c 66 2c 20 64  sOfDARG (self, d
0f70: 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20  Graph):.        
0f80: 22 6b 65 79 73 20 6f 66 20 44 41 52 47 20 61 72  "keys of DARG ar
0f90: 65 20 6c 6f 6e 67 20 6e 75 6d 62 65 72 73 20 28  e long numbers (
0fa0: 68 61 73 68 65 73 29 3a 20 74 68 69 73 20 66 75  hashes): this fu
0fb0: 6e 63 74 69 6f 6e 20 72 65 70 6c 61 63 65 20 74  nction replace t
0fc0: 68 65 73 65 20 68 61 73 68 65 73 20 77 69 74 68  hese hashes with
0fd0: 20 73 6d 61 6c 6c 65 72 20 6e 75 6d 62 65 72 73   smaller numbers
0fe0: 20 28 74 6f 20 72 65 64 75 63 65 20 73 74 6f 72   (to reduce stor
0ff0: 69 6e 67 20 73 69 7a 65 29 22 0a 20 20 20 20 20  ing size)".     
1000: 20 20 20 23 20 63 72 65 61 74 65 20 74 72 61 6e     # create tran
1010: 73 6c 61 74 69 6f 6e 20 64 69 63 74 69 6f 6e 61  slation dictiona
1020: 72 79 0a 20 20 20 20 20 20 20 20 64 4b 65 79 54  ry.        dKeyT
1030: 72 61 6e 73 20 3d 20 7b 7d 0a 20 20 20 20 20 20  rans = {}.      
1040: 20 20 66 6f 72 20 69 2c 20 6e 4b 65 79 20 69 6e    for i, nKey in
1050: 20 65 6e 75 6d 65 72 61 74 65 28 64 47 72 61 70   enumerate(dGrap
1060: 68 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  h):.            
1070: 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d 20  dKeyTrans[nKey] 
1080: 3d 20 69 0a 20 20 20 20 20 20 20 20 23 20 72 65  = i.        # re
1090: 70 6c 61 63 65 20 6b 65 79 73 0a 20 20 20 20 20  place keys.     
10a0: 20 20 20 64 4e 65 77 47 72 61 70 68 20 3d 20 7b     dNewGraph = {
10b0: 7d 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6e 4b  }.        for nK
10c0: 65 79 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61  ey, dVal in dGra
10d0: 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  ph.items():.    
10e0: 20 20 20 20 20 20 20 20 64 4e 65 77 47 72 61 70          dNewGrap
10f0: 68 5b 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79  h[dKeyTrans[nKey
1100: 5d 5d 20 3d 20 64 56 61 6c 0a 20 20 20 20 20 20  ]] = dVal.      
1110: 20 20 66 6f 72 20 5f 2c 20 64 56 61 6c 20 69 6e    for _, dVal in
1120: 20 64 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a   dGraph.items():
1130: 0a 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72  .            for
1140: 20 73 41 72 63 2c 20 76 61 6c 20 69 6e 20 64 56   sArc, val in dV
1150: 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  al.items():.    
1160: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 69              if i
1170: 73 69 6e 73 74 61 6e 63 65 28 76 61 6c 2c 20 69  sinstance(val, i
1180: 6e 74 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20  nt):.           
1190: 20 20 20 20 20 20 20 20 20 64 56 61 6c 5b 73 41           dVal[sA
11a0: 72 63 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b  rc] = dKeyTrans[
11b0: 76 61 6c 5d 0a 20 20 20 20 20 20 20 20 20 20 20  val].           
11c0: 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20       else:.     
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
11e0: 6f 72 20 73 41 72 63 32 2c 20 6e 4b 65 79 20 69  or sArc2, nKey i
11f0: 6e 20 76 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20  n val.items():. 
1200: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1210: 20 20 20 20 20 20 20 76 61 6c 5b 73 41 72 63 32         val[sArc2
1220: 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b 6e 4b  ] = dKeyTrans[nK
1230: 65 79 5d 0a 20 20 20 20 20 20 20 20 72 65 74 75  ey].        retu
1240: 72 6e 20 64 4e 65 77 47 72 61 70 68 0a 0a 20 20  rn dNewGraph..  
1250: 20 20 64 65 66 20 5f 73 6f 72 74 41 63 74 69 6f    def _sortActio
1260: 6e 73 20 28 73 65 6c 66 2c 20 64 47 72 61 70 68  ns (self, dGraph
1270: 29 3a 0a 20 20 20 20 20 20 20 20 22 77 68 65 6e  ):.        "when
1280: 20 61 20 70 61 74 74 65 72 6e 20 69 73 20 66 6f   a pattern is fo
1290: 75 6e 64 2c 20 73 65 76 65 72 61 6c 20 61 63 74  und, several act
12a0: 69 6f 6e 73 20 6d 61 79 20 62 65 20 6c 61 75 6e  ions may be laun
12b0: 63 68 65 64 2c 20 61 6e 64 20 69 74 20 6d 75 73  ched, and it mus
12c0: 74 20 62 65 20 70 65 72 66 6f 72 6d 65 64 20 69  t be performed i
12d0: 6e 20 61 20 63 65 72 74 61 69 6e 20 6f 72 64 65  n a certain orde
12e0: 72 22 0a 20 20 20 20 20 20 20 20 66 6f 72 20 5f  r".        for _
12f0: 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61 70 68  , dVal in dGraph
1300: 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20  .items():.      
1310: 20 20 20 20 20 20 69 66 20 22 3c 72 75 6c 65 73        if "<rules
1320: 3e 22 20 69 6e 20 64 56 61 6c 3a 0a 20 20 20 20  >" in dVal:.    
1330: 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72 20              for 
1340: 5f 2c 20 6e 4b 65 79 20 69 6e 20 64 56 61 6c 5b  _, nKey in dVal[
1350: 22 3c 72 75 6c 65 73 3e 22 5d 2e 69 74 65 6d 73  "<rules>"].items
1360: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
1370: 20 20 20 20 20 20 20 20 23 20 77 65 20 63 68 61          # we cha
1380: 6e 67 65 20 74 68 65 20 64 69 63 74 69 6f 6e 61  nge the dictiona
1390: 72 79 20 6f 66 20 61 63 74 69 6f 6e 73 20 69 6e  ry of actions in
13a0: 20 61 20 6c 69 73 74 20 6f 66 20 61 63 74 69 6f   a list of actio
13b0: 6e 73 20 28 76 61 6c 75 65 73 20 6f 66 20 64 69  ns (values of di
13c0: 63 74 69 6f 6e 61 72 79 20 61 6c 6c 20 70 6f 69  ctionary all poi
13d0: 6e 74 73 20 74 6f 20 74 68 65 20 66 69 6e 61 6c  nts to the final
13e0: 20 6e 6f 64 65 29 0a 20 20 20 20 20 20 20 20 20   node).         
13f0: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 69 73             if is
1400: 69 6e 73 74 61 6e 63 65 28 64 47 72 61 70 68 5b  instance(dGraph[
1410: 6e 4b 65 79 5d 2c 20 64 69 63 74 29 3a 0a 20 20  nKey], dict):.  
1420: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1430: 20 20 20 20 20 20 64 47 72 61 70 68 5b 6e 4b 65        dGraph[nKe
1440: 79 5d 20 3d 20 73 6f 72 74 65 64 28 64 47 72 61  y] = sorted(dGra
1450: 70 68 5b 6e 4b 65 79 5d 2e 6b 65 79 73 28 29 29  ph[nKey].keys())
1460: 0a 0a 20 20 20 20 64 65 66 20 5f 63 68 65 63 6b  ..    def _check
1470: 52 65 67 65 78 65 73 20 28 73 65 6c 66 2c 20 64  Regexes (self, d
1480: 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20  Graph):.        
1490: 22 63 68 65 63 6b 20 76 61 6c 69 64 69 74 79 20  "check validity 
14a0: 6f 66 20 72 65 67 65 78 65 73 22 0a 20 20 20 20  of regexes".    
14b0: 20 20 20 20 61 52 65 67 65 78 20 3d 20 73 65 74      aRegex = set
14c0: 28 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20 5f  ().        for _
14d0: 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61 70 68  , dVal in dGraph
14e0: 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20  .items():.      
14f0: 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f 76 61        if "<re_va
1500: 6c 75 65 3e 22 20 69 6e 20 64 56 61 6c 3a 0a 20  lue>" in dVal:. 
1510: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
1520: 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64 56 61  or sRegex in dVa
1530: 6c 5b 22 3c 72 65 5f 76 61 6c 75 65 3e 22 5d 3a  l["<re_value>"]:
1540: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1550: 20 20 20 20 20 69 66 20 73 52 65 67 65 78 20 6e       if sRegex n
1560: 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a 20 20  ot in aRegex:.  
1570: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1580: 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68 65 63        self._chec
1590: 6b 52 65 67 65 78 28 73 52 65 67 65 78 29 0a 20  kRegex(sRegex). 
15a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15b0: 20 20 20 20 20 20 20 61 52 65 67 65 78 2e 61 64         aRegex.ad
15c0: 64 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  d(sRegex).      
15d0: 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f 6d 6f        if "<re_mo
15e0: 72 70 68 3e 22 20 69 6e 20 64 56 61 6c 3a 0a 20  rph>" in dVal:. 
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66                 f
1600: 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64 56 61  or sRegex in dVa
1610: 6c 5b 22 3c 72 65 5f 6d 6f 72 70 68 3e 22 5d 3a  l["<re_morph>"]:
1620: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1630: 20 20 20 20 20 69 66 20 73 52 65 67 65 78 20 6e       if sRegex n
1640: 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a 20 20  ot in aRegex:.  
1650: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1660: 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68 65 63        self._chec
1670: 6b 52 65 67 65 78 28 73 52 65 67 65 78 29 0a 20  kRegex(sRegex). 
1680: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1690: 20 20 20 20 20 20 20 61 52 65 67 65 78 2e 61 64         aRegex.ad
16a0: 64 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  d(sRegex).      
16b0: 20 20 61 52 65 67 65 78 2e 63 6c 65 61 72 28 29    aRegex.clear()
16c0: 0a 0a 20 20 20 20 64 65 66 20 5f 63 68 65 63 6b  ..    def _check
16d0: 52 65 67 65 78 20 28 73 65 6c 66 2c 20 73 52 65  Regex (self, sRe
16e0: 67 65 78 29 3a 0a 20 20 20 20 20 20 20 20 23 70  gex):.        #p
16f0: 72 69 6e 74 28 73 52 65 67 65 78 29 0a 20 20 20  rint(sRegex).   
1700: 20 20 20 20 20 69 66 20 22 c2 ac 22 20 69 6e 20       if ".." in 
1710: 73 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20 20  sRegex:.        
1720: 20 20 20 20 73 50 61 74 74 65 72 6e 2c 20 73 4e      sPattern, sN
1730: 65 67 50 61 74 74 65 72 6e 20 3d 20 73 52 65 67  egPattern = sReg
1740: 65 78 2e 73 70 6c 69 74 28 22 c2 ac 22 29 0a 20  ex.split(".."). 
1750: 20 20 20 20 20 20 20 20 20 20 20 74 72 79 3a 0a             try:.
1760: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1770: 69 66 20 6e 6f 74 20 73 4e 65 67 50 61 74 74 65  if not sNegPatte
1780: 72 6e 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  rn:.            
1790: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 23          print("#
17a0: 20 57 61 72 6e 69 6e 67 21 20 45 6d 70 74 79 20   Warning! Empty 
17b0: 6e 65 67 70 61 74 74 65 72 6e 3a 22 2c 20 73 52  negpattern:", sR
17c0: 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20 20  egex).          
17d0: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
17e0: 28 73 50 61 74 74 65 72 6e 29 0a 20 20 20 20 20  (sPattern).     
17f0: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 73 4e             if sN
1800: 65 67 50 61 74 74 65 72 6e 20 21 3d 20 22 2a 22  egPattern != "*"
1810: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1820: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
1830: 28 73 4e 65 67 50 61 74 74 65 72 6e 29 0a 20 20  (sNegPattern).  
1840: 20 20 20 20 20 20 20 20 20 20 65 78 63 65 70 74            except
1850: 20 72 65 2e 65 72 72 6f 72 3a 0a 20 20 20 20 20   re.error:.     
1860: 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74             print
1870: 28 22 23 20 45 72 72 6f 72 2e 20 57 72 6f 6e 67  ("# Error. Wrong
1880: 20 72 65 67 65 78 3a 22 2c 20 73 52 65 67 65 78   regex:", sRegex
1890: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ).              
18a0: 20 20 65 78 69 74 28 29 0a 20 20 20 20 20 20 20    exit().       
18b0: 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20   else:.         
18c0: 20 20 20 74 72 79 3a 0a 20 20 20 20 20 20 20 20     try:.        
18d0: 20 20 20 20 20 20 20 20 69 66 20 6e 6f 74 20 73          if not s
18e0: 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20 20 20  Regex:.         
18f0: 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74             print
1900: 28 22 23 20 57 61 72 6e 69 6e 67 21 20 45 6d 70  ("# Warning! Emp
1910: 74 79 20 70 61 74 74 65 72 6e 3a 22 2c 20 73 52  ty pattern:", sR
1920: 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20 20  egex).          
1930: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
1940: 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20  (sRegex).       
1950: 20 20 20 20 20 65 78 63 65 70 74 20 72 65 2e 65       except re.e
1960: 72 72 6f 72 3a 0a 20 20 20 20 20 20 20 20 20 20  rror:.          
1970: 20 20 20 20 20 20 70 72 69 6e 74 28 22 23 20 45        print("# E
1980: 72 72 6f 72 2e 20 57 72 6f 6e 67 20 72 65 67 65  rror. Wrong rege
1990: 78 3a 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20  x:", sRegex).   
19a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 65 78 69               exi
19b0: 74 28 29 0a 0a 0a 63 6c 61 73 73 20 4e 6f 64 65  t()...class Node
19c0: 3a 0a 20 20 20 20 22 22 22 4e 6f 64 65 20 6f 66  :.    """Node of
19d0: 20 74 68 65 20 72 75 6c 65 20 67 72 61 70 68 22   the rule graph"
19e0: 22 22 0a 0a 20 20 20 20 4e 65 78 74 49 64 20 3d  ""..    NextId =
19f0: 20 30 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69 6e   0..    def __in
1a00: 69 74 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20  it__ (self):.   
1a10: 20 20 20 20 20 73 65 6c 66 2e 69 20 3d 20 4e 6f       self.i = No
1a20: 64 65 2e 4e 65 78 74 49 64 0a 20 20 20 20 20 20  de.NextId.      
1a30: 20 20 4e 6f 64 65 2e 4e 65 78 74 49 64 20 2b 3d    Node.NextId +=
1a40: 20 31 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e   1.        self.
1a50: 62 46 69 6e 61 6c 20 3d 20 46 61 6c 73 65 0a 20  bFinal = False. 
1a60: 20 20 20 20 20 20 20 73 65 6c 66 2e 64 41 72 63         self.dArc
1a70: 73 20 3d 20 7b 7d 20 20 20 20 20 20 20 20 20 20  s = {}          
1a80: 23 20 6b 65 79 3a 20 61 72 63 20 76 61 6c 75 65  # key: arc value
1a90: 3b 20 76 61 6c 75 65 3a 20 61 20 6e 6f 64 65 0a  ; value: a node.
1aa0: 0a 20 20 20 20 40 63 6c 61 73 73 6d 65 74 68 6f  .    @classmetho
1ab0: 64 0a 20 20 20 20 64 65 66 20 72 65 73 65 74 4e  d.    def resetN
1ac0: 65 78 74 49 64 20 28 63 6c 73 29 3a 0a 20 20 20  extId (cls):.   
1ad0: 20 20 20 20 20 22 72 65 73 65 74 20 74 6f 20 30       "reset to 0
1ae0: 20 74 68 65 20 6e 6f 64 65 20 63 6f 75 6e 74 65   the node counte
1af0: 72 22 0a 20 20 20 20 20 20 20 20 63 6c 73 2e 4e  r".        cls.N
1b00: 65 78 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64  extId = 0..    d
1b10: 65 66 20 5f 5f 73 74 72 5f 5f 20 28 73 65 6c 66  ef __str__ (self
1b20: 29 3a 0a 20 20 20 20 20 20 20 20 23 20 43 61 75  ):.        # Cau
1b30: 74 69 6f 6e 21 20 74 68 69 73 20 66 75 6e 63 74  tion! this funct
1b40: 69 6f 6e 20 69 73 20 75 73 65 64 20 66 6f 72 20  ion is used for 
1b50: 68 61 73 68 69 6e 67 20 61 6e 64 20 63 6f 6d 70  hashing and comp
1b60: 61 72 69 73 6f 6e 21 0a 20 20 20 20 20 20 20 20  arison!.        
1b70: 63 46 69 6e 61 6c 20 3d 20 22 31 22 20 20 69 66  cFinal = "1"  if
1b80: 20 73 65 6c 66 2e 62 46 69 6e 61 6c 20 20 65 6c   self.bFinal  el
1b90: 73 65 20 22 30 22 0a 20 20 20 20 20 20 20 20 6c  se "0".        l
1ba0: 20 3d 20 5b 63 46 69 6e 61 6c 5d 0a 20 20 20 20   = [cFinal].    
1bb0: 20 20 20 20 66 6f 72 20 28 6b 65 79 2c 20 6f 4e      for (key, oN
1bc0: 6f 64 65 29 20 69 6e 20 73 65 6c 66 2e 64 41 72  ode) in self.dAr
1bd0: 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  cs.items():.    
1be0: 20 20 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64          l.append
1bf0: 28 73 74 72 28 6b 65 79 29 29 0a 20 20 20 20 20  (str(key)).     
1c00: 20 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28         l.append(
1c10: 73 74 72 28 6f 4e 6f 64 65 2e 69 29 29 0a 20 20  str(oNode.i)).  
1c20: 20 20 20 20 20 20 72 65 74 75 72 6e 20 22 5f 22        return "_"
1c30: 2e 6a 6f 69 6e 28 6c 29 0a 0a 20 20 20 20 64 65  .join(l)..    de
1c40: 66 20 5f 5f 68 61 73 68 5f 5f 20 28 73 65 6c 66  f __hash__ (self
1c50: 29 3a 0a 20 20 20 20 20 20 20 20 23 20 55 73 65  ):.        # Use
1c60: 64 20 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20  d as a key in a 
1c70: 70 79 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72  python dictionar
1c80: 79 2e 0a 20 20 20 20 20 20 20 20 72 65 74 75 72  y..        retur
1c90: 6e 20 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29  n self.__str__()
1ca0: 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 0a 20 20 20  .__hash__()..   
1cb0: 20 64 65 66 20 5f 5f 65 71 5f 5f 20 28 73 65 6c   def __eq__ (sel
1cc0: 66 2c 20 6f 74 68 65 72 29 3a 0a 20 20 20 20 20  f, other):.     
1cd0: 20 20 20 23 20 55 73 65 64 20 61 73 20 61 20 6b     # Used as a k
1ce0: 65 79 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64  ey in a python d
1cf0: 69 63 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20  ictionary..     
1d00: 20 20 20 23 20 4e 6f 64 65 73 20 61 72 65 20 65     # Nodes are e
1d10: 71 75 69 76 61 6c 65 6e 74 20 69 66 20 74 68 65  quivalent if the
1d20: 79 20 68 61 76 65 20 69 64 65 6e 74 69 63 61 6c  y have identical
1d30: 20 61 72 63 73 2c 20 61 6e 64 20 65 61 63 68 20   arcs, and each 
1d40: 69 64 65 6e 74 69 63 61 6c 20 61 72 63 20 6c 65  identical arc le
1d50: 61 64 73 20 74 6f 20 69 64 65 6e 74 69 63 61 6c  ads to identical
1d60: 20 73 74 61 74 65 73 2e 0a 20 20 20 20 20 20 20   states..       
1d70: 20 72 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73   return self.__s
1d80: 74 72 5f 5f 28 29 20 3d 3d 20 6f 74 68 65 72 2e  tr__() == other.
1d90: 5f 5f 73 74 72 5f 5f 28 29 0a 0a 20 20 20 20 64  __str__()..    d
1da0: 65 66 20 67 65 74 4e 6f 64 65 41 73 44 69 63 74  ef getNodeAsDict
1db0: 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20   (self):.       
1dc0: 20 22 72 65 74 75 72 6e 73 20 74 68 65 20 6e 6f   "returns the no
1dd0: 64 65 20 61 73 20 61 20 64 69 63 74 69 6f 6e 61  de as a dictiona
1de0: 72 79 20 73 74 72 75 63 74 75 72 65 22 0a 20 20  ry structure".  
1df0: 20 20 20 20 20 20 64 4e 6f 64 65 20 3d 20 7b 7d        dNode = {}
1e00: 0a 20 20 20 20 20 20 20 20 64 52 65 56 61 6c 75  .        dReValu
1e10: 65 20 3d 20 7b 7d 20 20 20 23 20 72 65 67 65 78  e = {}   # regex
1e20: 20 66 6f 72 20 74 6f 6b 65 6e 20 76 61 6c 75 65   for token value
1e30: 73 0a 20 20 20 20 20 20 20 20 64 52 65 4d 6f 72  s.        dReMor
1e40: 70 68 20 3d 20 7b 7d 20 20 20 23 20 72 65 67 65  ph = {}   # rege
1e50: 78 20 66 6f 72 20 6d 6f 72 70 68 0a 20 20 20 20  x for morph.    
1e60: 20 20 20 20 64 4d 6f 72 70 68 20 3d 20 7b 7d 20      dMorph = {} 
1e70: 20 20 20 20 23 20 73 69 6d 70 6c 65 20 73 65 61      # simple sea
1e80: 72 63 68 20 69 6e 20 6d 6f 72 70 68 0a 20 20 20  rch in morph.   
1e90: 20 20 20 20 20 64 4c 65 6d 6d 61 20 3d 20 7b 7d       dLemma = {}
1ea0: 0a 20 20 20 20 20 20 20 20 64 4d 65 74 61 20 3d  .        dMeta =
1eb0: 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 54 61 67   {}.        dTag
1ec0: 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 52   = {}.        dR
1ed0: 75 6c 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20  ule = {}.       
1ee0: 20 66 6f 72 20 73 41 72 63 2c 20 6f 4e 6f 64 65   for sArc, oNode
1ef0: 20 69 6e 20 73 65 6c 66 2e 64 41 72 63 73 2e 69   in self.dArcs.i
1f00: 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20  tems():.        
1f10: 20 20 20 20 69 66 20 73 41 72 63 2e 73 74 61 72      if sArc.star
1f20: 74 73 77 69 74 68 28 22 40 22 29 20 61 6e 64 20  tswith("@") and 
1f30: 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20  len(sArc) > 1:. 
1f40: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64                 d
1f50: 52 65 4d 6f 72 70 68 5b 73 41 72 63 5b 31 3a 5d  ReMorph[sArc[1:]
1f60: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
1f70: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
1f80: 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74   elif sArc.start
1f90: 73 77 69 74 68 28 22 24 22 29 20 61 6e 64 20 6c  swith("$") and l
1fa0: 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20  en(sArc) > 1:.  
1fb0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 4d                dM
1fc0: 6f 72 70 68 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d  orph[sArc[1:]] =
1fd0: 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28   oNode.__hash__(
1fe0: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c  ).            el
1ff0: 69 66 20 73 41 72 63 2e 73 74 61 72 74 73 77 69  if sArc.startswi
2000: 74 68 28 22 7e 22 29 20 61 6e 64 20 6c 65 6e 28  th("~") and len(
2010: 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20 20  sArc) > 1:.     
2020: 20 20 20 20 20 20 20 20 20 20 20 64 52 65 56 61             dReVa
2030: 6c 75 65 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20  lue[sArc[1:]] = 
2040: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
2050: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 69  .            eli
2060: 66 20 73 41 72 63 2e 73 74 61 72 74 73 77 69 74  f sArc.startswit
2070: 68 28 22 3e 22 29 20 61 6e 64 20 6c 65 6e 28 73  h(">") and len(s
2080: 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20 20 20  Arc) > 1:.      
2090: 20 20 20 20 20 20 20 20 20 20 64 4c 65 6d 6d 61            dLemma
20a0: 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f  [sArc[1:]] = oNo
20b0: 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20  de.__hash__().  
20c0: 20 20 20 20 20 20 20 20 20 20 65 6c 69 66 20 73            elif s
20d0: 41 72 63 2e 73 74 61 72 74 73 77 69 74 68 28 22  Arc.startswith("
20e0: 2a 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63  *") and len(sArc
20f0: 29 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20  ) > 1:.         
2100: 20 20 20 20 20 20 20 64 4d 65 74 61 5b 73 41 72         dMeta[sAr
2110: 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f  c[1:]] = oNode._
2120: 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20  _hash__().      
2130: 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e        elif sArc.
2140: 73 74 61 72 74 73 77 69 74 68 28 22 2f 22 29 20  startswith("/") 
2150: 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20  and len(sArc) > 
2160: 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1:.             
2170: 20 20 20 64 54 61 67 5b 73 41 72 63 5b 31 3a 5d     dTag[sArc[1:]
2180: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
2190: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
21a0: 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74   elif sArc.start
21b0: 73 77 69 74 68 28 22 23 23 22 29 3a 0a 20 20 20  swith("##"):.   
21c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 64 52 75               dRu
21d0: 6c 65 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f  le[sArc[1:]] = o
21e0: 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a  Node.__hash__().
21f0: 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65              else
2200: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
2210: 20 20 64 4e 6f 64 65 5b 73 41 72 63 5d 20 3d 20    dNode[sArc] = 
2220: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
2230: 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65 56  .        if dReV
2240: 61 6c 75 65 3a 0a 20 20 20 20 20 20 20 20 20 20  alue:.          
2250: 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 76 61 6c    dNode["<re_val
2260: 75 65 3e 22 5d 20 3d 20 64 52 65 56 61 6c 75 65  ue>"] = dReValue
2270: 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65 4d  .        if dReM
2280: 6f 72 70 68 3a 0a 20 20 20 20 20 20 20 20 20 20  orph:.          
2290: 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 6d 6f 72    dNode["<re_mor
22a0: 70 68 3e 22 5d 20 3d 20 64 52 65 4d 6f 72 70 68  ph>"] = dReMorph
22b0: 0a 20 20 20 20 20 20 20 20 69 66 20 64 4d 6f 72  .        if dMor
22c0: 70 68 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ph:.            
22d0: 64 4e 6f 64 65 5b 22 3c 6d 6f 72 70 68 3e 22 5d  dNode["<morph>"]
22e0: 20 3d 20 64 4d 6f 72 70 68 0a 20 20 20 20 20 20   = dMorph.      
22f0: 20 20 69 66 20 64 4c 65 6d 6d 61 3a 0a 20 20 20    if dLemma:.   
2300: 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22           dNode["
2310: 3c 6c 65 6d 6d 61 73 3e 22 5d 20 3d 20 64 4c 65  <lemmas>"] = dLe
2320: 6d 6d 61 0a 20 20 20 20 20 20 20 20 69 66 20 64  mma.        if d
2330: 54 61 67 3a 0a 20 20 20 20 20 20 20 20 20 20 20  Tag:.           
2340: 20 64 4e 6f 64 65 5b 22 3c 74 61 67 73 3e 22 5d   dNode["<tags>"]
2350: 20 3d 20 64 54 61 67 0a 20 20 20 20 20 20 20 20   = dTag.        
2360: 69 66 20 64 4d 65 74 61 3a 0a 20 20 20 20 20 20  if dMeta:.      
2370: 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 6d 65        dNode["<me
2380: 74 61 3e 22 5d 20 3d 20 64 4d 65 74 61 0a 20 20  ta>"] = dMeta.  
2390: 20 20 20 20 20 20 69 66 20 64 52 75 6c 65 3a 0a        if dRule:.
23a0: 20 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64              dNod
23b0: 65 5b 22 3c 72 75 6c 65 73 3e 22 5d 20 3d 20 64  e["<rules>"] = d
23c0: 52 75 6c 65 0a 20 20 20 20 20 20 20 20 23 69 66  Rule.        #if
23d0: 20 73 65 6c 66 2e 62 46 69 6e 61 6c 3a 0a 20 20   self.bFinal:.  
23e0: 20 20 20 20 20 20 23 20 20 20 20 64 4e 6f 64 65        #    dNode
23f0: 5b 22 3c 66 69 6e 61 6c 3e 22 5d 20 3d 20 31 0a  ["<final>"] = 1.
2400: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64          return d
2410: 4e 6f 64 65 0a                                   Node.