Grammalecte  Hex Artifact Content

Artifact e3a97a1f6347117cbd8af4b536a5c4aa9151770c27514c140d5520e952ea6344:


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 0a 66 72 6f 6d 20 67  : MPL 2...from g
0050: 72 61 70 68 73 70 65 6c 6c 2e 70 72 6f 67 72 65  raphspell.progre
0060: 73 73 62 61 72 20 69 6d 70 6f 72 74 20 50 72 6f  ssbar import Pro
0070: 67 72 65 73 73 42 61 72 0a 0a 0a 63 6c 61 73 73  gressBar...class
0080: 20 44 41 52 47 3a 0a 20 20 20 20 22 22 22 44 49   DARG:.    """DI
0090: 52 45 43 54 20 41 43 59 43 4c 49 43 20 52 55 4c  RECT ACYCLIC RUL
00a0: 45 20 47 52 41 50 48 22 22 22 0a 20 20 20 20 23  E GRAPH""".    #
00b0: 20 54 68 69 73 20 63 6f 64 65 20 69 73 20 69 6e   This code is in
00c0: 73 70 69 72 65 64 20 66 72 6f 6d 20 53 74 65 76  spired from Stev
00d0: 65 20 48 61 6e 6f 76 e2 80 99 73 20 44 41 57 47  e Hanov...s DAWG
00e0: 2c 20 32 30 31 31 2e 20 28 68 74 74 70 3a 2f 2f  , 2011. (http://
00f0: 73 74 65 76 65 68 61 6e 6f 76 2e 63 61 2f 62 6c  stevehanov.ca/bl
0100: 6f 67 2f 69 6e 64 65 78 2e 70 68 70 3f 69 64 3d  og/index.php?id=
0110: 31 31 35 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f  115)..    def __
0120: 69 6e 69 74 5f 5f 20 28 73 65 6c 66 2c 20 6c 52  init__ (self, lR
0130: 75 6c 65 2c 20 73 4c 61 6e 67 43 6f 64 65 29 3a  ule, sLangCode):
0140: 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22  .        print("
0150: 3d 3d 3d 3d 3d 20 44 69 72 65 63 74 20 41 63 79  ===== Direct Acy
0160: 63 6c 69 63 20 52 75 6c 65 20 47 72 61 70 68 20  clic Rule Graph 
0170: 2d 20 4d 69 6e 69 6d 61 6c 20 41 63 79 63 6c 69  - Minimal Acycli
0180: 63 20 46 69 6e 69 74 65 20 53 74 61 74 65 20 41  c Finite State A
0190: 75 74 6f 6d 61 74 6f 6e 20 3d 3d 3d 3d 3d 22 29  utomaton =====")
01a0: 0a 0a 20 20 20 20 20 20 20 20 23 20 50 72 65 70  ..        # Prep
01b0: 61 72 69 6e 67 20 44 41 52 47 0a 20 20 20 20 20  aring DARG.     
01c0: 20 20 20 70 72 69 6e 74 28 22 20 3e 20 50 72 65     print(" > Pre
01d0: 70 61 72 69 6e 67 20 6c 69 73 74 20 6f 66 20 74  paring list of t
01e0: 6f 6b 65 6e 73 22 29 0a 20 20 20 20 20 20 20 20  okens").        
01f0: 73 65 6c 66 2e 73 4c 61 6e 67 43 6f 64 65 20 3d  self.sLangCode =
0200: 20 73 4c 61 6e 67 43 6f 64 65 0a 20 20 20 20 20   sLangCode.     
0210: 20 20 20 73 65 6c 66 2e 6e 52 75 6c 65 20 3d 20     self.nRule = 
0220: 6c 65 6e 28 6c 52 75 6c 65 29 0a 20 20 20 20 20  len(lRule).     
0230: 20 20 20 73 65 6c 66 2e 61 50 72 65 76 69 6f 75     self.aPreviou
0240: 73 52 75 6c 65 20 3d 20 5b 5d 0a 20 20 20 20 20  sRule = [].     
0250: 20 20 20 4e 6f 64 65 2e 72 65 73 65 74 4e 65 78     Node.resetNex
0260: 74 49 64 28 29 0a 20 20 20 20 20 20 20 20 73 65  tId().        se
0270: 6c 66 2e 6f 52 6f 6f 74 20 3d 20 4e 6f 64 65 28  lf.oRoot = Node(
0280: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c  ).        self.l
0290: 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20 3d  UncheckedNodes =
02a0: 20 5b 5d 20 20 23 20 6c 69 73 74 20 6f 66 20 6e   []  # list of n
02b0: 6f 64 65 73 20 74 68 61 74 20 68 61 76 65 20 6e  odes that have n
02c0: 6f 74 20 62 65 65 6e 20 63 68 65 63 6b 65 64 20  ot been checked 
02d0: 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f 6e 2e  for duplication.
02e0: 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d  .        self.lM
02f0: 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 20 3d 20  inimizedNodes = 
0300: 7b 7d 20 20 23 20 6c 69 73 74 20 6f 66 20 75 6e  {}  # list of un
0310: 69 71 75 65 20 6e 6f 64 65 73 20 74 68 61 74 20  ique nodes that 
0320: 68 61 76 65 20 62 65 65 6e 20 63 68 65 63 6b 65  have been checke
0330: 64 20 66 6f 72 20 64 75 70 6c 69 63 61 74 69 6f  d for duplicatio
0340: 6e 2e 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  n..        self.
0350: 6e 4e 6f 64 65 20 3d 20 30 0a 20 20 20 20 20 20  nNode = 0.      
0360: 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a    self.nArc = 0.
0370: 0a 20 20 20 20 20 20 20 20 23 20 62 75 69 6c 64  .        # build
0380: 0a 20 20 20 20 20 20 20 20 6c 52 75 6c 65 2e 73  .        lRule.s
0390: 6f 72 74 28 29 0a 20 20 20 20 20 20 20 20 6f 50  ort().        oP
03a0: 72 6f 67 42 61 72 20 3d 20 50 72 6f 67 72 65 73  rogBar = Progres
03b0: 73 42 61 72 28 30 2c 20 6c 65 6e 28 6c 52 75 6c  sBar(0, len(lRul
03c0: 65 29 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20  e)).        for 
03d0: 61 52 75 6c 65 20 69 6e 20 6c 52 75 6c 65 3a 0a  aRule in lRule:.
03e0: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
03f0: 2e 69 6e 73 65 72 74 28 61 52 75 6c 65 29 0a 20  .insert(aRule). 
0400: 20 20 20 20 20 20 20 20 20 20 20 6f 50 72 6f 67             oProg
0410: 42 61 72 2e 69 6e 63 72 65 6d 65 6e 74 28 31 29  Bar.increment(1)
0420: 0a 20 20 20 20 20 20 20 20 6f 50 72 6f 67 42 61  .        oProgBa
0430: 72 2e 64 6f 6e 65 28 29 0a 20 20 20 20 20 20 20  r.done().       
0440: 20 73 65 6c 66 2e 66 69 6e 69 73 68 28 29 0a 20   self.finish(). 
0450: 20 20 20 20 20 20 20 73 65 6c 66 2e 63 6f 75 6e         self.coun
0460: 74 4e 6f 64 65 73 28 29 0a 20 20 20 20 20 20 20  tNodes().       
0470: 20 73 65 6c 66 2e 63 6f 75 6e 74 41 72 63 73 28   self.countArcs(
0480: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 64  ).        self.d
0490: 69 73 70 6c 61 79 49 6e 66 6f 28 29 0a 0a 20 20  isplayInfo()..  
04a0: 20 20 23 20 42 55 49 4c 44 20 44 41 52 47 0a 20    # BUILD DARG. 
04b0: 20 20 20 64 65 66 20 69 6e 73 65 72 74 20 28 73     def insert (s
04c0: 65 6c 66 2c 20 61 52 75 6c 65 29 3a 0a 20 20 20  elf, aRule):.   
04d0: 20 20 20 20 20 22 69 6e 73 65 72 74 20 61 20 6e       "insert a n
04e0: 65 77 20 72 75 6c 65 20 28 74 6f 6b 65 6e 73 20  ew rule (tokens 
04f0: 6d 75 73 74 20 62 65 20 69 6e 73 65 72 74 65 64  must be inserted
0500: 20 69 6e 20 6f 72 64 65 72 29 22 0a 20 20 20 20   in order)".    
0510: 20 20 20 20 69 66 20 61 52 75 6c 65 20 3c 20 73      if aRule < s
0520: 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c  elf.aPreviousRul
0530: 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  e:.            e
0540: 78 69 74 28 22 23 20 45 72 72 6f 72 3a 20 74 6f  xit("# Error: to
0550: 6b 65 6e 73 20 6d 75 73 74 20 62 65 20 69 6e 73  kens must be ins
0560: 65 72 74 65 64 20 69 6e 20 6f 72 64 65 72 2e 22  erted in order."
0570: 29 0a 0a 20 20 20 20 20 20 20 20 23 20 66 69 6e  )..        # fin
0580: 64 20 63 6f 6d 6d 6f 6e 20 70 72 65 66 69 78 20  d common prefix 
0590: 62 65 74 77 65 65 6e 20 77 6f 72 64 20 61 6e 64  between word and
05a0: 20 70 72 65 76 69 6f 75 73 20 77 6f 72 64 0a 20   previous word. 
05b0: 20 20 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50 72         nCommonPr
05c0: 65 66 69 78 20 3d 20 30 0a 20 20 20 20 20 20 20  efix = 0.       
05d0: 20 66 6f 72 20 69 20 69 6e 20 72 61 6e 67 65 28   for i in range(
05e0: 6d 69 6e 28 6c 65 6e 28 61 52 75 6c 65 29 2c 20  min(len(aRule), 
05f0: 6c 65 6e 28 73 65 6c 66 2e 61 50 72 65 76 69 6f  len(self.aPrevio
0600: 75 73 52 75 6c 65 29 29 29 3a 0a 20 20 20 20 20  usRule))):.     
0610: 20 20 20 20 20 20 20 69 66 20 61 52 75 6c 65 5b         if aRule[
0620: 69 5d 20 21 3d 20 73 65 6c 66 2e 61 50 72 65 76  i] != self.aPrev
0630: 69 6f 75 73 52 75 6c 65 5b 69 5d 3a 0a 20 20 20  iousRule[i]:.   
0640: 20 20 20 20 20 20 20 20 20 20 20 20 20 62 72 65               bre
0650: 61 6b 0a 20 20 20 20 20 20 20 20 20 20 20 20 6e  ak.            n
0660: 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 20 2b 3d 20  CommonPrefix += 
0670: 31 0a 0a 20 20 20 20 20 20 20 20 23 20 43 68 65  1..        # Che
0680: 63 6b 20 74 68 65 20 6c 55 6e 63 68 65 63 6b 65  ck the lUnchecke
0690: 64 4e 6f 64 65 73 20 66 6f 72 20 72 65 64 75 6e  dNodes for redun
06a0: 64 61 6e 74 20 6e 6f 64 65 73 2c 20 70 72 6f 63  dant nodes, proc
06b0: 65 65 64 69 6e 67 20 66 72 6f 6d 20 6c 61 73 74  eeding from last
06c0: 0a 20 20 20 20 20 20 20 20 23 20 6f 6e 65 20 64  .        # one d
06d0: 6f 77 6e 20 74 6f 20 74 68 65 20 63 6f 6d 6d 6f  own to the commo
06e0: 6e 20 70 72 65 66 69 78 20 73 69 7a 65 2e 20 54  n prefix size. T
06f0: 68 65 6e 20 74 72 75 6e 63 61 74 65 20 74 68 65  hen truncate the
0700: 20 6c 69 73 74 20 61 74 20 74 68 61 74 20 70 6f   list at that po
0710: 69 6e 74 2e 0a 20 20 20 20 20 20 20 20 73 65 6c  int..        sel
0720: 66 2e 5f 6d 69 6e 69 6d 69 7a 65 28 6e 43 6f 6d  f._minimize(nCom
0730: 6d 6f 6e 50 72 65 66 69 78 29 0a 0a 20 20 20 20  monPrefix)..    
0740: 20 20 20 20 23 20 61 64 64 20 74 68 65 20 73 75      # add the su
0750: 66 66 69 78 2c 20 73 74 61 72 74 69 6e 67 20 66  ffix, starting f
0760: 72 6f 6d 20 74 68 65 20 63 6f 72 72 65 63 74 20  rom the correct 
0770: 6e 6f 64 65 20 6d 69 64 2d 77 61 79 20 74 68 72  node mid-way thr
0780: 6f 75 67 68 20 74 68 65 20 67 72 61 70 68 0a 20  ough the graph. 
0790: 20 20 20 20 20 20 20 69 66 20 6c 65 6e 28 73 65         if len(se
07a0: 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64  lf.lUncheckedNod
07b0: 65 73 29 20 3d 3d 20 30 3a 0a 20 20 20 20 20 20  es) == 0:.      
07c0: 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20 73 65        oNode = se
07d0: 6c 66 2e 6f 52 6f 6f 74 0a 20 20 20 20 20 20 20  lf.oRoot.       
07e0: 20 65 6c 73 65 3a 0a 20 20 20 20 20 20 20 20 20   else:.         
07f0: 20 20 20 6f 4e 6f 64 65 20 3d 20 73 65 6c 66 2e     oNode = self.
0800: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 5b  lUncheckedNodes[
0810: 2d 31 5d 5b 32 5d 0a 0a 20 20 20 20 20 20 20 20  -1][2]..        
0820: 69 54 6f 6b 65 6e 20 3d 20 6e 43 6f 6d 6d 6f 6e  iToken = nCommon
0830: 50 72 65 66 69 78 0a 20 20 20 20 20 20 20 20 66  Prefix.        f
0840: 6f 72 20 73 54 6f 6b 65 6e 20 69 6e 20 61 52 75  or sToken in aRu
0850: 6c 65 5b 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78  le[nCommonPrefix
0860: 3a 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  :]:.            
0870: 6f 4e 65 78 74 4e 6f 64 65 20 3d 20 4e 6f 64 65  oNextNode = Node
0880: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f  ().            o
0890: 4e 6f 64 65 2e 64 41 72 63 73 5b 73 54 6f 6b 65  Node.dArcs[sToke
08a0: 6e 5d 20 3d 20 6f 4e 65 78 74 4e 6f 64 65 0a 20  n] = oNextNode. 
08b0: 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e             self.
08c0: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 2e  lUncheckedNodes.
08d0: 61 70 70 65 6e 64 28 28 6f 4e 6f 64 65 2c 20 73  append((oNode, s
08e0: 54 6f 6b 65 6e 2c 20 6f 4e 65 78 74 4e 6f 64 65  Token, oNextNode
08f0: 29 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  )).            i
0900: 66 20 69 54 6f 6b 65 6e 20 3d 3d 20 28 6c 65 6e  f iToken == (len
0910: 28 61 52 75 6c 65 29 20 2d 20 32 29 3a 0a 20 20  (aRule) - 2):.  
0920: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e                oN
0930: 6f 64 65 2e 62 46 69 6e 61 6c 20 3d 20 54 72 75  ode.bFinal = Tru
0940: 65 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 54  e.            iT
0950: 6f 6b 65 6e 20 2b 3d 20 31 0a 20 20 20 20 20 20  oken += 1.      
0960: 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20 6f 4e        oNode = oN
0970: 65 78 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20  extNode.        
0980: 6f 4e 6f 64 65 2e 62 46 69 6e 61 6c 20 3d 20 54  oNode.bFinal = T
0990: 72 75 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66  rue.        self
09a0: 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 20 3d  .aPreviousRule =
09b0: 20 61 52 75 6c 65 0a 0a 20 20 20 20 64 65 66 20   aRule..    def 
09c0: 66 69 6e 69 73 68 20 28 73 65 6c 66 29 3a 0a 20  finish (self):. 
09d0: 20 20 20 20 20 20 20 22 6d 69 6e 69 6d 69 7a 65         "minimize
09e0: 20 75 6e 63 68 65 63 6b 65 64 20 6e 6f 64 65 73   unchecked nodes
09f0: 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f  ".        self._
0a00: 6d 69 6e 69 6d 69 7a 65 28 30 29 0a 0a 20 20 20  minimize(0)..   
0a10: 20 64 65 66 20 5f 6d 69 6e 69 6d 69 7a 65 20 28   def _minimize (
0a20: 73 65 6c 66 2c 20 64 6f 77 6e 54 6f 29 3a 0a 20  self, downTo):. 
0a30: 20 20 20 20 20 20 20 23 20 70 72 6f 63 65 65 64         # proceed
0a40: 20 66 72 6f 6d 20 74 68 65 20 6c 65 61 66 20 75   from the leaf u
0a50: 70 20 74 6f 20 61 20 63 65 72 74 61 69 6e 20 70  p to a certain p
0a60: 6f 69 6e 74 0a 20 20 20 20 20 20 20 20 66 6f 72  oint.        for
0a70: 20 69 20 69 6e 20 72 61 6e 67 65 28 20 6c 65 6e   i in range( len
0a80: 28 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64  (self.lUnchecked
0a90: 4e 6f 64 65 73 29 2d 31 2c 20 64 6f 77 6e 54 6f  Nodes)-1, downTo
0aa0: 2d 31 2c 20 2d 31 20 29 3a 0a 20 20 20 20 20 20  -1, -1 ):.      
0ab0: 20 20 20 20 20 20 6f 4e 6f 64 65 2c 20 73 54 6f        oNode, sTo
0ac0: 6b 65 6e 2c 20 6f 43 68 69 6c 64 4e 6f 64 65 20  ken, oChildNode 
0ad0: 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65  = self.lUnchecke
0ae0: 64 4e 6f 64 65 73 5b 69 5d 0a 20 20 20 20 20 20  dNodes[i].      
0af0: 20 20 20 20 20 20 69 66 20 6f 43 68 69 6c 64 4e        if oChildN
0b00: 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e  ode in self.lMin
0b10: 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20  imizedNodes:.   
0b20: 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20 72               # r
0b30: 65 70 6c 61 63 65 20 74 68 65 20 63 68 69 6c 64  eplace the child
0b40: 20 77 69 74 68 20 74 68 65 20 70 72 65 76 69 6f   with the previo
0b50: 75 73 6c 79 20 65 6e 63 6f 75 6e 74 65 72 65 64  usly encountered
0b60: 20 6f 6e 65 0a 20 20 20 20 20 20 20 20 20 20 20   one.           
0b70: 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72 63 73       oNode.dArcs
0b80: 5b 73 54 6f 6b 65 6e 5d 20 3d 20 73 65 6c 66 2e  [sToken] = self.
0b90: 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 5b  lMinimizedNodes[
0ba0: 6f 43 68 69 6c 64 4e 6f 64 65 5d 0a 20 20 20 20  oChildNode].    
0bb0: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
0bc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 23 20                # 
0bd0: 61 64 64 20 74 68 65 20 73 74 61 74 65 20 74 6f  add the state to
0be0: 20 74 68 65 20 6d 69 6e 69 6d 69 7a 65 64 20 6e   the minimized n
0bf0: 6f 64 65 73 2e 0a 20 20 20 20 20 20 20 20 20 20  odes..          
0c00: 20 20 20 20 20 20 73 65 6c 66 2e 6c 4d 69 6e 69        self.lMini
0c10: 6d 69 7a 65 64 4e 6f 64 65 73 5b 6f 43 68 69 6c  mizedNodes[oChil
0c20: 64 4e 6f 64 65 5d 20 3d 20 6f 43 68 69 6c 64 4e  dNode] = oChildN
0c30: 6f 64 65 0a 20 20 20 20 20 20 20 20 20 20 20 20  ode.            
0c40: 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e  self.lUncheckedN
0c50: 6f 64 65 73 2e 70 6f 70 28 29 0a 0a 20 20 20 20  odes.pop()..    
0c60: 64 65 66 20 63 6f 75 6e 74 4e 6f 64 65 73 20 28  def countNodes (
0c70: 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 22  self):.        "
0c80: 63 6f 75 6e 74 20 6e 6f 64 65 73 20 77 69 74 68  count nodes with
0c90: 69 6e 20 74 68 65 20 77 68 6f 6c 65 20 67 72 61  in the whole gra
0ca0: 70 68 22 0a 20 20 20 20 20 20 20 20 73 65 6c 66  ph".        self
0cb0: 2e 6e 4e 6f 64 65 20 3d 20 6c 65 6e 28 73 65 6c  .nNode = len(sel
0cc0: 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65  f.lMinimizedNode
0cd0: 73 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e  s)..    def coun
0ce0: 74 41 72 63 73 20 28 73 65 6c 66 29 3a 0a 20 20  tArcs (self):.  
0cf0: 20 20 20 20 20 20 22 63 6f 75 6e 74 20 61 72 63        "count arc
0d00: 73 20 77 69 74 68 69 6e 20 74 68 65 20 77 68 6f  s within the who
0d10: 6c 65 20 67 72 61 70 68 22 0a 20 20 20 20 20 20  le graph".      
0d20: 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d 20 30 0a    self.nArc = 0.
0d30: 20 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f 64          for oNod
0d40: 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d  e in self.lMinim
0d50: 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20  izedNodes:.     
0d60: 20 20 20 20 20 20 20 73 65 6c 66 2e 6e 41 72 63         self.nArc
0d70: 20 2b 3d 20 6c 65 6e 28 6f 4e 6f 64 65 2e 64 41   += len(oNode.dA
0d80: 72 63 73 29 0a 0a 20 20 20 20 64 65 66 20 64 69  rcs)..    def di
0d90: 73 70 6c 61 79 49 6e 66 6f 20 28 73 65 6c 66 29  splayInfo (self)
0da0: 3a 0a 20 20 20 20 20 20 20 20 22 64 69 73 70 6c  :.        "displ
0db0: 61 79 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 73 20  ay informations 
0dc0: 61 62 6f 75 74 20 74 68 65 20 72 75 6c 65 20 67  about the rule g
0dd0: 72 61 70 68 22 0a 20 20 20 20 20 20 20 20 70 72  raph".        pr
0de0: 69 6e 74 28 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b  int(" * {:<12} {
0df0: 3a 3e 31 36 2c 7d 22 2e 66 6f 72 6d 61 74 28 22  :>16,}".format("
0e00: 52 75 6c 65 73 3a 22 2c 20 73 65 6c 66 2e 6e 52  Rules:", self.nR
0e10: 75 6c 65 29 29 0a 20 20 20 20 20 20 20 20 70 72  ule)).        pr
0e20: 69 6e 74 28 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b  int(" * {:<12} {
0e30: 3a 3e 31 36 2c 7d 22 2e 66 6f 72 6d 61 74 28 22  :>16,}".format("
0e40: 4e 6f 64 65 73 3a 22 2c 20 73 65 6c 66 2e 6e 4e  Nodes:", self.nN
0e50: 6f 64 65 29 29 0a 20 20 20 20 20 20 20 20 70 72  ode)).        pr
0e60: 69 6e 74 28 22 20 2a 20 7b 3a 3c 31 32 7d 20 7b  int(" * {:<12} {
0e70: 3a 3e 31 36 2c 7d 22 2e 66 6f 72 6d 61 74 28 22  :>16,}".format("
0e80: 41 72 63 73 3a 22 2c 20 73 65 6c 66 2e 6e 41 72  Arcs:", self.nAr
0e90: 63 29 29 0a 0a 20 20 20 20 64 65 66 20 63 72 65  c))..    def cre
0ea0: 61 74 65 47 72 61 70 68 20 28 73 65 6c 66 29 3a  ateGraph (self):
0eb0: 0a 20 20 20 20 20 20 20 20 22 63 72 65 61 74 65  .        "create
0ec0: 20 74 68 65 20 67 72 61 70 68 20 61 73 20 61 20   the graph as a 
0ed0: 64 69 63 74 69 6f 6e 61 72 79 22 0a 20 20 20 20  dictionary".    
0ee0: 20 20 20 20 64 47 72 61 70 68 20 3d 20 7b 20 30      dGraph = { 0
0ef0: 3a 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e 67 65 74  : self.oRoot.get
0f00: 4e 6f 64 65 41 73 44 69 63 74 28 29 20 7d 0a 20  NodeAsDict() }. 
0f10: 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f 64 65         for oNode
0f20: 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69   in self.lMinimi
0f30: 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20  zedNodes:.      
0f40: 20 20 20 20 20 20 73 48 61 73 68 49 64 20 3d 20        sHashId = 
0f50: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
0f60: 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66 20  .            if 
0f70: 73 48 61 73 68 49 64 20 6e 6f 74 20 69 6e 20 64  sHashId not in d
0f80: 47 72 61 70 68 3a 0a 20 20 20 20 20 20 20 20 20  Graph:.         
0f90: 20 20 20 20 20 20 20 64 47 72 61 70 68 5b 73 48         dGraph[sH
0fa0: 61 73 68 49 64 5d 20 3d 20 6f 4e 6f 64 65 2e 67  ashId] = oNode.g
0fb0: 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29 0a 20  etNodeAsDict(). 
0fc0: 20 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 3a             else:
0fd0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
0fe0: 20 70 72 69 6e 74 28 22 45 72 72 6f 72 2e 20 44   print("Error. D
0ff0: 6f 75 62 6c 65 20 6e 6f 64 65 e2 80 a6 20 73 61  ouble node... sa
1000: 6d 65 20 69 64 3a 20 22 2c 20 73 48 61 73 68 49  me id: ", sHashI
1010: 64 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  d).             
1020: 20 20 20 70 72 69 6e 74 28 73 74 72 28 6f 4e 6f     print(str(oNo
1030: 64 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74  de.getNodeAsDict
1040: 28 29 29 29 0a 20 20 20 20 20 20 20 20 64 47 72  ())).        dGr
1050: 61 70 68 20 3d 20 73 65 6c 66 2e 5f 72 65 77 72  aph = self._rewr
1060: 69 74 65 4b 65 79 73 4f 66 44 41 52 47 28 64 47  iteKeysOfDARG(dG
1070: 72 61 70 68 29 0a 20 20 20 20 20 20 20 20 73 65  raph).        se
1080: 6c 66 2e 5f 63 68 65 63 6b 52 65 67 65 78 65 73  lf._checkRegexes
1090: 28 64 47 72 61 70 68 29 0a 20 20 20 20 20 20 20  (dGraph).       
10a0: 20 72 65 74 75 72 6e 20 64 47 72 61 70 68 0a 0a   return dGraph..
10b0: 20 20 20 20 64 65 66 20 5f 72 65 77 72 69 74 65      def _rewrite
10c0: 4b 65 79 73 4f 66 44 41 52 47 20 28 73 65 6c 66  KeysOfDARG (self
10d0: 2c 20 64 47 72 61 70 68 29 3a 0a 20 20 20 20 20  , dGraph):.     
10e0: 20 20 20 22 6b 65 79 73 20 6f 66 20 44 41 52 47     "keys of DARG
10f0: 20 61 72 65 20 6c 6f 6e 67 20 6e 75 6d 62 65 72   are long number
1100: 73 20 28 68 61 73 68 65 73 29 3a 20 74 68 69 73  s (hashes): this
1110: 20 66 75 6e 63 74 69 6f 6e 20 72 65 70 6c 61 63   function replac
1120: 65 20 74 68 65 73 65 20 68 61 73 68 65 73 20 77  e these hashes w
1130: 69 74 68 20 73 6d 61 6c 6c 65 72 20 6e 75 6d 62  ith smaller numb
1140: 65 72 73 20 28 74 6f 20 72 65 64 75 63 65 20 73  ers (to reduce s
1150: 74 6f 72 69 6e 67 20 73 69 7a 65 29 22 0a 20 20  toring size)".  
1160: 20 20 20 20 20 20 23 20 63 72 65 61 74 65 20 74        # create t
1170: 72 61 6e 73 6c 61 74 69 6f 6e 20 64 69 63 74 69  ranslation dicti
1180: 6f 6e 61 72 79 0a 20 20 20 20 20 20 20 20 64 4b  onary.        dK
1190: 65 79 54 72 61 6e 73 20 3d 20 7b 7d 0a 20 20 20  eyTrans = {}.   
11a0: 20 20 20 20 20 66 6f 72 20 69 2c 20 6e 4b 65 79       for i, nKey
11b0: 20 69 6e 20 65 6e 75 6d 65 72 61 74 65 28 64 47   in enumerate(dG
11c0: 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20 20  raph):.         
11d0: 20 20 20 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65     dKeyTrans[nKe
11e0: 79 5d 20 3d 20 69 0a 20 20 20 20 20 20 20 20 23  y] = i.        #
11f0: 20 72 65 70 6c 61 63 65 20 6b 65 79 73 0a 20 20   replace keys.  
1200: 20 20 20 20 20 20 64 4e 65 77 47 72 61 70 68 20        dNewGraph 
1210: 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 66 6f 72  = {}.        for
1220: 20 6e 4b 65 79 2c 20 64 56 61 6c 20 69 6e 20 64   nKey, dVal in d
1230: 47 72 61 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20  Graph.items():. 
1240: 20 20 20 20 20 20 20 20 20 20 20 64 4e 65 77 47             dNewG
1250: 72 61 70 68 5b 64 4b 65 79 54 72 61 6e 73 5b 6e  raph[dKeyTrans[n
1260: 4b 65 79 5d 5d 20 3d 20 64 56 61 6c 0a 20 20 20  Key]] = dVal.   
1270: 20 20 20 20 20 66 6f 72 20 6e 4b 65 79 2c 20 64       for nKey, d
1280: 56 61 6c 20 69 6e 20 64 47 72 61 70 68 2e 69 74  Val in dGraph.it
1290: 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20 20  ems():.         
12a0: 20 20 20 66 6f 72 20 73 41 72 63 2c 20 76 61 6c     for sArc, val
12b0: 20 69 6e 20 64 56 61 6c 2e 69 74 65 6d 73 28 29   in dVal.items()
12c0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
12d0: 20 20 69 66 20 74 79 70 65 28 76 61 6c 29 20 69    if type(val) i
12e0: 73 20 69 6e 74 3a 0a 20 20 20 20 20 20 20 20 20  s int:.         
12f0: 20 20 20 20 20 20 20 20 20 20 20 64 56 61 6c 5b             dVal[
1300: 73 41 72 63 5d 20 3d 20 64 4b 65 79 54 72 61 6e  sArc] = dKeyTran
1310: 73 5b 76 61 6c 5d 0a 20 20 20 20 20 20 20 20 20  s[val].         
1320: 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20 20         else:.   
1330: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1340: 20 66 6f 72 20 73 41 72 63 2c 20 6e 4b 65 79 20   for sArc, nKey 
1350: 69 6e 20 76 61 6c 2e 69 74 65 6d 73 28 29 3a 0a  in val.items():.
1360: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1370: 20 20 20 20 20 20 20 20 76 61 6c 5b 73 41 72 63          val[sArc
1380: 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b 6e 4b  ] = dKeyTrans[nK
1390: 65 79 5d 0a 20 20 20 20 20 20 20 20 72 65 74 75  ey].        retu
13a0: 72 6e 20 64 4e 65 77 47 72 61 70 68 0a 0a 20 20  rn dNewGraph..  
13b0: 20 20 64 65 66 20 5f 63 68 65 63 6b 52 65 67 65    def _checkRege
13c0: 78 65 73 20 28 64 47 72 61 70 68 29 3a 0a 20 20  xes (dGraph):.  
13d0: 20 20 20 20 20 20 22 63 68 65 63 6b 20 76 61 6c        "check val
13e0: 69 64 69 74 79 20 6f 66 20 72 65 67 65 78 65 73  idity of regexes
13f0: 22 0a 20 20 20 20 20 20 20 20 61 52 65 67 65 78  ".        aRegex
1400: 20 3d 20 73 65 74 28 29 0a 20 20 20 20 20 20 20   = set().       
1410: 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61 6c 20   for nKey, dVal 
1420: 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d 73 28  in dGraph.items(
1430: 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 69  ):.            i
1440: 66 20 22 3c 72 65 5f 76 61 6c 75 65 3e 22 20 69  f "<re_value>" i
1450: 6e 20 64 56 61 6c 3a 0a 20 20 20 20 20 20 20 20  n dVal:.        
1460: 20 20 20 20 20 20 20 20 66 6f 72 20 73 52 65 67          for sReg
1470: 65 78 20 69 6e 20 64 56 61 6c 5b 22 3c 72 65 5f  ex in dVal["<re_
1480: 76 61 6c 75 65 3e 22 5d 3a 0a 20 20 20 20 20 20  value>"]:.      
1490: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69 66                if
14a0: 20 73 52 65 67 65 78 20 6e 6f 74 20 69 6e 20 61   sRegex not in a
14b0: 52 65 67 65 78 3a 0a 20 20 20 20 20 20 20 20 20  Regex:.         
14c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 5f                 _
14d0: 63 68 65 63 6b 52 65 67 65 78 28 73 52 65 67 65  checkRegex(sRege
14e0: 78 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  x).             
14f0: 20 20 20 20 20 20 20 20 20 20 20 61 52 65 67 65             aRege
1500: 78 2e 61 64 64 28 73 52 65 67 65 78 29 0a 20 20  x.add(sRegex).  
1510: 20 20 20 20 20 20 20 20 20 20 69 66 20 22 3c 72            if "<r
1520: 65 5f 6d 6f 72 70 68 3e 22 20 69 6e 20 64 56 61  e_morph>" in dVa
1530: 6c 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  l:.             
1540: 20 20 20 66 6f 72 20 73 52 65 67 65 78 20 69 6e     for sRegex in
1550: 20 64 56 61 6c 5b 22 3c 72 65 5f 6d 6f 72 70 68   dVal["<re_morph
1560: 3e 22 5d 3a 0a 20 20 20 20 20 20 20 20 20 20 20  >"]:.           
1570: 20 20 20 20 20 20 20 20 20 69 66 20 73 52 65 67           if sReg
1580: 65 78 20 6e 6f 74 20 69 6e 20 61 52 65 67 65 78  ex not in aRegex
1590: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
15a0: 20 20 20 20 20 20 20 20 20 20 5f 63 68 65 63 6b            _check
15b0: 52 65 67 65 78 28 73 52 65 67 65 78 29 0a 20 20  Regex(sRegex).  
15c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
15d0: 20 20 20 20 20 20 61 52 65 67 65 78 2e 61 64 64        aRegex.add
15e0: 28 73 52 65 67 65 78 29 0a 20 20 20 20 20 20 20  (sRegex).       
15f0: 20 61 52 65 67 65 78 2e 63 6c 65 61 72 28 29 0a   aRegex.clear().
1600: 0a 20 20 20 20 64 65 66 20 5f 63 68 65 63 6b 52  .    def _checkR
1610: 65 67 65 78 20 28 73 52 65 67 65 78 29 3a 0a 20  egex (sRegex):. 
1620: 20 20 20 20 20 20 20 23 70 72 69 6e 74 28 73 52         #print(sR
1630: 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 69 66  egex).        if
1640: 20 22 c2 ac 22 20 69 6e 20 73 52 65 67 65 78 3a   ".." in sRegex:
1650: 0a 20 20 20 20 20 20 20 20 20 20 20 20 73 50 61  .            sPa
1660: 74 74 65 72 6e 2c 20 73 4e 65 67 50 61 74 74 65  ttern, sNegPatte
1670: 72 6e 20 3d 20 73 52 65 67 65 78 2e 73 70 6c 69  rn = sRegex.spli
1680: 74 28 22 c2 ac 22 29 0a 20 20 20 20 20 20 20 20  t("..").        
1690: 20 20 20 20 74 72 79 3a 0a 20 20 20 20 20 20 20      try:.       
16a0: 20 20 20 20 20 20 20 20 20 69 66 20 6e 6f 74 20           if not 
16b0: 73 4e 65 67 50 61 74 74 65 72 6e 3a 0a 20 20 20  sNegPattern:.   
16c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
16d0: 20 70 72 69 6e 74 28 22 23 20 57 61 72 6e 69 6e   print("# Warnin
16e0: 67 21 20 45 6d 70 74 79 20 6e 65 67 70 61 74 74  g! Empty negpatt
16f0: 65 72 6e 3a 22 2c 20 73 52 65 67 65 78 29 0a 20  ern:", sRegex). 
1700: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 72                 r
1710: 65 2e 63 6f 6d 70 69 6c 65 28 73 50 61 74 74 65  e.compile(sPatte
1720: 72 6e 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  rn).            
1730: 20 20 20 20 72 65 2e 63 6f 6d 70 69 6c 65 28 73      re.compile(s
1740: 4e 65 67 50 61 74 74 65 72 6e 29 0a 20 20 20 20  NegPattern).    
1750: 20 20 20 20 20 20 20 20 65 78 63 65 70 74 3a 0a          except:.
1760: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1770: 70 72 69 6e 74 28 22 23 20 45 72 72 6f 72 2e 20  print("# Error. 
1780: 57 72 6f 6e 67 20 72 65 67 65 78 3a 22 2c 20 73  Wrong regex:", s
1790: 52 65 67 65 78 29 0a 20 20 20 20 20 20 20 20 20  Regex).         
17a0: 20 20 20 20 20 20 20 74 72 61 63 65 62 61 63 6b         traceback
17b0: 2e 70 72 69 6e 74 5f 65 78 63 28 29 0a 20 20 20  .print_exc().   
17c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 65 78 69               exi
17d0: 74 28 29 0a 20 20 20 20 20 20 20 20 65 6c 73 65  t().        else
17e0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 74 72  :.            tr
17f0: 79 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  y:.             
1800: 20 20 20 69 66 20 6e 6f 74 20 73 52 65 67 65 78     if not sRegex
1810: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1820: 20 20 20 20 20 20 70 72 69 6e 74 28 22 23 20 57        print("# W
1830: 61 72 6e 69 6e 67 21 20 45 6d 70 74 79 20 70 61  arning! Empty pa
1840: 74 74 65 72 6e 3a 22 2c 20 73 52 65 67 65 78 29  ttern:", sRegex)
1850: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1860: 20 72 65 2e 63 6f 6d 70 69 6c 65 28 73 52 65 67   re.compile(sReg
1870: 65 78 29 0a 20 20 20 20 20 20 20 20 20 20 20 20  ex).            
1880: 65 78 63 65 70 74 3a 0a 20 20 20 20 20 20 20 20  except:.        
1890: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 23          print("#
18a0: 20 45 72 72 6f 72 2e 20 57 72 6f 6e 67 20 72 65   Error. Wrong re
18b0: 67 65 78 3a 22 2c 20 73 52 65 67 65 78 29 0a 20  gex:", sRegex). 
18c0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 74                 t
18d0: 72 61 63 65 62 61 63 6b 2e 70 72 69 6e 74 5f 65  raceback.print_e
18e0: 78 63 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  xc().           
18f0: 20 20 20 20 20 65 78 69 74 28 29 0a 0a 0a 63 6c       exit()...cl
1900: 61 73 73 20 4e 6f 64 65 3a 0a 20 20 20 20 22 22  ass Node:.    ""
1910: 22 4e 6f 64 65 20 6f 66 20 74 68 65 20 72 75 6c  "Node of the rul
1920: 65 20 67 72 61 70 68 22 22 22 0a 0a 20 20 20 20  e graph"""..    
1930: 4e 65 78 74 49 64 20 3d 20 30 0a 0a 20 20 20 20  NextId = 0..    
1940: 64 65 66 20 5f 5f 69 6e 69 74 5f 5f 20 28 73 65  def __init__ (se
1950: 6c 66 29 3a 0a 20 20 20 20 20 20 20 20 73 65 6c  lf):.        sel
1960: 66 2e 69 20 3d 20 4e 6f 64 65 2e 4e 65 78 74 49  f.i = Node.NextI
1970: 64 0a 20 20 20 20 20 20 20 20 4e 6f 64 65 2e 4e  d.        Node.N
1980: 65 78 74 49 64 20 2b 3d 20 31 0a 20 20 20 20 20  extId += 1.     
1990: 20 20 20 73 65 6c 66 2e 62 46 69 6e 61 6c 20 3d     self.bFinal =
19a0: 20 46 61 6c 73 65 0a 20 20 20 20 20 20 20 20 73   False.        s
19b0: 65 6c 66 2e 64 41 72 63 73 20 3d 20 7b 7d 20 20  elf.dArcs = {}  
19c0: 20 20 20 20 20 20 20 20 23 20 6b 65 79 3a 20 61          # key: a
19d0: 72 63 20 76 61 6c 75 65 3b 20 76 61 6c 75 65 3a  rc value; value:
19e0: 20 61 20 6e 6f 64 65 0a 0a 20 20 20 20 40 63 6c   a node..    @cl
19f0: 61 73 73 6d 65 74 68 6f 64 0a 20 20 20 20 64 65  assmethod.    de
1a00: 66 20 72 65 73 65 74 4e 65 78 74 49 64 20 28 63  f resetNextId (c
1a10: 6c 73 29 3a 0a 20 20 20 20 20 20 20 20 22 72 65  ls):.        "re
1a20: 73 65 74 20 74 6f 20 30 20 74 68 65 20 6e 6f 64  set to 0 the nod
1a30: 65 20 63 6f 75 6e 74 65 72 22 0a 20 20 20 20 20  e counter".     
1a40: 20 20 20 63 6c 73 2e 4e 65 78 74 49 64 20 3d 20     cls.NextId = 
1a50: 30 0a 0a 20 20 20 20 64 65 66 20 5f 5f 73 74 72  0..    def __str
1a60: 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  __ (self):.     
1a70: 20 20 20 23 20 43 61 75 74 69 6f 6e 21 20 74 68     # Caution! th
1a80: 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 75  is function is u
1a90: 73 65 64 20 66 6f 72 20 68 61 73 68 69 6e 67 20  sed for hashing 
1aa0: 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 21 0a  and comparison!.
1ab0: 20 20 20 20 20 20 20 20 63 46 69 6e 61 6c 20 3d          cFinal =
1ac0: 20 22 31 22 20 20 69 66 20 73 65 6c 66 2e 62 46   "1"  if self.bF
1ad0: 69 6e 61 6c 20 20 65 6c 73 65 20 22 30 22 0a 20  inal  else "0". 
1ae0: 20 20 20 20 20 20 20 6c 20 3d 20 5b 63 46 69 6e         l = [cFin
1af0: 61 6c 5d 0a 20 20 20 20 20 20 20 20 66 6f 72 20  al].        for 
1b00: 28 6b 65 79 2c 20 6f 4e 6f 64 65 29 20 69 6e 20  (key, oNode) in 
1b10: 73 65 6c 66 2e 64 41 72 63 73 2e 69 74 65 6d 73  self.dArcs.items
1b20: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
1b30: 6c 2e 61 70 70 65 6e 64 28 73 74 72 28 6b 65 79  l.append(str(key
1b40: 29 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 6c  )).            l
1b50: 2e 61 70 70 65 6e 64 28 73 74 72 28 6f 4e 6f 64  .append(str(oNod
1b60: 65 2e 69 29 29 0a 20 20 20 20 20 20 20 20 72 65  e.i)).        re
1b70: 74 75 72 6e 20 22 5f 22 2e 6a 6f 69 6e 28 6c 29  turn "_".join(l)
1b80: 0a 0a 20 20 20 20 64 65 66 20 5f 5f 68 61 73 68  ..    def __hash
1b90: 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  __ (self):.     
1ba0: 20 20 20 23 20 55 73 65 64 20 61 73 20 61 20 6b     # Used as a k
1bb0: 65 79 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64  ey in a python d
1bc0: 69 63 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20  ictionary..     
1bd0: 20 20 20 72 65 74 75 72 6e 20 73 65 6c 66 2e 5f     return self._
1be0: 5f 73 74 72 5f 5f 28 29 2e 5f 5f 68 61 73 68 5f  _str__().__hash_
1bf0: 5f 28 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f 65  _()..    def __e
1c00: 71 5f 5f 20 28 73 65 6c 66 2c 20 6f 74 68 65 72  q__ (self, other
1c10: 29 3a 0a 20 20 20 20 20 20 20 20 23 20 55 73 65  ):.        # Use
1c20: 64 20 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20  d as a key in a 
1c30: 70 79 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72  python dictionar
1c40: 79 2e 0a 20 20 20 20 20 20 20 20 23 20 4e 6f 64  y..        # Nod
1c50: 65 73 20 61 72 65 20 65 71 75 69 76 61 6c 65 6e  es are equivalen
1c60: 74 20 69 66 20 74 68 65 79 20 68 61 76 65 20 69  t if they have i
1c70: 64 65 6e 74 69 63 61 6c 20 61 72 63 73 2c 20 61  dentical arcs, a
1c80: 6e 64 20 65 61 63 68 20 69 64 65 6e 74 69 63 61  nd each identica
1c90: 6c 20 61 72 63 20 6c 65 61 64 73 20 74 6f 20 69  l arc leads to i
1ca0: 64 65 6e 74 69 63 61 6c 20 73 74 61 74 65 73 2e  dentical states.
1cb0: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
1cc0: 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29 20 3d  self.__str__() =
1cd0: 3d 20 6f 74 68 65 72 2e 5f 5f 73 74 72 5f 5f 28  = other.__str__(
1ce0: 29 0a 0a 20 20 20 20 64 65 66 20 67 65 74 4e 6f  )..    def getNo
1cf0: 64 65 41 73 44 69 63 74 20 28 73 65 6c 66 29 3a  deAsDict (self):
1d00: 0a 20 20 20 20 20 20 20 20 22 72 65 74 75 72 6e  .        "return
1d10: 73 20 74 68 65 20 6e 6f 64 65 20 61 73 20 61 20  s the node as a 
1d20: 64 69 63 74 69 6f 6e 61 72 79 20 73 74 72 75 63  dictionary struc
1d30: 74 75 72 65 22 0a 20 20 20 20 20 20 20 20 64 4e  ture".        dN
1d40: 6f 64 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20  ode = {}.       
1d50: 20 64 52 65 56 61 6c 75 65 20 3d 20 7b 7d 0a 20   dReValue = {}. 
1d60: 20 20 20 20 20 20 20 64 52 65 4d 6f 72 70 68 20         dReMorph 
1d70: 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 52 75  = {}.        dRu
1d80: 6c 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20  le = {}.        
1d90: 64 4c 65 6d 6d 61 20 3d 20 7b 7d 0a 20 20 20 20  dLemma = {}.    
1da0: 20 20 20 20 64 4d 65 74 61 20 3d 20 7b 7d 0a 20      dMeta = {}. 
1db0: 20 20 20 20 20 20 20 66 6f 72 20 73 41 72 63 2c         for sArc,
1dc0: 20 6f 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 64   oNode in self.d
1dd0: 41 72 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20  Arcs.items():.  
1de0: 20 20 20 20 20 20 20 20 20 20 69 66 20 73 41 72            if sAr
1df0: 63 2e 73 74 61 72 74 73 77 69 74 68 28 22 40 22  c.startswith("@"
1e00: 29 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20  ) and len(sArc) 
1e10: 3e 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20  > 1:.           
1e20: 20 20 20 20 20 64 52 65 4d 6f 72 70 68 5b 73 41       dReMorph[sA
1e30: 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e  rc[1:]] = oNode.
1e40: 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20  __hash__().     
1e50: 20 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63         elif sArc
1e60: 2e 73 74 61 72 74 73 77 69 74 68 28 22 7e 22 29  .startswith("~")
1e70: 20 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e   and len(sArc) >
1e80: 20 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20   1:.            
1e90: 20 20 20 20 64 52 65 56 61 6c 75 65 5b 73 41 72      dReValue[sAr
1ea0: 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f  c[1:]] = oNode._
1eb0: 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20  _hash__().      
1ec0: 20 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e        elif sArc.
1ed0: 73 74 61 72 74 73 77 69 74 68 28 22 3e 22 29 20  startswith(">") 
1ee0: 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20  and len(sArc) > 
1ef0: 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1:.             
1f00: 20 20 20 64 4c 65 6d 6d 61 5b 73 41 72 63 5b 31     dLemma[sArc[1
1f10: 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61  :]] = oNode.__ha
1f20: 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20  sh__().         
1f30: 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61     elif sArc.sta
1f40: 72 74 73 77 69 74 68 28 22 2a 22 29 20 61 6e 64  rtswith("*") and
1f50: 20 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a   len(sArc) > 1:.
1f60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1f70: 64 4d 65 74 61 5b 73 41 72 63 5b 31 3a 5d 5d 20  dMeta[sArc[1:]] 
1f80: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
1f90: 28 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 65  ().            e
1fa0: 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74 73 77  lif sArc.startsw
1fb0: 69 74 68 28 22 23 23 22 29 3a 0a 20 20 20 20 20  ith("##"):.     
1fc0: 20 20 20 20 20 20 20 20 20 20 20 64 52 75 6c 65             dRule
1fd0: 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f  [sArc[1:]] = oNo
1fe0: 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20  de.__hash__().  
1ff0: 20 20 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a            else:.
2000: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
2010: 64 4e 6f 64 65 5b 73 41 72 63 5d 20 3d 20 6f 4e  dNode[sArc] = oN
2020: 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20  ode.__hash__(). 
2030: 20 20 20 20 20 20 20 69 66 20 64 52 65 56 61 6c         if dReVal
2040: 75 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ue:.            
2050: 64 4e 6f 64 65 5b 22 3c 72 65 5f 76 61 6c 75 65  dNode["<re_value
2060: 3e 22 5d 20 3d 20 64 52 65 56 61 6c 75 65 0a 20  >"] = dReValue. 
2070: 20 20 20 20 20 20 20 69 66 20 64 52 65 4d 6f 72         if dReMor
2080: 70 68 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ph:.            
2090: 64 4e 6f 64 65 5b 22 3c 72 65 5f 6d 6f 72 70 68  dNode["<re_morph
20a0: 3e 22 5d 20 3d 20 64 52 65 4d 6f 72 70 68 0a 20  >"] = dReMorph. 
20b0: 20 20 20 20 20 20 20 69 66 20 64 4c 65 6d 6d 61         if dLemma
20c0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e  :.            dN
20d0: 6f 64 65 5b 22 3c 6c 65 6d 6d 61 73 3e 22 5d 20  ode["<lemmas>"] 
20e0: 3d 20 64 4c 65 6d 6d 61 0a 20 20 20 20 20 20 20  = dLemma.       
20f0: 20 69 66 20 64 4d 65 74 61 3a 0a 20 20 20 20 20   if dMeta:.     
2100: 20 20 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 6d         dNode["<m
2110: 65 74 61 3e 22 5d 20 3d 20 64 4d 65 74 61 0a 20  eta>"] = dMeta. 
2120: 20 20 20 20 20 20 20 69 66 20 64 52 75 6c 65 3a         if dRule:
2130: 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f  .            dNo
2140: 64 65 5b 22 3c 72 75 6c 65 73 3e 22 5d 20 3d 20  de["<rules>"] = 
2150: 64 52 75 6c 65 0a 20 20 20 20 20 20 20 20 23 69  dRule.        #i
2160: 66 20 73 65 6c 66 2e 62 46 69 6e 61 6c 3a 0a 20  f self.bFinal:. 
2170: 20 20 20 20 20 20 20 23 20 20 20 20 64 4e 6f 64         #    dNod
2180: 65 5b 22 3c 66 69 6e 61 6c 3e 22 5d 20 3d 20 31  e["<final>"] = 1
2190: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
21a0: 64 4e 6f 64 65 0a                                dNode.