Sulla scia dei post educativi di Luka e di Antonio ho riflettuto sul codice che sto producendo per il mio ultimo progetto che andrà a breve su codeplex, ovvero un parser di regex con successiva conversione ad automa deterministico minimizzato. L’implementazione “hand made” del parser  (lo scopo del progetto dovrebbe essere propedeutico per gli studenti che affrontano un primo corso sui compilatori o di informatica teorica) segue i consigli dell’ottimo testo Flexible Pattern Matching in Strings.

Questo è la prima implementazione che segue passo passo lo pseudo codice del libro (con l’aggiunta del campo enum sulla tipologia di nodo del parseTree):

   1: private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)
   2: {
   3:     NonDeterministicAutomaton left,right,star;
   4:     left = new NonDeterministicAutomaton();
   5:     right = new NonDeterministicAutomaton();
   6:     star = new NonDeterministicAutomaton();
   7:     if (current.NodeType == NodeType.ConcatenationOp || current.NodeType == NodeType.AlternationOp)
   8:     {
   9:         left = this.RecursiveTree2Automaton(current.Left);
  10:         right = this.RecursiveTree2Automaton(current.Right);
  11:     }
  12:     else if (current.NodeType == NodeType.KleenStarOp)
  13:     {
  14:         star = this.RecursiveTree2Automaton(current.Right);
  15:     }
  16:  
  17:     if (current.NodeType == NodeType.ConcatenationOp)
  18:     {
  19:         return Concatenation.Concatenate2NFA(left, right);
  20:     }
  21:  
  22:     if (current.NodeType == NodeType.AlternationOp)
  23:     {
  24:         return Alternation.Alternate2NFA(left, right);
  25:     }
  26:  
  27:     if (current.NodeType == NodeType.KleenStarOp)
  28:     {
  29:         return KleenStar.Iterate2NFA(star);
  30:     }
  31:     // At this point our current node is a simple char
  32:     //if (current.nodeType == NodeType.Character)
  33:     return new Symbol(current.Symbol.ToString()).Convert2NFA();            
  34: }

Il codice è piuttosto difficile da manutenere e testare a causa della quantità di branch presenti nel codice. Un primo miglioramento apportato è stato quello di inserire uno switch case e compattare la ricorsione con le operazioni di base:

   1: private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)
   2: {
   3:     NonDeterministicAutomaton left,right,star;
   4:     left = new NonDeterministicAutomaton();
   5:     right = new NonDeterministicAutomaton();
   6:     star = new NonDeterministicAutomaton();
   7:     switch (current.NodeType)
   8:     {
   9:         case NodeType.AlternationOp:
  10:             left = this.RecursiveTree2Automaton(current.Left);
  11:             right = this.RecursiveTree2Automaton(current.Right);
  12:             return Alternation.Alternate2NFA(left, right);
  13:  
  14:         case NodeType.ConcatenationOp:
  15:             left = this.RecursiveTree2Automaton(current.Left);
  16:             right = this.RecursiveTree2Automaton(current.Right);
  17:             return Concatenation.Concatenate2NFA(left, right);
  18:  
  19:         case NodeType.KleenStarOp:
  20:             star = this.RecursiveTree2Automaton(current.Right);
  21:             return KleenStar.Iterate2NFA(star);
  22:  
  23:         case NodeType.Character:
  24:             return new AlphabetSymbol(current.Symbol).Convert2NFA();                                                                  
  25:     }
  26:  
  27:     throw new Exception("Unknown conversion symbol");
  28: }

Il codice è maggiormente leggibile ma soffre del problema che se un domani oltre a supportare come operatori per le regex l’unione la concatenazione e la stella di Kleen (operatore asterisco) devo inserire altri case nel codice. Secondo voi è possibile migliorare ulteriormente il codice eliminando di fatto il costrutto switch case?

Di seguito per maggiore chiarezza il codice completo della classe che include il metodo RecursiveTreeToAutomaton

   1: /*  ----------------------------------------------------------------------------
   2:  *  Regex2Automaton
   3:  *  ----------------------------------------------------------------------------
   4:  *  Author:      Luca Del Tongo
   5:  *  Blog:          blogs.ugidotnet.org/wetblog
   6:  *  File:        NFABuilder.cs
   7:  *  Summary:     Class used to build an NFA from a Regex Pattern
   8:  *  Date:         31/03/2010
   9:  *  ----------------------------------------------------------------------------
  10:  *
  11:  */
  12:  
  13: namespace Regex2Automaton
  14: {
  15:     using System;
  16:     using System.Collections.Generic;
  17:     using System.Linq;
  18:     using System.Text;
  19:  
  20:     /// <summary>
  21:     /// Class used to build an NFA from a Regex Pattern
  22:     /// </summary>
  23:     public class NFABuilder
  24:     {
  25:         public RegexParser RegexParser { get; set; }
  26:                 
  27:         public NFABuilder()
  28:         {
  29:             this.RegexParser = new RegexParser();
  30:         }
  31:        
  32:         public NonDeterministicAutomaton BuildNFA(string pattern)
  33:         {
  34:             ParseTree parseTree = RegexParser.BuildParseTree(pattern);
  35:             return this.RecursiveTree2Automaton(parseTree);            
  36:         }
  37:  
  38:         public NonDeterministicAutomaton BuildNFA(ParseTree patternParseTree)
  39:         {            
  40:             return this.RecursiveTree2Automaton(patternParseTree);
  41:         }
  42:  
  43:         private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)
  44:         {
  45:             NonDeterministicAutomaton left,right,star;
  46:             left = new NonDeterministicAutomaton();
  47:             right = new NonDeterministicAutomaton();
  48:             star = new NonDeterministicAutomaton();
  49:             switch (current.NodeType)
  50:             {
  51:                 case NodeType.AlternationOp:
  52:                     left = this.RecursiveTree2Automaton(current.Left);
  53:                     right = this.RecursiveTree2Automaton(current.Right);
  54:                     return Alternation.Alternate2NFA(left, right);
  55:  
  56:                 case NodeType.ConcatenationOp:
  57:                     left = this.RecursiveTree2Automaton(current.Left);
  58:                     right = this.RecursiveTree2Automaton(current.Right);
  59:                     return Concatenation.Concatenate2NFA(left, right);
  60:  
  61:                 case NodeType.KleenStarOp:
  62:                     star = this.RecursiveTree2Automaton(current.Right);
  63:                     return KleenStar.Iterate2NFA(star);
  64:  
  65:                 case NodeType.Character:
  66:                     return new AlphabetSymbol(current.Symbol).Convert2NFA();                                                                  
  67:             }
  68:  
  69:             throw new Exception("Unknown conversion symbol");
  70:         }
  71:     }  
  72: }