Analizzatore lessicale per espressioni regolari

Un analizzatore lessicale è un fase fondamentale della compilazione/interpretazione. Il suo scopo è quello di accettare in ingresso uno stream di caratteri e produrre uno stream di token, dove ogni token è rappresentato dal testo e dal tipo.

Nel nostro esempio mostreremo un semplice Lexer per espressioni regolari.
Gli operatori sono il simbolo * (chiusura di Kleene), il simbolo + (chiusura positiva) e il simbolo | (l’or tra due stringhe).
Una stringa verrà rappresentata da una sequenza di lettere o numeri e gli spazi vuoti verranno scartati.
La stringa vuota (comunemente rappresentata dalla lettera epsilon in letteratura) verrà rappresentata dal carattere $
Il lexer non applicherà nessuna strategia di recovery a seguito di un errore, ma lancerà semplicemente un eccezione UnknownTokenException.

Mostriamo dunque le varie classi che compongono l’esempio. Iniziamo dallo stream di caratteri:

com.at.analysis.CharStream

package com.at.analysis;

public class CharStream {
  private String _stream;
  private int    _currIdx = 0;

  public CharStream(String stream) {
    _stream= stream;
  }

  public char LA(int offset) {
    if (_currIdx + offset >= _stream.length() || offset < 0) {
      return 0;
    }
    return _stream.charAt(offset + _currIdx);
  }

  public char consume() {
    if (_currIdx >= _stream.length()) {
      return 0;
    }
    return _stream.charAt(_currIdx++);
  }
}

Notiamo che, banalmente, lo stream itera su una stringa, può consumare un carattere (legge e avanza il cursore identificato da _currIdx) o guardare avanti nella stringa (look ahead) con il metodo public char LA(int offset). Tale metodo consente di leggere il carattere corrente senza consumarlo se invocato con parametro offset = 0.
Nello specifico, useremo questo metodo per identificare i token di tipo stringa.

Dallo stream di caratteri creeremo uno stream di token. La classe che rappresenta quest’ultimo è questa:

com.at.analysis.TokenStream

package com.at.analysis;

import java.util.List;

public class TokenStream {
  private List<Token> _stream;
  private int         _currIdx;

  public TokenStream(List<Token> stream) {
    _stream= stream;
    _currIdx= 0;
  }

  public Token LA(int offset) {
    if (_currIdx + offset >= _stream.size()) {
      return null;
    }
    return _stream.get(_currIdx + offset);
  }

  public Token consume() {
    if (_currIdx >= _stream.size()) {
      return null;
    }
    return _stream.get(_currIdx++);
  }

  @Override
  public String toString() {
    StringBuilder sb= new StringBuilder().append("[");
    for (int i= 0; i < _stream.size(); i++) {
      sb.append(_stream.get(i));
      if (i < _stream.size() - 1) {
        sb.append(", ");
      }
    }
    sb.append("]");
    return sb.toString();
  }
}

Un istanza di questa classe gestisce, come detto, dei token rappresentati dal testo e dal tipo:

com.at.analysis.TokenType

package com.at.analysis;

public enum TokenType {
  OPERAND, OPERATOR, LParen, RParen
}

com.at.analysis.Token

package com.at.analysis;

public class Token {
  protected String    text;
  protected TokenType type;

  public Token(char c, TokenType type) {
    this.text= String.valueOf(c);
    this.type= type;
  }

  public Token(String text, TokenType type) {
    this.text= text;
    this.type= type;
  }

  public String getText() {
    return text;
  }

  public TokenType getType() {
    return type;
  }

  @Override
  public String toString() {
    return this.getClass().getSimpleName() + " <" + text + ", " + type.toString() + ">";
  }
}

Non ci rimane dunque che da mostrare il lexer vero e proprio:

package com.at.lexer;

import java.util.ArrayList;
import java.util.List;

import com.at.analysis.CharStream;
import com.at.analysis.Token;
import com.at.analysis.TokenStream;
import com.at.analysis.TokenType;
import com.at.analysis.exc.UnknownTokenException;

public class RELexer {
  private CharStream _stream;

  public RELexer(CharStream stream) {
    _stream= stream;
  }

  public TokenStream scan() throws UnknownTokenException {
    List<Token> tokens= new ArrayList<Token>();
    //
    char c= 0;
    while ((c= _stream.consume()) != 0) {
      if (c == ' ') {
        continue;
      } else if (c == ')') {
        tokens.add(new Token(")", TokenType.RParen));
      } else if (c == '(') {
        tokens.add(new Token("(", TokenType.LParen));
      } else if (Character.isDigit(c) || Character.isLetter(c)) {
        String str= String.valueOf(c);
        while (Character.isDigit(_stream.LA(0)) || Character.isLetter(_stream.LA(0))) { // look-ahead
          str+= String.valueOf(_stream.consume());
        }
        tokens.add(new Token(str, TokenType.OPERAND));
      } else if(c == '$') {
        tokens.add(new Token("", TokenType.OPERAND));
      } else if (c == '|' || c == '*' || c == '+') {
        tokens.add(new Token(c, TokenType.OPERATOR));
      } else {
        throw new UnknownTokenException(String.valueOf(c));
      }
    }
    //
    return new TokenStream(tokens);
  }

  public static void main(String[] args) throws Throwable {
    RELexer lex= new RELexer(new CharStream("(010)*11(0|010|$)+(ab | ba)bb"));
    TokenStream tokenStream= lex.scan();
    System.out.println(tokenStream);
  }
}

I controlli dedicati alle parentesi e agli operatori sono banali. Quello dedicato al riconoscimento degli operandi ha una logica semplice: se ho appena consumato una lettera/numero, continuo a consumare dallo stream fin tanto che il look ahead mi dice che ho una lettera/numero.

Avviando il metodo main della classe, vedremo sullo standard output la lista dei token trovati dal lexer.