Parser Çalışmalarım - XML Yapısı

Giriş

Bir kaç defa, XML'de tanımlı mesaj yapılarını okuyup bunları parse edebilen kodlarla uğraşmam gerekti. Bazı şeyleri not almak istedim

1. Birbirinden çok farklı XML yapılarını işleyebilecek jenerik bir kod yazmak çok zor bir şey. Var olan yapıya uymayan bir XML gelince bir sürü adaptor yazmak gerekiyor. Bu kadar uğraşa değmeyebilir.

İki Tane XML Lazım

Genellikle iki tane XML gerekiyor. Bu XML dosyalarına farkı farklı isimler verilebilir. Ben kısaca şöyle diyeceğim

1. Record Definition XML

2. Element Definition XML

Record Definition XML

Parse edilecek tüm mesajları içerir. Çoğu protokolde, Record içinde Record var. En azından mesajlarda header bulunuyor.

Element Definition XML

Record içindeki alanlar genellikle bir çok farklı yerde kullanılıyor. Bu yüzden element veya field diye düşünülebilecek bu yapıları farklı bir XML içinde tanımlamak gerekiyor.

1. Her Element 'in bir tane tekil key değeri bulunuyor. Buna identifier diyelim.

Örnek

Sadece 2 tane element 'ten ibaret çok basit bir record

<record id="foo">
  <field id="timeIndicator"/>
 <field id="statusIndicator"/>
</record>

Element yapısı şöyle. Burada field'ın her bir değerinin ne anlama geldiği gösteriliyor.

<element id="timeIndicator" length="2">
  <item code="0" value="No Time Indicator">
  <item code="1" value="Time Indicator">
</element>

XML okunur ve XmlDefinition ve ondan katılan sınıflar yaratılır. Bu sınıflar RecordDefinition, FieldDefinition vs. gibi şeyler. Definition sınıflar sadece XML'deki veriyi bilirler. Yani metadata.

Metadata'yı sarmalayan sınıflar lazım. Bunlar Record, Field gibi sınıflar.  

Record nesnesi kabaca şöyle. Her field kendi içindeki definition nesnesine bakarak stream'den ne kadar veri okuyacağını biliyor. 

public class Record {
  List<Field> fields;

  public boolean parse(Stream stream){
    //Field'ları dolaş ve stream'den okunan değerleri ata
  }
}

Örnek - Açmalı Kapamalı Alanlar

Bu yapılarda F1 gibi bir alanın değerine bakılır. 

- Eğer F1 = 0 ise, F2 ve F3 alanlar geçerlidir. 

- F1 farklı bir değere sahipse, F4 alanı geçerlidir. Yani kod olarak düşünürsek if/else yapısına benziyor

Birinci problem bu yapıyı XML olarak ifade edebilmek. İkinci problem ise bu yapıyı parse edebilecek jenerik kodu yazabilmek.

XML şöyle olabilir. Bu aslında çok basit bir örnek. Çok daha karmaşık şeyler düşünülebilir.

<record id="foo">
  <field id="timeIndicator"/>
  <field id="statusIndicator"/>
  <structureswitch id="indicatorSwitch">
    <when>
      <case value="1"/>
      <field id="voiceIndicator"/>
    </when>
    <when>
      <case value="2"/>
        <field id="smsIndicator"/>
    </when>
    <otherwise>
      <field id="emailIndicator"/>
    </otherwise>
  </structureswitch>
</record>

Parser Çalışmalarım - Ayrıştırıcı

Giriş
İki defa Parser (Ayrıştırıcı) işi ile uğraşmam gerekti. Her ikisinde de farklı yöntemler kullandım. Parser denilince akla sadece bir stream'den veriyi okuyup mesaj haline getiren şey geliyor.

İşin bir de mesaj oluşturup gönderme ve hatta mesajları belli kurallara göre gönderme tarafı da olabiliyor. Bu konuyu Parser ile karıştırmayıp Transmission Queue veya Message Crafting başlığı ile ayrı olarak ele almakta fayda var.

