Lexical ve syntax analysis: lexer, recursive descent, LL ve LR

Bir derleyicinin ilk iki aşaması lexical analysis (sözcük analizi) ve syntax analysis (sözdizimi analizi, parsing). Vizede en çok çıkan soru: verilen recursive-descent fonksiyonlarıyla bir ifadenin ayrıştırmasını adım adım izlemek. Ayrıca left recursion kaldırma ve pairwise disjointness testi kısa, net puanlar.

Altın kurallar:

1. Lexer token üretir, parser ağaç kurar.
2. Recursive descent’te her nonterminal bir fonksiyon. { } while döngüsü, [ ] if.
3. lex() her token için bir kez çağrılır ve bir sonraki token’ı nextToken’a koyar.
4. Left recursion top-down parser’ı öldürür, kaldırılmalı.
5. LL = top-down, LR = bottom-up.

Neden iki ayrı aşama?

Lexical analysis

Lexer kaynak kodu karakter karakter okur, karakterleri lexeme’lere toplar ve her lexeme’e bir token verir. Boşlukları ve yorumları atlar, kullanıcı tanımlı isimleri symbol table’a ekler, hataları (geçersiz karakter) bildirir.

result = rate * (count + 15);

IDENT(result) ASSIGN_OP(=) IDENT(rate) MULT_OP(*) LEFT_PAREN(()
IDENT(count) ADD_OP(+) INT_LIT(15) RIGHT_PAREN()) SEMICOLON(;)

10 lexeme. Lexer bir sonlu otomat (finite automaton) gibi çalışır; bunu çizmenin yolu durum diyagramı (state diagram):

            letter/digit
             ┌────┐
   letter    ▼    │
Start ─────► id ──┘ ── başka karakter ──► return IDENT (ya da reserved word)
  │
  │ digit    digit
  │         ┌────┐
  └───────► int ◄┘ ── başka karakter ──► return INT_LIT

Her harf ve her rakam için ayrı ok çizmek yerine karakter sınıfları kullanılır: LETTER ve DIGIT. Reserved word’ler (if, while) ayrı durum almaz; identifier olarak tanınır, sonra bir tabloya bakılarak ayrılır.

Parsing: top-down ve bottom-up

Parser iki iş yapar: sözdizimi hatalarını bulmak ve parse tree’yi (ya da onun bilgisini) üretmek.

LL: Left-to-right okuma, Leftmost derivation. LR: Left-to-right okuma, Rightmost derivation (tersten). Her türlü belirsiz olmayan gramer için genel parse algoritmaları $O(n^3)$; derleyicilerde kullanılan LL ve LR parser’lar gramerin bir alt sınıfıyla çalışır ve $O(n)$‘dir.

Recursive descent

Her nonterminal için bir fonksiyon yazılır. EBNF ile çok doğal eşleşir:

/* <expr> -> <term> {(+ | -) <term>} */
void expr() {
  term();
  while (nextToken == ADD_OP || nextToken == SUB_OP) {
    lex();
    term();
  }
}
/* <term> -> <factor> {(* | /) <factor>} */
void term() {
  factor();
  while (nextToken == MULT_OP || nextToken == DIV_OP) {
    lex();
    factor();
  }
}
/* <factor> -> id | int_constant | ( <expr> ) */
void factor() {
  if (nextToken == IDENT || nextToken == INT_LIT)
    lex();
  else if (nextToken == LEFT_PAREN) {
    lex();
    expr();
    if (nextToken == RIGHT_PAREN) lex();
    else error();
  }
  else error();
}

Kural: bir fonksiyon çağrıldığında nextToken zaten o fonksiyonun ilk token’ını tutuyor. Program lex() ile başlar, sonra expr() çağrılır.

İzleme: (a + b) * c

Enter <expr>
  Enter <term>
    Enter <factor>            next = (  → lex, next = a
      Enter <expr>
        Enter <term>
          Enter <factor>      next = a  → lex, next = +
          Exit <factor>
        Exit <term>           + çarpma değil, term döner
        lex, next = b         expr'nin while'ı + gördü
        Enter <term>
          Enter <factor>      next = b  → lex, next = )
          Exit <factor>
        Exit <term>
      Exit <expr>             ) toplama değil
      lex, next = *           factor ) bekliyordu, buldu
    Exit <factor>
    lex, next = c             term'in while'ı * gördü
    Enter <factor>            next = c  → lex, next = EOF
    Exit <factor>
  Exit <term>
