Expression (Ifade) Parse Etme

Giriş
Bu yazı tamamen konu hakkında anladıklarımın özeti. Her anladığım, doğru olmayabilir.

Yazıda syntax (söz dizim), semantics (anlam/yorum) gibi konulara girmiyorum. Çok basit bir yazı olsun istedim.

Konuyla ilgili olarak Gramer başlıklı yazıya da göz atabilirsiniz.

Statement (Deyim) Nedir?
Wikipedia şöyle tanımlıyor.

In computer programming, a statement is the smallest standalone element of an imperative programming language that expresses some action to be carried out.

Basit bir örnek vermek gerekirse statement konuşma dilindeki tam bir cümle gibi düşünülebilir. Konuşma dilinde cümle nasıl nokta ile bitiyorsa statement ta çoğu dilde ; karakteri ile biter. C dilindeki statement grameri şöyledir.

stat        : labeled_stat
            | exp_stat
            | compound_stat
            | selection_stat
            | iteration_stat
            | jump_stat
            ;

Gramerde statement'ın exp_stat yani expression statement'lardan oluşabileceği görülüyor. Expression statement ise şöyledir.

exp_stat    : exp ';'
            |   ';'
            ;

Expression (İfade) Nedir?
Expression (İfade) tek değerden ibaret kod parçasıdır.Expression (İfade), Statement'tan (deyim)  farklıdır. Örneğin

for(i = 0; i < (1 << 7); i++)

satırında 1 << 7 constant bir expression'dır. Çünkü 128 değerini döner.
Örnek
Java'da lambda body expressin'dan oluşursa blok içine alınmaz. Ancak throw bir statement(deyim) oldupu için blok içinde kullanılması gerekir. Dolayısıyla şu kod derlenmez.

Supplier<Long> asd = () -> throw new RuntimeException(); // This won't compile :(

Şöyle yaparız.

Supplier<Long> asd = () -> {
    throw new RuntimeException();
};

Örnek
Bir statement tek bir expression'dan oluşamaz. Elimizde şöyle bir kod olsun.

public static void main(String[] args)
{
  1+2;
}

Şu çıktıyı alırız.

Main.java:5: error: not a statement
        1+2;
         ^
1 error

Expression Java Language Specification'da (JLS) şöyledir.

ExpressionStatement:
  StatementExpression ;

StatementExpression:
  Assignment 
  PreIncrementExpression 
  PreDecrementExpression 
  PostIncrementExpression 
  PostDecrementExpression 
  MethodInvocation 
  ClassInstanceCreationExpression

Expression Nasıl Parse Edilir?
Lexer veya Scanner
İfade daha küçük parçalara ayırılmalıdır. Bu işlemi yapan programa Lexer denilir. Lexer'in çıktısı Token'lardır. Tokenlar Operator (İşlem) ve Operand (İşlenen) olarak ayrılırlar. Bir çok lexer düzenli ifadeler (regular expression) ile ayırma işlemi yapar.

Aşağıda lexer ile kullanılan bazı düzenli ifade örnekleri var:

number := [digit][digit|underscore]+
reserved_word := 'if' | 'then' | 'else' | 'for' | 'while' | ...
identifier := [letter][letter|digit|underscore]*
assignment_operator := '=' | '+=' | '-=' | '*=' | '/=' 
addition_operator := '+' | '-' 
multiplication_operator := '*' | '/' | '%'

Lex
En çok kullanılan lexer'lardan biris lex uygulaması. lex aslında lexer üreten bir uygulama. Üretilen kod çoğu lexer gibi 2 boyutlu state transition tabloları kullanıyor.

Token Tree
Burada matematiksel bir ifadeyi çalıştıran örnek bir uygulama var. Ayırım neticesinde işlemlerin öncelik sırasına göre bir ağaç yapısı oluşturulur.

Her zaman ağaç yapısı oluşturulmak zorunda değildir. Başka yapılar da kullanılabilir. örneğin, stack (yığıt) yapısı da kullanıma çok uygundur.

Java

Örnek

