Grammalecte  Hex Artifact Content

Artifact 5064c8e0275996fa506057f959914b91eff55134669dc116cf94c520bd82811e:


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 72 65  raph).        re
1080: 74 75 72 6e 20 64 47 72 61 70 68 0a 0a 20 20 20  turn dGraph..   
1090: 20 64 65 66 20 5f 72 65 77 72 69 74 65 4b 65 79   def _rewriteKey
10a0: 73 4f 66 44 41 52 47 20 28 73 65 6c 66 2c 20 64  sOfDARG (self, d
10b0: 47 72 61 70 68 29 3a 0a 20 20 20 20 20 20 20 20  Graph):.        
10c0: 22 6b 65 79 73 20 6f 66 20 44 41 52 47 20 61 72  "keys of DARG ar
10d0: 65 20 6c 6f 6e 67 20 6e 75 6d 62 65 72 73 20 28  e long numbers (
10e0: 68 61 73 68 65 73 29 3a 20 74 68 69 73 20 66 75  hashes): this fu
10f0: 6e 63 74 69 6f 6e 20 72 65 70 6c 61 63 65 20 74  nction replace t
1100: 68 65 73 65 20 68 61 73 68 65 73 20 77 69 74 68  hese hashes with
1110: 20 73 6d 61 6c 6c 65 72 20 6e 75 6d 62 65 72 73   smaller numbers
1120: 20 28 74 6f 20 72 65 64 75 63 65 20 73 74 6f 72   (to reduce stor
1130: 69 6e 67 20 73 69 7a 65 29 22 0a 20 20 20 20 20  ing size)".     
1140: 20 20 20 23 20 63 72 65 61 74 65 20 74 72 61 6e     # create tran
1150: 73 6c 61 74 69 6f 6e 20 64 69 63 74 69 6f 6e 61  slation dictiona
1160: 72 79 0a 20 20 20 20 20 20 20 20 64 4b 65 79 54  ry.        dKeyT
1170: 72 61 6e 73 20 3d 20 7b 7d 0a 20 20 20 20 20 20  rans = {}.      
1180: 20 20 66 6f 72 20 69 2c 20 6e 4b 65 79 20 69 6e    for i, nKey in
1190: 20 65 6e 75 6d 65 72 61 74 65 28 64 47 72 61 70   enumerate(dGrap
11a0: 68 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  h):.            
11b0: 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d 20  dKeyTrans[nKey] 
11c0: 3d 20 69 0a 20 20 20 20 20 20 20 20 23 20 72 65  = i.        # re
11d0: 70 6c 61 63 65 20 6b 65 79 73 0a 20 20 20 20 20  place keys.     
11e0: 20 20 20 64 4e 65 77 47 72 61 70 68 20 3d 20 7b     dNewGraph = {
11f0: 7d 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6e 4b  }.        for nK
1200: 65 79 2c 20 64 56 61 6c 20 69 6e 20 64 47 72 61  ey, dVal in dGra
1210: 70 68 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  ph.items():.    
1220: 20 20 20 20 20 20 20 20 64 4e 65 77 47 72 61 70          dNewGrap
1230: 68 5b 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79  h[dKeyTrans[nKey
1240: 5d 5d 20 3d 20 64 56 61 6c 0a 20 20 20 20 20 20  ]] = dVal.      
1250: 20 20 66 6f 72 20 6e 4b 65 79 2c 20 64 56 61 6c    for nKey, dVal
1260: 20 69 6e 20 64 47 72 61 70 68 2e 69 74 65 6d 73   in dGraph.items
1270: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
1280: 66 6f 72 20 73 41 72 63 2c 20 76 61 6c 20 69 6e  for sArc, val in
1290: 20 64 56 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20   dVal.items():. 
12a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 69                 i
12b0: 66 20 74 79 70 65 28 76 61 6c 29 20 69 73 20 69  f type(val) is i
12c0: 6e 74 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  nt:.            
12d0: 20 20 20 20 20 20 20 20 64 56 61 6c 5b 73 41 72          dVal[sAr
12e0: 63 5d 20 3d 20 64 4b 65 79 54 72 61 6e 73 5b 76  c] = dKeyTrans[v
12f0: 61 6c 5d 0a 20 20 20 20 20 20 20 20 20 20 20 20  al].            
1300: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
1310: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 66 6f                fo
1320: 72 20 73 41 72 63 2c 20 6e 4b 65 79 20 69 6e 20  r sArc, nKey in 
1330: 76 61 6c 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20  val.items():.   
1340: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1350: 20 20 20 20 20 76 61 6c 5b 73 41 72 63 5d 20 3d       val[sArc] =
1360: 20 64 4b 65 79 54 72 61 6e 73 5b 6e 4b 65 79 5d   dKeyTrans[nKey]
1370: 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20  .        return 
1380: 64 4e 65 77 47 72 61 70 68 0a 0a 0a 63 6c 61 73  dNewGraph...clas
1390: 73 20 4e 6f 64 65 3a 0a 20 20 20 20 22 22 22 4e  s Node:.    """N
13a0: 6f 64 65 20 6f 66 20 74 68 65 20 72 75 6c 65 20  ode of the rule 
13b0: 67 72 61 70 68 22 22 22 0a 0a 20 20 20 20 4e 65  graph"""..    Ne
13c0: 78 74 49 64 20 3d 20 30 0a 0a 20 20 20 20 64 65  xtId = 0..    de
13d0: 66 20 5f 5f 69 6e 69 74 5f 5f 20 28 73 65 6c 66  f __init__ (self
13e0: 29 3a 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  ):.        self.
13f0: 69 20 3d 20 4e 6f 64 65 2e 4e 65 78 74 49 64 0a  i = Node.NextId.
1400: 20 20 20 20 20 20 20 20 4e 6f 64 65 2e 4e 65 78          Node.Nex
1410: 74 49 64 20 2b 3d 20 31 0a 20 20 20 20 20 20 20  tId += 1.       
1420: 20 73 65 6c 66 2e 62 46 69 6e 61 6c 20 3d 20 46   self.bFinal = F
1430: 61 6c 73 65 0a 20 20 20 20 20 20 20 20 73 65 6c  alse.        sel
1440: 66 2e 64 41 72 63 73 20 3d 20 7b 7d 20 20 20 20  f.dArcs = {}    
1450: 20 20 20 20 20 20 23 20 6b 65 79 3a 20 61 72 63        # key: arc
1460: 20 76 61 6c 75 65 3b 20 76 61 6c 75 65 3a 20 61   value; value: a
1470: 20 6e 6f 64 65 0a 0a 20 20 20 20 40 63 6c 61 73   node..    @clas
1480: 73 6d 65 74 68 6f 64 0a 20 20 20 20 64 65 66 20  smethod.    def 
1490: 72 65 73 65 74 4e 65 78 74 49 64 20 28 63 6c 73  resetNextId (cls
14a0: 29 3a 0a 20 20 20 20 20 20 20 20 22 72 65 73 65  ):.        "rese
14b0: 74 20 74 6f 20 30 20 74 68 65 20 6e 6f 64 65 20  t to 0 the node 
14c0: 63 6f 75 6e 74 65 72 22 0a 20 20 20 20 20 20 20  counter".       
14d0: 20 63 6c 73 2e 4e 65 78 74 49 64 20 3d 20 30 0a   cls.NextId = 0.
14e0: 0a 20 20 20 20 64 65 66 20 5f 5f 73 74 72 5f 5f  .    def __str__
14f0: 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20   (self):.       
1500: 20 23 20 43 61 75 74 69 6f 6e 21 20 74 68 69 73   # Caution! this
1510: 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 75 73 65   function is use
1520: 64 20 66 6f 72 20 68 61 73 68 69 6e 67 20 61 6e  d for hashing an
1530: 64 20 63 6f 6d 70 61 72 69 73 6f 6e 21 0a 20 20  d comparison!.  
1540: 20 20 20 20 20 20 63 46 69 6e 61 6c 20 3d 20 22        cFinal = "
1550: 31 22 20 20 69 66 20 73 65 6c 66 2e 62 46 69 6e  1"  if self.bFin
1560: 61 6c 20 20 65 6c 73 65 20 22 30 22 0a 20 20 20  al  else "0".   
1570: 20 20 20 20 20 6c 20 3d 20 5b 63 46 69 6e 61 6c       l = [cFinal
1580: 5d 0a 20 20 20 20 20 20 20 20 66 6f 72 20 28 6b  ].        for (k
1590: 65 79 2c 20 6f 4e 6f 64 65 29 20 69 6e 20 73 65  ey, oNode) in se
15a0: 6c 66 2e 64 41 72 63 73 2e 69 74 65 6d 73 28 29  lf.dArcs.items()
15b0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6c 2e  :.            l.
15c0: 61 70 70 65 6e 64 28 73 74 72 28 6b 65 79 29 29  append(str(key))
15d0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 6c 2e 61  .            l.a
15e0: 70 70 65 6e 64 28 73 74 72 28 6f 4e 6f 64 65 2e  ppend(str(oNode.
15f0: 69 29 29 0a 20 20 20 20 20 20 20 20 72 65 74 75  i)).        retu
1600: 72 6e 20 22 5f 22 2e 6a 6f 69 6e 28 6c 29 0a 0a  rn "_".join(l)..
1610: 20 20 20 20 64 65 66 20 5f 5f 68 61 73 68 5f 5f      def __hash__
1620: 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20 20 20   (self):.       
1630: 20 23 20 55 73 65 64 20 61 73 20 61 20 6b 65 79   # Used as a key
1640: 20 69 6e 20 61 20 70 79 74 68 6f 6e 20 64 69 63   in a python dic
1650: 74 69 6f 6e 61 72 79 2e 0a 20 20 20 20 20 20 20  tionary..       
1660: 20 72 65 74 75 72 6e 20 73 65 6c 66 2e 5f 5f 73   return self.__s
1670: 74 72 5f 5f 28 29 2e 5f 5f 68 61 73 68 5f 5f 28  tr__().__hash__(
1680: 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f 65 71 5f  )..    def __eq_
1690: 5f 20 28 73 65 6c 66 2c 20 6f 74 68 65 72 29 3a  _ (self, other):
16a0: 0a 20 20 20 20 20 20 20 20 23 20 55 73 65 64 20  .        # Used 
16b0: 61 73 20 61 20 6b 65 79 20 69 6e 20 61 20 70 79  as a key in a py
16c0: 74 68 6f 6e 20 64 69 63 74 69 6f 6e 61 72 79 2e  thon dictionary.
16d0: 0a 20 20 20 20 20 20 20 20 23 20 4e 6f 64 65 73  .        # Nodes
16e0: 20 61 72 65 20 65 71 75 69 76 61 6c 65 6e 74 20   are equivalent 
16f0: 69 66 20 74 68 65 79 20 68 61 76 65 20 69 64 65  if they have ide
1700: 6e 74 69 63 61 6c 20 61 72 63 73 2c 20 61 6e 64  ntical arcs, and
1710: 20 65 61 63 68 20 69 64 65 6e 74 69 63 61 6c 20   each identical 
1720: 61 72 63 20 6c 65 61 64 73 20 74 6f 20 69 64 65  arc leads to ide
1730: 6e 74 69 63 61 6c 20 73 74 61 74 65 73 2e 0a 20  ntical states.. 
1740: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 73 65         return se
1750: 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29 20 3d 3d 20  lf.__str__() == 
1760: 6f 74 68 65 72 2e 5f 5f 73 74 72 5f 5f 28 29 0a  other.__str__().
1770: 0a 20 20 20 20 64 65 66 20 67 65 74 4e 6f 64 65  .    def getNode
1780: 41 73 44 69 63 74 20 28 73 65 6c 66 29 3a 0a 20  AsDict (self):. 
1790: 20 20 20 20 20 20 20 22 72 65 74 75 72 6e 73 20         "returns 
17a0: 74 68 65 20 6e 6f 64 65 20 61 73 20 61 20 64 69  the node as a di
17b0: 63 74 69 6f 6e 61 72 79 20 73 74 72 75 63 74 75  ctionary structu
17c0: 72 65 22 0a 20 20 20 20 20 20 20 20 64 4e 6f 64  re".        dNod
17d0: 65 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64  e = {}.        d
17e0: 52 65 56 61 6c 75 65 20 3d 20 7b 7d 0a 20 20 20  ReValue = {}.   
17f0: 20 20 20 20 20 64 52 65 4d 6f 72 70 68 20 3d 20       dReMorph = 
1800: 7b 7d 0a 20 20 20 20 20 20 20 20 64 52 75 6c 65  {}.        dRule
1810: 20 3d 20 7b 7d 0a 20 20 20 20 20 20 20 20 64 4c   = {}.        dL
1820: 65 6d 6d 61 20 3d 20 7b 7d 0a 20 20 20 20 20 20  emma = {}.      
1830: 20 20 64 4d 65 74 61 20 3d 20 7b 7d 0a 20 20 20    dMeta = {}.   
1840: 20 20 20 20 20 66 6f 72 20 73 41 72 63 2c 20 6f       for sArc, o
1850: 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 64 41 72  Node in self.dAr
1860: 63 73 2e 69 74 65 6d 73 28 29 3a 0a 20 20 20 20  cs.items():.    
1870: 20 20 20 20 20 20 20 20 69 66 20 73 41 72 63 2e          if sArc.
1880: 73 74 61 72 74 73 77 69 74 68 28 22 40 22 29 20  startswith("@") 
1890: 61 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20  and len(sArc) > 
18a0: 31 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20  1:.             
18b0: 20 20 20 64 52 65 4d 6f 72 70 68 5b 73 41 72 63     dReMorph[sArc
18c0: 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f  [1:]] = oNode.__
18d0: 68 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20  hash__().       
18e0: 20 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73       elif sArc.s
18f0: 74 61 72 74 73 77 69 74 68 28 22 7e 22 29 20 61  tartswith("~") a
1900: 6e 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20 31  nd len(sArc) > 1
1910: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  :.              
1920: 20 20 64 52 65 56 61 6c 75 65 5b 73 41 72 63 5b    dReValue[sArc[
1930: 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68  1:]] = oNode.__h
1940: 61 73 68 5f 5f 28 29 0a 20 20 20 20 20 20 20 20  ash__().        
1950: 20 20 20 20 65 6c 69 66 20 73 41 72 63 2e 73 74      elif sArc.st
1960: 61 72 74 73 77 69 74 68 28 22 3e 22 29 20 61 6e  artswith(">") an
1970: 64 20 6c 65 6e 28 73 41 72 63 29 20 3e 20 31 3a  d len(sArc) > 1:
1980: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20  .               
1990: 20 64 4c 65 6d 6d 61 5b 73 41 72 63 5b 31 3a 5d   dLemma[sArc[1:]
19a0: 5d 20 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68  ] = oNode.__hash
19b0: 5f 5f 28 29 0a 20 20 20 20 20 20 20 20 20 20 20  __().           
19c0: 20 65 6c 69 66 20 73 41 72 63 2e 73 74 61 72 74   elif sArc.start
19d0: 73 77 69 74 68 28 22 2a 22 29 20 61 6e 64 20 6c  swith("*") and l
19e0: 65 6e 28 73 41 72 63 29 20 3e 20 31 3a 0a 20 20  en(sArc) > 1:.  
19f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 4d                dM
1a00: 65 74 61 5b 73 41 72 63 5b 31 3a 5d 5d 20 3d 20  eta[sArc[1:]] = 
1a10: 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29  oNode.__hash__()
1a20: 0a 20 20 20 20 20 20 20 20 20 20 20 20 65 6c 69  .            eli
1a30: 66 20 73 41 72 63 2e 73 74 61 72 74 73 77 69 74  f sArc.startswit
1a40: 68 28 22 23 23 22 29 3a 0a 20 20 20 20 20 20 20  h("##"):.       
1a50: 20 20 20 20 20 20 20 20 20 64 52 75 6c 65 5b 73           dRule[s
1a60: 41 72 63 5b 31 3a 5d 5d 20 3d 20 6f 4e 6f 64 65  Arc[1:]] = oNode
1a70: 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20 20  .__hash__().    
1a80: 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a 20 20          else:.  
1a90: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 64 4e                dN
1aa0: 6f 64 65 5b 73 41 72 63 5d 20 3d 20 6f 4e 6f 64  ode[sArc] = oNod
1ab0: 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20 20  e.__hash__().   
1ac0: 20 20 20 20 20 69 66 20 64 52 65 56 61 6c 75 65       if dReValue
1ad0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e  :.            dN
1ae0: 6f 64 65 5b 22 3c 72 65 5f 76 61 6c 75 65 3e 22  ode["<re_value>"
1af0: 5d 20 3d 20 64 52 65 56 61 6c 75 65 0a 20 20 20  ] = dReValue.   
1b00: 20 20 20 20 20 69 66 20 64 52 65 4d 6f 72 70 68       if dReMorph
1b10: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 64 4e  :.            dN
1b20: 6f 64 65 5b 22 3c 72 65 5f 6d 6f 72 70 68 3e 22  ode["<re_morph>"
1b30: 5d 20 3d 20 64 52 65 4d 6f 72 70 68 0a 20 20 20  ] = dReMorph.   
1b40: 20 20 20 20 20 69 66 20 64 4c 65 6d 6d 61 3a 0a       if dLemma:.
1b50: 20 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64              dNod
1b60: 65 5b 22 3c 6c 65 6d 6d 61 73 3e 22 5d 20 3d 20  e["<lemmas>"] = 
1b70: 64 4c 65 6d 6d 61 0a 20 20 20 20 20 20 20 20 69  dLemma.        i
1b80: 66 20 64 4d 65 74 61 3a 0a 20 20 20 20 20 20 20  f dMeta:.       
1b90: 20 20 20 20 20 64 4e 6f 64 65 5b 22 3c 6d 65 74       dNode["<met
1ba0: 61 3e 22 5d 20 3d 20 64 4d 65 74 61 0a 20 20 20  a>"] = dMeta.   
1bb0: 20 20 20 20 20 69 66 20 64 52 75 6c 65 3a 0a 20       if dRule:. 
1bc0: 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65             dNode
1bd0: 5b 22 3c 72 75 6c 65 73 3e 22 5d 20 3d 20 64 52  ["<rules>"] = dR
1be0: 75 6c 65 0a 20 20 20 20 20 20 20 20 23 69 66 20  ule.        #if 
1bf0: 73 65 6c 66 2e 62 46 69 6e 61 6c 3a 0a 20 20 20  self.bFinal:.   
1c00: 20 20 20 20 20 23 20 20 20 20 64 4e 6f 64 65 5b       #    dNode[
1c10: 22 3c 66 69 6e 61 6c 3e 22 5d 20 3d 20 31 0a 20  "<final>"] = 1. 
1c20: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 4e         return dN
1c30: 6f 64 65 0a                                      ode.