Grammalecte  Hex Artifact Content

Artifact 02fc45c5348ed3fc9b3f366a663461efb7559185f63fd36c39f68ceff758774e:


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 66 72 6f 6d 20 67 72 61 70 68  ack...from graph
0070: 73 70 65 6c 6c 2e 70 72 6f 67 72 65 73 73 62 61  spell.progressba
0080: 72 20 69 6d 70 6f 72 74 20 50 72 6f 67 72 65 73  r import Progres
0090: 73 42 61 72 0a 0a 0a 63 6c 61 73 73 20 44 41 52  sBar...class DAR
00a0: 47 3a 0a 20 20 20 20 22 22 22 44 49 52 45 43 54  G:.    """DIRECT
00b0: 20 41 43 59 43 4c 49 43 20 52 55 4c 45 20 47 52   ACYCLIC RULE GR
00c0: 41 50 48 22 22 22 0a 20 20 20 20 23 20 54 68 69  APH""".    # Thi
00d0: 73 20 63 6f 64 65 20 69 73 20 69 6e 73 70 69 72  s code is inspir
00e0: 65 64 20 66 72 6f 6d 20 53 74 65 76 65 20 48 61  ed from Steve Ha
00f0: 6e 6f 76 e2 80 99 73 20 44 41 57 47 2c 20 32 30  nov...s DAWG, 20
0100: 31 31 2e 20 28 68 74 74 70 3a 2f 2f 73 74 65 76  11. (http://stev
0110: 65 68 61 6e 6f 76 2e 63 61 2f 62 6c 6f 67 2f 69  ehanov.ca/blog/i
0120: 6e 64 65 78 2e 70 68 70 3f 69 64 3d 31 31 35 29  ndex.php?id=115)
0130: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 69 6e 69 74  ..    def __init
0140: 5f 5f 20 28 73 65 6c 66 2c 20 6c 52 75 6c 65 2c  __ (self, lRule,
0150: 20 73 4c 61 6e 67 43 6f 64 65 29 3a 0a 20 20 20   sLangCode):.   
0160: 20 20 20 20 20 70 72 69 6e 74 28 22 3d 3d 3d 3d       print("====
0170: 3d 20 44 69 72 65 63 74 20 41 63 79 63 6c 69 63  = Direct Acyclic
0180: 20 52 75 6c 65 20 47 72 61 70 68 20 2d 20 4d 69   Rule Graph - Mi
0190: 6e 69 6d 61 6c 20 41 63 79 63 6c 69 63 20 46 69  nimal Acyclic Fi
01a0: 6e 69 74 65 20 53 74 61 74 65 20 41 75 74 6f 6d  nite State Autom
01b0: 61 74 6f 6e 20 3d 3d 3d 3d 3d 22 29 0a 0a 20 20  aton =====")..  
01c0: 20 20 20 20 20 20 23 20 50 72 65 70 61 72 69 6e        # Preparin
01d0: 67 20 44 41 52 47 0a 20 20 20 20 20 20 20 20 70  g DARG.        p
01e0: 72 69 6e 74 28 22 20 3e 20 50 72 65 70 61 72 69  rint(" > Prepari
01f0: 6e 67 20 6c 69 73 74 20 6f 66 20 74 6f 6b 65 6e  ng list of token
0200: 73 22 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66  s").        self
0210: 2e 73 4c 61 6e 67 43 6f 64 65 20 3d 20 73 4c 61  .sLangCode = sLa
0220: 6e 67 43 6f 64 65 0a 20 20 20 20 20 20 20 20 73  ngCode.        s
0230: 65 6c 66 2e 6e 52 75 6c 65 20 3d 20 6c 65 6e 28  elf.nRule = len(
0240: 6c 52 75 6c 65 29 0a 20 20 20 20 20 20 20 20 73  lRule).        s
0250: 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c  elf.aPreviousRul
0260: 65 20 3d 20 5b 5d 0a 20 20 20 20 20 20 20 20 4e  e = [].        N
0270: 6f 64 65 2e 72 65 73 65 74 4e 65 78 74 49 64 28  ode.resetNextId(
0280: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6f  ).        self.o
0290: 52 6f 6f 74 20 3d 20 4e 6f 64 65 28 29 0a 20 20  Root = Node().  
02a0: 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e 63 68        self.lUnch
02b0: 65 63 6b 65 64 4e 6f 64 65 73 20 3d 20 5b 5d 20  eckedNodes = [] 
02c0: 20 23 20 6c 69 73 74 20 6f 66 20 6e 6f 64 65 73   # list of nodes
02d0: 20 74 68 61 74 20 68 61 76 65 20 6e 6f 74 20 62   that have not b
02e0: 65 65 6e 20 63 68 65 63 6b 65 64 20 66 6f 72 20  een checked for 
02f0: 64 75 70 6c 69 63 61 74 69 6f 6e 2e 0a 20 20 20  duplication..   
0300: 20 20 20 20 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d       self.lMinim
0310: 69 7a 65 64 4e 6f 64 65 73 20 3d 20 7b 7d 20 20  izedNodes = {}  
0320: 23 20 6c 69 73 74 20 6f 66 20 75 6e 69 71 75 65  # list of unique
0330: 20 6e 6f 64 65 73 20 74 68 61 74 20 68 61 76 65   nodes that have
0340: 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20 66 6f   been checked fo
0350: 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e 0a 20  r duplication.. 
0360: 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 4e 6f 64         self.nNod
0370: 65 20 3d 20 30 0a 20 20 20 20 20 20 20 20 73 65  e = 0.        se
0380: 6c 66 2e 6e 41 72 63 20 3d 20 30 0a 0a 20 20 20  lf.nArc = 0..   
0390: 20 20 20 20 20 23 20 62 75 69 6c 64 0a 20 20 20       # build.   
03a0: 20 20 20 20 20 6c 52 75 6c 65 2e 73 6f 72 74 28       lRule.sort(
03b0: 29 0a 20 20 20 20 20 20 20 20 6f 50 72 6f 67 42  ).        oProgB
03c0: 61 72 20 3d 20 50 72 6f 67 72 65 73 73 42 61 72  ar = ProgressBar
03d0: 28 30 2c 20 6c 65 6e 28 6c 52 75 6c 65 29 29 0a  (0, len(lRule)).
03e0: 20 20 20 20 20 20 20 20 66 6f 72 20 61 52 75 6c          for aRul
03f0: 65 20 69 6e 20 6c 52 75 6c 65 3a 0a 20 20 20 20  e in lRule:.    
0400: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 69 6e 73          self.ins
0410: 65 72 74 28 61 52 75 6c 65 29 0a 20 20 20 20 20  ert(aRule).     
0420: 20 20 20 20 20 20 20 6f 50 72 6f 67 42 61 72 2e         oProgBar.
0430: 69 6e 63 72 65 6d 65 6e 74 28 31 29 0a 20 20 20  increment(1).   
0440: 20 20 20 20 20 6f 50 72 6f 67 42 61 72 2e 64 6f       oProgBar.do
0450: 6e 65 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c  ne().        sel
0460: 66 2e 66 69 6e 69 73 68 28 29 0a 20 20 20 20 20  f.finish().     
0470: 20 20 20 73 65 6c 66 2e 63 6f 75 6e 74 4e 6f 64     self.countNod
0480: 65 73 28 29 0a 20 20 20 20 20 20 20 20 73 65 6c  es().        sel
0490: 66 2e 63 6f 75 6e 74 41 72 63 73 28 29 0a 20 20  f.countArcs().  
04a0: 20 20 20 20 20 20 73 65 6c 66 2e 64 69 73 70 6c        self.displ
04b0: 61 79 49 6e 66 6f 28 29 0a 0a 20 20 20 20 23 20  ayInfo()..    # 
04c0: 42 55 49 4c 44 20 44 41 52 47 0a 20 20 20 20 64  BUILD DARG.    d
04d0: 65 66 20 69 6e 73 65 72 74 20 28 73 65 6c 66 2c  ef insert (self,
04e0: 20 61 52 75 6c 65 29 3a 0a 20 20 20 20 20 20 20   aRule):.       
04f0: 20 22 69 6e 73 65 72 74 20 61 20 6e 65 77 20 72   "insert a new r
0500: 75 6c 65 20 28 74 6f 6b 65 6e 73 20 6d 75 73 74  ule (tokens must
0510: 20 62 65 20 69 6e 73 65 72 74 65 64 20 69 6e 20   be inserted in 
0520: 6f 72 64 65 72 29 22 0a 20 20 20 20 20 20 20 20  order)".        
0530: 69 66 20 61 52 75 6c 65 20 3c 20 73 65 6c 66 2e  if aRule < self.
0540: 61 50 72 65 76 69 6f 75 73 52 75 6c 65 3a 0a 20  aPreviousRule:. 
0550: 20 20 20 20 20 20 20 20 20 20 20 65 78 69 74 28             exit(
0560: 22 23 20 45 72 72 6f 72 3a 20 74 6f 6b 65 6e 73  "# Error: tokens
0570: 20 6d 75 73 74 20 62 65 20 69 6e 73 65 72 74 65   must be inserte
0580: 64 20 69 6e 20 6f 72 64 65 72 2e 22 29 0a 0a 20  d in order.").. 
0590: 20 20 20 20 20 20 20 23 20 66 69 6e 64 20 63 6f         # find co
05a0: 6d 6d 6f 6e 20 70 72 65 66 69 78 20 62 65 74 77  mmon prefix betw
05b0: 65 65 6e 20 77 6f 72 64 20 61 6e 64 20 70 72 65  een word and pre
05c0: 76 69 6f 75 73 20 77 6f 72 64 0a 20 20 20 20 20  vious word.     
05d0: 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78     nCommonPrefix
05e0: 20 3d 20 30 0a 20 20 20 20 20 20 20 20 66 6f 72   = 0.        for
05f0: 20 69 20 69 6e 20 72 61 6e 67 65 28 6d 69 6e 28   i in range(min(
0600: 6c 65 6e 28 61 52 75 6c 65 29 2c 20 6c 65 6e 28  len(aRule), len(
0610: 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75  self.aPreviousRu
0620: 6c 65 29 29 29 3a 0a 20 20 20 20 20 20 20 20 20  le))):.         
0630: 20 20 20 69 66 20 61 52 75 6c 65 5b 69 5d 20 21     if aRule[i] !
0640: 3d 20 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73  = self.aPrevious
0650: 52 75 6c 65 5b 69 5d 3a 0a 20 20 20 20 20 20 20  Rule[i]:.       
0660: 20 20 20 20 20 20 20 20 20 62 72 65 61 6b 0a 20           break. 
0670: 20 20 20 20 20 20 20 20 20 20 20 6e 43 6f 6d 6d             nComm
0680: 6f 6e 50 72 65 66 69 78 20 2b 3d 20 31 0a 0a 20  onPrefix += 1.. 
0690: 20 20 20 20 20 20 20 23 20 43 68 65 63 6b 20 74         # Check t
06a0: 68 65 20 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64  he lUncheckedNod
06b0: 65 73 20 66 6f 72 20 72 65 64 75 6e 64 61 6e 74  es for redundant
06c0: 20 6e 6f 64 65 73 2c 20 70 72 6f 63 65 65 64 69   nodes, proceedi
06d0: 6e 67 20 66 72 6f 6d 20 6c 61 73 74 0a 20 20 20  ng from last.   
06e0: 20 20 20 20 20 23 20 6f 6e 65 20 64 6f 77 6e 20       # one down 
06f0: 74 6f 20 74 68 65 20 63 6f 6d 6d 6f 6e 20 70 72  to the common pr
0700: 65 66 69 78 20 73 69 7a 65 2e 20 54 68 65 6e 20  efix size. Then 
0710: 74 72 75 6e 63 61 74 65 20 74 68 65 20 6c 69 73  truncate the lis
0720: 74 20 61 74 20 74 68 61 74 20 70 6f 69 6e 74 2e  t at that point.
0730: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f 6d  .        self._m
0740: 69 6e 69 6d 69 7a 65 28 6e 43 6f 6d 6d 6f 6e 50  inimize(nCommonP
0750: 72 65 66 69 78 29 0a 0a 20 20 20 20 20 20 20 20  refix)..        
0760: 23 20 61 64 64 20 74 68 65 20 73 75 66 66 69 78  # add the suffix
0770: 2c 20 73 74 61 72 74 69 6e 67 20 66 72 6f 6d 20  , starting from 
0780: 74 68 65 20 63 6f 72 72 65 63 74 20 6e 6f 64 65  the correct node
0790: 20 6d 69 64 2d 77 61 79 20 74 68 72 6f 75 67 68   mid-way through
07a0: 20 74 68 65 20 67 72 61 70 68 0a 20 20 20 20 20   the graph.     
07b0: 20 20 20 69 66 20 6c 65 6e 28 73 65 6c 66 2e 6c     if len(self.l
07c0: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 29 20  UncheckedNodes) 
07d0: 3d 3d 20 30 3a 0a 20 20 20 20 20 20 20 20 20 20  == 0:.          
07e0: 20 20 6f 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6f    oNode = self.o
07f0: 52 6f 6f 74 0a 20 20 20 20 20 20 20 20 65 6c 73  Root.        els
0800: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f  e:.            o
0810: 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6c 55 6e 63  Node = self.lUnc
0820: 68 65 63 6b 65 64 4e 6f 64 65 73 5b 2d 31 5d 5b  heckedNodes[-1][
0830: 32 5d 0a 0a 20 20 20 20 20 20 20 20 69 54 6f 6b  2]..        iTok
0840: 65 6e 20 3d 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66  en = nCommonPref
0850: 69 78 0a 20 20 20 20 20 20 20 20 66 6f 72 20 73  ix.        for s
0860: 54 6f 6b 65 6e 20 69 6e 20 61 52 75 6c 65 5b 6e  Token in aRule[n
0870: 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 3a 5d 3a 0a  CommonPrefix:]:.
0880: 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 65 78              oNex
0890: 74 4e 6f 64 65 20 3d 20 4e 6f 64 65 28 29 0a 20  tNode = Node(). 
08a0: 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65             oNode
08b0: 2e 64 41 72 63 73 5b 73 54 6f 6b 65 6e 5d 20 3d  .dArcs[sToken] =
08c0: 20 6f 4e 65 78 74 4e 6f 64 65 0a 20 20 20 20 20   oNextNode.     
08d0: 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e 63         self.lUnc
08e0: 68 65 63 6b 65 64 4e 6f 64 65 73 2e 61 70 70 65  heckedNodes.appe
08f0: 6e 64 28 28 6f 4e 6f 64 65 2c 20 73 54 6f 6b 65  nd((oNode, sToke
0900: 6e 2c 20 6f 4e 65 78 74 4e 6f 64 65 29 29 0a 20  n, oNextNode)). 
0910: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 69 54             if iT
0920: 6f 6b 65 6e 20 3d 3d 20 28 6c 65 6e 28 61 52 75  oken == (len(aRu
0930: 6c 65 29 20 2d 20 32 29 3a 0a 20 20 20 20 20 20  le) - 2):.      
0940: 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e            oNode.
0950: 62 46 69 6e 61 6c 20 3d 20 54 72 75 65 0a 20 20  bFinal = True.  
0960: 20 20 20 20 20 20 20 20 20 20 69 54 6f 6b 65 6e            iToken
0970: 20 2b 3d 20 31 0a 20 20 20 20 20 20 20 20 20 20   += 1.          
0980: 20 20 6f 4e 6f 64 65 20 3d 20 6f 4e 65 78 74 4e    oNode = oNextN
0990: 6f 64 65 0a 20 20 20 20 20 20 20 20 6f 4e 6f 64  ode.        oNod
09a0: 65 2e 62 46 69 6e 61 6c 20 3d 20 54 72 75 65 0a  e.bFinal = True.
09b0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 61 50 72          self.aPr
09c0: 65 76 69 6f 75 73 52 75 6c 65 20 3d 20 61 52 75  eviousRule = aRu
09d0: 6c 65 0a 0a 20 20 20 20 64 65 66 20 66 69 6e 69  le..    def fini
09e0: 73 68 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  sh (self):.     
09f0: 20 20 20 22 6d 69 6e 69 6d 69 7a 65 20 75 6e 63     "minimize unc
0a00: 68 65 63 6b 65 64 20 6e 6f 64 65 73 22 0a 20 20  hecked nodes".  
0a10: 20 20 20 20 20 20 73 65 6c 66 2e 5f 6d 69 6e 69        self._mini
0a20: 6d 69 7a 65 28 30 29 0a 0a 20 20 20 20 64 65 66  mize(0)..    def
0a30: 20 5f 6d 69 6e 69 6d 69 7a 65 20 28 73 65 6c 66   _minimize (self
0a40: 2c 20 64 6f 77 6e 54 6f 29 3a 0a 20 20 20 20 20  , downTo):.     
0a50: 20 20 20 23 20 70 72 6f 63 65 65 64 20 66 72 6f     # proceed fro
0a60: 6d 20 74 68 65 20 6c 65 61 66 20 75 70 20 74 6f  m the leaf up to
0a70: 20 61 20 63 65 72 74 61 69 6e 20 70 6f 69 6e 74   a certain point
0a80: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 69 20 69  .        for i i
0a90: 6e 20 72 61 6e 67 65 28 20 6c 65 6e 28 73 65 6c  n range( len(sel
0aa0: 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65  f.lUncheckedNode
0ab0: 73 29 2d 31 2c 20 64 6f 77 6e 54 6f 2d 31 2c 20  s)-1, downTo-1, 
0ac0: 2d 31 20 29 3a 0a 20 20 20 20 20 20 20 20 20 20  -1 ):.          
0ad0: 20 20 6f 4e 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c    oNode, sToken,
0ae0: 20 6f 43 68 69 6c 64 4e 6f 64 65 20 3d 20 73 65   oChildNode = se
0af0: 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64  lf.lUncheckedNod
0b00: 65 73 5b 69 5d 0a 20 20 20 20 20 20 20 20 20 20  es[i].          
0b10: 20 20 69 66 20 6f 43 68 69 6c 64 4e 6f 64 65 20    if oChildNode 
0b20: 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a  in self.lMinimiz
0b30: 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20 20  edNodes:.       
0b40: 20 20 20 20 20 20 20 20 20 23 20 72 65 70 6c 61           # repla
0b50: 63 65 20 74 68 65 20 63 68 69 6c 64 20 77 69 74  ce the child wit
0b60: 68 20 74 68 65 20 70 72 65 76 69 6f 75 73 6c 79  h the previously
0b70: 20 65 6e 63 6f 75 6e 74 65 72 65 64 20 6f 6e 65   encountered one
0b80: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0b90: 20 6f 4e 6f 64 65 2e 64 41 72 63 73 5b 73 54 6f   oNode.dArcs[sTo
0ba0: 6b 65 6e 5d 20 3d 20 73 65 6c 66 2e 6c 4d 69 6e  ken] = self.lMin
0bb0: 69 6d 69 7a 65 64 4e 6f 64 65 73 5b 6f 43 68 69  imizedNodes[oChi
0bc0: 6c 64 4e 6f 64 65 5d 0a 20 20 20 20 20 20 20 20  ldNode].        
0bd0: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
0be0: 20 20 20 20 20 20 20 20 20 20 23 20 61 64 64 20            # add 
0bf0: 74 68 65 20 73 74 61 74 65 20 74 6f 20 74 68 65  the state to the
0c00: 20 6d 69 6e 69 6d 69 7a 65 64 20 6e 6f 64 65 73   minimized nodes
0c10: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
0c20: 20 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65    self.lMinimize
0c30: 64 4e 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f 64  dNodes[oChildNod
0c40: 65 5d 20 3d 20 6f 43 68 69 6c 64 4e 6f 64 65 0a  e] = oChildNode.
0c50: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
0c60: 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73  .lUncheckedNodes
0c70: 2e 70 6f 70 28 29 0a 0a 20 20 20 20 64 65 66 20  .pop()..    def 
0c80: 63 6f 75 6e 74 4e 6f 64 65 73 20 28 73 65 6c 66  countNodes (self
0c90: 29 3a 0a 20 20 20 20 20 20 20 20 22 63 6f 75 6e  ):.        "coun
0ca0: 74 20 6e 6f 64 65 73 20 77 69 74 68 69 6e 20 74  t nodes within t
0cb0: 68 65 20 77 68 6f 6c 65 20 67 72 61 70 68 22 0a  he whole graph".
0cc0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 4e 6f          self.nNo
0cd0: 64 65 20 3d 20 6c 65 6e 28 73 65 6c 66 2e 6c 4d  de = len(self.lM
0ce0: 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 29 0a 0a  inimizedNodes)..
0cf0: 20 20 20 20 64 65 66 20 63 6f 75 6e 74 41 72 63      def countArc
0d00: 73 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20  s (self):.      
0d10: 20 20 22 63 6f 75 6e 74 20 61 72 63 73 20 77 69    "count arcs wi
0d20: 74 68 69 6e 20 74 68 65 20 77 68 6f 6c 65 20 67  thin the whole g
0d30: 72 61 70 68 22 0a 20 20 20 20 20 20 20 20 73 65  raph".        se
0d40: 6c 66 2e 6e 41 72 63 20 3d 20 30 0a 20 20 20 20  lf.nArc = 0.    
0d50: 20 20 20 20 66 6f 72 20 6f 4e 6f 64 65 20 69 6e      for oNode in
0d60: 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64   self.lMinimized
0d70: 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20  Nodes:.         
0d80: 20 20 20 73 65 6c 66 2e 6e 41 72 63 20 2b 3d 20     self.nArc += 
0d90: 6c 65 6e 28 6f 4e 6f 64 65 2e 64 41 72 63 73 29  len(oNode.dArcs)
0da0: 0a 0a 20 20 20 20 64 65 66 20 64 69 73 70 6c 61  ..    def displa
0db0: 79 49 6e 66 6f 20 28 73 65 6c 66 29 3a 0a 20 20  yInfo (self):.  
0dc0: 20 20 20 20 20 20 22 64 69 73 70 6c 61 79 20 69        "display i
0dd0: 6e 66 6f 72 6d 61 74 69 6f 6e 73 20 61 62 6f 75  nformations abou
0de0: 74 20 74 68 65 20 72 75 6c 65 20 67 72 61 70 68  t the rule graph
0df0: 22 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28  ".        print(
0e00: 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36  " * {:<12} {:>16
0e10: 2c 7d 22 2e 66 6f 72 6d 61 74 28 22 52 75 6c 65  ,}".format("Rule
0e20: 73 3a 22 2c 20 73 65 6c 66 2e 6e 52 75 6c 65 29  s:", self.nRule)
0e30: 29 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28  ).        print(
0e40: 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36  " * {:<12} {:>16
0e50: 2c 7d 22 2e 66 6f 72 6d 61 74 28 22 4e 6f 64 65  ,}".format("Node
0e60: 73 3a 22 2c 20 73 65 6c 66 2e 6e 4e 6f 64 65 29  s:", self.nNode)
0e70: 29 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28  ).        print(
0e80: 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36  " * {:<12} {:>16
0e90: 2c 7d 22 2e 66 6f 72 6d 61 74 28 22 41 72 63 73  ,}".format("Arcs
0ea0: 3a 22 2c 20 73 65 6c 66 2e 6e 41 72 63 29 29 0a  :", self.nArc)).
0eb0: 0a 20 20 20 20 64 65 66 20 63 72 65 61 74 65 47  .    def createG
0ec0: 72 61 70 68 20 28 73 65 6c 66 29 3a 0a 20 20 20  raph (self):.   
0ed0: 20 20 20 20 20 22 63 72 65 61 74 65 20 74 68 65       "create the
0ee0: 20 67 72 61 70 68 20 61 73 20 61 20 64 69 63 74   graph as a dict
0ef0: 69 6f 6e 61 72 79 22 0a 20 20 20 20 20 20 20 20  ionary".        
0f00: 64 47 72 61 70 68 20 3d 20 7b 20 30 3a 20 73 65  dGraph = { 0: se
0f10: 6c 66 2e 6f 52 6f 6f 74 2e 67 65 74 4e 6f 64 65  lf.oRoot.getNode
0f20: 41 73 44 69 63 74 28 29 20 7d 0a 20 20 20 20 20  AsDict() }.     
0f30: 20 20 20 66 6f 72 20 6f 4e 6f 64 65 20 69 6e 20     for oNode in 
0f40: 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e  self.lMinimizedN
0f50: 6f 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20 20  odes:.          
0f60: 20 20 73 48 61 73 68 49 64 20 3d 20 6f 4e 6f 64    sHashId = oNod
0f70: 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20  e.__hash__().   
0f80: 20 20 20 20 20 20 20 20 20 69 66 20 73 48 61 73           if sHas
0f90: 68 49 64 20 6e 6f 74 20 69 6e 20 64 47 72 61 70  hId not in dGrap
0fa0: 68 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  h:.             
0fb0: 20 20 20 64 47 72 61 70 68 5b 73 48 61 73 68 49     dGraph[sHashI
0fc0: 64 5d 20 3d 20 6f 4e 6f 64 65 2e 67 65 74 4e 6f  d] = oNode.getNo
0fd0: 64 65 41 73 44 69 63 74 28 29 0a 20 20 20 20 20  deAsDict().     
0fe0: 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20         else:.   
0ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72 69               pri
1000: 6e 74 28 22 45 72 72 6f 72 2e 20 44 6f 75 62 6c  nt("Error. Doubl
1010: 65 20 6e 6f 64 65 e2 80 a6 20 73 61 6d 65 20 69  e node... same i
1020: 64 3a 20 22 2c 20 73 48 61 73 68 49 64 29 0a 20  d: ", sHashId). 
1030: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 70                 p
1040: 72 69 6e 74 28 73 74 72 28 6f 4e 6f 64 65 2e 67  rint(str(oNode.g
1050: 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29 29 29  etNodeAsDict()))
1060: 0a 20 20 20 20 20 20 20 20 64 47 72 61 70 68 20  .        dGraph 
1070: 3d 20 73 65 6c 66 2e 5f 72 65 77 72 69 74 65 4b  = self._rewriteK
1080: 65 79 73 4f 66 44 41 52 47 28 64 47 72 61 70 68  eysOfDARG(dGraph
1090: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f  ).        self._
10a0: 63 68 65 63 6b 52 65 67 65 78 65 73 28 64 47 72  checkRegexes(dGr
10b0: 61 70 68 29 0a 20 20 20 20 20 20 20 20 72 65 74  aph).        ret
10c0: 75 72 6e 20 64 47 72 61 70 68 0a 0a 20 20 20 20  urn dGraph..    
10d0: 64 65 66 20 5f 72 65 77 72 69 74 65 4b 65 79 73  def _rewriteKeys
10e0: 4f 66 44 41 52 47 20 28 73 65 6c 66 2c 20 64 47  OfDARG (self, dG
10f0: 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20 22  raph):.        "
1100: 6b 65 79 73 20 6f 66 20 44 41 52 47 20 61 72 65  keys of DARG are
1110: 20 6c 6f 6e 67 20 6e 75 6d 62 65 72 73 20 28 68   long numbers (h
1120: 61 73 68 65 73 29 3a 20 74 68 69 73 20 66 75 6e  ashes): this fun
1130: 63 74 69 6f 6e 20 72 65 70 6c 61 63 65 20 74 68  ction replace th
1140: 65 73 65 20 68 61 73 68 65 73 20 77 69 74 68 20  ese hashes with 
1150: 73 6d 61 6c 6c 65 72 20 6e 75 6d 62 65 72 73 20  smaller numbers 
1160: 28 74 6f 20 72 65 64 75 63 65 20 73 74 6f 72 69  (to reduce stori
1170: 6e 67 20 73 69 7a 65 29 22 0a 20 20 20 20 20 20  ng size)".      
1180: 20 20 23 20 63 72 65 61 74 65 20 74 72 61 6e 73    # create trans
1190: 6c 61 74 69 6f 6e 20 64 69 63 74 69 6f 6e 61 72  lation dictionar
11a0: 79 0a 20 20 20 20 20 20 20 20 64 4b 65 79 54 72  y.        dKeyTr
11b0: 61 6e 73 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20  ans = {}.       
11c0: 20 66 6f 72 20 69 2c 20 6e 4b 65 79 20 69 6e 20   for i, nKey in 
11d0: 65 6e 75 6d 65 72 61 74 65 28 64 47 72 61 70 68  enumerate(dGraph
11e0: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64  ):.            d
11f0: 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d 20 3d  KeyTrans[nKey] =
1200: 20 69 0a 20 20 20 20 20 20 20 20 23 20 72 65 70   i.        # rep
1210: 6c 61 63 65 20 6b 65 79 73 0a 20 20 20 20 20 20  lace keys.      
1220: 20 20 64 4e 65 77 47 72 61 70 68 20 3d 20 7b 7d    dNewGraph = {}
1230: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6e 4b 65  .        for nKe
1240: 79 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61 70  y, dVal in dGrap
1250: 68 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20  h.items():.     
1260: 20 20 20 20 20 20 20 64 4e 65 77 47 72 61 70 68         dNewGraph
1270: 5b 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d  [dKeyTrans[nKey]
1280: 5d 20 3d 20 64 56 61 6c 0a 20 20 20 20 20 20 20  ] = dVal.       
1290: 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61 6c 20   for nKey, dVal 
12a0: 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d 73 28  in dGraph.items(
12b0: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 66  ):.            f
12c0: 6f 72 20 73 41 72 63 2c 20 76 61 6c 20 69 6e 20  or sArc, val in 
12d0: 64 56 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20 20  dVal.items():.  
12e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66                if
12f0: 20 74 79 70 65 28 76 61 6c 29 20 69 73 20 69 6e   type(val) is in
1300: 74 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  t:.             
1310: 20 20 20 20 20 20 20 64 56 61 6c 5b 73 41 72 63         dVal[sArc
1320: 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b 76 61  ] = dKeyTrans[va
1330: 6c 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  l].             
1340: 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20     else:.       
1350: 20 20 20 20 20 20 20 20 20 20 20 20 20 66 6f 72               for
1360: 20 73 41 72 63 2c 20 6e 4b 65 79 20 69 6e 20 76   sArc, nKey in v
1370: 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  al.items():.    
1380: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1390: 20 20 20 20 76 61 6c 5b 73 41 72 63 5d 20 3d 20      val[sArc] = 
13a0: 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d 0a  dKeyTrans[nKey].
13b0: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64          return d
13c0: 4e 65 77 47 72 61 70 68 0a 0a 20 20 20 20 64 65  NewGraph..    de
13d0: 66 20 5f 63 68 65 63 6b 52 65 67 65 78 65 73 20  f _checkRegexes 
13e0: 28 73 65 6c 66 2c 20 64 47 72 61 70 68 29 3a 0a  (self, dGraph):.
13f0: 20 20 20 20 20 20 20 20 22 63 68 65 63 6b 20 76          "check v
1400: 61 6c 69 64 69 74 79 20 6f 66 20 72 65 67 65 78  alidity of regex
1410: 65 73 22 0a 20 20 20 20 20 20 20 20 61 52 65 67  es".        aReg
1420: 65 78 20 3d 20 73 65 74 28 29 0a 20 20 20 20 20  ex = set().     
1430: 20 20 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61     for nKey, dVa
1440: 6c 20 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d  l in dGraph.item
1450: 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20  s():.           
1460: 20 69 66 20 22 3c 72 65 5f 76 61 6c 75 65 3e 22   if "<re_value>"
1470: 20 69 6e 20 64 56 61 6c 3a 0a 20 20 20 20 20 20   in dVal:.      
1480: 20 20 20 20 20 20 20 20 20 20 66 6f 72 20 73 52            for sR
1490: 65 67 65 78 20 69 6e 20 64 56 61 6c 5b 22 3c 72  egex in dVal["<r
14a0: 65 5f 76 61 6c 75 65 3e 22 5d 3a 0a 20 20 20 20  e_value>"]:.    
14b0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
14c0: 69 66 20 73 52 65 67 65 78 20 6e 6f 74 20 69 6e  if sRegex not in
14d0: 20 61 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20   aRegex:.       
14e0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
14f0: 20 73 65 6c 66 2e 5f 63 68 65 63 6b 52 65 67 65   self._checkRege
1500: 78 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  x(sRegex).      
1510: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1520: 20 20 61 52 65 67 65 78 2e 61 64 64 28 73 52 65    aRegex.add(sRe
1530: 67 65 78 29 0a 20 20 20 20 20 20 20 20 20 20 20  gex).           
1540: 20 69 66 20 22 3c 72 65 5f 6d 6f 72 70 68 3e 22   if "<re_morph>"
1550: 20 69 6e 20 64 56 61 6c 3a 0a 20 20 20 20 20 20   in dVal:.      
1560: 20 20 20 20 20 20 20 20 20 20 66 6f 72 20 73 52            for sR
1570: 65 67 65 78 20 69 6e 20 64 56 61 6c 5b 22 3c 72  egex in dVal["<r
1580: 65 5f 6d 6f 72 70 68 3e 22 5d 3a 0a 20 20 20 20  e_morph>"]:.    
1590: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15a0: 69 66 20 73 52 65 67 65 78 20 6e 6f 74 20 69 6e  if sRegex not in
15b0: 20 61 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20   aRegex:.       
15c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15d0: 20 73 65 6c 66 2e 5f 63 68 65 63 6b 52 65 67 65   self._checkRege
15e0: 78 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20  x(sRegex).      
15f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1600: 20 20 61 52 65 67 65 78 2e 61 64 64 28 73 52 65    aRegex.add(sRe
1610: 67 65 78 29 0a 20 20 20 20 20 20 20 20 61 52 65  gex).        aRe
1620: 67 65 78 2e 63 6c 65 61 72 28 29 0a 0a 20 20 20  gex.clear()..   
1630: 20 64 65 66 20 5f 63 68 65 63 6b 52 65 67 65 78   def _checkRegex
1640: 20 28 73 65 6c 66 2c 20 73 52 65 67 65 78 29 3a   (self, sRegex):
1650: 0a 20 20 20 20 20 20 20 20 23 70 72 69 6e 74 28  .        #print(
1660: 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20 20  sRegex).        
1670: 69 66 20 22 c2 ac 22 20 69 6e 20 73 52 65 67 65  if ".." in sRege
1680: 78 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 73  x:.            s
1690: 50 61 74 74 65 72 6e 2c 20 73 4e 65 67 50 61 74  Pattern, sNegPat
16a0: 74 65 72 6e 20 3d 20 73 52 65 67 65 78 2e 73 70  tern = sRegex.sp
16b0: 6c 69 74 28 22 c2 ac 22 29 0a 20 20 20 20 20 20  lit("..").      
16c0: 20 20 20 20 20 20 74 72 79 3a 0a 20 20 20 20 20        try:.     
16d0: 20 20 20 20 20 20 20 20 20 20 20 69 66 20 6e 6f             if no
16e0: 74 20 73 4e 65 67 50 61 74 74 65 72 6e 3a 0a 20  t sNegPattern:. 
16f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1700: 20 20 20 70 72 69 6e 74 28 22 23 20 57 61 72 6e     print("# Warn
1710: 69 6e 67 21 20 45 6d 70 74 79 20 6e 65 67 70 61  ing! Empty negpa
1720: 74 74 65 72 6e 3a 22 2c 20 73 52 65 67 65 78 29  ttern:", sRegex)
1730: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1740: 20 72 65 2e 63 6f 6d 70 69 6c 65 28 73 50 61 74   re.compile(sPat
1750: 74 65 72 6e 29 0a 20 20 20 20 20 20 20 20 20 20  tern).          
1760: 20 20 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65        re.compile
1770: 28 73 4e 65 67 50 61 74 74 65 72 6e 29 0a 20 20  (sNegPattern).  
1780: 20 20 20 20 20 20 20 20 20 20 65 78 63 65 70 74            except
1790: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
17a0: 20 20 70 72 69 6e 74 28 22 23 20 45 72 72 6f 72    print("# Error
17b0: 2e 20 57 72 6f 6e 67 20 72 65 67 65 78 3a 22 2c  . Wrong regex:",
17c0: 20 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20   sRegex).       
17d0: 20 20 20 20 20 20 20 20 20 74 72 61 63 65 62 61           traceba
17e0: 63 6b 2e 70 72 69 6e 74 5f 65 78 63 28 29 0a 20  ck.print_exc(). 
17f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 65                 e
1800: 78 69 74 28 29 0a 20 20 20 20 20 20 20 20 65 6c  xit().        el
1810: 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  se:.            
1820: 74 72 79 3a 0a 20 20 20 20 20 20 20 20 20 20 20  try:.           
1830: 20 20 20 20 20 69 66 20 6e 6f 74 20 73 52 65 67       if not sReg
1840: 65 78 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ex:.            
1850: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 23          print("#
1860: 20 57 61 72 6e 69 6e 67 21 20 45 6d 70 74 79 20   Warning! Empty 
1870: 70 61 74 74 65 72 6e 3a 22 2c 20 73 52 65 67 65  pattern:", sRege
1880: 78 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  x).             
1890: 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65 28 73 52     re.compile(sR
18a0: 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20 20  egex).          
18b0: 20 20 65 78 63 65 70 74 3a 0a 20 20 20 20 20 20    except:.      
18c0: 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74 28            print(
18d0: 22 23 20 45 72 72 6f 72 2e 20 57 72 6f 6e 67 20  "# Error. Wrong 
18e0: 72 65 67 65 78 3a 22 2c 20 73 52 65 67 65 78 29  regex:", sRegex)
18f0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1900: 20 74 72 61 63 65 62 61 63 6b 2e 70 72 69 6e 74   traceback.print
1910: 5f 65 78 63 28 29 0a 20 20 20 20 20 20 20 20 20  _exc().         
1920: 20 20 20 20 20 20 20 65 78 69 74 28 29 0a 0a 0a         exit()...
1930: 63 6c 61 73 73 20 4e 6f 64 65 3a 0a 20 20 20 20  class Node:.    
1940: 22 22 22 4e 6f 64 65 20 6f 66 20 74 68 65 20 72  """Node of the r
1950: 75 6c 65 20 67 72 61 70 68 22 22 22 0a 0a 20 20  ule graph"""..  
1960: 20 20 4e 65 78 74 49 64 20 3d 20 30 0a 0a 20 20    NextId = 0..  
1970: 20 20 64 65 66 20 5f 5f 69 6e 69 74 5f 5f 20 28    def __init__ (
1980: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 73  self):.        s
1990: 65 6c 66 2e 69 20 3d 20 4e 6f 64 65 2e 4e 65 78  elf.i = Node.Nex
19a0: 74 49 64 0a 20 20 20 20 20 20 20 20 4e 6f 64 65  tId.        Node
19b0: 2e 4e 65 78 74 49 64 20 2b 3d 20 31 0a 20 20 20  .NextId += 1.   
19c0: 20 20 20 20 20 73 65 6c 66 2e 62 46 69 6e 61 6c       self.bFinal
19d0: 20 3d 20 46 61 6c 73 65 0a 20 20 20 20 20 20 20   = False.       
19e0: 20 73 65 6c 66 2e 64 41 72 63 73 20 3d 20 7b 7d   self.dArcs = {}
19f0: 20 20 20 20 20 20 20 20 20 20 23 20 6b 65 79 3a            # key:
1a00: 20 61 72 63 20 76 61 6c 75 65 3b 20 76 61 6c 75   arc value; valu
1a10: 65 3a 20 61 20 6e 6f 64 65 0a 0a 20 20 20 20 40  e: a node..    @
1a20: 63 6c 61 73 73 6d 65 74 68 6f 64 0a 20 20 20 20  classmethod.    
1a30: 64 65 66 20 72 65 73 65 74 4e 65 78 74 49 64 20  def resetNextId 
1a40: 28 63 6c 73 29 3a 0a 20 20 20 20 20 20 20 20 22  (cls):.        "
1a50: 72 65 73 65 74 20 74 6f 20 30 20 74 68 65 20 6e  reset to 0 the n
1a60: 6f 64 65 20 63 6f 75 6e 74 65 72 22 0a 20 20 20  ode counter".   
1a70: 20 20 20 20 20 63 6c 73 2e 4e 65 78 74 49 64 20       cls.NextId 
1a80: 3d 20 30 0a 0a 20 20 20 20 64 65 66 20 5f 5f 73  = 0..    def __s
1a90: 74 72 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20  tr__ (self):.   
1aa0: 20 20 20 20 20 23 20 43 61 75 74 69 6f 6e 21 20       # Caution! 
1ab0: 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73  this function is
1ac0: 20 75 73 65 64 20 66 6f 72 20 68 61 73 68 69 6e   used for hashin
1ad0: 67 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e  g and comparison
1ae0: 21 0a 20 20 20 20 20 20 20 20 63 46 69 6e 61 6c  !.        cFinal
1af0: 20 3d 20 22 31 22 20 20 69 66 20 73 65 6c 66 2e   = "1"  if self.
1b00: 62 46 69 6e 61 6c 20 20 65 6c 73 65 20 22 30 22  bFinal  else "0"
1b10: 0a 20 20 20 20 20 20 20 20 6c 20 3d 20 5b 63 46  .        l = [cF
1b20: 69 6e 61 6c 5d 0a 20 20 20 20 20 20 20 20 66 6f  inal].        fo
1b30: 72 20 28 6b 65 79 2c 20 6f 4e 6f 64 65 29 20 69  r (key, oNode) i
1b40: 6e 20 73 65 6c 66 2e 64 41 72 63 73 2e 69 74 65  n self.dArcs.ite
1b50: 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20  ms():.          
1b60: 20 20 6c 2e 61 70 70 65 6e 64 28 73 74 72 28 6b    l.append(str(k
1b70: 65 79 29 29 0a 20 20 20 20 20 20 20 20 20 20 20  ey)).           
1b80: 20 6c 2e 61 70 70 65 6e 64 28 73 74 72 28 6f 4e   l.append(str(oN
1b90: 6f 64 65 2e 69 29 29 0a 20 20 20 20 20 20 20 20  ode.i)).        
1ba0: 72 65 74 75 72 6e 20 22 5f 22 2e 6a 6f 69 6e 28  return "_".join(
1bb0: 6c 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f 68 61  l)..    def __ha
1bc0: 73 68 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20  sh__ (self):.   
1bd0: 20 20 20 20 20 23 20 55 73 65 64 20 61 73 20 61       # Used as a
1be0: 20 6b 65 79 20 69 6e 20 61 20 70 79 74 68 6f 6e   key in a python
1bf0: 20 64 69 63 74 69 6f 6e 61 72 79 2e 0a 20 20 20   dictionary..   
1c00: 20 20 20 20 20 72 65 74 75 72 6e 20 73 65 6c 66       return self
1c10: 2e 5f 5f 73 74 72 5f 5f 28 29 2e 5f 5f 68 61 73  .__str__().__has
1c20: 68 5f 5f 28 29 0a 0a 20 20 20 20 64 65 66 20 5f  h__()..    def _
1c30: 5f 65 71 5f 5f 20 28 73 65 6c 66 2c 20 6f 74 68  _eq__ (self, oth
1c40: 65 72 29 3a 0a 20 20 20 20 20 20 20 20 23 20 55  er):.        # U
1c50: 73 65 64 20 61 73 20 61 20 6b 65 79 20 69 6e 20  sed as a key in 
1c60: 61 20 70 79 74 68 6f 6e 20 64 69 63 74 69 6f 6e  a python diction
1c70: 61 72 79 2e 0a 20 20 20 20 20 20 20 20 23 20 4e  ary..        # N
1c80: 6f 64 65 73 20 61 72 65 20 65 71 75 69 76 61 6c  odes are equival
1c90: 65 6e 74 20 69 66 20 74 68 65 79 20 68 61 76 65  ent if they have
1ca0: 20 69 64 65 6e 74 69 63 61 6c 20 61 72 63 73 2c   identical arcs,
1cb0: 20 61 6e 64 20 65 61 63 68 20 69 64 65 6e 74 69   and each identi
1cc0: 63 61 6c 20 61 72 63 20 6c 65 61 64 73 20 74 6f  cal arc leads to
1cd0: 20 69 64 65 6e 74 69 63 61 6c 20 73 74 61 74 65   identical state
1ce0: 73 2e 0a 20 20 20 20 20 20 20 20 72 65 74 75 72  s..        retur
1cf0: 6e 20 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29  n self.__str__()
1d00: 20 3d 3d 20 6f 74 68 65 72 2e 5f 5f 73 74 72 5f   == other.__str_
1d10: 5f 28 29 0a 0a 20 20 20 20 64 65 66 20 67 65 74  _()..    def get
1d20: 4e 6f 64 65 41 73 44 69 63 74 20 28 73 65 6c 66  NodeAsDict (self
1d30: 29 3a 0a 20 20 20 20 20 20 20 20 22 72 65 74 75  ):.        "retu
1d40: 72 6e 73 20 74 68 65 20 6e 6f 64 65 20 61 73 20  rns the node as 
1d50: 61 20 64 69 63 74 69 6f 6e 61 72 79 20 73 74 72  a dictionary str
1d60: 75 63 74 75 72 65 22 0a 20 20 20 20 20 20 20 20  ucture".        
1d70: 64 4e 6f 64 65 20 3d 20 7b 7d 0a 20 20 20 20 20  dNode = {}.     
1d80: 20 20 20 64 52 65 56 61 6c 75 65 20 3d 20 7b 7d     dReValue = {}
1d90: 0a 20 20 20 20 20 20 20 20 64 52 65 4d 6f 72 70  .        dReMorp
1da0: 68 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64  h = {}.        d
1db0: 52 75 6c 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20  Rule = {}.      
1dc0: 20 20 64 4c 65 6d 6d 61 20 3d 20 7b 7d 0a 20 20    dLemma = {}.  
1dd0: 20 20 20 20 20 20 64 4d 65 74 61 20 3d 20 7b 7d        dMeta = {}
1de0: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 73 41 72  .        for sAr
1df0: 63 2c 20 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66  c, oNode in self
1e00: 2e 64 41 72 63 73 2e 69 74 65 6d 73 28 29 3a 0a  .dArcs.items():.
1e10: 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20 73              if s
1e20: 41 72 63 2e 73 74 61 72 74 73 77 69 74 68 28 22  Arc.startswith("
1e30: 40 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63  @") and len(sArc
1e40: 29 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20  ) > 1:.         
1e50: 20 20 20 20 20 20 20 64 52 65 4d 6f 72 70 68 5b         dReMorph[
1e60: 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64  sArc[1:]] = oNod
1e70: 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20  e.__hash__().   
1e80: 20 20 20 20 20 20 20 20 20 65 6c 69 66 20 73 41           elif sA
1e90: 72 63 2e 73 74 61 72 74 73 77 69 74 68 28 22 7e  rc.startswith("~
1ea0: 22 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29  ") and len(sArc)
1eb0: 20 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20   > 1:.          
1ec0: 20 20 20 20 20 20 64 52 65 56 61 6c 75 65 5b 73        dReValue[s
1ed0: 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65  Arc[1:]] = oNode
1ee0: 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20  .__hash__().    
1ef0: 20 20 20 20 20 20 20 20 65 6c 69 66 20 73 41 72          elif sAr
1f00: 63 2e 73 74 61 72 74 73 77 69 74 68 28 22 3e 22  c.startswith(">"
1f10: 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20  ) and len(sArc) 
1f20: 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20  > 1:.           
1f30: 20 20 20 20 20 64 4c 65 6d 6d 61 5b 73 41 72 63       dLemma[sArc
1f40: 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f  [1:]] = oNode.__
1f50: 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20  hash__().       
1f60: 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73       elif sArc.s
1f70: 74 61 72 74 73 77 69 74 68 28 22 2a 22 29 20 61  tartswith("*") a
1f80: 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20 31  nd len(sArc) > 1
1f90: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1fa0: 20 20 64 4d 65 74 61 5b 73 41 72 63 5b 31 3a 5d    dMeta[sArc[1:]
1fb0: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
1fc0: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
1fd0: 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74   elif sArc.start
1fe0: 73 77 69 74 68 28 22 23 23 22 29 3a 0a 20 20 20  swith("##"):.   
1ff0: 20 20 20 20 20 20 20 20 20 20 20 20 20 64 52 75               dRu
2000: 6c 65 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f  le[sArc[1:]] = o
2010: 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a  Node.__hash__().
2020: 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65              else
2030: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
2040: 20 20 64 4e 6f 64 65 5b 73 41 72 63 5d 20 3d 20    dNode[sArc] = 
2050: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
2060: 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65 56  .        if dReV
2070: 61 6c 75 65 3a 0a 20 20 20 20 20 20 20 20 20 20  alue:.          
2080: 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 76 61 6c    dNode["<re_val
2090: 75 65 3e 22 5d 20 3d 20 64 52 65 56 61 6c 75 65  ue>"] = dReValue
20a0: 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 65 4d  .        if dReM
20b0: 6f 72 70 68 3a 0a 20 20 20 20 20 20 20 20 20 20  orph:.          
20c0: 20 20 64 4e 6f 64 65 5b 22 3c 72 65 5f 6d 6f 72    dNode["<re_mor
20d0: 70 68 3e 22 5d 20 3d 20 64 52 65 4d 6f 72 70 68  ph>"] = dReMorph
20e0: 0a 20 20 20 20 20 20 20 20 69 66 20 64 4c 65 6d  .        if dLem
20f0: 6d 61 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ma:.            
2100: 64 4e 6f 64 65 5b 22 3c 6c 65 6d 6d 61 73 3e 22  dNode["<lemmas>"
2110: 5d 20 3d 20 64 4c 65 6d 6d 61 0a 20 20 20 20 20  ] = dLemma.     
2120: 20 20 20 69 66 20 64 4d 65 74 61 3a 0a 20 20 20     if dMeta:.   
2130: 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22           dNode["
2140: 3c 6d 65 74 61 3e 22 5d 20 3d 20 64 4d 65 74 61  <meta>"] = dMeta
2150: 0a 20 20 20 20 20 20 20 20 69 66 20 64 52 75 6c  .        if dRul
2160: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64  e:.            d
2170: 4e 6f 64 65 5b 22 3c 72 75 6c 65 73 3e 22 5d 20  Node["<rules>"] 
2180: 3d 20 64 52 75 6c 65 0a 20 20 20 20 20 20 20 20  = dRule.        
2190: 23 69 66 20 73 65 6c 66 2e 62 46 69 6e 61 6c 3a  #if self.bFinal:
21a0: 0a 20 20 20 20 20 20 20 20 23 20 20 20 20 64 4e  .        #    dN
21b0: 6f 64 65 5b 22 3c 66 69 6e 61 6c 3e 22 5d 20 3d  ode["<final>"] =
21c0: 20 31 0a 20 20 20 20 20 20 20 20 72 65 74 75 72   1.        retur
21d0: 6e 20 64 4e 6f 64 65 0a                          n dNode.