An Investigation of the common structure underlying the correctness and completeness proofs of parsing algorithms

Abstract

VI ÖZET SÖZ DİZİMSEL İNCELEME YÖNTEMLERİNİN DOĞRULUK İSPATLERININ ORTAK YAPISI ÜZERİNE KARŞILAŞTIRMALI ÖN ARAŞTIRMA Söz dizimsel inceleme yöntemleri, belli bir gramer ve belli bir kelime için, bu kelimenin verilen gramerden türetilip türetilemiyeceğine karar veren araçlardır. Başka bir deyişle, bu kelimenin verilen gramerin oluşturduğu dile ait olup olmadığına karar verirler. Bunun için, hangi söz dizimsel inceleme yöntemi kullanılırsa kullanılsın, hepsinin de sağlaması gereken önemli bir özellik vardır: doğruluk özelliği. Bütün söz dizimsel inceleme yöntemleri aynı amacı güttüğüne göre (verilen kelimenin dile ait olup olmadığına karar vermek), ve bu amacı yerine getirmek için hepsi de aynı gramer, aynı dil ile uğraştığına göre, doğruluk ispatlarının benzer olabileceğini düşündük. Bu yüksek lisans tez çalışmasının ana konusu böyle bir benzerliğin olup olmadığını araştırmak. Bunun için üç ayrı söz dizimsel inceleme yöntemini ele aldık, ve bunların doğruluk ispatlarını tekrar baştan yaparak, karşılaştırdık. Böylece, gerçekten benzerlik olup olmadığını tespit etmeye çalıştık Bulmuş olduğumuz benzerlikler bize tüm söz dizimsel inceleme yöntemine ortak genel bir doğruluk ispatı yapısı olabileceğine dair kuvvetli ip uçları vermektedir.

ABSTRACT AN INVESTIGATION OF THE COMMON STRUCTURE UNDERLYING THE CORRECTNESS AND COMPLETENESS PROOFS OF PARSING ALGORITHMS Parsing algorithms are methods that permit, given a string and a grammar, to decide if this string is obtainable from the grammar. Whatever the method, all parsing algorithms have to satisfy two properties: soundness and completeness. It seems natural to think that since all parsing algorithms are dealing with the same entities (grammar, language, recognizer...), with the same aim (to see if the given string is in the language), their correctness proofs should be similar. The work done in this MS thesis is a comparative analysis on three parsing algorithms. In order to see if really there exist similarities among the correctness proofs of different parsing algorithms, we tried to rewrite those proofs for the analyzed algorithms, in a homogeneous manner. The similarities found among the correctness proofs make us think that there is a generic proof architecture lying under all correctness proofs of all context free grammar architecture.