Parçalama Ağacı (Parse Tree)

Yazan : Şadi Evren ŞEKER

Parçalam işlemi  (parsing) bilgisayar bilimlerinde çeşitli amaçlar için kullanılmaktadır. Özellikle de dil ile ilgili işlemlerin hemen hepsinde ihtiyaç duyulan bir işlemdir. Örneğin bir programlama dilinde yazılan komutların algılanması için öncelikle kelimeleirn parçalanması (parse) gerekir. Benzer şekilde dopal dil işleme (natural language processing) işlemlerinde de doğal dilde bulunan kelimelerin algılanması bir parçalamadan (ek ve köklerin ayrılmasından) sonra gerçekleşmektedir.

Çeşitli sebeplerle kullanılan parçalama ağaçları basitçe verilen bir dilbilgisine (grammer) göre verilen cümlenin (veya kelimenin) nasıl parçalandığını şekilsel olarak gösteren ağaçlardır:

Örneğin aşağıda BNF yapısında verilmiş dili ele alalım:

<dil>::=<işlem>

<işlem> ::= <işlem> + <terim> | <işlem> – <terim> | <terim>

<terim> ::= <terim> * <unsur> | <terim> / <unsur> | <unsur>

<unsur> ::= sayı | ( <işlem> )

<sayı> ::= 1|2|3…|9|0

Bu dilde aşağıdaki örneğin nasıl parçalandığını inceleyelim:

4+8*(2-3)

Bu dilde tanımlı olan yukarıdaki işlemin parçalama ağacı aşağıdaki şekildedir:

yukarıdaki şekilde devamlı (nonterminal) terimlerden sonuncu (terminal) terimlere kadar bir BNF dilinin nasıl açıldığı gösterilmiştir.