Grammalecte  Hex Artifact Content

Artifact 49bc8d20396f83d8496c0e52618eb66060acf4d07c3254e100390a823a5bc081:


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 0a 0a 63 6c 61 73 73 20 44 41 52 47 3a  re...class DARG:
0060: 0a 20 20 20 20 22 22 22 44 49 52 45 43 54 20 41  .    """DIRECT A
0070: 43 59 43 4c 49 43 20 52 55 4c 45 20 47 52 41 50  CYCLIC RULE GRAP
0080: 48 22 22 22 0a 20 20 20 20 23 20 54 68 69 73 20  H""".    # This 
0090: 63 6f 64 65 20 69 73 20 69 6e 73 70 69 72 65 64  code is inspired
00a0: 20 66 72 6f 6d 20 53 74 65 76 65 20 48 61 6e 6f   from Steve Hano
00b0: 76 e2 80 99 73 20 44 41 57 47 2c 20 32 30 31 31  v...s DAWG, 2011
00c0: 2e 20 28 68 74 74 70 3a 2f 2f 73 74 65 76 65 68  . (http://steveh
00d0: 61 6e 6f 76 2e 63 61 2f 62 6c 6f 67 2f 69 6e 64  anov.ca/blog/ind
00e0: 65 78 2e 70 68 70 3f 69 64 3d 31 31 35 29 0a 0a  ex.php?id=115)..
00f0: 20 20 20 20 64 65 66 20 5f 5f 69 6e 69 74 5f 5f      def __init__
0100: 20 28 73 65 6c 66 2c 20 6c 52 75 6c 65 2c 20 73   (self, lRule, s
0110: 4c 61 6e 67 43 6f 64 65 29 3a 0a 20 20 20 20 20  LangCode):.     
0120: 20 20 20 70 72 69 6e 74 28 22 20 3e 20 44 41 52     print(" > DAR
0130: 47 22 2c 20 65 6e 64 3d 22 22 29 0a 0a 20 20 20  G", end="")..   
0140: 20 20 20 20 20 23 20 50 72 65 70 61 72 69 6e 67       # Preparing
0150: 20 44 41 52 47 0a 20 20 20 20 20 20 20 20 73 65   DARG.        se
0160: 6c 66 2e 73 4c 61 6e 67 43 6f 64 65 20 3d 20 73  lf.sLangCode = s
0170: 4c 61 6e 67 43 6f 64 65 0a 20 20 20 20 20 20 20  LangCode.       
0180: 20 73 65 6c 66 2e 6e 52 75 6c 65 20 3d 20 6c 65   self.nRule = le
0190: 6e 28 6c 52 75 6c 65 29 0a 20 20 20 20 20 20 20  n(lRule).       
01a0: 20 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52   self.aPreviousR
01b0: 75 6c 65 20 3d 20 5b 5d 0a 20 20 20 20 20 20 20  ule = [].       
01c0: 20 4e 6f 64 65 2e 72 65 73 65 74 4e 65 78 74 49   Node.resetNextI
01d0: 64 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66  d().        self
01e0: 2e 6f 52 6f 6f 74 20 3d 20 4e 6f 64 65 28 29 0a  .oRoot = Node().
01f0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e          self.lUn
0200: 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 3d 20 5b  checkedNodes = [
0210: 5d 20 20 23 20 6c 69 73 74 20 6f 66 20 6e 6f 64  ]  # list of nod
0220: 65 73 20 74 68 61 74 20 68 61 76 65 20 6e 6f 74  es that have not
0230: 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20 66 6f   been checked fo
0240: 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e 0a 20  r duplication.. 
0250: 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d 69 6e         self.lMin
0260: 69 6d 69 7a 65 64 4e 6f 64 65 73 20 3d 20 7b 7d  imizedNodes = {}
0270: 20 20 23 20 6c 69 73 74 20 6f 66 20 75 6e 69 71    # list of uniq
0280: 75 65 20 6e 6f 64 65 73 20 74 68 61 74 20 68 61  ue nodes that ha
0290: 76 65 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20  ve been checked 
02a0: 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e  for duplication.
02b0: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 4e  .        self.nN
02c0: 6f 64 65 20 3d 20 30 0a 20 20 20 20 20 20 20 20  ode = 0.        
02d0: 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a 0a 20  self.nArc = 0.. 
02e0: 20 20 20 20 20 20 20 23 20 62 75 69 6c 64 0a 20         # build. 
02f0: 20 20 20 20 20 20 20 6c 52 75 6c 65 2e 73 6f 72         lRule.sor
0300: 74 28 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20  t().        for 
0310: 61 52 75 6c 65 20 69 6e 20 6c 52 75 6c 65 3a 0a  aRule in lRule:.
0320: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
0330: 2e 69 6e 73 65 72 74 28 61 52 75 6c 65 29 0a 20  .insert(aRule). 
0340: 20 20 20 20 20 20 20 73 65 6c 66 2e 66 69 6e 69         self.fini
0350: 73 68 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c  sh().        sel
0360: 66 2e 63 6f 75 6e 74 4e 6f 64 65 73 28 29 0a 20  f.countNodes(). 
0370: 20 20 20 20 20 20 20 73 65 6c 66 2e 63 6f 75 6e         self.coun
0380: 74 41 72 63 73 28 29 0a 20 20 20 20 20 20 20 20  tArcs().        
0390: 73 65 6c 66 2e 64 69 73 70 6c 61 79 49 6e 66 6f  self.displayInfo
03a0: 28 29 0a 0a 20 20 20 20 23 20 42 55 49 4c 44 20  ()..    # BUILD 
03b0: 44 41 52 47 0a 20 20 20 20 64 65 66 20 69 6e 73  DARG.    def ins
03c0: 65 72 74 20 28 73 65 6c 66 2c 20 61 52 75 6c 65  ert (self, aRule
03d0: 29 3a 0a 20 20 20 20 20 20 20 20 22 69 6e 73 65  ):.        "inse
03e0: 72 74 20 61 20 6e 65 77 20 72 75 6c 65 20 28 74  rt a new rule (t
03f0: 6f 6b 65 6e 73 20 6d 75 73 74 20 62 65 20 69 6e  okens must be in
0400: 73 65 72 74 65 64 20 69 6e 20 6f 72 64 65 72 29  serted in order)
0410: 22 0a 20 20 20 20 20 20 20 20 69 66 20 61 52 75  ".        if aRu
0420: 6c 65 20 3c 20 73 65 6c 66 2e 61 50 72 65 76 69  le < self.aPrevi
0430: 6f 75 73 52 75 6c 65 3a 0a 20 20 20 20 20 20 20  ousRule:.       
0440: 20 20 20 20 20 65 78 69 74 28 22 23 20 45 72 72       exit("# Err
0450: 6f 72 3a 20 74 6f 6b 65 6e 73 20 6d 75 73 74 20  or: tokens must 
0460: 62 65 20 69 6e 73 65 72 74 65 64 20 69 6e 20 6f  be inserted in o
0470: 72 64 65 72 2e 22 29 0a 0a 20 20 20 20 20 20 20  rder.")..       
0480: 20 23 20 66 69 6e 64 20 63 6f 6d 6d 6f 6e 20 70   # find common p
0490: 72 65 66 69 78 20 62 65 74 77 65 65 6e 20 77 6f  refix between wo
04a0: 72 64 20 61 6e 64 20 70 72 65 76 69 6f 75 73 20  rd and previous 
04b0: 77 6f 72 64 0a 20 20 20 20 20 20 20 20 6e 43 6f  word.        nCo
04c0: 6d 6d 6f 6e 50 72 65 66 69 78 20 3d 20 30 0a 20  mmonPrefix = 0. 
04d0: 20 20 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20         for i in 
04e0: 72 61 6e 67 65 28 6d 69 6e 28 6c 65 6e 28 61 52  range(min(len(aR
04f0: 75 6c 65 29 2c 20 6c 65 6e 28 73 65 6c 66 2e 61  ule), len(self.a
0500: 50 72 65 76 69 6f 75 73 52 75 6c 65 29 29 29 3a  PreviousRule))):
0510: 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20  .            if 
0520: 61 52 75 6c 65 5b 69 5d 20 21 3d 20 73 65 6c 66  aRule[i] != self
0530: 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 5b 69  .aPreviousRule[i
0540: 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ]:.             
0550: 20 20 20 62 72 65 61 6b 0a 20 20 20 20 20 20 20     break.       
0560: 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66       nCommonPref
0570: 69 78 20 2b 3d 20 31 0a 0a 20 20 20 20 20 20 20  ix += 1..       
0580: 20 23 20 43 68 65 63 6b 20 74 68 65 20 6c 55 6e   # Check the lUn
0590: 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 66 6f 72  checkedNodes for
05a0: 20 72 65 64 75 6e 64 61 6e 74 20 6e 6f 64 65 73   redundant nodes
05b0: 2c 20 70 72 6f 63 65 65 64 69 6e 67 20 66 72 6f  , proceeding fro
05c0: 6d 20 6c 61 73 74 0a 20 20 20 20 20 20 20 20 23  m last.        #
05d0: 20 6f 6e 65 20 64 6f 77 6e 20 74 6f 20 74 68 65   one down to the
05e0: 20 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78 20 73   common prefix s
05f0: 69 7a 65 2e 20 54 68 65 6e 20 74 72 75 6e 63 61  ize. Then trunca
0600: 74 65 20 74 68 65 20 6c 69 73 74 20 61 74 20 74  te the list at t
0610: 68 61 74 20 70 6f 69 6e 74 2e 0a 20 20 20 20 20  hat point..     
0620: 20 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a     self._minimiz
0630: 65 28 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 29  e(nCommonPrefix)
0640: 0a 0a 20 20 20 20 20 20 20 20 23 20 61 64 64 20  ..        # add 
0650: 74 68 65 20 73 75 66 66 69 78 2c 20 73 74 61 72  the suffix, star
0660: 74 69 6e 67 20 66 72 6f 6d 20 74 68 65 20 63 6f  ting from the co
0670: 72 72 65 63 74 20 6e 6f 64 65 20 6d 69 64 2d 77  rrect node mid-w
0680: 61 79 20 74 68 72 6f 75 67 68 20 74 68 65 20 67  ay through the g
0690: 72 61 70 68 0a 20 20 20 20 20 20 20 20 69 66 20  raph.        if 
06a0: 6e 6f 74 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63  not self.lUnchec
06b0: 6b 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20  kedNodes:.      
06c0: 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20 73 65        oNode = se
06d0: 6c 66 2e 6f 52 6f 6f 74 0a 20 20 20 20 20 20 20  lf.oRoot.       
06e0: 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20   else:.         
06f0: 20 20 20 6f 4e 6f 64 65 20 3d 20 73 65 6c 66 2e     oNode = self.
0700: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 5b  lUncheckedNodes[
0710: 2d 31 5d 5b 32 5d 0a 0a 20 20 20 20 20 20 20 20  -1][2]..        
0720: 69 54 6f 6b 65 6e 20 3d 20 6e 43 6f 6d 6d 6f 6e  iToken = nCommon
0730: 50 72 65 66 69 78 0a 20 20 20 20 20 20 20 20 66  Prefix.        f
0740: 6f 72 20 73 54 6f 6b 65 6e 20 69 6e 20 61 52 75  or sToken in aRu
0750: 6c 65 5b 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78  le[nCommonPrefix
0760: 3a 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  :]:.            
0770: 6f 4e 65 78 74 4e 6f 64 65 20 3d 20 4e 6f 64 65  oNextNode = Node
0780: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f  ().            o
0790: 4e 6f 64 65 2e 64 41 72 63 73 5b 73 54 6f 6b 65  Node.dArcs[sToke
07a0: 6e 5d 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a 20  n] = oNextNode. 
07b0: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
07c0: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 2e  lUncheckedNodes.
07d0: 61 70 70 65 6e 64 28 28 6f 4e 6f 64 65 2c 20 73  append((oNode, s
07e0: 54 6f 6b 65 6e 2c 20 6f 4e 65 78 74 4e 6f 64 65  Token, oNextNode
07f0: 29 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  )).            i
0800: 66 20 69 54 6f 6b 65 6e 20 3d 3d 20 28 6c 65 6e  f iToken == (len
0810: 28 61 52 75 6c 65 29 20 2d 20 32 29 3a 0a 20 20  (aRule) - 2):.  
0820: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e                oN
0830: 6f 64 65 2e 62 46 69 6e 61 6c 20 3d 20 54 72 75  ode.bFinal = Tru
0840: 65 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 54  e.            iT
0850: 6f 6b 65 6e 20 2b 3d 20 31 0a 20 20 20 20 20 20  oken += 1.      
0860: 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20 6f 4e        oNode = oN
0870: 65 78 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20  extNode.        
0880: 6f 4e 6f 64 65 2e 62 46 69 6e 61 6c 20 3d 20 54  oNode.bFinal = T
0890: 72 75 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66  rue.        self
08a0: 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 20 3d  .aPreviousRule =
08b0: 20 61 52 75 6c 65 0a 0a 20 20 20 20 64 65 66 20   aRule..    def 
08c0: 66 69 6e 69 73 68 20 28 73 65 6c 66 29 3a 0a 20  finish (self):. 
08d0: 20 20 20 20 20 20 20 22 6d 69 6e 69 6d 69 7a 65         "minimize
08e0: 20 75 6e 63 68 65 63 6b 65 64 20 6e 6f 64 65 73   unchecked nodes
08f0: 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f  ".        self._
0900: 6d 69 6e 69 6d 69 7a 65 28 30 29 0a 0a 20 20 20  minimize(0)..   
0910: 20 64 65 66 20 5f 6d 69 6e 69 6d 69 7a 65 20 28   def _minimize (
0920: 73 65 6c 66 2c 20 64 6f 77 6e 54 6f 29 3a 0a 20  self, downTo):. 
0930: 20 20 20 20 20 20 20 23 20 70 72 6f 63 65 65 64         # proceed
0940: 20 66 72 6f 6d 20 74 68 65 20 6c 65 61 66 20 75   from the leaf u
0950: 70 20 74 6f 20 61 20 63 65 72 74 61 69 6e 20 70  p to a certain p
0960: 6f 69 6e 74 0a 20 20 20 20 20 20 20 20 66 6f 72  oint.        for
0970: 20 69 20 69 6e 20 72 61 6e 67 65 28 20 6c 65 6e   i in range( len
0980: 28 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64  (self.lUnchecked
0990: 4e 6f 64 65 73 29 2d 31 2c 20 64 6f 77 6e 54 6f  Nodes)-1, downTo
09a0: 2d 31 2c 20 2d 31 20 29 3a 0a 20 20 20 20 20 20  -1, -1 ):.      
09b0: 20 20 20 20 20 20 6f 4e 6f 64 65 2c 20 73 54 6f        oNode, sTo
09c0: 6b 65 6e 2c 20 6f 43 68 69 6c 64 4e 6f 64 65 20  ken, oChildNode 
09d0: 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65  = self.lUnchecke
09e0: 64 4e 6f 64 65 73 5b 69 5d 0a 20 20 20 20 20 20  dNodes[i].      
09f0: 20 20 20 20 20 20 69 66 20 6f 43 68 69 6c 64 4e        if oChildN
0a00: 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e  ode in self.lMin
0a10: 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20  imizedNodes:.   
0a20: 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20 72               # r
0a30: 65 70 6c 61 63 65 20 74 68 65 20 63 68 69 6c 64  eplace the child
0a40: 20 77 69 74 68 20 74 68 65 20 70 72 65 76 69 6f   with the previo
0a50: 75 73 6c 79 20 65 6e 63 6f 75 6e 74 65 72 65 64  usly encountered
0a60: 20 6f 6e 65 0a 20 20 20 20 20 20 20 20 20 20 20   one.           
0a70: 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72 63 73       oNode.dArcs
0a80: 5b 73 54 6f 6b 65 6e 5d 20 3d 20 73 65 6c 66 2e  [sToken] = self.
0a90: 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 5b  lMinimizedNodes[
0aa0: 6f 43 68 69 6c 64 4e 6f 64 65 5d 0a 20 20 20 20  oChildNode].    
0ab0: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
0ac0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20                # 
0ad0: 61 64 64 20 74 68 65 20 73 74 61 74 65 20 74 6f  add the state to
0ae0: 20 74 68 65 20 6d 69 6e 69 6d 69 7a 65 64 20 6e   the minimized n
0af0: 6f 64 65 73 2e 0a 20 20 20 20 20 20 20 20 20 20  odes..          
0b00: 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d 69 6e 69        self.lMini
0b10: 6d 69 7a 65 64 4e 6f 64 65 73 5b 6f 43 68 69 6c  mizedNodes[oChil
0b20: 64 4e 6f 64 65 5d 20 3d 20 6f 43 68 69 6c 64 4e  dNode] = oChildN
0b30: 6f 64 65 0a 20 20 20 20 20 20 20 20 20 20 20 20  ode.            
0b40: 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e  self.lUncheckedN
0b50: 6f 64 65 73 2e 70 6f 70 28 29 0a 0a 20 20 20 20  odes.pop()..    
0b60: 64 65 66 20 63 6f 75 6e 74 4e 6f 64 65 73 20 28  def countNodes (
0b70: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
0b80: 63 6f 75 6e 74 20 6e 6f 64 65 73 20 77 69 74 68  count nodes with
0b90: 69 6e 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61  in the whole gra
0ba0: 70 68 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66  ph".        self
0bb0: 2e 6e 4e 6f 64 65 20 3d 20 6c 65 6e 28 73 65 6c  .nNode = len(sel
0bc0: 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65  f.lMinimizedNode
0bd0: 73 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e  s)..    def coun
0be0: 74 41 72 63 73 20 28 73 65 6c 66 29 3a 0a 20 20  tArcs (self):.  
0bf0: 20 20 20 20 20 20 22 63 6f 75 6e 74 20 61 72 63        "count arc
0c00: 73 20 77 69 74 68 69 6e 20 74 68 65 20 77 68 6f  s within the who
0c10: 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20 20 20  le graph".      
0c20: 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 6c 65    self.nArc = le
0c30: 6e 28 73 65 6c 66 2e 6f 52 6f 6f 74 2e 64 41 72  n(self.oRoot.dAr
0c40: 63 73 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20  cs).        for 
0c50: 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d  oNode in self.lM
0c60: 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20  inimizedNodes:. 
0c70: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
0c80: 6e 41 72 63 20 2b 3d 20 6c 65 6e 28 6f 4e 6f 64  nArc += len(oNod
0c90: 65 2e 64 41 72 63 73 29 0a 0a 20 20 20 20 64 65  e.dArcs)..    de
0ca0: 66 20 64 69 73 70 6c 61 79 49 6e 66 6f 20 28 73  f displayInfo (s
0cb0: 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22 64  elf):.        "d
0cc0: 69 73 70 6c 61 79 20 69 6e 66 6f 72 6d 61 74 69  isplay informati
0cd0: 6f 6e 73 20 61 62 6f 75 74 20 74 68 65 20 72 75  ons about the ru
0ce0: 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20 20 20  le graph".      
0cf0: 20 20 70 72 69 6e 74 28 22 3a 20 7b 3a 3e 31 30    print(": {:>10
0d00: 2c 7d 20 72 75 6c 65 73 2c 20 20 7b 3a 3e 31 30  ,} rules,  {:>10
0d10: 2c 7d 20 6e 6f 64 65 73 2c 20 20 7b 3a 3e 31 30  ,} nodes,  {:>10
0d20: 2c 7d 20 61 72 63 73 22 2e 66 6f 72 6d 61 74 28  ,} arcs".format(
0d30: 73 65 6c 66 2e 6e 52 75 6c 65 2c 20 73 65 6c 66  self.nRule, self
0d40: 2e 6e 4e 6f 64 65 2c 20 73 65 6c 66 2e 6e 41 72  .nNode, self.nAr
0d50: 63 29 29 0a 0a 20 20 20 20 64 65 66 20 63 72 65  c))..    def cre
0d60: 61 74 65 47 72 61 70 68 20 28 73 65 6c 66 29 3a  ateGraph (self):
0d70: 0a 20 20 20 20 20 20 20 20 22 63 72 65 61 74 65  .        "create
0d80: 20 74 68 65 20 67 72 61 70 68 20 61 73 20 61 20   the graph as a 
0d90: 64 69 63 74 69 6f 6e 61 72 79 22 0a 20 20 20 20  dictionary".    
0da0: 20 20 20 20 64 47 72 61 70 68 20 3d 20 7b 20 30      dGraph = { 0
0db0: 3a 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e 67 65 74  : self.oRoot.get
0dc0: 4e 6f 64 65 41 73 44 69 63 74 28 29 20 7d 0a 20  NodeAsDict() }. 
0dd0: 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f 64 65         for oNode
0de0: 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69   in self.lMinimi
0df0: 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20  zedNodes:.      
0e00: 20 20 20 20 20 20 73 48 61 73 68 49 64 20 3d 20        sHashId = 
0e10: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
0e20: 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20  .            if 
0e30: 73 48 61 73 68 49 64 20 6e 6f 74 20 69 6e 20 64  sHashId not in d
0e40: 47 72 61 70 68 3a 0a 20 20 20 20 20 20 20 20 20  Graph:.         
0e50: 20 20 20 20 20 20 20 64 47 72 61 70 68 5b 73 48         dGraph[sH
0e60: 61 73 68 49 64 5d 20 3d 20 6f 4e 6f 64 65 2e 67  ashId] = oNode.g
0e70: 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29 0a 20  etNodeAsDict(). 
0e80: 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 3a             else:
0e90: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0ea0: 20 70 72 69 6e 74 28 22 45 72 72 6f 72 2e 20 44   print("Error. D
0eb0: 6f 75 62 6c 65 20 6e 6f 64 65 e2 80 a6 20 73 61  ouble node... sa
0ec0: 6d 65 20 69 64 3a 20 22 2c 20 73 48 61 73 68 49  me id: ", sHashI
0ed0: 64 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  d).             
0ee0: 20 20 20 70 72 69 6e 74 28 73 74 72 28 6f 4e 6f     print(str(oNo
0ef0: 64 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74  de.getNodeAsDict
0f00: 28 29 29 29 0a 20 20 20 20 20 20 20 20 64 47 72  ())).        dGr
0f10: 61 70 68 20 3d 20 73 65 6c 66 2e 5f 72 65 77 72  aph = self._rewr
0f20: 69 74 65 4b 65 79 73 4f 66 44 41 52 47 28 64 47  iteKeysOfDARG(dG
0f30: 72 61 70 68 29 0a 20 20 20 20 20 20 20 20 73 65  raph).        se
0f40: 6c 66 2e 5f 73 6f 72 74 41 63 74 69 6f 6e 73 28  lf._sortActions(
0f50: 64 47 72 61 70 68 29 0a 20 20 20 20 20 20 20 20  dGraph).        
0f60: 73 65 6c 66 2e 5f 63 68 65 63 6b 52 65 67 65 78  self._checkRegex
0f70: 65 73 28 64 47 72 61 70 68 29 0a 20 20 20 20 20  es(dGraph).     
0f80: 20 20 20 72 65 74 75 72 6e 20 64 47 72 61 70 68     return dGraph
0f90: 0a 0a 20 20 20 20 64 65 66 20 5f 72 65 77 72 69  ..    def _rewri
0fa0: 74 65 4b 65 79 73 4f 66 44 41 52 47 20 28 73 65  teKeysOfDARG (se
0fb0: 6c 66 2c 20 64 47 72 61 70 68 29 3a 0a 20 20 20  lf, dGraph):.   
0fc0: 20 20 20 20 20 22 6b 65 79 73 20 6f 66 20 44 41       "keys of DA
0fd0: 52 47 20 61 72 65 20 6c 6f 6e 67 20 6e 75 6d 62  RG are long numb
0fe0: 65 72 73 20 28 68 61 73 68 65 73 29 3a 20 74 68  ers (hashes): th
0ff0: 69 73 20 66 75 6e 63 74 69 6f 6e 20 72 65 70 6c  is function repl
1000: 61 63 65 20 74 68 65 73 65 20 68 61 73 68 65 73  ace these hashes
1010: 20 77 69 74 68 20 73 6d 61 6c 6c 65 72 20 6e 75   with smaller nu
1020: 6d 62 65 72 73 20 28 74 6f 20 72 65 64 75 63 65  mbers (to reduce
1030: 20 73 74 6f 72 69 6e 67 20 73 69 7a 65 29 22 0a   storing size)".
1040: 20 20 20 20 20 20 20 20 23 20 63 72 65 61 74 65          # create
1050: 20 74 72 61 6e 73 6c 61 74 69 6f 6e 20 64 69 63   translation dic
1060: 74 69 6f 6e 61 72 79 0a 20 20 20 20 20 20 20 20  tionary.        
1070: 64 4b 65 79 54 72 61 6e 73 20 3d 20 7b 7d 0a 20  dKeyTrans = {}. 
1080: 20 20 20 20 20 20 20 66 6f 72 20 69 2c 20 6e 4b         for i, nK
1090: 65 79 20 69 6e 20 65 6e 75 6d 65 72 61 74 65 28  ey in enumerate(
10a0: 64 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20  dGraph):.       
10b0: 20 20 20 20 20 64 4b 65 79 54 72 61 6e 73 5b 6e       dKeyTrans[n
10c0: 4b 65 79 5d 20 3d 20 69 0a 20 20 20 20 20 20 20  Key] = i.       
10d0: 20 23 20 72 65 70 6c 61 63 65 20 6b 65 79 73 0a   # replace keys.
10e0: 20 20 20 20 20 20 20 20 64 4e 65 77 47 72 61 70          dNewGrap
10f0: 68 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 66  h = {}.        f
1100: 6f 72 20 6e 4b 65 79 2c 20 64 56 61 6c 20 69 6e  or nKey, dVal in
1110: 20 64 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a   dGraph.items():
1120: 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e 65  .            dNe
1130: 77 47 72 61 70 68 5b 64 4b 65 79 54 72 61 6e 73  wGraph[dKeyTrans
1140: 5b 6e 4b 65 79 5d 5d 20 3d 20 64 56 61 6c 0a 20  [nKey]] = dVal. 
1150: 20 20 20 20 20 20 20 66 6f 72 20 5f 2c 20 64 56         for _, dV
1160: 61 6c 20 69 6e 20 64 47 72 61 70 68 2e 69 74 65  al in dGraph.ite
1170: 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20  ms():.          
1180: 20 20 66 6f 72 20 73 41 72 63 2c 20 76 61 6c 20    for sArc, val 
1190: 69 6e 20 64 56 61 6c 2e 69 74 65 6d 73 28 29 3a  in dVal.items():
11a0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
11b0: 20 69 66 20 69 73 69 6e 73 74 61 6e 63 65 28 76   if isinstance(v
11c0: 61 6c 2c 20 69 6e 74 29 3a 0a 20 20 20 20 20 20  al, int):.      
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 56                dV
11e0: 61 6c 5b 73 41 72 63 5d 20 3d 20 64 4b 65 79 54  al[sArc] = dKeyT
11f0: 72 61 6e 73 5b 76 61 6c 5d 0a 20 20 20 20 20 20  rans[val].      
1200: 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a            else:.
1210: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1220: 20 20 20 20 66 6f 72 20 73 41 72 63 32 2c 20 6e      for sArc2, n
1230: 4b 65 79 20 69 6e 20 76 61 6c 2e 69 74 65 6d 73  Key in val.items
1240: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
1250: 20 20 20 20 20 20 20 20 20 20 20 20 76 61 6c 5b              val[
1260: 73 41 72 63 32 5d 20 3d 20 64 4b 65 79 54 72 61  sArc2] = dKeyTra
1270: 6e 73 5b 6e 4b 65 79 5d 0a 20 20 20 20 20 20 20  ns[nKey].       
1280: 20 72 65 74 75 72 6e 20 64 4e 65 77 47 72 61 70   return dNewGrap
1290: 68 0a 0a 20 20 20 20 64 65 66 20 5f 73 6f 72 74  h..    def _sort
12a0: 41 63 74 69 6f 6e 73 20 28 73 65 6c 66 2c 20 64  Actions (self, d
12b0: 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20  Graph):.        
12c0: 22 77 68 65 6e 20 61 20 70 61 74 74 65 72 6e 20  "when a pattern 
12d0: 69 73 20 66 6f 75 6e 64 2c 20 73 65 76 65 72 61  is found, severa
12e0: 6c 20 61 63 74 69 6f 6e 73 20 6d 61 79 20 62 65  l actions may be
12f0: 20 6c 61 75 6e 63 68 65 64 2c 20 61 6e 64 20 69   launched, and i
1300: 74 20 6d 75 73 74 20 62 65 20 70 65 72 66 6f 72  t must be perfor
1310: 6d 65 64 20 69 6e 20 61 20 63 65 72 74 61 69 6e  med in a certain
1320: 20 6f 72 64 65 72 22 0a 20 20 20 20 20 20 20 20   order".        
1330: 66 6f 72 20 5f 2c 20 64 56 61 6c 20 69 6e 20 64  for _, dVal in d
1340: 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20  Graph.items():. 
1350: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 22 3c             if "<
1360: 72 75 6c 65 73 3e 22 20 69 6e 20 64 56 61 6c 3a  rules>" in dVal:
1370: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1380: 20 66 6f 72 20 5f 2c 20 6e 4b 65 79 20 69 6e 20   for _, nKey in 
1390: 64 56 61 6c 5b 22 3c 72 75 6c 65 73 3e 22 5d 2e  dVal["<rules>"].
13a0: 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20  items():.       
13b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20 77               # w
13c0: 65 20 63 68 61 6e 67 65 20 74 68 65 20 64 69 63  e change the dic
13d0: 74 69 6f 6e 61 72 79 20 6f 66 20 61 63 74 69 6f  tionary of actio
13e0: 6e 73 20 69 6e 20 61 20 6c 69 73 74 20 6f 66 20  ns in a list of 
13f0: 61 63 74 69 6f 6e 73 20 28 76 61 6c 75 65 73 20  actions (values 
1400: 6f 66 20 64 69 63 74 69 6f 6e 61 72 79 20 61 6c  of dictionary al
1410: 6c 20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 20  l points to the 
1420: 66 69 6e 61 6c 20 6e 6f 64 65 29 0a 20 20 20 20  final node).    
1430: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1440: 69 66 20 69 73 69 6e 73 74 61 6e 63 65 28 64 47  if isinstance(dG
1450: 72 61 70 68 5b 6e 4b 65 79 5d 2c 20 64 69 63 74  raph[nKey], dict
1460: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ):.             
1470: 20 20 20 20 20 20 20 20 20 20 20 64 47 72 61 70             dGrap
1480: 68 5b 6e 4b 65 79 5d 20 3d 20 73 6f 72 74 65 64  h[nKey] = sorted
1490: 28 64 47 72 61 70 68 5b 6e 4b 65 79 5d 2e 6b 65  (dGraph[nKey].ke
14a0: 79 73 28 29 29 0a 0a 20 20 20 20 64 65 66 20 5f  ys())..    def _
14b0: 63 68 65 63 6b 52 65 67 65 78 65 73 20 28 73 65  checkRegexes (se
14c0: 6c 66 2c 20 64 47 72 61 70 68 29 3a 0a 20 20 20  lf, dGraph):.   
14d0: 20 20 20 20 20 22 63 68 65 63 6b 20 76 61 6c 69       "check vali
14e0: 64 69 74 79 20 6f 66 20 72 65 67 65 78 65 73 22  dity of regexes"
14f0: 0a 20 20 20 20 20 20 20 20 61 52 65 67 65 78 20  .        aRegex 
1500: 3d 20 73 65 74 28 29 0a 20 20 20 20 20 20 20 20  = set().        
1510: 66 6f 72 20 5f 2c 20 64 56 61 6c 20 69 6e 20 64  for _, dVal in d
1520: 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20  Graph.items():. 
1530: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 22 3c             if "<
1540: 72 65 5f 76 61 6c 75 65 3e 22 20 69 6e 20 64 56  re_value>" in dV
1550: 61 6c 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  al:.            
1560: 20 20 20 20 66 6f 72 20 73 52 65 67 65 78 20 69      for sRegex i
1570: 6e 20 64 56 61 6c 5b 22 3c 72 65 5f 76 61 6c 75  n dVal["<re_valu
1580: 65 3e 22 5d 3a 0a 20 20 20 20 20 20 20 20 20 20  e>"]:.          
1590: 20 20 20 20 20 20 20 20 20 20 69 66 20 73 52 65            if sRe
15a0: 67 65 78 20 6e 6f 74 20 69 6e 20 61 52 65 67 65  gex not in aRege
15b0: 78 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  x:.             
15c0: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
15d0: 5f 63 68 65 63 6b 52 65 67 65 78 28 73 52 65 67  _checkRegex(sReg
15e0: 65 78 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  ex).            
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 61 52 65 67              aReg
1600: 65 78 2e 61 64 64 28 73 52 65 67 65 78 29 0a 20  ex.add(sRegex). 
1610: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 22 3c             if "<
1620: 72 65 5f 6d 6f 72 70 68 3e 22 20 69 6e 20 64 56  re_morph>" in dV
1630: 61 6c 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  al:.            
1640: 20 20 20 20 66 6f 72 20 73 52 65 67 65 78 20 69      for sRegex i
1650: 6e 20 64 56 61 6c 5b 22 3c 72 65 5f 6d 6f 72 70  n dVal["<re_morp
1660: 68 3e 22 5d 3a 0a 20 20 20 20 20 20 20 20 20 20  h>"]:.          
1670: 20 20 20 20 20 20 20 20 20 20 69 66 20 73 52 65            if sRe
1680: 67 65 78 20 6e 6f 74 20 69 6e 20 61 52 65 67 65  gex not in aRege
1690: 78 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  x:.             
16a0: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
16b0: 5f 63 68 65 63 6b 52 65 67 65 78 28 73 52 65 67  _checkRegex(sReg
16c0: 65 78 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  ex).            
16d0: 20 20 20 20 20 20 20 20 20 20 20 20 61 52 65 67              aReg
16e0: 65 78 2e 61 64 64 28 73 52 65 67 65 78 29 0a 20  ex.add(sRegex). 
16f0: 20 20 20 20 20 20 20 61 52 65 67 65 78 2e 63 6c         aRegex.cl
1700: 65 61 72 28 29 0a 0a 20 20 20 20 64 65 66 20 5f  ear()..    def _
1710: 63 68 65 63 6b 52 65 67 65 78 20 28 73 65 6c 66  checkRegex (self
1720: 2c 20 73 52 65 67 65 78 29 3a 0a 20 20 20 20 20  , sRegex):.     
1730: 20 20 20 23 70 72 69 6e 74 28 73 52 65 67 65 78     #print(sRegex
1740: 29 0a 20 20 20 20 20 20 20 20 69 66 20 22 c2 ac  ).        if "..
1750: 22 20 69 6e 20 73 52 65 67 65 78 3a 0a 20 20 20  " in sRegex:.   
1760: 20 20 20 20 20 20 20 20 20 73 50 61 74 74 65 72           sPatter
1770: 6e 2c 20 73 4e 65 67 50 61 74 74 65 72 6e 20 3d  n, sNegPattern =
1780: 20 73 52 65 67 65 78 2e 73 70 6c 69 74 28 22 c2   sRegex.split(".
1790: ac 22 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  .").            
17a0: 74 72 79 3a 0a 20 20 20 20 20 20 20 20 20 20 20  try:.           
17b0: 20 20 20 20 20 69 66 20 6e 6f 74 20 73 4e 65 67       if not sNeg
17c0: 50 61 74 74 65 72 6e 3a 0a 20 20 20 20 20 20 20  Pattern:.       
17d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72 69               pri
17e0: 6e 74 28 22 23 20 57 61 72 6e 69 6e 67 21 20 45  nt("# Warning! E
17f0: 6d 70 74 79 20 6e 65 67 70 61 74 74 65 72 6e 3a  mpty negpattern:
1800: 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20 20 20  ", sRegex).     
1810: 20 20 20 20 20 20 20 20 20 20 20 72 65 2e 63 6f             re.co
1820: 6d 70 69 6c 65 28 73 50 61 74 74 65 72 6e 29 0a  mpile(sPattern).
1830: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1840: 69 66 20 73 4e 65 67 50 61 74 74 65 72 6e 20 21  if sNegPattern !
1850: 3d 20 22 2a 22 3a 0a 20 20 20 20 20 20 20 20 20  = "*":.         
1860: 20 20 20 20 20 20 20 20 20 20 20 72 65 2e 63 6f             re.co
1870: 6d 70 69 6c 65 28 73 4e 65 67 50 61 74 74 65 72  mpile(sNegPatter
1880: 6e 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  n).            e
1890: 78 63 65 70 74 20 72 65 2e 65 72 72 6f 72 3a 0a  xcept re.error:.
18a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
18b0: 70 72 69 6e 74 28 22 23 20 45 72 72 6f 72 2e 20  print("# Error. 
18c0: 57 72 6f 6e 67 20 72 65 67 65 78 3a 22 2c 20 73  Wrong regex:", s
18d0: 52 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20  Regex).         
18e0: 20 20 20 20 20 20 20 65 78 69 74 28 29 0a 20 20         exit().  
18f0: 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20        else:.    
1900: 20 20 20 20 20 20 20 20 74 72 79 3a 0a 20 20 20          try:.   
1910: 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20               if 
1920: 6e 6f 74 20 73 52 65 67 65 78 3a 0a 20 20 20 20  not sRegex:.    
1930: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1940: 70 72 69 6e 74 28 22 23 20 57 61 72 6e 69 6e 67  print("# Warning
1950: 21 20 45 6d 70 74 79 20 70 61 74 74 65 72 6e 3a  ! Empty pattern:
1960: 22 2c 20 73 52 65 67 65 78 29 0a 20 20 20 20 20  ", sRegex).     
1970: 20 20 20 20 20 20 20 20 20 20 20 72 65 2e 63 6f             re.co
1980: 6d 70 69 6c 65 28 73 52 65 67 65 78 29 0a 20 20  mpile(sRegex).  
1990: 20 20 20 20 20 20 20 20 20 20 65 78 63 65 70 74            except
19a0: 20 72 65 2e 65 72 72 6f 72 3a 0a 20 20 20 20 20   re.error:.     
19b0: 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74             print
19c0: 28 22 23 20 45 72 72 6f 72 2e 20 57 72 6f 6e 67  ("# Error. Wrong
19d0: 20 72 65 67 65 78 3a 22 2c 20 73 52 65 67 65 78   regex:", sRegex
19e0: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ).              
19f0: 20 20 65 78 69 74 28 29 0a 0a 0a 63 6c 61 73 73    exit()...class
1a00: 20 4e 6f 64 65 3a 0a 20 20 20 20 22 22 22 4e 6f   Node:.    """No
1a10: 64 65 20 6f 66 20 74 68 65 20 72 75 6c 65 20 67  de of the rule g
1a20: 72 61 70 68 22 22 22 0a 0a 20 20 20 20 4e 65 78  raph"""..    Nex
1a30: 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64 65 66  tId = 0..    def
1a40: 20 5f 5f 69 6e 69 74 5f 5f 20 28 73 65 6c 66 29   __init__ (self)
1a50: 3a 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 69  :.        self.i
1a60: 20 3d 20 4e 6f 64 65 2e 4e 65 78 74 49 64 0a 20   = Node.NextId. 
1a70: 20 20 20 20 20 20 20 4e 6f 64 65 2e 4e 65 78 74         Node.Next
1a80: 49 64 20 2b 3d 20 31 0a 20 20 20 20 20 20 20 20  Id += 1.        
1a90: 73 65 6c 66 2e 62 46 69 6e 61 6c 20 3d 20 46 61  self.bFinal = Fa
1aa0: 6c 73 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66  lse.        self
1ab0: 2e 64 41 72 63 73 20 3d 20 7b 7d 20 20 20 20 20  .dArcs = {}     
1ac0: 20 20 20 20 20 23 20 6b 65 79 3a 20 61 72 63 20       # key: arc 
1ad0: 76 61 6c 75 65 3b 20 76 61 6c 75 65 3a 20 61 20  value; value: a 
1ae0: 6e 6f 64 65 0a 0a 20 20 20 20 40 63 6c 61 73 73  node..    @class
1af0: 6d 65 74 68 6f 64 0a 20 20 20 20 64 65 66 20 72  method.    def r
1b00: 65 73 65 74 4e 65 78 74 49 64 20 28 63 6c 73 29  esetNextId (cls)
1b10: 3a 0a 20 20 20 20 20 20 20 20 22 72 65 73 65 74  :.        "reset
1b20: 20 74 6f 20 30 20 74 68 65 20 6e 6f 64 65 20 63   to 0 the node c
1b30: 6f 75 6e 74 65 72 22 0a 20 20 20 20 20 20 20 20  ounter".        
1b40: 63 6c 73 2e 4e 65 78 74 49 64 20 3d 20 30 0a 0a  cls.NextId = 0..
1b50: 20 20 20 20 64 65 66 20 5f 5f 73 74 72 5f 5f 20      def __str__ 
1b60: 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20  (self):.        
1b70: 23 20 43 61 75 74 69 6f 6e 21 20 74 68 69 73 20  # Caution! this 
1b80: 66 75 6e 63 74 69 6f 6e 20 69 73 20 75 73 65 64  function is used
1b90: 20 66 6f 72 20 68 61 73 68 69 6e 67 20 61 6e 64   for hashing and
1ba0: 20 63 6f 6d 70 61 72 69 73 6f 6e 21 0a 20 20 20   comparison!.   
1bb0: 20 20 20 20 20 63 46 69 6e 61 6c 20 3d 20 22 31       cFinal = "1
1bc0: 22 20 20 69 66 20 73 65 6c 66 2e 62 46 69 6e 61  "  if self.bFina
1bd0: 6c 20 20 65 6c 73 65 20 22 30 22 0a 20 20 20 20  l  else "0".    
1be0: 20 20 20 20 6c 20 3d 20 5b 63 46 69 6e 61 6c 5d      l = [cFinal]
1bf0: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 28 6b 65  .        for (ke
1c00: 79 2c 20 6f 4e 6f 64 65 29 20 69 6e 20 73 65 6c  y, oNode) in sel
1c10: 66 2e 64 41 72 63 73 2e 69 74 65 6d 73 28 29 3a  f.dArcs.items():
1c20: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6c 2e 61  .            l.a
1c30: 70 70 65 6e 64 28 73 74 72 28 6b 65 79 29 29 0a  ppend(str(key)).
1c40: 20 20 20 20 20 20 20 20 20 20 20 20 6c 2e 61 70              l.ap
1c50: 70 65 6e 64 28 73 74 72 28 6f 4e 6f 64 65 2e 69  pend(str(oNode.i
1c60: 29 29 0a 20 20 20 20 20 20 20 20 72 65 74 75 72  )).        retur
1c70: 6e 20 22 5f 22 2e 6a 6f 69 6e 28 6c 29 0a 0a 20  n "_".join(l).. 
1c80: 20 20 20 64 65 66 20 5f 5f 68 61 73 68 5f 5f 20     def __hash__ 
1c90: 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20  (self):.        
1ca0: 23 20 55 73 65 64 20 61 73 20 61 20 6b 65 79 20  # Used as a key 
1cb0: 69 6e 20 61 20 70 79 74 68 6f 6e 20 64 69 63 74  in a python dict
1cc0: 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20 20 20 20  ionary..        
1cd0: 72 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73 74  return self.__st
1ce0: 72 5f 5f 28 29 2e 5f 5f 68 61 73 68 5f 5f 28 29  r__().__hash__()
1cf0: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 65 71 5f 5f  ..    def __eq__
1d00: 20 28 73 65 6c 66 2c 20 6f 74 68 65 72 29 3a 0a   (self, other):.
1d10: 20 20 20 20 20 20 20 20 23 20 55 73 65 64 20 61          # Used a
1d20: 73 20 61 20 6b 65 79 20 69 6e 20 61 20 70 79 74  s a key in a pyt
1d30: 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72 79 2e 0a  hon dictionary..
1d40: 20 20 20 20 20 20 20 20 23 20 4e 6f 64 65 73 20          # Nodes 
1d50: 61 72 65 20 65 71 75 69 76 61 6c 65 6e 74 20 69  are equivalent i
1d60: 66 20 74 68 65 79 20 68 61 76 65 20 69 64 65 6e  f they have iden
1d70: 74 69 63 61 6c 20 61 72 63 73 2c 20 61 6e 64 20  tical arcs, and 
1d80: 65 61 63 68 20 69 64 65 6e 74 69 63 61 6c 20 61  each identical a
1d90: 72 63 20 6c 65 61 64 73 20 74 6f 20 69 64 65 6e  rc leads to iden
1da0: 74 69 63 61 6c 20 73 74 61 74 65 73 2e 0a 20 20  tical states..  
1db0: 20 20 20 20 20 20 72 65 74 75 72 6e 20 73 65 6c        return sel
1dc0: 66 2e 5f 5f 73 74 72 5f 5f 28 29 20 3d 3d 20 6f  f.__str__() == o
1dd0: 74 68 65 72 2e 5f 5f 73 74 72 5f 5f 28 29 0a 0a  ther.__str__()..
1de0: 20 20 20 20 64 65 66 20 67 65 74 4e 6f 64 65 41      def getNodeA
1df0: 73 44 69 63 74 20 28 73 65 6c 66 29 3a 0a 20 20  sDict (self):.  
1e00: 20 20 20 20 20 20 22 72 65 74 75 72 6e 73 20 74        "returns t
1e10: 68 65 20 6e 6f 64 65 20 61 73 20 61 20 64 69 63  he node as a dic
1e20: 74 69 6f 6e 61 72 79 20 73 74 72 75 63 74 75 72  tionary structur
1e30: 65 22 0a 20 20 20 20 20 20 20 20 64 4e 6f 64 65  e".        dNode
1e40: 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 52   = {}.        dR
1e50: 65 56 61 6c 75 65 20 3d 20 7b 7d 20 20 20 23 20  eValue = {}   # 
1e60: 72 65 67 65 78 20 66 6f 72 20 74 6f 6b 65 6e 20  regex for token 
1e70: 76 61 6c 75 65 73 0a 20 20 20 20 20 20 20 20 64  values.        d
1e80: 52 65 4d 6f 72 70 68 20 3d 20 7b 7d 20 20 20 23  ReMorph = {}   #
1e90: 20 72 65 67 65 78 20 66 6f 72 20 6d 6f 72 70 68   regex for morph
1ea0: 0a 20 20 20 20 20 20 20 20 64 4d 6f 72 70 68 20  .        dMorph 
1eb0: 3d 20 7b 7d 20 20 20 20 20 23 20 73 69 6d 70 6c  = {}     # simpl
1ec0: 65 20 73 65 61 72 63 68 20 69 6e 20 6d 6f 72 70  e search in morp
1ed0: 68 0a 20 20 20 20 20 20 20 20 64 4c 65 6d 6d 61  h.        dLemma
1ee0: 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 4d   = {}.        dM
1ef0: 65 74 61 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20  eta = {}.       
1f00: 20 64 54 61 67 20 3d 20 7b 7d 0a 20 20 20 20 20   dTag = {}.     
1f10: 20 20 20 64 52 75 6c 65 20 3d 20 7b 7d 0a 20 20     dRule = {}.  
1f20: 20 20 20 20 20 20 66 6f 72 20 73 41 72 63 2c 20        for sArc, 
1f30: 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 64 41  oNode in self.dA
1f40: 72 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20  rcs.items():.   
1f50: 20 20 20 20 20 20 20 20 20 69 66 20 73 41 72 63           if sArc
1f60: 2e 73 74 61 72 74 73 77 69 74 68 28 22 40 22 29  .startswith("@")
1f70: 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e   and len(sArc) >
1f80: 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20   1:.            
1f90: 20 20 20 20 64 52 65 4d 6f 72 70 68 5b 73 41 72      dReMorph[sAr
1fa0: 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f  c[1:]] = oNode._
1fb0: 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20  _hash__().      
1fc0: 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e        elif sArc.
1fd0: 73 74 61 72 74 73 77 69 74 68 28 22 24 22 29 20  startswith("$") 
1fe0: 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20  and len(sArc) > 
1ff0: 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1:.             
2000: 20 20 20 64 4d 6f 72 70 68 5b 73 41 72 63 5b 31     dMorph[sArc[1
2010: 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61  :]] = oNode.__ha
2020: 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20  sh__().         
2030: 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61     elif sArc.sta
2040: 72 74 73 77 69 74 68 28 22 7e 22 29 20 61 6e 64  rtswith("~") and
2050: 20 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a   len(sArc) > 1:.
2060: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2070: 64 52 65 56 61 6c 75 65 5b 73 41 72 63 5b 31 3a  dReValue[sArc[1:
2080: 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73  ]] = oNode.__has
2090: 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20  h__().          
20a0: 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72    elif sArc.star
20b0: 74 73 77 69 74 68 28 22 3e 22 29 20 61 6e 64 20  tswith(">") and 
20c0: 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20  len(sArc) > 1:. 
20d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64                 d
20e0: 4c 65 6d 6d 61 5b 73 41 72 63 5b 31 3a 5d 5d 20  Lemma[sArc[1:]] 
20f0: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
2100: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
2110: 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74 73 77  lif sArc.startsw
2120: 69 74 68 28 22 2a 22 29 20 61 6e 64 20 6c 65 6e  ith("*") and len
2130: 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20 20 20  (sArc) > 1:.    
2140: 20 20 20 20 20 20 20 20 20 20 20 20 64 4d 65 74              dMet
2150: 61 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e  a[sArc[1:]] = oN
2160: 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20  ode.__hash__(). 
2170: 20 20 20 20 20 20 20 20 20 20 20 65 6c 69 66 20             elif 
2180: 73 41 72 63 2e 73 74 61 72 74 73 77 69 74 68 28  sArc.startswith(
2190: 22 2f 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72  "/") and len(sAr
21a0: 63 29 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20  c) > 1:.        
21b0: 20 20 20 20 20 20 20 20 64 54 61 67 5b 73 41 72          dTag[sAr
21c0: 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f  c[1:]] = oNode._
21d0: 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20  _hash__().      
21e0: 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e        elif sArc.
21f0: 73 74 61 72 74 73 77 69 74 68 28 22 23 23 22 29  startswith("##")
2200: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
2210: 20 20 64 52 75 6c 65 5b 73 41 72 63 5b 31 3a 5d    dRule[sArc[1:]
2220: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
2230: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
2240: 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20   else:.         
2250: 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 73 41 72         dNode[sAr
2260: 63 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73  c] = oNode.__has
2270: 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 69 66  h__().        if
2280: 20 64 52 65 56 61 6c 75 65 3a 0a 20 20 20 20 20   dReValue:.     
2290: 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72         dNode["<r
22a0: 65 5f 76 61 6c 75 65 3e 22 5d 20 3d 20 64 52 65  e_value>"] = dRe
22b0: 56 61 6c 75 65 0a 20 20 20 20 20 20 20 20 69 66  Value.        if
22c0: 20 64 52 65 4d 6f 72 70 68 3a 0a 20 20 20 20 20   dReMorph:.     
22d0: 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 72         dNode["<r
22e0: 65 5f 6d 6f 72 70 68 3e 22 5d 20 3d 20 64 52 65  e_morph>"] = dRe
22f0: 4d 6f 72 70 68 0a 20 20 20 20 20 20 20 20 69 66  Morph.        if
2300: 20 64 4d 6f 72 70 68 3a 0a 20 20 20 20 20 20 20   dMorph:.       
2310: 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 6d 6f 72       dNode["<mor
2320: 70 68 3e 22 5d 20 3d 20 64 4d 6f 72 70 68 0a 20  ph>"] = dMorph. 
2330: 20 20 20 20 20 20 20 69 66 20 64 4c 65 6d 6d 61         if dLemma
2340: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e  :.            dN
2350: 6f 64 65 5b 22 3c 6c 65 6d 6d 61 73 3e 22 5d 20  ode["<lemmas>"] 
2360: 3d 20 64 4c 65 6d 6d 61 0a 20 20 20 20 20 20 20  = dLemma.       
2370: 20 69 66 20 64 54 61 67 3a 0a 20 20 20 20 20 20   if dTag:.      
2380: 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 74 61        dNode["<ta
2390: 67 73 3e 22 5d 20 3d 20 64 54 61 67 0a 20 20 20  gs>"] = dTag.   
23a0: 20 20 20 20 20 69 66 20 64 4d 65 74 61 3a 0a 20       if dMeta:. 
23b0: 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65             dNode
23c0: 5b 22 3c 6d 65 74 61 3e 22 5d 20 3d 20 64 4d 65  ["<meta>"] = dMe
23d0: 74 61 0a 20 20 20 20 20 20 20 20 69 66 20 64 52  ta.        if dR
23e0: 75 6c 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20  ule:.           
23f0: 20 64 4e 6f 64 65 5b 22 3c 72 75 6c 65 73 3e 22   dNode["<rules>"
2400: 5d 20 3d 20 64 52 75 6c 65 0a 20 20 20 20 20 20  ] = dRule.      
2410: 20 20 23 69 66 20 73 65 6c 66 2e 62 46 69 6e 61    #if self.bFina
2420: 6c 3a 0a 20 20 20 20 20 20 20 20 23 20 20 20 20  l:.        #    
2430: 64 4e 6f 64 65 5b 22 3c 66 69 6e 61 6c 3e 22 5d  dNode["<final>"]
2440: 20 3d 20 31 0a 20 20 20 20 20 20 20 20 72 65 74   = 1.        ret
2450: 75 72 6e 20 64 4e 6f 64 65 0a                    urn dNode.