Grammalecte  Hex Artifact Content

Artifact bf378d22b583a5a54e7fc50129f5edd18435bb3d1cccc2fe99ea9626181c3e2a:


0000: 23 21 70 79 74 68 6f 6e 33 0a 0a 23 20 52 55 4c  #!python3..# RUL
0010: 45 20 47 52 41 50 48 20 42 55 49 4c 44 45 52 0a  E GRAPH BUILDER.
0020: 23 0a 23 20 62 79 20 4f 6c 69 76 69 65 72 20 52  #.# by Olivier R
0030: 2e 0a 23 20 4c 69 63 65 6e 73 65 3a 20 4d 50 4c  ..# License: MPL
0040: 20 32 0a 0a 0a 69 6d 70 6f 72 74 20 6a 73 6f 6e   2...import json
0050: 0a 69 6d 70 6f 72 74 20 74 69 6d 65 0a 69 6d 70  .import time.imp
0060: 6f 72 74 20 74 72 61 63 65 62 61 63 6b 0a 0a 66  ort traceback..f
0070: 72 6f 6d 20 67 72 61 70 68 73 70 65 6c 6c 2e 70  rom graphspell.p
0080: 72 6f 67 72 65 73 73 62 61 72 20 69 6d 70 6f 72  rogressbar impor
0090: 74 20 50 72 6f 67 72 65 73 73 42 61 72 0a 0a 0a  t ProgressBar...
00a0: 0a 63 6c 61 73 73 20 44 41 52 47 3a 0a 20 20 20  .class DARG:.   
00b0: 20 22 22 22 44 49 52 45 43 54 20 41 43 59 43 4c   """DIRECT ACYCL
00c0: 49 43 20 52 55 4c 45 20 47 52 41 50 48 22 22 22  IC RULE GRAPH"""
00d0: 0a 20 20 20 20 23 20 54 68 69 73 20 63 6f 64 65  .    # This code
00e0: 20 69 73 20 69 6e 73 70 69 72 65 64 20 66 72 6f   is inspired fro
00f0: 6d 20 53 74 65 76 65 20 48 61 6e 6f 76 e2 80 99  m Steve Hanov...
0100: 73 20 44 41 57 47 2c 20 32 30 31 31 2e 20 28 68  s DAWG, 2011. (h
0110: 74 74 70 3a 2f 2f 73 74 65 76 65 68 61 6e 6f 76  ttp://stevehanov
0120: 2e 63 61 2f 62 6c 6f 67 2f 69 6e 64 65 78 2e 70  .ca/blog/index.p
0130: 68 70 3f 69 64 3d 31 31 35 29 0a 0a 20 20 20 20  hp?id=115)..    
0140: 64 65 66 20 5f 5f 69 6e 69 74 5f 5f 20 28 73 65  def __init__ (se
0150: 6c 66 2c 20 6c 52 75 6c 65 2c 20 73 4c 61 6e 67  lf, lRule, sLang
0160: 43 6f 64 65 29 3a 0a 20 20 20 20 20 20 20 20 70  Code):.        p
0170: 72 69 6e 74 28 22 3d 3d 3d 3d 3d 20 44 69 72 65  rint("===== Dire
0180: 63 74 20 41 63 79 63 6c 69 63 20 52 75 6c 65 20  ct Acyclic Rule 
0190: 47 72 61 70 68 20 2d 20 4d 69 6e 69 6d 61 6c 20  Graph - Minimal 
01a0: 41 63 79 63 6c 69 63 20 46 69 6e 69 74 65 20 53  Acyclic Finite S
01b0: 74 61 74 65 20 41 75 74 6f 6d 61 74 6f 6e 20 3d  tate Automaton =
01c0: 3d 3d 3d 3d 22 29 0a 0a 20 20 20 20 20 20 20 20  ====")..        
01d0: 23 20 50 72 65 70 61 72 69 6e 67 20 44 41 52 47  # Preparing DARG
01e0: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22  .        print("
01f0: 20 3e 20 50 72 65 70 61 72 69 6e 67 20 6c 69 73   > Preparing lis
0200: 74 20 6f 66 20 74 6f 6b 65 6e 73 22 29 0a 20 20  t of tokens").  
0210: 20 20 20 20 20 20 73 65 6c 66 2e 73 4c 61 6e 67        self.sLang
0220: 43 6f 64 65 20 3d 20 73 4c 61 6e 67 43 6f 64 65  Code = sLangCode
0230: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 52  .        self.nR
0240: 75 6c 65 20 3d 20 6c 65 6e 28 6c 52 75 6c 65 29  ule = len(lRule)
0250: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 61 50  .        self.aP
0260: 72 65 76 69 6f 75 73 52 75 6c 65 20 3d 20 5b 5d  reviousRule = []
0270: 0a 20 20 20 20 20 20 20 20 4e 6f 64 65 2e 72 65  .        Node.re
0280: 73 65 74 4e 65 78 74 49 64 28 29 0a 20 20 20 20  setNextId().    
0290: 20 20 20 20 73 65 6c 66 2e 6f 52 6f 6f 74 20 3d      self.oRoot =
02a0: 20 4e 6f 64 65 28 29 0a 20 20 20 20 20 20 20 20   Node().        
02b0: 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e  self.lUncheckedN
02c0: 6f 64 65 73 20 3d 20 5b 5d 20 20 23 20 6c 69 73  odes = []  # lis
02d0: 74 20 6f 66 20 6e 6f 64 65 73 20 74 68 61 74 20  t of nodes that 
02e0: 68 61 76 65 20 6e 6f 74 20 62 65 65 6e 20 63 68  have not been ch
02f0: 65 63 6b 65 64 20 66 6f 72 20 64 75 70 6c 69 63  ecked for duplic
0300: 61 74 69 6f 6e 2e 0a 20 20 20 20 20 20 20 20 73  ation..        s
0310: 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f  elf.lMinimizedNo
0320: 64 65 73 20 3d 20 7b 7d 20 20 23 20 6c 69 73 74  des = {}  # list
0330: 20 6f 66 20 75 6e 69 71 75 65 20 6e 6f 64 65 73   of unique nodes
0340: 20 74 68 61 74 20 68 61 76 65 20 62 65 65 6e 20   that have been 
0350: 63 68 65 63 6b 65 64 20 66 6f 72 20 64 75 70 6c  checked for dupl
0360: 69 63 61 74 69 6f 6e 2e 0a 20 20 20 20 20 20 20  ication..       
0370: 20 73 65 6c 66 2e 6e 4e 6f 64 65 20 3d 20 30 0a   self.nNode = 0.
0380: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 41 72          self.nAr
0390: 63 20 3d 20 30 0a 20 20 20 20 20 20 20 20 0a 20  c = 0.        . 
03a0: 20 20 20 20 20 20 20 23 20 62 75 69 6c 64 0a 20         # build. 
03b0: 20 20 20 20 20 20 20 6c 52 75 6c 65 2e 73 6f 72         lRule.sor
03c0: 74 28 29 0a 20 20 20 20 20 20 20 20 6f 50 72 6f  t().        oPro
03d0: 67 42 61 72 20 3d 20 50 72 6f 67 72 65 73 73 42  gBar = ProgressB
03e0: 61 72 28 30 2c 20 6c 65 6e 28 6c 52 75 6c 65 29  ar(0, len(lRule)
03f0: 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20 61 52  ).        for aR
0400: 75 6c 65 20 69 6e 20 6c 52 75 6c 65 3a 0a 20 20  ule in lRule:.  
0410: 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e 69            self.i
0420: 6e 73 65 72 74 28 61 52 75 6c 65 29 0a 20 20 20  nsert(aRule).   
0430: 20 20 20 20 20 20 20 20 20 6f 50 72 6f 67 42 61           oProgBa
0440: 72 2e 69 6e 63 72 65 6d 65 6e 74 28 31 29 0a 20  r.increment(1). 
0450: 20 20 20 20 20 20 20 6f 50 72 6f 67 42 61 72 2e         oProgBar.
0460: 64 6f 6e 65 28 29 0a 20 20 20 20 20 20 20 20 73  done().        s
0470: 65 6c 66 2e 66 69 6e 69 73 68 28 29 0a 20 20 20  elf.finish().   
0480: 20 20 20 20 20 73 65 6c 66 2e 63 6f 75 6e 74 4e       self.countN
0490: 6f 64 65 73 28 29 0a 20 20 20 20 20 20 20 20 73  odes().        s
04a0: 65 6c 66 2e 63 6f 75 6e 74 41 72 63 73 28 29 0a  elf.countArcs().
04b0: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 64 69 73          self.dis
04c0: 70 6c 61 79 49 6e 66 6f 28 29 0a 0a 20 20 20 20  playInfo()..    
04d0: 23 20 42 55 49 4c 44 20 44 41 52 47 0a 20 20 20  # BUILD DARG.   
04e0: 20 64 65 66 20 69 6e 73 65 72 74 20 28 73 65 6c   def insert (sel
04f0: 66 2c 20 61 52 75 6c 65 29 3a 0a 20 20 20 20 20  f, aRule):.     
0500: 20 20 20 69 66 20 61 52 75 6c 65 20 3c 20 73 65     if aRule < se
0510: 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65  lf.aPreviousRule
0520: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 73 79  :.            sy
0530: 73 2e 65 78 69 74 28 22 23 20 45 72 72 6f 72 3a  s.exit("# Error:
0540: 20 74 6f 6b 65 6e 73 20 6d 75 73 74 20 62 65 20   tokens must be 
0550: 69 6e 73 65 72 74 65 64 20 69 6e 20 6f 72 64 65  inserted in orde
0560: 72 2e 22 29 0a 20 20 20 20 0a 20 20 20 20 20 20  r.").    .      
0570: 20 20 23 20 66 69 6e 64 20 63 6f 6d 6d 6f 6e 20    # find common 
0580: 70 72 65 66 69 78 20 62 65 74 77 65 65 6e 20 77  prefix between w
0590: 6f 72 64 20 61 6e 64 20 70 72 65 76 69 6f 75 73  ord and previous
05a0: 20 77 6f 72 64 0a 20 20 20 20 20 20 20 20 6e 43   word.        nC
05b0: 6f 6d 6d 6f 6e 50 72 65 66 69 78 20 3d 20 30 0a  ommonPrefix = 0.
05c0: 20 20 20 20 20 20 20 20 66 6f 72 20 69 20 69 6e          for i in
05d0: 20 72 61 6e 67 65 28 6d 69 6e 28 6c 65 6e 28 61   range(min(len(a
05e0: 52 75 6c 65 29 2c 20 6c 65 6e 28 73 65 6c 66 2e  Rule), len(self.
05f0: 61 50 72 65 76 69 6f 75 73 52 75 6c 65 29 29 29  aPreviousRule)))
0600: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  :.            if
0610: 20 61 52 75 6c 65 5b 69 5d 20 21 3d 20 73 65 6c   aRule[i] != sel
0620: 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 5b  f.aPreviousRule[
0630: 69 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  i]:.            
0640: 20 20 20 20 62 72 65 61 6b 0a 20 20 20 20 20 20      break.      
0650: 20 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72 65        nCommonPre
0660: 66 69 78 20 2b 3d 20 31 0a 0a 20 20 20 20 20 20  fix += 1..      
0670: 20 20 23 20 43 68 65 63 6b 20 74 68 65 20 6c 55    # Check the lU
0680: 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 66 6f  ncheckedNodes fo
0690: 72 20 72 65 64 75 6e 64 61 6e 74 20 6e 6f 64 65  r redundant node
06a0: 73 2c 20 70 72 6f 63 65 65 64 69 6e 67 20 66 72  s, proceeding fr
06b0: 6f 6d 20 6c 61 73 74 0a 20 20 20 20 20 20 20 20  om last.        
06c0: 23 20 6f 6e 65 20 64 6f 77 6e 20 74 6f 20 74 68  # one down to th
06d0: 65 20 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78 20  e common prefix 
06e0: 73 69 7a 65 2e 20 54 68 65 6e 20 74 72 75 6e 63  size. Then trunc
06f0: 61 74 65 20 74 68 65 20 6c 69 73 74 20 61 74 20  ate the list at 
0700: 74 68 61 74 20 70 6f 69 6e 74 2e 0a 20 20 20 20  that point..    
0710: 20 20 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69      self._minimi
0720: 7a 65 28 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78  ze(nCommonPrefix
0730: 29 0a 0a 20 20 20 20 20 20 20 20 23 20 61 64 64  )..        # add
0740: 20 74 68 65 20 73 75 66 66 69 78 2c 20 73 74 61   the suffix, sta
0750: 72 74 69 6e 67 20 66 72 6f 6d 20 74 68 65 20 63  rting from the c
0760: 6f 72 72 65 63 74 20 6e 6f 64 65 20 6d 69 64 2d  orrect node mid-
0770: 77 61 79 20 74 68 72 6f 75 67 68 20 74 68 65 20  way through the 
0780: 67 72 61 70 68 0a 20 20 20 20 20 20 20 20 69 66  graph.        if
0790: 20 6c 65 6e 28 73 65 6c 66 2e 6c 55 6e 63 68 65   len(self.lUnche
07a0: 63 6b 65 64 4e 6f 64 65 73 29 20 3d 3d 20 30 3a  ckedNodes) == 0:
07b0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f  .            oNo
07c0: 64 65 20 3d 20 73 65 6c 66 2e 6f 52 6f 6f 74 0a  de = self.oRoot.
07d0: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
07e0: 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 20            oNode 
07f0: 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65  = self.lUnchecke
0800: 64 4e 6f 64 65 73 5b 2d 31 5d 5b 32 5d 0a 0a 20  dNodes[-1][2].. 
0810: 20 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 3d 20         iToken = 
0820: 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 0a 20 20  nCommonPrefix.  
0830: 20 20 20 20 20 20 66 6f 72 20 73 54 6f 6b 65 6e        for sToken
0840: 20 69 6e 20 61 52 75 6c 65 5b 6e 43 6f 6d 6d 6f   in aRule[nCommo
0850: 6e 50 72 65 66 69 78 3a 5d 3a 0a 20 20 20 20 20  nPrefix:]:.     
0860: 20 20 20 20 20 20 20 6f 4e 65 78 74 4e 6f 64 65         oNextNode
0870: 20 3d 20 4e 6f 64 65 28 29 0a 20 20 20 20 20 20   = Node().      
0880: 20 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72 63        oNode.dArc
0890: 73 5b 73 54 6f 6b 65 6e 5d 20 3d 20 6f 4e 65 78  s[sToken] = oNex
08a0: 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20 20 20  tNode.          
08b0: 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65    self.lUnchecke
08c0: 64 4e 6f 64 65 73 2e 61 70 70 65 6e 64 28 28 6f  dNodes.append((o
08d0: 4e 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f 4e  Node, sToken, oN
08e0: 65 78 74 4e 6f 64 65 29 29 0a 20 20 20 20 20 20  extNode)).      
08f0: 20 20 20 20 20 20 69 66 20 69 54 6f 6b 65 6e 20        if iToken 
0900: 3d 3d 20 28 6c 65 6e 28 61 52 75 6c 65 29 20 2d  == (len(aRule) -
0910: 20 32 29 3a 20 0a 20 20 20 20 20 20 20 20 20 20   2): .          
0920: 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e        oNode.bFin
0930: 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20 20 20  al = True.      
0940: 20 20 20 20 20 20 69 54 6f 6b 65 6e 20 2b 3d 20        iToken += 
0950: 31 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  1.            oN
0960: 6f 64 65 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a  ode = oNextNode.
0970: 20 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46          oNode.bF
0980: 69 6e 61 6c 20 3d 20 54 72 75 65 0a 20 20 20 20  inal = True.    
0990: 20 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f      self.aPrevio
09a0: 75 73 52 75 6c 65 20 3d 20 61 52 75 6c 65 0a 0a  usRule = aRule..
09b0: 20 20 20 20 64 65 66 20 66 69 6e 69 73 68 20 28      def finish (
09c0: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
09d0: 6d 69 6e 69 6d 69 7a 65 20 75 6e 63 68 65 63 6b  minimize uncheck
09e0: 65 64 20 6e 6f 64 65 73 22 0a 20 20 20 20 20 20  ed nodes".      
09f0: 20 20 73 65 6c 66 2e 5f 6d 69 6e 69 6d 69 7a 65    self._minimize
0a00: 28 30 29 0a 0a 20 20 20 20 64 65 66 20 5f 6d 69  (0)..    def _mi
0a10: 6e 69 6d 69 7a 65 20 28 73 65 6c 66 2c 20 64 6f  nimize (self, do
0a20: 77 6e 54 6f 29 3a 0a 20 20 20 20 20 20 20 20 23  wnTo):.        #
0a30: 20 70 72 6f 63 65 65 64 20 66 72 6f 6d 20 74 68   proceed from th
0a40: 65 20 6c 65 61 66 20 75 70 20 74 6f 20 61 20 63  e leaf up to a c
0a50: 65 72 74 61 69 6e 20 70 6f 69 6e 74 0a 20 20 20  ertain point.   
0a60: 20 20 20 20 20 66 6f 72 20 69 20 69 6e 20 72 61       for i in ra
0a70: 6e 67 65 28 20 6c 65 6e 28 73 65 6c 66 2e 6c 55  nge( len(self.lU
0a80: 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 29 2d 31  ncheckedNodes)-1
0a90: 2c 20 64 6f 77 6e 54 6f 2d 31 2c 20 2d 31 20 29  , downTo-1, -1 )
0aa0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e  :.            oN
0ab0: 6f 64 65 2c 20 73 54 6f 6b 65 6e 2c 20 6f 43 68  ode, sToken, oCh
0ac0: 69 6c 64 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6c  ildNode = self.l
0ad0: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 5b 69  UncheckedNodes[i
0ae0: 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  ].            if
0af0: 20 6f 43 68 69 6c 64 4e 6f 64 65 20 69 6e 20 73   oChildNode in s
0b00: 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f  elf.lMinimizedNo
0b10: 64 65 73 3a 0a 20 20 20 20 20 20 20 20 20 20 20  des:.           
0b20: 20 20 20 20 20 23 20 72 65 70 6c 61 63 65 20 74       # replace t
0b30: 68 65 20 63 68 69 6c 64 20 77 69 74 68 20 74 68  he child with th
0b40: 65 20 70 72 65 76 69 6f 75 73 6c 79 20 65 6e 63  e previously enc
0b50: 6f 75 6e 74 65 72 65 64 20 6f 6e 65 0a 20 20 20  ountered one.   
0b60: 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f               oNo
0b70: 64 65 2e 64 41 72 63 73 5b 73 54 6f 6b 65 6e 5d  de.dArcs[sToken]
0b80: 20 3d 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a   = self.lMinimiz
0b90: 65 64 4e 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f  edNodes[oChildNo
0ba0: 64 65 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20  de].            
0bb0: 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20  else:.          
0bc0: 20 20 20 20 20 20 23 20 61 64 64 20 74 68 65 20        # add the 
0bd0: 73 74 61 74 65 20 74 6f 20 74 68 65 20 6d 69 6e  state to the min
0be0: 69 6d 69 7a 65 64 20 6e 6f 64 65 73 2e 0a 20 20  imized nodes..  
0bf0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 73 65                se
0c00: 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64  lf.lMinimizedNod
0c10: 65 73 5b 6f 43 68 69 6c 64 4e 6f 64 65 5d 20 3d  es[oChildNode] =
0c20: 20 6f 43 68 69 6c 64 4e 6f 64 65 0a 20 20 20 20   oChildNode.    
0c30: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 55 6e          self.lUn
0c40: 63 68 65 63 6b 65 64 4e 6f 64 65 73 2e 70 6f 70  checkedNodes.pop
0c50: 28 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e  ()..    def coun
0c60: 74 4e 6f 64 65 73 20 28 73 65 6c 66 29 3a 0a 20  tNodes (self):. 
0c70: 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 4e 6f 64         self.nNod
0c80: 65 20 3d 20 6c 65 6e 28 73 65 6c 66 2e 6c 4d 69  e = len(self.lMi
0c90: 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 29 0a 0a 20  nimizedNodes).. 
0ca0: 20 20 20 64 65 66 20 63 6f 75 6e 74 41 72 63 73     def countArcs
0cb0: 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20   (self):.       
0cc0: 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a 20   self.nArc = 0. 
0cd0: 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f 64 65         for oNode
0ce0: 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69   in self.lMinimi
0cf0: 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20  zedNodes:.      
0d00: 20 20 20 20 20 20 73 65 6c 66 2e 6e 41 72 63 20        self.nArc 
0d10: 2b 3d 20 6c 65 6e 28 6f 4e 6f 64 65 2e 64 41 72  += len(oNode.dAr
0d20: 63 73 29 0a 0a 20 20 20 20 64 65 66 20 64 69 73  cs)..    def dis
0d30: 70 6c 61 79 49 6e 66 6f 20 28 73 65 6c 66 29 3a  playInfo (self):
0d40: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22  .        print("
0d50: 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c   * {:<12} {:>16,
0d60: 7d 22 2e 66 6f 72 6d 61 74 28 22 52 75 6c 65 73  }".format("Rules
0d70: 3a 22 2c 20 73 65 6c 66 2e 6e 52 75 6c 65 29 29  :", self.nRule))
0d80: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22  .        print("
0d90: 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c   * {:<12} {:>16,
0da0: 7d 22 2e 66 6f 72 6d 61 74 28 22 4e 6f 64 65 73  }".format("Nodes
0db0: 3a 22 2c 20 73 65 6c 66 2e 6e 4e 6f 64 65 29 29  :", self.nNode))
0dc0: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22  .        print("
0dd0: 20 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c   * {:<12} {:>16,
0de0: 7d 22 2e 66 6f 72 6d 61 74 28 22 41 72 63 73 3a  }".format("Arcs:
0df0: 22 2c 20 73 65 6c 66 2e 6e 41 72 63 29 29 0a 0a  ", self.nArc))..
0e00: 20 20 20 20 64 65 66 20 63 72 65 61 74 65 47 72      def createGr
0e10: 61 70 68 20 28 73 65 6c 66 29 3a 0a 20 20 20 20  aph (self):.    
0e20: 20 20 20 20 64 47 72 61 70 68 20 3d 20 7b 20 30      dGraph = { 0
0e30: 3a 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e 67 65 74  : self.oRoot.get
0e40: 4e 6f 64 65 41 73 44 69 63 74 28 29 20 7d 0a 20  NodeAsDict() }. 
0e50: 20 20 20 20 20 20 20 70 72 69 6e 74 28 30 2c 20         print(0, 
0e60: 22 5c 74 22 2c 20 73 65 6c 66 2e 6f 52 6f 6f 74  "\t", self.oRoot
0e70: 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29  .getNodeAsDict()
0e80: 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6f 4e  ).        for oN
0e90: 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e  ode in self.lMin
0ea0: 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20  imizedNodes:.   
0eb0: 20 20 20 20 20 20 20 20 20 73 48 61 73 68 49 64           sHashId
0ec0: 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f   = oNode.__hash_
0ed0: 5f 28 29 20 0a 20 20 20 20 20 20 20 20 20 20 20  _() .           
0ee0: 20 69 66 20 73 48 61 73 68 49 64 20 6e 6f 74 20   if sHashId not 
0ef0: 69 6e 20 64 47 72 61 70 68 3a 0a 20 20 20 20 20  in dGraph:.     
0f00: 20 20 20 20 20 20 20 20 20 20 20 64 47 72 61 70             dGrap
0f10: 68 5b 73 48 61 73 68 49 64 5d 20 3d 20 6f 4e 6f  h[sHashId] = oNo
0f20: 64 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74  de.getNodeAsDict
0f30: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  ().             
0f40: 20 20 20 70 72 69 6e 74 28 73 48 61 73 68 49 64     print(sHashId
0f50: 2c 20 22 5c 74 22 2c 20 64 47 72 61 70 68 5b 73  , "\t", dGraph[s
0f60: 48 61 73 68 49 64 5d 29 0a 20 20 20 20 20 20 20  HashId]).       
0f70: 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20       else:.     
0f80: 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74             print
0f90: 28 22 45 72 72 6f 72 2e 20 44 6f 75 62 6c 65 20  ("Error. Double 
0fa0: 6e 6f 64 65 e2 80 a6 20 73 61 6d 65 20 69 64 3a  node... same id:
0fb0: 20 22 2c 20 73 48 61 73 68 49 64 29 0a 20 20 20   ", sHashId).   
0fc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 70 72 69               pri
0fd0: 6e 74 28 73 74 72 28 6f 4e 6f 64 65 2e 67 65 74  nt(str(oNode.get
0fe0: 4e 6f 64 65 41 73 44 69 63 74 28 29 29 29 0a 20  NodeAsDict())). 
0ff0: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 47         return dG
1000: 72 61 70 68 0a 0a 0a 0a 63 6c 61 73 73 20 4e 6f  raph....class No
1010: 64 65 3a 0a 20 20 20 20 4e 65 78 74 49 64 20 3d  de:.    NextId =
1020: 20 30 0a 20 20 20 20 0a 20 20 20 20 64 65 66 20   0.    .    def 
1030: 5f 5f 69 6e 69 74 5f 5f 20 28 73 65 6c 66 29 3a  __init__ (self):
1040: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 69 20  .        self.i 
1050: 3d 20 4e 6f 64 65 2e 4e 65 78 74 49 64 0a 20 20  = Node.NextId.  
1060: 20 20 20 20 20 20 4e 6f 64 65 2e 4e 65 78 74 49        Node.NextI
1070: 64 20 2b 3d 20 31 0a 20 20 20 20 20 20 20 20 73  d += 1.        s
1080: 65 6c 66 2e 62 46 69 6e 61 6c 20 3d 20 46 61 6c  elf.bFinal = Fal
1090: 73 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  se.        self.
10a0: 64 41 72 63 73 20 3d 20 7b 7d 20 20 20 20 20 20  dArcs = {}      
10b0: 20 20 20 20 23 20 6b 65 79 3a 20 61 72 63 20 76      # key: arc v
10c0: 61 6c 75 65 3b 20 76 61 6c 75 65 3a 20 61 20 6e  alue; value: a n
10d0: 6f 64 65 0a 0a 20 20 20 20 40 63 6c 61 73 73 6d  ode..    @classm
10e0: 65 74 68 6f 64 0a 20 20 20 20 64 65 66 20 72 65  ethod.    def re
10f0: 73 65 74 4e 65 78 74 49 64 20 28 63 6c 73 29 3a  setNextId (cls):
1100: 0a 20 20 20 20 20 20 20 20 63 6c 73 2e 4e 65 78  .        cls.Nex
1110: 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64 65 66  tId = 0..    def
1120: 20 5f 5f 73 74 72 5f 5f 20 28 73 65 6c 66 29 3a   __str__ (self):
1130: 0a 20 20 20 20 20 20 20 20 23 20 43 61 75 74 69  .        # Cauti
1140: 6f 6e 21 20 74 68 69 73 20 66 75 6e 63 74 69 6f  on! this functio
1150: 6e 20 69 73 20 75 73 65 64 20 66 6f 72 20 68 61  n is used for ha
1160: 73 68 69 6e 67 20 61 6e 64 20 63 6f 6d 70 61 72  shing and compar
1170: 69 73 6f 6e 21 0a 20 20 20 20 20 20 20 20 63 46  ison!.        cF
1180: 69 6e 61 6c 20 3d 20 22 31 22 20 20 69 66 20 73  inal = "1"  if s
1190: 65 6c 66 2e 62 46 69 6e 61 6c 20 20 65 6c 73 65  elf.bFinal  else
11a0: 20 22 30 22 0a 20 20 20 20 20 20 20 20 6c 20 3d   "0".        l =
11b0: 20 5b 63 46 69 6e 61 6c 5d 0a 20 20 20 20 20 20   [cFinal].      
11c0: 20 20 66 6f 72 20 28 6b 65 79 2c 20 6f 4e 6f 64    for (key, oNod
11d0: 65 29 20 69 6e 20 73 65 6c 66 2e 64 41 72 63 73  e) in self.dArcs
11e0: 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20  .items():.      
11f0: 20 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 73        l.append(s
1200: 74 72 28 6b 65 79 29 29 0a 20 20 20 20 20 20 20  tr(key)).       
1210: 20 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 73 74       l.append(st
1220: 72 28 6f 4e 6f 64 65 2e 69 29 29 0a 20 20 20 20  r(oNode.i)).    
1230: 20 20 20 20 72 65 74 75 72 6e 20 22 5f 22 2e 6a      return "_".j
1240: 6f 69 6e 28 6c 29 0a 0a 20 20 20 20 64 65 66 20  oin(l)..    def 
1250: 5f 5f 68 61 73 68 5f 5f 20 28 73 65 6c 66 29 3a  __hash__ (self):
1260: 0a 20 20 20 20 20 20 20 20 23 20 55 73 65 64 20  .        # Used 
1270: 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20 70 79  as a key in a py
1280: 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72 79 2e  thon dictionary.
1290: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
12a0: 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29 2e 5f  self.__str__()._
12b0: 5f 68 61 73 68 5f 5f 28 29 0a 0a 20 20 20 20 64  _hash__()..    d
12c0: 65 66 20 5f 5f 65 71 5f 5f 20 28 73 65 6c 66 2c  ef __eq__ (self,
12d0: 20 6f 74 68 65 72 29 3a 0a 20 20 20 20 20 20 20   other):.       
12e0: 20 23 20 55 73 65 64 20 61 73 20 61 20 6b 65 79   # Used as a key
12f0: 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64 69 63   in a python dic
1300: 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20 20 20  tionary..       
1310: 20 23 20 4e 6f 64 65 73 20 61 72 65 20 65 71 75   # Nodes are equ
1320: 69 76 61 6c 65 6e 74 20 69 66 20 74 68 65 79 20  ivalent if they 
1330: 68 61 76 65 20 69 64 65 6e 74 69 63 61 6c 20 61  have identical a
1340: 72 63 73 2c 20 61 6e 64 20 65 61 63 68 20 69 64  rcs, and each id
1350: 65 6e 74 69 63 61 6c 20 61 72 63 20 6c 65 61 64  entical arc lead
1360: 73 20 74 6f 20 69 64 65 6e 74 69 63 61 6c 20 73  s to identical s
1370: 74 61 74 65 73 2e 0a 20 20 20 20 20 20 20 20 72  tates..        r
1380: 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73 74 72  eturn self.__str
1390: 5f 5f 28 29 20 3d 3d 20 6f 74 68 65 72 2e 5f 5f  __() == other.__
13a0: 73 74 72 5f 5f 28 29 20 20 20 20 20 20 20 20 0a  str__()        .
13b0: 0a 20 20 20 20 64 65 66 20 67 65 74 4e 6f 64 65  .    def getNode
13c0: 41 73 44 69 63 74 20 28 73 65 6c 66 29 3a 0a 20  AsDict (self):. 
13d0: 20 20 20 20 20 20 20 22 72 65 74 75 72 6e 73 20         "returns 
13e0: 74 68 65 20 6e 6f 64 65 20 61 73 20 61 20 64 69  the node as a di
13f0: 63 74 69 6f 6e 61 72 79 20 73 74 72 75 63 74 75  ctionary structu
1400: 72 65 22 0a 20 20 20 20 20 20 20 20 64 4e 6f 64  re".        dNod
1410: 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64  e = {}.        d
1420: 52 65 67 65 78 20 3d 20 7b 7d 0a 20 20 20 20 20  Regex = {}.     
1430: 20 20 20 64 52 75 6c 65 73 20 3d 20 7b 7d 0a 20     dRules = {}. 
1440: 20 20 20 20 20 20 20 66 6f 72 20 61 72 63 2c 20         for arc, 
1450: 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 64 41  oNode in self.dA
1460: 72 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20  rcs.items():.   
1470: 20 20 20 20 20 20 20 20 20 69 66 20 74 79 70 65           if type
1480: 28 61 72 63 29 20 3d 3d 20 73 74 72 20 61 6e 64  (arc) == str and
1490: 20 61 72 63 2e 73 74 61 72 74 73 77 69 74 68 28   arc.startswith(
14a0: 22 7e 22 29 3a 0a 20 20 20 20 20 20 20 20 20 20  "~"):.          
14b0: 20 20 20 20 20 20 64 52 65 67 65 78 5b 61 72 63        dRegex[arc
14c0: 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f  [1:]] = oNode.__
14d0: 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20  hash__().       
14e0: 20 20 20 20 20 65 6c 69 66 20 61 72 63 2e 73 74       elif arc.st
14f0: 61 72 74 73 77 69 74 68 28 22 23 23 22 29 3a 0a  artswith("##"):.
1500: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1510: 64 52 75 6c 65 73 5b 61 72 63 5b 31 3a 5d 5d 20  dRules[arc[1:]] 
1520: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
1530: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
1540: 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20  lse:.           
1550: 20 20 20 20 20 64 4e 6f 64 65 5b 61 72 63 5d 20       dNode[arc] 
1560: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
1570: 28 29 0a 20 20 20 20 20 20 20 20 69 66 20 64 52  ().        if dR
1580: 65 67 65 78 3a 0a 20 20 20 20 20 20 20 20 20 20  egex:.          
1590: 20 20 64 4e 6f 64 65 5b 22 3c 72 65 67 65 78 3e    dNode["<regex>
15a0: 22 5d 20 3d 20 64 52 65 67 65 78 0a 20 20 20 20  "] = dRegex.    
15b0: 20 20 20 20 69 66 20 64 52 75 6c 65 73 3a 0a 20      if dRules:. 
15c0: 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65             dNode
15d0: 5b 22 3c 72 75 6c 65 73 3e 22 5d 20 3d 20 64 52  ["<rules>"] = dR
15e0: 75 6c 65 73 0a 20 20 20 20 20 20 20 20 23 69 66  ules.        #if
15f0: 20 73 65 6c 66 2e 62 46 69 6e 61 6c 3a 0a 20 20   self.bFinal:.  
1600: 20 20 20 20 20 20 23 20 20 20 20 64 4e 6f 64 65        #    dNode
1610: 5b 22 3c 66 69 6e 61 6c 3e 22 5d 20 3d 20 31 0a  ["<final>"] = 1.
1620: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64          return d
1630: 4e 6f 64 65 0a                                   Node.