Sözdizimi: BNF, türetme, parse tree ve belirsizlik

Bu konu vizede en çok puan getiren bölüm. Soru tipleri belli: verilen gramerle leftmost derivation yaz, parse tree çiz, bir gramerin belirsiz olduğunu ispatla, gramerden öncelik ve birleşme yönünü oku, EBNF’yi BNF’ye çevir. Hepsi mekanik. Tarifi bilen kaybetmez.

Altın kurallar:

1. Leftmost derivation: her satırda sadece en soldaki tek nonterminal’i değiştir.
2. Ağaçta aşağıdaki önce hesaplanır. Yüksek öncelikli operatör ağaçta derindedir.
3. Sol özyineleme sola birleşme verir, sağ özyineleme sağa birleşme.
4. Belirsizlik ispatı = tek cümle + iki farklı ağaç. “Kuralda iki alternatif var” ispat değildir.
5. EBNF ifade gücü eklemez. Her EBNF kuralı BNF ile yazılabilir.

Sözdizimi ve anlam

Bir dilin tanımı iki parçadan oluşur. Sözdizimi (syntax) ifadelerin biçimidir: hangi karakter dizileri geçerli program? Anlam (semantics) bu ifadelerin ne yaptığıdır. while (x < 5) x++; cümlesinin doğru yazılmış olması syntax, döngünün x 5 olana kadar artırması semantics.

Programın en küçük anlamlı birimi lexeme’dir: sum, =, 17, ;. Her lexeme bir kategoriye ait, bu kategoriye token denir. sum ve total farklı lexeme ama ikisi de aynı token: IDENT.

Dili tanımlamanın iki yolu var. Recognizer (tanıyıcı) bir cümleyi alır, “dile ait mi?” diye karar verir; derleyicinin syntax analyzer’ı budur. Generator (üretici) dilin cümlelerini üretir; gramer budur.

BNF

BNF (Backus-Naur Form), 1950’lerin sonunda ALGOL 58/60 için kullanıldı ve Chomsky’nin context-free grammar (bağlamdan bağımsız gramer) sınıfıyla aynı güçtedir. Bir kural (rule, production) şu biçimdedir:

<if_stmt> -> if <logic_expr> then <stmt>
           | if <logic_expr> then <stmt> else <stmt>

• Sol taraf (LHS) tek bir nonterminal: köşeli parantezli soyutlama, <if_stmt> gibi.
• Sağ taraf (RHS) terminal ve nonterminal dizisi. Terminal dilin gerçek sembolleri: if, then, +.
• | aynı LHS için alternatif demek.
• Başlangıç sembolü (start symbol) genelde ilk kuralın LHS’si: <program>, <assign>.

BNF’de tekrar için döngü yok. Listeler özyineleme (recursion) ile yazılır:

<ident_list> -> ident | ident , <ident_list>

Bu kural x, x , y, x , y , z … üretir.

Türetme (derivation)

Türetme, başlangıç sembolünden başlayıp kuralları uygulayarak cümleye ulaşmaktır. Her ara satır bir sentential form, sadece terminallerden oluşan son satır bir sentence. Standart gramerimiz:

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

A = B + C * A için leftmost derivation:

<assign> => <id> = <expr>
         => A = <expr>
         => A = <expr> + <term>
         => A = <term> + <term>
         => A = <factor> + <term>
         => A = <id> + <term>
         => A = B + <term>
         => A = B + <term> * <factor>
         => A = B + <factor> * <factor>
         => A = B + <id> * <factor>
         => A = B + C * <factor>
         => A = B + C * <id>
         => A = B + C * A

13 adım. Hangi kuralı seçeceğine nasıl karar verdin? Cümlenin en üst seviyedeki operatörüne bak. Burada + en üstte (çarpma ondan önce hesaplanacak), o yüzden <expr> önce <expr> + <term> olarak açıldı. B = ( A + C ) * B cümlesinde parantez dışındaki tek operatör *, bu yüzden <expr> => <term> => <term> * <factor> yoluna girersin.

Rightmost derivation aynı işi en sağdaki nonterminal’den başlayarak yapar. Aynı ağaca karşılık gelir, sadece açma sırası farklı:

<assign> => <id> = <expr>
         => <id> = <expr> + <term>
         => <id> = <expr> + <factor>
         => <id> = <expr> + <id>
         => <id> = <expr> + C
         ...
         => A = B + C

TUZAK · tek satırda tek değişiklik. Bir adımda iki nonterminal’i birden açmak ya da kuralda olmayan kestirme yapmak (<expr> => B gibi; arada <term>, <factor>, <id> var) puan kaybettirir. Her satırda tam bir kural uygula.

Parse tree

Türetmenin hiyerarşik hali. Kök başlangıç sembolü, her iç düğüm bir nonterminal ve çocukları uygulanan kuralın RHS’si (soldan sağa), yapraklar terminaller. A = B + C * A için:

<assign>
├── <id> ── A
├── =
└── <expr>
    ├── <expr> ── <term> ── <factor> ── <id> ── B
    ├── +
    └── <term>
        ├── <term> ── <factor> ── <id> ── C
        ├── *
        └── <factor> ── <id> ── A

Yaprakları soldan sağa oku: A = B + C * A. Tutuyorsa ağaç doğru. Ağacın bir faydası daha var: anlamı gösterir. C * A alt ağaçta, yani önce hesaplanır, sonucu B’ye eklenir.

Belirsizlik (ambiguity)

Bir gramer, en az bir cümle için iki farklı parse tree üretebiliyorsa belirsizdir. Eşdeğer tanım: o cümlenin iki farklı leftmost derivation’ı vardır.