Exit <expr>

Sayım: factor 4 kez, term 3 kez, expr 2 kez girildi, lex 7 kez çağrıldı. Sınavda izleme yaparken her satırda “nextToken şu an ne?” sorusunu sor. Döngü koşulu her zaman o anki nextToken’a bakar.

TUZAK · hangi döngü yakalar? x - y / 2 için - işaretini term değil expr’nin döngüsü yakalar (term sadece * ve / arar). / ise ikinci term() çağrısının içinde işlenir. Böylece ağaç x - (y / 2) olur ve öncelik kendiliğinden doğru çıkar.

<list> -> id { , id } için de aynı mantık: id , id , girdisinde son virgülden sonra id beklenirken EOF gelir, hata.

LL gramerin iki problemi

1. Left recursion

<expr> -> <expr> + <term> | <term>

expr() ilk iş olarak expr()’yi çağırır, hiç token tüketmeden. Sonsuz özyineleme. Doğrudan left recursion kaldırma kalıbı:

$A \to A\alpha \mid \beta \quad\Longrightarrow\quad A \to \beta A', \quad A' \to \alpha A' \mid \varepsilon$

<T>  -> <T> * <F> | <T> / <F> | <F>
⇓
<T>  -> <F> <T'>
<T'> -> * <F> <T'> | / <F> <T'> | ε

Yeni gramer aynı dili üretir (id, id * id, id / id * id, …). Sadece yapısı farklı.

2. Pairwise disjointness

Parser, bir sonraki token’a bakarak hangi RHS’yi seçeceğini bilmeli. Bunun için bir nonterminal’in her iki alternatifinin FIRST kümeleri kesişmemeli. FIRST(α), α’dan türeyen dizilerin ilk terminallerinin kümesi.

<A> -> a <B> | <B> b         FIRST(a<B>) = {a}
<B> -> a <C> | d             FIRST(<B>b) = FIRST(<B>) = {a, d}
                             {a} ∩ {a, d} = {a}  → TEST BAŞARISIZ

Düzeltme left factoring: ortak öneki dışarı al.

<stmt> -> if <c> then <s> | if <c> then <s> else <s>
⇓
<stmt> -> if <c> then <s> <rest>
<rest> -> else <s> | ε

Bottom-up parsing

Bottom-up parser girdiyi soldan okur, token’ları bir yığına koyar (shift) ve yığının üstündeki dizi bir RHS ile eşleştiğinde onu LHS’ye indirger (reduce). İndirgenecek doğru alt diziye handle denir. Sonuç, rightmost derivation’ın tersten yazılmış halidir:

id + id * id
<factor> + id * id         handle: ilk id
<term> + id * id
<expr> + id * id
<expr> + <factor> * id
<expr> + <term> * id       burada <expr> + <term> indirgenmez, * bekliyor
<expr> + <term> * <factor>
<expr> + <term>
<expr>

8 indirgeme. Zor kısım handle’ı doğru seçmek: <expr> + <term> bir RHS ama sonrasında * geldiği için şimdi indirgenirse çarpma yanlış bağlanır. LR parser’lar bu kararı bir tablo (ACTION/GOTO) ile verir; tabloyu kurmak bu dersin vize kapsamı dışında, fikri bilmek yeterli.

Sık yapılan hatalar

result = rate * (count + 15);

Enter <expr>
  Enter <term>
    Enter <factor>      next = x (IDENT) → lex, next = -
    Exit <factor>
  Exit <term>           - çarpma/bölme değil, term döner
  expr sees - → lex, next = y
  Enter <term> ... y / 2 burada (factor, lex /, factor)

<A> -> a <B> | <B> b
<B> -> a <C> | d
<C> -> c

<S> -> x <S> | <T> y | z
<T> -> w <T> | v

id + id * id
<factor> + id * id
<term> + id * id
<expr> + id * id
<expr> + <factor> * id
<expr> + <term> * id
<expr> + <term> * <factor>
<expr> + <term>
<expr>