1. Gömülü Proje Parser
Bu projede mesajlar A zarfı içindeki B zarfı içindeki C mesajları şeklindeydi. Uygulama sadece C mesajları ile ilgileniyordu. Parser Java'daki Stax Parser gibi çalışacak şekilde tasarlandı. Yani C mesajlarını okudukça uygulamaya bir çeşit event(olay) gönderiyordu. Bu Parser push modda çalışıyor diye düşünülebilir. Uygulama A ve B zarfları ile ilgilenmediği için görece olarak gerçekleştirmesi kolay.

Tek sıkıntı mesajların zor ve açmalı kapamalı yapıya sahip olması ve gömülü ortamın getirdiği bellek kısıtlarıydı

2. Java Parser
Bu projedeki mesajlar sınırsız bir derinlikte ve zarf tipinde olabiliyordu. A zarfının içine B,C,D gibi herhangi bir zarf ve alt zarfların içine de yine belirsiz tipte mesajlar gelebiliyordu. Bu projedeki parser pull modda çalışıyordu. Yani parse() merodu sonucunda bir çeşit Composite dönüyordu.

Composite yapısını tasarlaması zordu. Ayrıca Parser içinden diğer parser'ları çağırmak ta gerektiği için her parser'a bir Context nesnesi geçmek gerekiyor. Context içinde Composite nesnesi, parser işleminin sonucu, Parser'ın çalışma modu gibi gerekli parametreler bulunuyordu.

Mesajlar için ayrı ayrı modüller/kütüphaneler tasarlanmıştı. Böylece mesajların tekrar kullanılabilir olması hedeflenmişti. Yani ben elle mesajı oluşturup gönderebiliyordum.

2.1 Genel Sıkıntılar - Bozuk Veri
Parser'ın hatalı gelen mesajları bir şekilde anlayıp bir şey yapması gerekiyor. Verinin nereden bozulduğunu anlaması kolay değil. Yapılabilecek bazı şeyler şöyle.

- Örneğin eski veri atılıp yeni bir başlangıç yapmak.
- Hatalı olan kısma kadar olan veriyi düzgünce  işleyip geri kalanını "Bozuk Veri" olarak göstermek.
- Bence en güzel yöntem Parser'ın okuduğı kanalı kapatıp gerekiyorsa tekrar açmak

2.2 Genel Sıkıntılar - Parser'ın Çıktısını İşleyen Kod
Parser'ımız Composite döndüğü için bu kanalı dinleyen kod parçasına herşey geliyor. Yani Wireshark'tan Ethernet + IP + TCP + Data almak gibi. Ancak kod parçamız sadece Data ile ilgileniyor. Dolayısıyla kodumuzun Composite içinde yürüyerek işlemek istediği düğümü bulması gerekiyor.

2.3 Parser'ın Okuduğu Kanal İle Kod Parçasına Kadar Olan Tasarım

2.3.1. Event Driven Processor
Bu seçenek şöyle
Poller -> Stream Buffer (Kanal)-> Parser -> Processor (Kod Parçası)
Burada karşımıza yine iki seçenek çıkıyor. Poller'a ayrı ayrı kanallar takmak veya tek bir kanal takıp kanalın ucunda Parser'lara göre ayrıştırmak.

Aralarında çok fark yok. Tek dikkat edilmesi gereken köprüyü yani kanalı kapatırken önce Poller ucunu daha sonra Processor ucunu kapatmak. Ya da tam tersi yeterki tutarlı olsun :)

2.3.1. Pulling Processor
Bu seçenek şöyle

Processor -> Channel'dan okur -> Parser'a verir ve çıktıyı işler.

Bu seçenek Processor sayısı fazla ile çok thread'e sebep olduğu için tercih edilmiyor.

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.