Sulla scia del post precedente e dei commenti ricevuti, in particolar modo ho riflettuto molto sull’accusa :) mossa da Antonio circa la violazione dell’information hiding (aka stupro di oggetti) condivido l’approccio che ho seguito nel disegnare il parser per espressioni regolari a discesa ricorsiva (Recursive Descent Parser). Senza scendere troppo nei dettagli di come operi un parser, diciamo che in una prima fase il Parser esegue analisi lessicale appoggiandosi ad un oggetto Tokenizer che ha il compito di trasformare una stringa in input (nel caso in esame una regex) in uno stream di Tokens. Un token rappresenta un elemento di una regex che può essere quindi un semplice simbolo oppure uno dei classici operatori quali unione, concatenazione, iterazione e parentesi.

Per la definizione dei Tokens si possono scegliere diversi approcci, solitamente si definisce un token usando un enum che specifica il tipo di token:

   1: enum Kind{SYM,UNION,CONCAT,...}
   2: struct Token {
   3: public readonly Kind kind;
   4: public readonly string nval;
   5: private Token(Kind k){ kind=k;nval=0; }
   6: private Token(string n){kind=Kind.NUM;nval=n;}
   7:  
   8: static public Token From Kind(Kind k){return new Token(k);}
   9: static public Token From StringRep(string d){return new Token(d);}
  10: }

Definita la classe Token poi il Tokenizer ricevendo un input una regex del tipo a(b|c)* andrà ad istanziare lo stream di Tokens con un codice del tipo

   1: public List<Token> Scan(string regexInput)
   2: {
   3:      CharEnumerator tokenEnumerator = regexInput.GetEnumerator();
   4:      List<Token> tokens = new List<Token>();
   5:  
   6:      while (tokenEnumerator.MoveNext())
   7:      {
   8:         switch (tokenEnumerator.Current)
   9:                     {
  10:                         case '*':
  11:                             tokens.Add(Token.FromKind(KIND.Iteration);
  12:                             break;
  13:                         case '|':
  14:                             tokens.Add(Token.FromKind(KIND.Alternation);
  15:                             break;
  16:                         etc...
  17:                     }         
  18:      }
  19: }
 
Questo tipo di approccio seppur chiaro non sfrutta le potenzialità di un linguaggio OO. Ho deciso quindi per il mio caso di utilizzare un approccio OO, definendo una gerarchia di classi per i Token

 tokenscd[1]

Il codice di creazione dei tokens diventa cosi:

   1: public List<Token> Scan(string input)
   2: {
   3:   CharEnumerator tokenEnumerator = input.GetEnumerator();
   4:   while (tokenEnumerator.MoveNext())
   5:     {
   6:        tokens.Add(TokenBuilder.GetTokenFromChar(tokenEnumerator.Current));
   7:     }                        
   8:   return tokens;
   9: }

 

La creazione dei tokens viene affidata alla classe TokenBuilder che utilizzando un dictionary che ha per chiave un carattere e per valore un delegate, istanzia la corretta tipologia di token tipizzato.

   1: public class TokenCreator
   2:     {
   3:         private Dictionary<char, Func<char, Token>> fromCharKind2Token { get; set; }
   4:  
   5:         public TokenCreator(HashSet<char> terminals)
   6:         {
   7:             fromCharKind2Token = new Dictionary<char, Func<char, Token>>();
   8:  
   9:             Func<char, Token> symbolCreationDelegate = (sym) => new SymbolToken(sym);
  10:  
  11:             foreach (char terminal in terminals)
  12:             {
  13:                 fromCharKind2Token.Add(terminal, symbolCreationDelegate);                                        
  14:             }
  15:  
  16:             fromCharKind2Token.Add('|', (sym) => new AlternationToken());
  17:  
  18:             fromCharKind2Token.Add('.', (sym) => new ConcatenationToken());
  19:  
  20:             fromCharKind2Token.Add('*', (sym) => new IterationToken() );
  21:  
  22:             fromCharKind2Token.Add('(', (sym) => new OpenParenthesisToken());
  23:  
  24:             fromCharKind2Token.Add(')', (sym) => new CloseParenthesisToken());
  25:         }
  26:         
  27:         public Token GetTokenFromChar(char symbol)
  28:         {
  29:             return fromCharKind2Token[symbol].Invoke(symbol);
  30:         }
  31:  
  32:     }

 

A questo punto lo stream di tokens devono essere analizzati dal Parser per effettuare l’analisi sintattica e costruire l’albero di Parsing, ovvero il famoso ParseTree del post precedente. L’analisi sintattica si basa sulla definizione di una grammatica che permette di dare significato ad un flusso di tokens.

Vediamo quindi come definire la struttura dei nodi che compongono l’albero di Parsing, tenendo presente che nel caso specifico dall’albero di parsing dovrò non tanto ad esempio calcolare il valore dell’espressione come nel caso dei parser aritmetici bensi dovrò convertire l’albero di parsing che rappresenta la mia regex in un automa a stati finiti non deterministico.

treenodefullcd[1]

La gerarchia di classi del dominio dell’albero di Parsing prevede una classe base astratta TreeNode che oltre ad implementare le apposite interfacce ha come campi privati un Token (classe astratta) ed un campo Id. Gli altri nodi dell’albero sono classi derivate dalla classe base astratta e possono avere un numero variabili di nodi figli. Sfruttando questa gerarchia di classi a questo punto possiamo vedere uno stralcio di codice del parser a discesa ricorsiva…

   1: public class Parser
   2:     {
   3:         private Token[] Tokens { get; set; }
   4:         private int next = 0;                         
   5:                 
   6:         public TreeNode Parse(List<Token> ts)
   7:         {
   8:             Tokens = ts.ToArray();
   9:             return Expr();            
  10:         }
  11:  
  12:         private void Move()
  13:         {
  14:             next++;
  15:         }
  16:  
  17:         private Token NextToken()
  18:         {
  19:             return (next < Tokens.Length) ? Tokens[next] : new EndingToken();
  20:         }
  21:  
  22:         /// <summary>
  23:         /// expr   ::= concat '|' expr | concat
  24:         /// </summary>
  25:         /// <returns></returns>
  26:         private TreeNode Expr()
  27:         {
  28:             TreeNode left = Concat();
  29:  
  30:             if (NextToken() is AlternationToken)
  31:             {
  32:                 Move();
  33:  
  34:                 TreeNode right = Expr();
  35:  
  36:                 AlternationNode exprNode = new AlternationNode(new AlternationToken(),left,right);
  37:  
  38:                 return exprNode;
  39:             }
  40:             else
  41:                 return left;
  42:         }
  43:       ...
  44:       ...
  45:       ...
  46: }

 

Sfruttando l’ereditarietà il codice risulta fortemente tipizzato e privo dei classici confronti tra simbolo corrente e stringa che vengono fatti nella maggior parte dei parser hand made. Il codice del parser a discesa ricorsiva dipende strettamente dalla grammatica che sta alla base del parser, se la grammatica può subire estensioni frequenti, è necessario un approccio maggiormente flessibile che sfrutta design patterns quali visitor ed abstract factory come descritto in questo ottimo paper (lettura consigliata).

Si accettano feedback :)

Nunc est bibendum, nunc pede libero pulsanda tellus