Grammalecte  Hex Artifact Content

Artifact 0a2000eec82782e9fa3f729cd67db563bdd3603a4515e0d1104292cf1c9fb060:


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: 41 52 47 22 2c 20 65 6e 64 3d 22 22 29 0a 0a 20  ARG", end="").. 
0150: 20 20 20 20 20 20 20 23 20 50 72 65 70 61 72 69         # Prepari
0160: 6e 67 20 44 41 52 47 0a 20 20 20 20 20 20 20 20  ng DARG.        
0170: 73 65 6c 66 2e 73 4c 61 6e 67 43 6f 64 65 20 3d  self.sLangCode =
0180: 20 73 4c 61 6e 67 43 6f 64 65 0a 20 20 20 20 20   sLangCode.     
0190: 20 20 20 73 65 6c 66 2e 6e 52 75 6c 65 20 3d 20     self.nRule = 
01a0: 6c 65 6e 28 6c 52 75 6c 65 29 0a 20 20 20 20 20  len(lRule).     
01b0: 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f 75     self.aPreviou
01c0: 73 52 75 6c 65 20 3d 20 5b 5d 0a 20 20 20 20 20  sRule = [].     
01d0: 20 20 20 4e 6f 64 65 2e 72 65 73 65 74 4e 65 78     Node.resetNex
01e0: 74 49 64 28 29 0a 20 20 20 20 20 20 20 20 73 65  tId().        se
01f0: 6c 66 2e 6f 52 6f 6f 74 20 3d 20 4e 6f 64 65 28  lf.oRoot = Node(
0200: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c  ).        self.l
0210: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 3d  UncheckedNodes =
0220: 20 5b 5d 20 20 23 20 6c 69 73 74 20 6f 66 20 6e   []  # list of n
0230: 6f 64 65 73 20 74 68 61 74 20 68 61 76 65 20 6e  odes that have n
0240: 6f 74 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20  ot been checked 
0250: 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e  for duplication.
0260: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d  .        self.lM
0270: 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 20 3d 20  inimizedNodes = 
0280: 7b 7d 20 20 23 20 6c 69 73 74 20 6f 66 20 75 6e  {}  # list of un
0290: 69 71 75 65 20 6e 6f 64 65 73 20 74 68 61 74 20  ique nodes that 
02a0: 68 61 76 65 20 62 65 65 6e 20 63 68 65 63 6b 65  have been checke
02b0: 64 20 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f  d for duplicatio
02c0: 6e 2e 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  n..        self.
02d0: 6e 4e 6f 64 65 20 3d 20 30 0a 20 20 20 20 20 20  nNode = 0.      
02e0: 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a    self.nArc = 0.
02f0: 0a 20 20 20 20 20 20 20 20 23 20 62 75 69 6c 64  .        # build
0300: 0a 20 20 20 20 20 20 20 20 6c 52 75 6c 65 2e 73  .        lRule.s
0310: 6f 72 74 28 29 0a 20 20 20 20 20 20 20 20 66 6f  ort().        fo
0320: 72 20 61 52 75 6c 65 20 69 6e 20 6c 52 75 6c 65  r aRule in lRule
0330: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 73 65  :.            se
0340: 6c 66 2e 69 6e 73 65 72 74 28 61 52 75 6c 65 29  lf.insert(aRule)
0350: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 66 69  .        self.fi
0360: 6e 69 73 68 28 29 0a 20 20 20 20 20 20 20 20 73  nish().        s
0370: 65 6c 66 2e 63 6f 75 6e 74 4e 6f 64 65 73 28 29  elf.countNodes()
0380: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 63 6f  .        self.co
0390: 75 6e 74 41 72 63 73 28 29 0a 20 20 20 20 20 20  untArcs().      
03a0: 20 20 73 65 6c 66 2e 64 69 73 70 6c 61 79 49 6e    self.displayIn
03b0: 66 6f 28 29 0a 0a 20 20 20 20 23 20 42 55 49 4c  fo()..    # BUIL
03c0: 44 20 44 41 52 47 0a 20 20 20 20 64 65 66 20 69  D DARG.    def i
03d0: 6e 73 65 72 74 20 28 73 65 6c 66 2c 20 61 52 75  nsert (self, aRu
03e0: 6c 65 29 3a 0a 20 20 20 20 20 20 20 20 22 69 6e  le):.        "in
03f0: 73 65 72 74 20 61 20 6e 65 77 20 72 75 6c 65 20  sert a new rule 
0400: 28 74 6f 6b 65 6e 73 20 6d 75 73 74 20 62 65 20  (tokens must be 
0410: 69 6e 73 65 72 74 65 64 20 69 6e 20 6f 72 64 65  inserted in orde
0420: 72 29 22 0a 20 20 20 20 20 20 20 20 69 66 20 61  r)".        if a
0430: 52 75 6c 65 20 3c 20 73 65 6c 66 2e 61 50 72 65  Rule < self.aPre
0440: 76 69 6f 75 73 52 75 6c 65 3a 0a 20 20 20 20 20  viousRule:.     
0450: 20 20 20 20 20 20 20 65 78 69 74 28 22 23 20 45         exit("# E
0460: 72 72 6f 72 3a 20 74 6f 6b 65 6e 73 20 6d 75 73  rror: tokens mus
0470: 74 20 62 65 20 69 6e 73 65 72 74 65 64 20 69 6e  t be inserted in
0480: 20 6f 72 64 65 72 2e 22 29 0a 0a 20 20 20 20 20   order.")..     
0490: 20 20 20 23 20 66 69 6e 64 20 63 6f 6d 6d 6f 6e     # find common
04a0: 20 70 72 65 66 69 78 20 62 65 74 77 65 65 6e 20   prefix between 
04b0: 77 6f 72 64 20 61 6e 64 20 70 72 65 76 69 6f 75  word and previou
04c0: 73 20 77 6f 72 64 0a 20 20 20 20 20 20 20 20 6e  s word.        n
04d0: 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 20 3d 20 30  CommonPrefix = 0
04e0: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 69 20 69  .        for i i
04f0: 6e 20 72 61 6e 67 65 28 6d 69 6e 28 6c 65 6e 28  n range(min(len(
0500: 61 52 75 6c 65 29 2c 20 6c 65 6e 28 73 65 6c 66  aRule), len(self
0510: 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 29 29  .aPreviousRule))
0520: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  ):.            i
0530: 66 20 61 52 75 6c 65 5b 69 5d 20 21 3d 20 73 65  f aRule[i] != se
0540: 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65  lf.aPreviousRule
0550: 5b 69 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20  [i]:.           
0560: 20 20 20 20 20 62 72 65 61 6b 0a 20 20 20 20 20       break.     
0570: 20 20 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72         nCommonPr
0580: 65 66 69 78 20 2b 3d 20 31 0a 0a 20 20 20 20 20  efix += 1..     
0590: 20 20 20 23 20 43 68 65 63 6b 20 74 68 65 20 6c     # Check the l
05a0: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 66  UncheckedNodes f
05b0: 6f 72 20 72 65 64 75 6e 64 61 6e 74 20 6e 6f 64  or redundant nod
05c0: 65 73 2c 20 70 72 6f 63 65 65 64 69 6e 67 20 66  es, proceeding f
05d0: 72 6f 6d 20 6c 61 73 74 0a 20 20 20 20 20 20 20  rom last.       
05e0: 20 23 20 6f 6e 65 20 64 6f 77 6e 20 74 6f 20 74   # one down to t
05f0: 68 65 20 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78  he common prefix
0600: 20 73 69 7a 65 2e 20 54 68 65 6e 20 74 72 75 6e   size. Then trun
0610: 63 61 74 65 20 74 68 65 20 6c 69 73 74 20 61 74  cate the list at
0620: 20 74 68 61 74 20 70 6f 69 6e 74 2e 0a 20 20 20   that point..   
0630: 20 20 20 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d       self._minim
0640: 69 7a 65 28 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69  ize(nCommonPrefi
0650: 78 29 0a 0a 20 20 20 20 20 20 20 20 23 20 61 64  x)..        # ad
0660: 64 20 74 68 65 20 73 75 66 66 69 78 2c 20 73 74  d the suffix, st
0670: 61 72 74 69 6e 67 20 66 72 6f 6d 20 74 68 65 20  arting from the 
0680: 63 6f 72 72 65 63 74 20 6e 6f 64 65 20 6d 69 64  correct node mid
0690: 2d 77 61 79 20 74 68 72 6f 75 67 68 20 74 68 65  -way through the
06a0: 20 67 72 61 70 68 0a 20 20 20 20 20 20 20 20 69   graph.        i
06b0: 66 20 6c 65 6e 28 73 65 6c 66 2e 6c 55 6e 63 68  f len(self.lUnch
06c0: 65 63 6b 65 64 4e 6f 64 65 73 29 20 3d 3d 20 30  eckedNodes) == 0
06d0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  :.            oN
06e0: 6f 64 65 20 3d 20 73 65 6c 66 2e 6f 52 6f 6f 74  ode = self.oRoot
06f0: 0a 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20  .        else:. 
0700: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
0710: 20 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b   = self.lUncheck
0720: 65 64 4e 6f 64 65 73 5b 2d 31 5d 5b 32 5d 0a 0a  edNodes[-1][2]..
0730: 20 20 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 3d          iToken =
0740: 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 0a 20   nCommonPrefix. 
0750: 20 20 20 20 20 20 20 66 6f 72 20 73 54 6f 6b 65         for sToke
0760: 6e 20 69 6e 20 61 52 75 6c 65 5b 6e 43 6f 6d 6d  n in aRule[nComm
0770: 6f 6e 50 72 65 66 69 78 3a 5d 3a 0a 20 20 20 20  onPrefix:]:.    
0780: 20 20 20 20 20 20 20 20 6f 4e 65 78 74 4e 6f 64          oNextNod
0790: 65 20 3d 20 4e 6f 64 65 28 29 0a 20 20 20 20 20  e = Node().     
07a0: 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72         oNode.dAr
07b0: 63 73 5b 73 54 6f 6b 65 6e 5d 20 3d 20 6f 4e 65  cs[sToken] = oNe
07c0: 78 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20 20  xtNode.         
07d0: 20 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b     self.lUncheck
07e0: 65 64 4e 6f 64 65 73 2e 61 70 70 65 6e 64 28 28  edNodes.append((
07f0: 6f 4e 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f  oNode, sToken, o
0800: 4e 65 78 74 4e 6f 64 65 29 29 0a 20 20 20 20 20  NextNode)).     
0810: 20 20 20 20 20 20 20 69 66 20 69 54 6f 6b 65 6e         if iToken
0820: 20 3d 3d 20 28 6c 65 6e 28 61 52 75 6c 65 29 20   == (len(aRule) 
0830: 2d 20 32 29 3a 0a 20 20 20 20 20 20 20 20 20 20  - 2):.          
0840: 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e        oNode.bFin
0850: 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20 20 20  al = True.      
0860: 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 2b 3d 20        iToken += 
0870: 31 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  1.            oN
0880: 6f 64 65 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a  ode = oNextNode.
0890: 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46          oNode.bF
08a0: 69 6e 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20  inal = True.    
08b0: 20 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f      self.aPrevio
08c0: 75 73 52 75 6c 65 20 3d 20 61 52 75 6c 65 0a 0a  usRule = aRule..
08d0: 20 20 20 20 64 65 66 20 66 69 6e 69 73 68 20 28      def finish (
08e0: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
08f0: 6d 69 6e 69 6d 69 7a 65 20 75 6e 63 68 65 63 6b  minimize uncheck
0900: 65 64 20 6e 6f 64 65 73 22 0a 20 20 20 20 20 20  ed nodes".      
0910: 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a 65    self._minimize
0920: 28 30 29 0a 0a 20 20 20 20 64 65 66 20 5f 6d 69  (0)..    def _mi
0930: 6e 69 6d 69 7a 65 20 28 73 65 6c 66 2c 20 64 6f  nimize (self, do
0940: 77 6e 54 6f 29 3a 0a 20 20 20 20 20 20 20 20 23  wnTo):.        #
0950: 20 70 72 6f 63 65 65 64 20 66 72 6f 6d 20 74 68   proceed from th
0960: 65 20 6c 65 61 66 20 75 70 20 74 6f 20 61 20 63  e leaf up to a c
0970: 65 72 74 61 69 6e 20 70 6f 69 6e 74 0a 20 20 20  ertain point.   
0980: 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20 72 61       for i in ra
0990: 6e 67 65 28 20 6c 65 6e 28 73 65 6c 66 2e 6c 55  nge( len(self.lU
09a0: 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 29 2d 31  ncheckedNodes)-1
09b0: 2c 20 64 6f 77 6e 54 6f 2d 31 2c 20 2d 31 20 29  , downTo-1, -1 )
09c0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  :.            oN
09d0: 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f 43 68  ode, sToken, oCh
09e0: 69 6c 64 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6c  ildNode = self.l
09f0: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 5b 69  UncheckedNodes[i
0a00: 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  ].            if
0a10: 20 6f 43 68 69 6c 64 4e 6f 64 65 20 69 6e 20 73   oChildNode in s
0a20: 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f  elf.lMinimizedNo
0a30: 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20 20 20  des:.           
0a40: 20 20 20 20 20 23 20 72 65 70 6c 61 63 65 20 74       # replace t
0a50: 68 65 20 63 68 69 6c 64 20 77 69 74 68 20 74 68  he child with th
0a60: 65 20 70 72 65 76 69 6f 75 73 6c 79 20 65 6e 63  e previously enc
0a70: 6f 75 6e 74 65 72 65 64 20 6f 6e 65 0a 20 20 20  ountered one.   
0a80: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f               oNo
0a90: 64 65 2e 64 41 72 63 73 5b 73 54 6f 6b 65 6e 5d  de.dArcs[sToken]
0aa0: 20 3d 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a   = self.lMinimiz
0ab0: 65 64 4e 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f  edNodes[oChildNo
0ac0: 64 65 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20  de].            
0ad0: 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20  else:.          
0ae0: 20 20 20 20 20 20 23 20 61 64 64 20 74 68 65 20        # add the 
0af0: 73 74 61 74 65 20 74 6f 20 74 68 65 20 6d 69 6e  state to the min
0b00: 69 6d 69 7a 65 64 20 6e 6f 64 65 73 2e 0a 20 20  imized nodes..  
0b10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65                se
0b20: 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64  lf.lMinimizedNod
0b30: 65 73 5b 6f 43 68 69 6c 64 4e 6f 64 65 5d 20 3d  es[oChildNode] =
0b40: 20 6f 43 68 69 6c 64 4e 6f 64 65 0a 20 20 20 20   oChildNode.    
0b50: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e          self.lUn
0b60: 63 68 65 63 6b 65 64 4e 6f 64 65 73 2e 70 6f 70  checkedNodes.pop
0b70: 28 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e  ()..    def coun
0b80: 74 4e 6f 64 65 73 20 28 73 65 6c 66 29 3a 0a 20  tNodes (self):. 
0b90: 20 20 20 20 20 20 20 22 63 6f 75 6e 74 20 6e 6f         "count no
0ba0: 64 65 73 20 77 69 74 68 69 6e 20 74 68 65 20 77  des within the w
0bb0: 68 6f 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20  hole graph".    
0bc0: 20 20 20 20 73 65 6c 66 2e 6e 4e 6f 64 65 20 3d      self.nNode =
0bd0: 20 6c 65 6e 28 73 65 6c 66 2e 6c 4d 69 6e 69 6d   len(self.lMinim
0be0: 69 7a 65 64 4e 6f 64 65 73 29 0a 0a 20 20 20 20  izedNodes)..    
0bf0: 64 65 66 20 63 6f 75 6e 74 41 72 63 73 20 28 73  def countArcs (s
0c00: 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22 63  elf):.        "c
0c10: 6f 75 6e 74 20 61 72 63 73 20 77 69 74 68 69 6e  ount arcs within
0c20: 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61 70 68   the whole graph
0c30: 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e  ".        self.n
0c40: 41 72 63 20 3d 20 30 0a 20 20 20 20 20 20 20 20  Arc = 0.        
0c50: 66 6f 72 20 6f 4e 6f 64 65 20 69 6e 20 73 65 6c  for oNode in sel
0c60: 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65  f.lMinimizedNode
0c70: 73 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 73  s:.            s
0c80: 65 6c 66 2e 6e 41 72 63 20 2b 3d 20 6c 65 6e 28  elf.nArc += len(
0c90: 6f 4e 6f 64 65 2e 64 41 72 63 73 29 0a 0a 20 20  oNode.dArcs)..  
0ca0: 20 20 64 65 66 20 64 69 73 70 6c 61 79 49 6e 66    def displayInf
0cb0: 6f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20  o (self):.      
0cc0: 20 20 22 64 69 73 70 6c 61 79 20 69 6e 66 6f 72    "display infor
0cd0: 6d 61 74 69 6f 6e 73 20 61 62 6f 75 74 20 74 68  mations about th
0ce0: 65 20 72 75 6c 65 20 67 72 61 70 68 22 0a 20 20  e rule graph".  
0cf0: 20 20 20 20 20 20 70 72 69 6e 74 28 22 3a 20 7b        print(": {
0d00: 3a 3e 31 30 2c 7d 20 72 75 6c 65 73 2c 20 20 7b  :>10,} rules,  {
0d10: 3a 3e 31 30 2c 7d 20 6e 6f 64 65 73 2c 20 20 7b  :>10,} nodes,  {
0d20: 3a 3e 31 30 2c 7d 20 61 72 63 73 22 2e 66 6f 72  :>10,} arcs".for
0d30: 6d 61 74 28 73 65 6c 66 2e 6e 52 75 6c 65 2c 20  mat(self.nRule, 
0d40: 73 65 6c 66 2e 6e 4e 6f 64 65 2c 20 73 65 6c 66  self.nNode, self
0d50: 2e 6e 41 72 63 29 29 0a 0a 20 20 20 20 64 65 66  .nArc))..    def
0d60: 20 63 72 65 61 74 65 47 72 61 70 68 20 28 73 65   createGraph (se
0d70: 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22 63 72  lf):.        "cr
0d80: 65 61 74 65 20 74 68 65 20 67 72 61 70 68 20 61  eate the graph a
0d90: 73 20 61 20 64 69 63 74 69 6f 6e 61 72 79 22 0a  s a dictionary".
0da0: 20 20 20 20 20 20 20 20 64 47 72 61 70 68 20 3d          dGraph =
0db0: 20 7b 20 30 3a 20 73 65 6c 66 2e 6f 52 6f 6f 74   { 0: self.oRoot
0dc0: 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29  .getNodeAsDict()
0dd0: 20 7d 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6f   }.        for o
0de0: 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69  Node in self.lMi
0df0: 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20  nimizedNodes:.  
0e00: 20 20 20 20 20 20 20 20 20 20 73 48 61 73 68 49            sHashI
0e10: 64 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  d = oNode.__hash
0e20: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
0e30: 20 69 66 20 73 48 61 73 68 49 64 20 6e 6f 74 20   if sHashId not 
0e40: 69 6e 20 64 47 72 61 70 68 3a 0a 20 20 20 20 20  in dGraph:.     
0e50: 20 20 20 20 20 20 20 20 20 20 20 64 47 72 61 70             dGrap
0e60: 68 5b 73 48 61 73 68 49 64 5d 20 3d 20 6f 4e 6f  h[sHashId] = oNo
0e70: 64 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74  de.getNodeAsDict
0e80: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
0e90: 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20  lse:.           
0ea0: 20 20 20 20 20 70 72 69 6e 74 28 22 45 72 72 6f       print("Erro
0eb0: 72 2e 20 44 6f 75 62 6c 65 20 6e 6f 64 65 e2 80  r. Double node..
0ec0: a6 20 73 61 6d 65 20 69 64 3a 20 22 2c 20 73 48  . same id: ", sH
0ed0: 61 73 68 49 64 29 0a 20 20 20 20 20 20 20 20 20  ashId).         
0ee0: 20 20 20 20 20 20 20 70 72 69 6e 74 28 73 74 72         print(str
0ef0: 28 6f 4e 6f 64 65 2e 67 65 74 4e 6f 64 65 41 73  (oNode.getNodeAs
0f00: 44 69 63 74 28 29 29 29 0a 20 20 20 20 20 20 20  Dict())).       
0f10: 20 64 47 72 61 70 68 20 3d 20 73 65 6c 66 2e 5f   dGraph = self._
0f20: 72 65 77 72 69 74 65 4b 65 79 73 4f 66 44 41 52  rewriteKeysOfDAR
0f30: 47 28 64 47 72 61 70 68 29 0a 20 20 20 20 20 20  G(dGraph).      
0f40: 20 20 73 65 6c 66 2e 5f 73 6f 72 74 41 63 74 69    self._sortActi
0f50: 6f 6e 73 28 64 47 72 61 70 68 29 0a 20 20 20 20  ons(dGraph).    
0f60: 20 20 20 20 73 65 6c 66 2e 5f 63 68 65 63 6b 52      self._checkR
0f70: 65 67 65 78 65 73 28 64 47 72 61 70 68 29 0a 20  egexes(dGraph). 
0f80: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 47         return dG
0f90: 72 61 70 68 0a 0a 20 20 20 20 64 65 66 20 5f 72  raph..    def _r
0fa0: 65 77 72 69 74 65 4b 65 79 73 4f 66 44 41 52 47  ewriteKeysOfDARG
0fb0: 20 28 73 65 6c 66 2c 20 64 47 72 61 70 68 29 3a   (self, dGraph):
0fc0: 0a 20 20 20 20 20 20 20 20 22 6b 65 79 73 20 6f  .        "keys o
0fd0: 66 20 44 41 52 47 20 61 72 65 20 6c 6f 6e 67 20  f DARG are long 
0fe0: 6e 75 6d 62 65 72 73 20 28 68 61 73 68 65 73 29  numbers (hashes)
0ff0: 3a 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  : this function 
1000: 72 65 70 6c 61 63 65 20 74 68 65 73 65 20 68 61  replace these ha
1010: 73 68 65 73 20 77 69 74 68 20 73 6d 61 6c 6c 65  shes with smalle
1020: 72 20 6e 75 6d 62 65 72 73 20 28 74 6f 20 72 65  r numbers (to re
1030: 64 75 63 65 20 73 74 6f 72 69 6e 67 20 73 69 7a  duce storing siz
1040: 65 29 22 0a 20 20 20 20 20 20 20 20 23 20 63 72  e)".        # cr
1050: 65 61 74 65 20 74 72 61 6e 73 6c 61 74 69 6f 6e  eate translation
1060: 20 64 69 63 74 69 6f 6e 61 72 79 0a 20 20 20 20   dictionary.    
1070: 20 20 20 20 64 4b 65 79 54 72 61 6e 73 20 3d 20      dKeyTrans = 
1080: 7b 7d 0a 20 20 20 20 20 20 20 20 66 6f 72 20 69  {}.        for i
1090: 2c 20 6e 4b 65 79 20 69 6e 20 65 6e 75 6d 65 72  , nKey in enumer
10a0: 61 74 65 28 64 47 72 61 70 68 29 3a 0a 20 20 20  ate(dGraph):.   
10b0: 20 20 20 20 20 20 20 20 20 64 4b 65 79 54 72 61           dKeyTra
10c0: 6e 73 5b 6e 4b 65 79 5d 20 3d 20 69 0a 20 20 20  ns[nKey] = i.   
10d0: 20 20 20 20 20 23 20 72 65 70 6c 61 63 65 20 6b       # replace k
10e0: 65 79 73 0a 20 20 20 20 20 20 20 20 64 4e 65 77  eys.        dNew
10f0: 47 72 61 70 68 20 3d 20 7b 7d 0a 20 20 20 20 20  Graph = {}.     
1100: 20 20 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61     for nKey, dVa
1110: 6c 20 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d  l in dGraph.item
1120: 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20  s():.           
1130: 20 64 4e 65 77 47 72 61 70 68 5b 64 4b 65 79 54   dNewGraph[dKeyT
1140: 72 61 6e 73 5b 6e 4b 65 79 5d 5d 20 3d 20 64 56  rans[nKey]] = dV
1150: 61 6c 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6e  al.        for n
1160: 4b 65 79 2c 20 64 56 61 6c 20 69 6e 20 64 47 72  Key, dVal in dGr
1170: 61 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20  aph.items():.   
1180: 20 20 20 20 20 20 20 20 20 66 6f 72 20 73 41 72           for sAr
1190: 63 2c 20 76 61 6c 20 69 6e 20 64 56 61 6c 2e 69  c, val in dVal.i
11a0: 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20  tems():.        
11b0: 20 20 20 20 20 20 20 20 69 66 20 74 79 70 65 28          if type(
11c0: 76 61 6c 29 20 69 73 20 69 6e 74 3a 0a 20 20 20  val) is int:.   
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11e0: 20 64 56 61 6c 5b 73 41 72 63 5d 20 3d 20 64 4b   dVal[sArc] = dK
11f0: 65 79 54 72 61 6e 73 5b 76 61 6c 5d 0a 20 20 20  eyTrans[val].   
1200: 20 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73               els
1210: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  e:.             
1220: 20 20 20 20 20 20 20 66 6f 72 20 73 41 72 63 2c         for sArc,
1230: 20 6e 4b 65 79 20 69 6e 20 76 61 6c 2e 69 74 65   nKey in val.ite
1240: 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20  ms():.          
1250: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 76 61                va
1260: 6c 5b 73 41 72 63 5d 20 3d 20 64 4b 65 79 54 72  l[sArc] = dKeyTr
1270: 61 6e 73 5b 6e 4b 65 79 5d 0a 20 20 20 20 20 20  ans[nKey].      
1280: 20 20 72 65 74 75 72 6e 20 64 4e 65 77 47 72 61    return dNewGra
1290: 70 68 0a 0a 20 20 20 20 64 65 66 20 5f 73 6f 72  ph..    def _sor
12a0: 74 41 63 74 69 6f 6e 73 20 28 73 65 6c 66 2c 20  tActions (self, 
12b0: 64 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20  dGraph):.       
12c0: 20 22 77 68 65 6e 20 61 20 70 61 74 74 65 72 6e   "when a pattern
12d0: 20 69 73 20 66 6f 75 6e 64 2c 20 73 65 76 65 72   is found, sever
12e0: 61 6c 20 61 63 74 69 6f 6e 73 20 6d 61 79 20 62  al actions may b
12f0: 65 20 6c 61 75 6e 63 68 65 64 2c 20 61 6e 64 20  e launched, and 
1300: 69 74 20 6d 75 73 74 20 62 65 20 70 65 72 66 6f  it must be perfo
1310: 72 6d 65 64 20 69 6e 20 61 20 63 65 72 74 61 69  rmed in a certai
1320: 6e 20 6f 72 64 65 72 22 0a 20 20 20 20 20 20 20  n order".       
1330: 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61 6c 20   for nKey, dVal 
1340: 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d 73 28  in dGraph.items(
1350: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  ):.            i
1360: 66 20 22 3c 72 75 6c 65 73 3e 22 20 69 6e 20 64  f "<rules>" in d
1370: 56 61 6c 3a 0a 20 20 20 20 20 20 20 20 20 20 20  Val:.           
1380: 20 20 20 20 20 66 6f 72 20 73 4c 69 6e 65 49 64       for sLineId
1390: 2c 20 6e 4b 65 79 20 69 6e 20 64 56 61 6c 5b 22  , nKey in dVal["
13a0: 3c 72 75 6c 65 73 3e 22 5d 2e 69 74 65 6d 73 28  <rules>"].items(
13b0: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ):.             
13c0: 20 20 20 20 20 20 20 23 20 77 65 20 63 68 61 6e         # we chan
13d0: 67 65 20 74 68 65 20 64 69 63 74 69 6f 6e 61 72  ge the dictionar
13e0: 79 20 6f 66 20 61 63 74 69 6f 6e 73 20 69 6e 20  y of actions in 
13f0: 61 20 6c 69 73 74 20 6f 66 20 61 63 74 69 6f 6e  a list of action
1400: 73 20 28 76 61 6c 75 65 73 20 6f 66 20 64 69 63  s (values of dic
1410: 74 69 6f 6e 61 72 79 20 61 6c 6c 20 70 6f 69 6e  tionary all poin
1420: 74 73 20 74 6f 20 74 68 65 20 66 69 6e 61 6c 20  ts to the final 
1430: 6e 6f 64 65 29 0a 20 20 20 20 20 20 20 20 20 20  node).          
1440: 20 20 20 20 20 20 20 20 20 20 69 66 20 69 73 69            if isi
1450: 6e 73 74 61 6e 63 65 28 64 47 72 61 70 68 5b 6e  nstance(dGraph[n
1460: 4b 65 79 5d 2c 20 64 69 63 74 29 3a 0a 20 20 20  Key], dict):.   
1470: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1480: 20 20 20 20 20 64 47 72 61 70 68 5b 6e 4b 65 79       dGraph[nKey
1490: 5d 20 3d 20 73 6f 72 74 65 64 28 64 47 72 61 70  ] = sorted(dGrap
14a0: 68 5b 6e 4b 65 79 5d 2e 6b 65 79 73 28 29 29 0a  h[nKey].keys()).
14b0: 0a 20 20 20 20 64 65 66 20 5f 63 68 65 63 6b 52  .    def _checkR
14c0: 65 67 65 78 65 73 20 28 73 65 6c 66 2c 20 64 47  egexes (self, dG
14d0: 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20 22  raph):.        "
14e0: 63 68 65 63 6b 20 76 61 6c 69 64 69 74 79 20 6f  check validity o
14f0: 66 20 72 65 67 65 78 65 73 22 0a 20 20 20 20 20  f regexes".     
1500: 20 20 20 61 52 65 67 65 78 20 3d 20 73 65 74 28     aRegex = set(
1510: 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6e 4b  ).        for nK
1520: 65 79 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61  ey, dVal in dGra
1530: 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  ph.items():.    
1540: 20 20 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f          if "<re_
1550: 76 61 6c 75 65 3e 22 20 69 6e 20 64 56 61 6c 3a  value>" in dVal:
1560: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1570: 20 66 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64   for sRegex in d
1580: 56 61 6c 5b 22 3c 72 65 5f 76 61 6c 75 65 3e 22  Val["<re_value>"
1590: 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ]:.             
15a0: 20 20 20 20 20 20 20 69 66 20 73 52 65 67 65 78         if sRegex
15b0: 20 6e 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a   not in aRegex:.
15c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15d0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68          self._ch
15e0: 65 63 6b 52 65 67 65 78 28 73 52 65 67 65 78 29  eckRegex(sRegex)
15f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1600: 20 20 20 20 20 20 20 20 20 61 52 65 67 65 78 2e           aRegex.
1610: 61 64 64 28 73 52 65 67 65 78 29 0a 20 20 20 20  add(sRegex).    
1620: 20 20 20 20 20 20 20 20 69 66 20 22 3c 72 65 5f          if "<re_
1630: 6d 6f 72 70 68 3e 22 20 69 6e 20 64 56 61 6c 3a  morph>" in dVal:
1640: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1650: 20 66 6f 72 20 73 52 65 67 65 78 20 69 6e 20 64   for sRegex in d
1660: 56 61 6c 5b 22 3c 72 65 5f 6d 6f 72 70 68 3e 22  Val["<re_morph>"
1670: 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ]:.             
1680: 20 20 20 20 20 20 20 69 66 20 73 52 65 67 65 78         if sRegex
1690: 20 6e 6f 74 20 69 6e 20 61 52 65 67 65 78 3a 0a   not in aRegex:.
16a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
16b0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f 63 68          self._ch
16c0: 65 63 6b 52 65 67 65 78 28 73 52 65 67 65 78 29  eckRegex(sRegex)
16d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
16e0: 20 20 20 20 20 20 20 20 20 61 52 65 67 65 78 2e           aRegex.
16f0: 61 64 64 28 73 52 65 67 65 78 29 0a 20 20 20 20  add(sRegex).    
1700: 20 20 20 20 61 52 65 67 65 78 2e 63 6c 65 61 72      aRegex.clear
1710: 28 29 0a 0a 20 20 20 20 64 65 66 20 5f 63 68 65  ()..    def _che
1720: 63 6b 52 65 67 65 78 20 28 73 65 6c 66 2c 20 73  ckRegex (self, s
1730: 52 65 67 65 78 29 3a 0a 20 20 20 20 20 20 20 20  Regex):.        
1740: 23 70 72 69 6e 74 28 73 52 65 67 65 78 29 0a 20  #print(sRegex). 
1750: 20 20 20 20 20 20 20 69 66 20 22 c2 ac 22 20 69         if ".." i
1760: 6e 20 73 52 65 67 65 78 3a 0a 20 20 20 20 20 20  n sRegex:.      
1770: 20 20 20 20 20 20 73 50 61 74 74 65 72 6e 2c 20        sPattern, 
1780: 73 4e 65 67 50 61 74 74 65 72 6e 20 3d 20 73 52  sNegPattern = sR
1790: 65 67 65 78 2e 73 70 6c 69 74 28 22 c2 ac 22 29  egex.split("..")
17a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 74 72 79  .            try
17b0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
17c0: 20 20 69 66 20 6e 6f 74 20 73 4e 65 67 50 61 74    if not sNegPat
17d0: 74 65 72 6e 3a 0a 20 20 20 20 20 20 20 20 20 20  tern:.          
17e0: 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74 28            print(
17f0: 22 23 20 57 61 72 6e 69 6e 67 21 20 45 6d 70 74  "# Warning! Empt
1800: 79 20 6e 65 67 70 61 74 74 65 72 6e 3a 22 2c 20  y negpattern:", 
1810: 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20 20  sRegex).        
1820: 20 20 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69          re.compi
1830: 6c 65 28 73 50 61 74 74 65 72 6e 29 0a 20 20 20  le(sPattern).   
1840: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20               if 
1850: 73 4e 65 67 50 61 74 74 65 72 6e 20 21 3d 20 22  sNegPattern != "
1860: 2a 22 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  *":.            
1870: 20 20 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69          re.compi
1880: 6c 65 28 73 4e 65 67 50 61 74 74 65 72 6e 29 0a  le(sNegPattern).
1890: 20 20 20 20 20 20 20 20 20 20 20 20 65 78 63 65              exce
18a0: 70 74 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  pt:.            
18b0: 20 20 20 20 70 72 69 6e 74 28 22 23 20 45 72 72      print("# Err
18c0: 6f 72 2e 20 57 72 6f 6e 67 20 72 65 67 65 78 3a  or. Wrong regex:
18d0: 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20 20 20  ", sRegex).     
18e0: 20 20 20 20 20 20 20 20 20 20 20 65 78 69 74 28             exit(
18f0: 29 0a 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a  ).        else:.
1900: 20 20 20 20 20 20 20 20 20 20 20 20 74 72 79 3a              try:
1910: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1920: 20 69 66 20 6e 6f 74 20 73 52 65 67 65 78 3a 0a   if not sRegex:.
1930: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1940: 20 20 20 20 70 72 69 6e 74 28 22 23 20 57 61 72      print("# War
1950: 6e 69 6e 67 21 20 45 6d 70 74 79 20 70 61 74 74  ning! Empty patt
1960: 65 72 6e 3a 22 2c 20 73 52 65 67 65 78 29 0a 20  ern:", sRegex). 
1970: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 72                 r
1980: 65 2e 63 6f 6d 70 69 6c 65 28 73 52 65 67 65 78  e.compile(sRegex
1990: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 78  ).            ex
19a0: 63 65 70 74 3a 0a 20 20 20 20 20 20 20 20 20 20  cept:.          
19b0: 20 20 20 20 20 20 70 72 69 6e 74 28 22 23 20 45        print("# E
19c0: 72 72 6f 72 2e 20 57 72 6f 6e 67 20 72 65 67 65  rror. Wrong rege
19d0: 78 3a 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20  x:", sRegex).   
19e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 65 78 69               exi
19f0: 74 28 29 0a 0a 0a 63 6c 61 73 73 20 4e 6f 64 65  t()...class Node
1a00: 3a 0a 20 20 20 20 22 22 22 4e 6f 64 65 20 6f 66  :.    """Node of
1a10: 20 74 68 65 20 72 75 6c 65 20 67 72 61 70 68 22   the rule graph"
1a20: 22 22 0a 0a 20 20 20 20 4e 65 78 74 49 64 20 3d  ""..    NextId =
1a30: 20 30 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69 6e   0..    def __in
1a40: 69 74 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20  it__ (self):.   
1a50: 20 20 20 20 20 73 65 6c 66 2e 69 20 3d 20 4e 6f       self.i = No
1a60: 64 65 2e 4e 65 78 74 49 64 0a 20 20 20 20 20 20  de.NextId.      
1a70: 20 20 4e 6f 64 65 2e 4e 65 78 74 49 64 20 2b 3d    Node.NextId +=
1a80: 20 31 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e   1.        self.
1a90: 62 46 69 6e 61 6c 20 3d 20 46 61 6c 73 65 0a 20  bFinal = False. 
1aa0: 20 20 20 20 20 20 20 73 65 6c 66 2e 64 41 72 63         self.dArc
1ab0: 73 20 3d 20 7b 7d 20 20 20 20 20 20 20 20 20 20  s = {}          
1ac0: 23 20 6b 65 79 3a 20 61 72 63 20 76 61 6c 75 65  # key: arc value
1ad0: 3b 20 76 61 6c 75 65 3a 20 61 20 6e 6f 64 65 0a  ; value: a node.
1ae0: 0a 20 20 20 20 40 63 6c 61 73 73 6d 65 74 68 6f  .    @classmetho
1af0: 64 0a 20 20 20 20 64 65 66 20 72 65 73 65 74 4e  d.    def resetN
1b00: 65 78 74 49 64 20 28 63 6c 73 29 3a 0a 20 20 20  extId (cls):.   
1b10: 20 20 20 20 20 22 72 65 73 65 74 20 74 6f 20 30       "reset to 0
1b20: 20 74 68 65 20 6e 6f 64 65 20 63 6f 75 6e 74 65   the node counte
1b30: 72 22 0a 20 20 20 20 20 20 20 20 63 6c 73 2e 4e  r".        cls.N
1b40: 65 78 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64  extId = 0..    d
1b50: 65 66 20 5f 5f 73 74 72 5f 5f 20 28 73 65 6c 66  ef __str__ (self
1b60: 29 3a 0a 20 20 20 20 20 20 20 20 23 20 43 61 75  ):.        # Cau
1b70: 74 69 6f 6e 21 20 74 68 69 73 20 66 75 6e 63 74  tion! this funct
1b80: 69 6f 6e 20 69 73 20 75 73 65 64 20 66 6f 72 20  ion is used for 
1b90: 68 61 73 68 69 6e 67 20 61 6e 64 20 63 6f 6d 70  hashing and comp
1ba0: 61 72 69 73 6f 6e 21 0a 20 20 20 20 20 20 20 20  arison!.        
1bb0: 63 46 69 6e 61 6c 20 3d 20 22 31 22 20 20 69 66  cFinal = "1"  if
1bc0: 20 73 65 6c 66 2e 62 46 69 6e 61 6c 20 20 65 6c   self.bFinal  el
1bd0: 73 65 20 22 30 22 0a 20 20 20 20 20 20 20 20 6c  se "0".        l
1be0: 20 3d 20 5b 63 46 69 6e 61 6c 5d 0a 20 20 20 20   = [cFinal].    
1bf0: 20 20 20 20 66 6f 72 20 28 6b 65 79 2c 20 6f 4e      for (key, oN
1c00: 6f 64 65 29 20 69 6e 20 73 65 6c 66 2e 64 41 72  ode) in self.dAr
1c10: 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  cs.items():.    
1c20: 20 20 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64          l.append
1c30: 28 73 74 72 28 6b 65 79 29 29 0a 20 20 20 20 20  (str(key)).     
1c40: 20 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28         l.append(
1c50: 73 74 72 28 6f 4e 6f 64 65 2e 69 29 29 0a 20 20  str(oNode.i)).  
1c60: 20 20 20 20 20 20 72 65 74 75 72 6e 20 22 5f 22        return "_"
1c70: 2e 6a 6f 69 6e 28 6c 29 0a 0a 20 20 20 20 64 65  .join(l)..    de
1c80: 66 20 5f 5f 68 61 73 68 5f 5f 20 28 73 65 6c 66  f __hash__ (self
1c90: 29 3a 0a 20 20 20 20 20 20 20 20 23 20 55 73 65  ):.        # Use
1ca0: 64 20 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20  d as a key in a 
1cb0: 70 79 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72  python dictionar
1cc0: 79 2e 0a 20 20 20 20 20 20 20 20 72 65 74 75 72  y..        retur
1cd0: 6e 20 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29  n self.__str__()
1ce0: 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 0a 20 20 20  .__hash__()..   
1cf0: 20 64 65 66 20 5f 5f 65 71 5f 5f 20 28 73 65 6c   def __eq__ (sel
1d00: 66 2c 20 6f 74 68 65 72 29 3a 0a 20 20 20 20 20  f, other):.     
1d10: 20 20 20 23 20 55 73 65 64 20 61 73 20 61 20 6b     # Used as a k
1d20: 65 79 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64  ey in a python d
1d30: 69 63 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20  ictionary..     
1d40: 20 20 20 23 20 4e 6f 64 65 73 20 61 72 65 20 65     # Nodes are e
1d50: 71 75 69 76 61 6c 65 6e 74 20 69 66 20 74 68 65  quivalent if the
1d60: 79 20 68 61 76 65 20 69 64 65 6e 74 69 63 61 6c  y have identical
1d70: 20 61 72 63 73 2c 20 61 6e 64 20 65 61 63 68 20   arcs, and each 
1d80: 69 64 65 6e 74 69 63 61 6c 20 61 72 63 20 6c 65  identical arc le
1d90: 61 64 73 20 74 6f 20 69 64 65 6e 74 69 63 61 6c  ads to identical
1da0: 20 73 74 61 74 65 73 2e 0a 20 20 20 20 20 20 20   states..       
1db0: 20 72 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73   return self.__s
1dc0: 74 72 5f 5f 28 29 20 3d 3d 20 6f 74 68 65 72 2e  tr__() == other.
1dd0: 5f 5f 73 74 72 5f 5f 28 29 0a 0a 20 20 20 20 64  __str__()..    d
1de0: 65 66 20 67 65 74 4e 6f 64 65 41 73 44 69 63 74  ef getNodeAsDict
1df0: 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20   (self):.       
1e00: 20 22 72 65 74 75 72 6e 73 20 74 68 65 20 6e 6f   "returns the no
1e10: 64 65 20 61 73 20 61 20 64 69 63 74 69 6f 6e 61  de as a dictiona
1e20: 72 79 20 73 74 72 75 63 74 75 72 65 22 0a 20 20  ry structure".  
1e30: 20 20 20 20 20 20 64 4e 6f 64 65 20 3d 20 7b 7d        dNode = {}
1e40: 0a 20 20 20 20 20 20 20 20 64 52 65 56 61 6c 75  .        dReValu
1e50: 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64  e = {}.        d
1e60: 52 65 4d 6f 72 70 68 20 3d 20 7b 7d 0a 20 20 20  ReMorph = {}.   
1e70: 20 20 20 20 20 64 52 75 6c 65 20 3d 20 7b 7d 0a       dRule = {}.
1e80: 20 20 20 20 20 20 20 20 64 4c 65 6d 6d 61 20 3d          dLemma =
1e90: 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 4d 65 74   {}.        dMet
1ea0: 61 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64  a = {}.        d
1eb0: 54 61 67 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20  Tag = {}.       
1ec0: 20 66 6f 72 20 73 41 72 63 2c 20 6f 4e 6f 64 65   for sArc, oNode
1ed0: 20 69 6e 20 73 65 6c 66 2e 64 41 72 63 73 2e 69   in self.dArcs.i
1ee0: 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20  tems():.        
1ef0: 20 20 20 20 69 66 20 73 41 72 63 2e 73 74 61 72      if sArc.star
1f00: 74 73 77 69 74 68 28 22 40 22 29 20 61 6e 64 20  tswith("@") and 
1f10: 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20  len(sArc) > 1:. 
1f20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64                 d
1f30: 52 65 4d 6f 72 70 68 5b 73 41 72 63 5b 31 3a 5d  ReMorph[sArc[1:]
1f40: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
1f50: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
1f60: 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74   elif sArc.start
1f70: 73 77 69 74 68 28 22 7e 22 29 20 61 6e 64 20 6c  swith("~") and l
1f80: 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20  en(sArc) > 1:.  
1f90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 52                dR
1fa0: 65 56 61 6c 75 65 5b 73 41 72 63 5b 31 3a 5d 5d  eValue[sArc[1:]]
1fb0: 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f   = oNode.__hash_
1fc0: 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  _().            
1fd0: 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74 73  elif sArc.starts
1fe0: 77 69 74 68 28 22 3e 22 29 20 61 6e 64 20 6c 65  with(">") and le
1ff0: 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20  n(sArc) > 1:.   
2000: 20 20 20 20 20 20 20 20 20 20 20 20 20 64 4c 65               dLe
2010: 6d 6d 61 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20  mma[sArc[1:]] = 
2020: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
2030: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 69  .            eli
2040: 66 20 73 41 72 63 2e 73 74 61 72 74 73 77 69 74  f sArc.startswit
2050: 68 28 22 2a 22 29 20 61 6e 64 20 6c 65 6e 28 73  h("*") and len(s
2060: 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20 20 20  Arc) > 1:.      
2070: 20 20 20 20 20 20 20 20 20 20 64 4d 65 74 61 5b            dMeta[
2080: 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64  sArc[1:]] = oNod
2090: 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20  e.__hash__().   
20a0: 20 20 20 20 20 20 20 20 20 65 6c 69 66 20 73 41           elif sA
20b0: 72 63 2e 73 74 61 72 74 73 77 69 74 68 28 22 2f  rc.startswith("/
20c0: 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29  ") and len(sArc)
20d0: 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20   > 1:.          
20e0: 20 20 20 20 20 20 64 54 61 67 5b 73 41 72 63 5b        dTag[sArc[
20f0: 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68  1:]] = oNode.__h
2100: 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20  ash__().        
2110: 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74      elif sArc.st
2120: 61 72 74 73 77 69 74 68 28 22 23 23 22 29 3a 0a  artswith("##"):.
2130: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2140: 64 52 75 6c 65 5b 73 41 72 63 5b 31 3a 5d 5d 20  dRule[sArc[1:]] 
2150: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
2160: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
2170: 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20  lse:.           
2180: 20 20 20 20 20 64 4e 6f 64 65 5b 73 41 72 63 5d       dNode[sArc]
2190: 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f   = oNode.__hash_
21a0: 5f 28 29 0a 20 20 20 20 20 20 20 20 69 66 20 64  _().        if d
21b0: 52 65 56 61 6c 75 65 3a 0a 20 20 20 20 20 20 20  ReValue:.       
21c0: 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f       dNode["<re_
21d0: 76 61 6c 75 65 3e 22 5d 20 3d 20 64 52 65 56 61  value>"] = dReVa
21e0: 6c 75 65 0a 20 20 20 20 20 20 20 20 69 66 20 64  lue.        if d
21f0: 52 65 4d 6f 72 70 68 3a 0a 20 20 20 20 20 20 20  ReMorph:.       
2200: 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f       dNode["<re_
2210: 6d 6f 72 70 68 3e 22 5d 20 3d 20 64 52 65 4d 6f  morph>"] = dReMo
2220: 72 70 68 0a 20 20 20 20 20 20 20 20 69 66 20 64  rph.        if d
2230: 4c 65 6d 6d 61 3a 0a 20 20 20 20 20 20 20 20 20  Lemma:.         
2240: 20 20 20 64 4e 6f 64 65 5b 22 3c 6c 65 6d 6d 61     dNode["<lemma
2250: 73 3e 22 5d 20 3d 20 64 4c 65 6d 6d 61 0a 20 20  s>"] = dLemma.  
2260: 20 20 20 20 20 20 69 66 20 64 54 61 67 3a 0a 20        if dTag:. 
2270: 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65             dNode
2280: 5b 22 3c 74 61 67 73 3e 22 5d 20 3d 20 64 54 61  ["<tags>"] = dTa
2290: 67 0a 20 20 20 20 20 20 20 20 69 66 20 64 4d 65  g.        if dMe
22a0: 74 61 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ta:.            
22b0: 64 4e 6f 64 65 5b 22 3c 6d 65 74 61 3e 22 5d 20  dNode["<meta>"] 
22c0: 3d 20 64 4d 65 74 61 0a 20 20 20 20 20 20 20 20  = dMeta.        
22d0: 69 66 20 64 52 75 6c 65 3a 0a 20 20 20 20 20 20  if dRule:.      
22e0: 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72 75        dNode["<ru
22f0: 6c 65 73 3e 22 5d 20 3d 20 64 52 75 6c 65 0a 20  les>"] = dRule. 
2300: 20 20 20 20 20 20 20 23 69 66 20 73 65 6c 66 2e         #if self.
2310: 62 46 69 6e 61 6c 3a 0a 20 20 20 20 20 20 20 20  bFinal:.        
2320: 23 20 20 20 20 64 4e 6f 64 65 5b 22 3c 66 69 6e  #    dNode["<fin
2330: 61 6c 3e 22 5d 20 3d 20 31 0a 20 20 20 20 20 20  al>"] = 1.      
2340: 20 20 72 65 74 75 72 6e 20 64 4e 6f 64 65 0a       return dNode.