Μελέτη και βελτίωση της επίδοσης του συντακτικού αναλυτή Packrat

Abstract

Πρακτικά όλες οι γλώσσες, είτε φυσικές είτε γλώσσες μηχανής, βασίζονται στην έκφραση της πληροφορίας με γραμμικό τρόπο. Συνήθως η αναπαράσταση γίνεται με τη μορφή μίας συμβολοσειράς, που είναι μια ακολουθία χαρακτήρων από ένα τυποποιημένο σύνολο. Οποιαδήποτε εφαρμογή επεξεργασίας γλώσσας πρέπει να μετατρέψει τις συμβολοσειρές σε πιο αφηρημένες δομές όπως λέξεις, φράσεις, προτάσεις, εκφράσεις ή εντολές. Συντακτική ανάλυση (parsing) είναι η διαδικασία που εξάγει χρήσιμη δομημένη πληροφορία από γραμμικό κείμενο. Το packrat parsing είναι μία τεχνική συντακτικής ανάλυσης που βασίζεται στις parsing expression grammars (PEGs), μία παραλλαγή των γραμματικών χωρίς συμφραζόμενα. Ένας packrat parser παρέχει την ισχύ και την απλότητα των καθοδικών συντακτικών αναλυτών, ωστόσο εγγυάται γραμμικό χρόνο εκτέλεσης. Οποιαδήποτε γλώσσα που ορίζεται από μία LL(k) ή LR(k) γραμματική μπορεί να αναγνωριστεί από έναν packrat parser, καθώς και πολλές άλλες γλώσσες που οι συμβατικοί αλγόριθμοι γραμμικού χρόνου δεν υποστηρίζουν. Σκοπός της παρούσας εργασίας είναι αφενός η υλοποίηση ενός συντακτικού αναλυτή packrat στη κλασική του μορφή, αφετέρου η βελτίωση της επίδοσής του είτε τροποποιώντας τον αρχικό αλγόριθμο, είτε παραλληλοποιώντας τον ώστε να τρέξει αποδοτικότερα σε ένα πολυπύρηνο σύστημα.