Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2024-01-23
Συγγραφέας:
ΚΩΝΣΤΑΝΤΙΝΙΔΗΣ ΔΗΜΗΤΡΙΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Ροντογιάννης Παναγιώτης, Καθηγητής, Τμήμα Πληροφορικής & Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Χαραλαμπίδης Άγγελος, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής & Τηλεματικής, Χαροκόπειο Πανεπιστήμιο
Πρωτότυπος Τίτλος:
Transforming Boolean grammars to Datalog
Γλώσσες εργασίας:
Αγγλικά
Ελληνικά
Μεταφρασμένος τίτλος:
Μετατροπή Boolean γραμματικών σε Datalog
Περίληψη:
Οι γραμματικές χωρίς συμφραζόμενα (CFGs) αποτελούν σημαντικό πεδίο στην πληρο-
φορική και η χρήση τους, ειδικά σε μεταγλωττιστές, αποτελεί ακρογωνιαίο λίθο των τε-
χνολογιών πληροφορίας. Αντίθετα, ο λογικός προγραμματισμός, λαμβάνοντας υπόψη την
ισοδυναμία του με οποιαδήποτε γλώσσα προγραμματισμού, είναι ένας υποτιμημένος και
γενικά υποεκπροσωπούμενος τομέας προγραμματισμού. Οι γραμματικές και ο λογικός
προγραμματισμός είναι δύο πολύ διαφορετικές κατασκευές, όμως, φαίνονται όμοιες στο
συντακτικό τους. Στον επιστημονικό κόσμο, έχει εισαχθεί μια μετατροπή των CFGs σε
ένα λογικό πρόγραμμα, η οποία εξετάζει την περίπλοκη σχέση μεταξύ αυτών των δύο.
Οι επεκτάσεις των CFGs που προτείνονται από τον Okhotin, οι συζευκτικές γραμματικές
που προσθέτουν την πράξη της σύζευξης στις CFGs και οι γραμματικές Boolean που
επεκτείνουν τις συζευκτικές γραμματικές με την πράξη της άρνησης, είναι ένα σημαντικό
βήμα στην θεωρία τυπικών γλωσσών. Σε αυτή τη πτυχιακή, προτείνεται μια επέκταση της
προαναφερθείσας μετατροπής ώστε να χειρίζεται συζευκτικές και Boolean γραμματικές.
Εισάγεται ένας σαφής μαθηματικός ορισμός της μετατροπής, ο οποίος υλοποιείται μέσω
ενός απλού CFG parser που παράγει ένα Αφηρημένο Συντακτικό Δέντρο. Στους κόμβους
του δέντρου που αντιστοιχούν σε κανόνες γραμματικής, εφαρμόζεται η μετατροπή και πα-
ράγεται ένας κανόνας Datalog. Το τελικό προϊόν είναι ένα πρόγραμμα Datalog που πιθα-
νώς περιέχει άρνηση. Για το λόγο αυτό, η καλώς θεμελιωμένη σημασιολογία για την άρ-
νηση χρησιμοποιούνται για να προσδιοριστεί, εν τέλει, η ύπαρξη μιας συμβολοσειράς στη
γλώσσα που δημιουργήθηκε από την παρεχόμενη γραμματική. Η μετατροπή που προτεί-
νουμε ενισχύει τη γεφύρωση μεταξύ γραμματικών και λογικού προγραμματισμού και είναι
μια ενδιαφέρουσα επέκταση που ενισχύει τη διαίσθησή μας για τις ομοιότητες αυτών των
δύο κόσμων.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
Γραμματικές χωρίς συμφραζόμενα, Συζευκτικές γραμματικές, Boolean γραμματικές, Datalog
Αρ. σελίδων ευρετηρίου:
2
Αρ. βιβλιογραφικών αναφορών:
15
