Gramer

Gramer Bileşenleri
Gramer ve türlerine girmeden önce gramer bileşenlerini bilmek gerekir. Bileşenler şunlardır
Terminal (devamlı), nonterminal (terminal), start symbol (başlama simgesi) ve production.

Production
S -> aSB bir production'dır. Terminal a , nonterminal S'in tanımladığı string seti ve terminal b'nin birleşiminden oluşur.

Substitution
A->xy production satırında A'nın yerine xy karakterlerinin konmasına da substitution denilir.

Gramer Gösterimi
En çok kullanılan gramer gösterim şekli Backus-Naum Form (BNF)'tir. BNF tekrar eden şeyleri gösterimde zahmetlidir. Bu yüzden Extended BNF gösterimi geliştirilmiştir.

EBNF parametrelerler gruplanmış alt kuralları da destekler.

Context Free Grammar (İçerikten Bağımsız Gramer) - Nedir?
Context Free Grammar yazısına taşıdım.

Context Sensitive Grammar Nedir?
Context Sensitive Grammar en çok doğal konuşma dilinde bulunur. Programlama dillerinde parsing safhasında karmaşıklığı çok artırdığı için pek tercih edilmez.

Örnek
Elimizde şöyle bir sql olsun.

SELECT x FROM y WHERE z

Açıklaması şöyle.

y can be another select query itself, so it cannot be simulated with finite-state machine.

Örnek
XML'de rastgele tag isimleri kullanılabilir. Her tag'in düzgün bir şekilde açılıp kapandığı kontrol edilmelidir. XMl Context Sensitive bir gramer kullanır.

<hi>
 <bye>
 the closing tag has to match bye
 </bye>
</hi> <!-- has to match "hi" -->

Örnek
C++ Context Free olduğunu iddia etse de aslında Context Sensitive bir grammar kullanır.

foo (a);

şeklindeki bir satır foo metodunu a parametresi ile çağırmak olabileceği gibi, foo tipinden a değişkeni tanımlamak (a'nın etrafından parantez olabilir veya olmayabilir) olarak ta anlaşılabilir. Yine aynı şekilde

x * y ;

 x ve y'nin çarpımı olabileceği gibi, x'e point eden y pointer'ı tanımlaması da olabilir.

Gramer ve Recursion
Gramerlerde left, middle veya right recursion olabilir. Recursion kullanılan gramer, parser türüne göre problem çıkarabiliyor.

1.Left Recursion
Şöyledir.
A→A∣1

2. Middle Recursion
Şöyledir.
A→0A1∣1

3. Right Recursion
Şöyledir.
A→0A∣1

Right Recursive Gramer, LR Parser ile kullanılamaz.

Şimdi biraz daha detaylandıralım.

Left Recursive Grammar Nedir?
Left Recursive Grammar (LRG) 'lar kendi içlerinde gruplanıyor.

1. Immediate Left Recursive Grammar 
Anlaması en kolay olanı.
Örnek 1
Şöyle yaparız

M -> M + n | n

Örnek 2
Şöyle yaparız

Expression ::= Expression '*' Expression
            || Expression '+' Expression
            || Term

Term ::= Number | Variable

LRG'ler sonsuz döngüye girebildikleri için pek tercih edilmezler. Grameri LRG olmaktan çıkarmak için çözümler bile bulunmuş.
Örnek
Elimizde şöyle bir gramer olsun

Expression  ::= AdditionExpression

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

MultiplicationExpression    ::=
    Term
        | MultiplicationExpression '*' Term
        | MultiplicationExpression '/' Term

Term    ::=
    Number
        | '(' AdditionExpression ')'

Number  ::=
    [+-]?[0-9]+(\.[0-9]+)?

Recursive'den çıkarmak için şöyle yaparız.

AdditionExpression  ::= 
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

Context Free Gramerler İçin Kullanılabilen Parser Çeşitleri Nelerdir
Context Free gramerler için LL Parser ve LR parser kullanılabilir. Bu iki parser çeşidini karşılaştıran şu yazıyı okudum ama anlamadım :)

1. LL Parser

LL Parser tablolar kullanır. Look ahead (ileri bakış) kullanırsa - örneğin 2 token ileri bakıyorsa LL (2) olarak belirtilir. Producution'dan başlayarak string'e ulaşmaya çalışır. Bu yüzden top-down olarak adlandırılır.

2. LL(1) Parser
Basit bir LL(1) grameri şöyledir.

S -> F

S -> ( S + F )

F -> a

3. LL(2) Parser
Aşağıdaki örnek Y iki token öteye bakmak zorunda olduğu için LL(2)'dir.

Z-> X

X-> Y
 -> b Y a

Y-> c
 -> c a

3. LL(2) Parser'dan LL(1)'e Dönüşüm
Elimizde şöyle bir kural olsun. Element iki token öteya bakmak zorunda olduğu için LL(2)'dir.

ELEMENT ::= PREFIX > ELEMENT_OR_DATA END_TAG

Dönüşümü şöyle yaparız.

LR Parser
LR Parser string'den production'a ulaşmaya çalışır. Bu yüzden bottom-up olarak adlandırılır.