Αλγοριθμοι Συντακτικης Αναγνωρισης

Abstract

Ο σκοπός της εν λόγω διπλωματικής εργασίας είναι η υλοποίηση τριών αλγορίθμων συντακτικής ανάλυσης για γλώσσες οι οποίες δύναται να περιγραφούν από γραμματικές χωρίς συμφραζόμενα (Context-Free Grammars). Οι παρακάτω αλγόριθμοι που υλοποιήθηκαν είναι οι ταχύτεροι που αναφέρονται στην βιβλιογραφία και σχετίζονται άμεσα, αφού στην πραγματικότητα οι δύο τελευταίοι αποτελούν την σταδιακή βελτίωση του πρώτου.1. Αλγόριθμος Earley (Jay Earley) [B.3],2. Αλγόριθμος Graham (Susan L. Graham, Michael A. Harrison, Walter L Ruzzo) [B.4],3. Αλγόριθμος Fu - Chiang (K. S. Fu, Y. T. Chiang) [B.5].Επιπλέον, επιχειρήθηκε μία αξιολόγηση και σύγκριση των τριών υλοποιήσεων. Στις τρεις υλοποιήσεις εφαρμόστηκαν τρεις διαφορετικές γραμματικές χωρίς συμφραζόμενα και μελετήθηκε η απόδοση των αλγορίθμων για διάφορα μεγέθη συμβολοσειράς εισόδου. Οι αλγόριθμοι υλοποιήθηκαν σε A.N.S.I. C++, ενώ για την περίπτωση του αλγορίθμου των Chiang & Fu χρησιμοποιήθηκε και η βιβλιοθήκη MPI για παράλληλη επεξεργασία, καθώς η υλοποίηση εφαρμόστηκε σε Linux cluster υπολογιστών.