<E> -> <E> + <E> | <E> * <E> | x

x + x * x için iki ağaç var: kökte + (x + (x * x)) ya da kökte * ((x + x) * x). Değer koyunca fark ortaya çıkar: 2 + 3 * 4 birinci ağaçta 14, ikincide 20. Derleyici hangi kodu üreteceğini bilemez; belirsizliğin neden kötü olduğu bu.

İspat tarifi:

1. Aynı operatörden iki tane (a - b - a) ya da iki farklı operatör (a + b * c) olan kısa bir cümle seç.
2. İki ağacı çiz, kökteki operatör farklı olsun.
3. İki ağacın da yapraklarının aynı cümleyi verdiğini göster.

Belirsizliği gidermek: öncelik ve birleşme yönü

Her öncelik seviyesi için ayrı bir nonterminal kullan. Düşük öncelikli operatör başlangıç sembolüne yakın (ağaçta yukarıda), yüksek öncelikli olan aşağıda.

Birleşme yönü özyinelemenin hangi tarafta olduğundan gelir:

• Sol özyineleme (<expr> -> <expr> + <term>): LHS, RHS’nin solunda tekrar ediyor. Soldaki işlem derinde kalır. Sola birleşir: 9 - 4 - 2 = (9 - 4) - 2 = 3.
• Sağ özyineleme (<t> -> <f> ^ <t>): sağa birleşir: 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 512. Üs alma için doğru seçim budur.

<e> -> <e> - <t> | <t>          - sola birleşir, düşük öncelik
<t> -> <f> ^ <t> | <f>          ^ sağa birleşir, yüksek öncelik
<f> -> NUM

Bu gramerle 10 - 2 ^ 3 - 1 = (10 - (2 ^ 3)) - 1 = 1.

TUZAK · gramer kuralı dayatır. Sınavda bazen “ters” gramer verilir: <e> -> <e> * <t>, <t> -> <t> + <f>. Burada + daha aşağıda, yani önce hesaplanır: 2 * 3 + 4 = 2 * (3 + 4) = 14. Matematikten bildiğin kuralı değil, ağacı uygula. Aynı şekilde <e> -> <t> - <e> sağ özyinelemeli olduğu için 10 - 4 - 3 = 10 - (4 - 3) = 9 olur.

Dangling else

<stmt> -> if c then <stmt> | if c then <stmt> else <stmt> | s

if c then if c then s else s iki ağaca sahip: else içteki ya da dıştaki if’e ait olabilir. Java, C, C++ kuralı: else en yakın eşleşmemiş if’e bağlanır. Gramerle zorlamak için ifadeler <matched> (her if’in else’i var) ve <unmatched> diye ayrılır; o zaman aynı cümlenin tek ağacı kalır. Python girintiyle, Ruby ve Ada end / end if ile, Perl her dalda süslü parantez zorunluluğuyla sorunu sözdiziminde çözer.

EBNF

EBNF (Extended BNF) gücü artırmaz, kuralları kısaltır ve okunur yapar.

EBNF:  <expr> -> <term> { (+ | -) <term> }
BNF:   <expr> -> <expr> + <term> | <expr> - <term> | <term>

EBNF:  <args> -> ( [ id { , id } ] )
BNF:   <args> -> ( ) | ( <list> )
       <list> -> id | id , <list>

{ } ile yazılan tekrarı BNF’ye çevirirken sol özyineleme seçmek + ve - için olağan sola birleşmeyi korur. { } “en az bir” demek değildir; sıfır tekrar da dahildir. “En az bir” için X { X } yazılır.

Gramer yazma

Sık çıkan iki kalıp:

bir veya daha fazla a, sonra bir veya daha fazla b:
<S> -> <A> <B>
<A> -> a <A> | a
<B> -> b <B> | b

a^n b^2n, n >= 1 (sayılar bağlı):
<S> -> a <S> b b | a b b

Sayılar bağlıysa (“eşit sayıda”, “iki katı”) iki uç aynı kuralda birlikte üretilir. Bağımsızsa ayrı nonterminal’ler yan yana konur. Yazdıktan sonra iki-üç cümleyle kontrol et ve dile ait olmayan bir cümlenin üretilmediğini de düşün.

Hangi cümleler üretilir?

<S> -> a <S> | <B>
<B> -> b <B> c | b c

Önce dili tarif et: başta sıfır veya daha fazla a, sonra eşit sayıda (en az bir) b ve c. aabc ✔, abbcc ✔, bc ✔, abcc ✘ (b ve c sayısı farklı), aab ✘ (c yok).

Sık yapılan hatalar

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

<assign> => <id> = <expr> => A = <expr>
=> A = <expr> + <term> => A = <term> + <term>
=> A = <factor> + <term> => A = <id> + <term> => A = B + <term>
=> A = B + <term> * <factor> => A = B + <factor> * <factor>
=> A = B + <id> * <factor> => A = B + C * <factor>
=> A = B + C * <id> => A = B + C * A

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + <term> | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

<S> -> a <S> | <B>
<B> -> b <B> c | b c

<E> -> <E> + <E> | <E> * <E> | x

<e> -> <e> - <t> | <t>
<t> -> <f> ^ <t> | <f>
<f> -> NUM

<e> -> <e> * <t> | <t>
<t> -> <t> + <f> | <f>
<f> -> NUM

<e> -> <t> - <e> | <t>
<t> -> NUM

<stmt> -> if c then <stmt> | if c then <stmt> else <stmt> | s