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 != ',';
}
}