Token şöyle. Satır ile çalıştığımız için başlangıç ve bitiş konumunu bilmek yeterli. Eğer satırla çalışmasaydım muhtemelen token değerini de bir bellek alanında saklama gerekirdi.

public class Token<T> {
  T type;
  int start
  int stop;
}

Lexer temeli şöyle

public abstract class AbstractLineLexer<T> {
  String line;

  //Position is incremented by inheriting Lexer
  int pos;

  private final Token[] lookAheadTokens;
  private int lookAheadPosition;
  private int lookAheadLength;

  AbstractLineLexer(int k) {
    lookAheadTokens = new Token[k + 1];
    for (int i = 0; i < lookAheadTokens.length; i++) {
      lookAheadTokens[i] = new Token();
    }
  }

  public void setLine(String line) {
    this.line = line;
    this.pos = 0;
    this.lookAheadPosition = 0;
    this.lookAheadLength = 0;
  }

  public Token<T> consume() throws Exception {...}

  public Token<T> lookAhead(int k) throws Exception {....}

  //Read next token from input into token object.
  protected abstract void readToken(Token<TYPE> token) throws MalformedBatchException;

}

Esas kod şöyle. Burada circular buffer şeklinde bir yapı var. lookAhead() ile istenilen sayıda token circular buffer'a dolduruluyor ve en son token döndürülüyor. Eğer istenirse consume() ile token'lar birer birer de tüketilebilir.

Token<T> consume() throws Exception {
  if (lookAheadLength == 0) {
    lookAhead(1);
  }
  lookAheadLength--;
  lookAheadPosition = (lookAheadPosition + 1) % lookAheadTokens.length;
  return lookAheadTokens[lookAheadPosition];
}

Token<T> lookAhead(int k) throws Exception {
  if (k >= lookAheadTokens.length || k < 0) {
    throw new IllegalStateException("Invalid look ahead value: " + k);
  }
  while (lookAheadLength <= k) {
    Token token = lookAheadTokens[(lookAheadPosition + lookAheadLength++) 
      % lookAheadTokens.length]
    readToken(token);
  }
  return lookAheadTokens[(lookAheadPosition + k) % lookAheadTokens.length];
}

Kalıtan Lexer'ın token tipleri şöyle

enum TokenType {
  ENTRY_BEGIN("{"),
  ENTRY_END("}"),
  ARRAY_BEGIN("["),
  ARRAY_END("]"),
  ARRAY_SEPARATOR(","),
  SEPARATOR("|"),
  STRING("String"),
  IDENTIFIER("Identifier"),
  EOL("End of line");

  final String name;

  TokenType(String name) {
    this.name = name;
  }
}

Lexer ise şöyle

public class Lexer extends AbstractLineLexer<TokenType> {

  Lexer(int k) {
    super(k);
  }

  @Override
  public void readToken(Token<TokenType> token) throws MalformedBatchException {
    token.start = pos; //Save start position of token
    if (token.start == line.length()) {
      token.type = TokenType.EOL;
    } else {
      token.type = readToken();
    }
    token.stop = pos; //Save stop position of token
  }

  protected TokenType readToken() throws MalformedBatchException {
    char c = line.charAt(pos++);
    switch (c) {
      case '{':
        return TokenType.ENTRY_BEGIN;
      case '}':
        return TokenType.ENTRY_END;
      case '[':
        return TokenType.ARRAY_BEGIN;
      case ']':
        return TokenType.ARRAY_END;
      case ',':
        return TokenType.ARRAY_SEPARATOR;
      case '|':
        return TokenType.SEPARATOR;
      case '"':
        while (pos < line.length()) {
          if (line.charAt(pos++) == '"') {
            return TokenType.STRING;
          }
        }
        throw new Exception("Expected character '\"'", line.length());
      default:
        if (isIdChar(c)) {
          while (pos < line.length() && isIdChar(line.charAt(pos))) {
            pos++;
          }
          return TokenType.IDENTIFIER;
        } else {
          throw new Exception("Unexpected character '" + c + "'", pos - 1);
        }
      }
    }

  private boolean isIdChar(char c) {
    return c != '"' && c != '|' && c != '{' && c != '}' && c != '[' && c != ']' 
      && c != ',';
  }
}