Πέρα από τις κανονικές εκφράσεις: Εισαγωγή στην ανάλυση γραμματικών χωρίς περιβάλλον

Ένα σημαντικό και χρήσιμο εργαλείο που είναι ήδη μέρος των οπλοστασίων των περισσότερων προγραμματιστών είναι η αξιόπιστη τακτική έκφραση . Αλλά πέρα ​​από αυτό βρίσκονται γραμματικές χωρίς πλαίσιο. Αυτή είναι μια απλή ιδέα με φανταχτερό όνομα.

Μια κανονική έκφραση είναι μια μέθοδος επικύρωσης και εύρεσης προτύπων σε κείμενο. Τα είδη των προτύπων (aka γραμματικά) που μπορεί να περιγραφεί και να ανιχνεύεται χρησιμοποιώντας μια κανονική έκφραση που ονομάζεται κανονικές γλώσσες . Οι κανονικές γλώσσες είναι οι απλούστερες επίσημες γλώσσες στην ιεραρχία του Chomsky .

Οι τακτικές εκφράσεις είναι ιδανικές για την εύρεση ή την επικύρωση πολλών τύπων απλών μοτίβων, για παράδειγμα αριθμούς τηλεφώνου, διευθύνσεις ηλεκτρονικού ταχυδρομείου και διευθύνσεις URL. Ωστόσο, υπολείπονται όταν εφαρμόζονται σε μοτίβα που μπορούν να έχουν αναδρομική δομή, όπως:

  • Ετικέτες ανοίγματος / κλεισίματος HTML / XML
  • άνοιγμα / κλείσιμο τιράντες {/} σε γλώσσες προγραμματισμού
  • άνοιγμα / κλείσιμο παρενθέσεων σε αριθμητικές εκφράσεις

Για να αναλύσουμε αυτά τα είδη μοτίβων, χρειαζόμαστε κάτι πιο ισχυρό. Μπορούμε να προχωρήσουμε στο επόμενο επίπεδο τυπικών γραμματικών που ονομάζονται γραμματικές χωρίς περιβάλλον (CFG).

Ανάλυση μαθηματικών εκφράσεων

Η ανάλυση του συνόλου όλων των μαθηματικών εκφράσεων είναι πέρα ​​από τη δύναμη μιας πραγματικής κανονικής έκφρασης. Ο λόγος είναι ότι αυτές μπορούν να περιέχουν αυθαίρετα βαθιά ένθετα ζεύγη παρενθέσεων.

Για παράδειγμα, εξετάστε την έκφραση: (2 + (3 * (7–4)))

Παρατηρήστε ότι η δομή της αριθμητικής έκφρασης είναι ουσιαστικά ένα δέντρο:

 + / \ 2 * / \ 3 - / \ 7 4

Η δομή του δέντρου που δημιουργείται ως αποτέλεσμα της εκτέλεσης ενός αναλυτή CFG ονομάζεται δέντρο ανάλυσης .

Περιγράφοντας γραμματικές χωρίς περιβάλλον

Υπάρχουν δύο δημοφιλείς μέθοδοι έκφρασης γραμματικών CFG:

  1. Extended Bachus-Naur Form (EBNF) - περιγράφει ένα CFG όσον αφορά τους κανόνες παραγωγής . Αυτοί είναι κανόνες που, όταν εφαρμόζονται, μπορούν να δημιουργήσουν όλες τις πιθανές νομικές φράσεις στη γλώσσα.
  2. Parsing Expression Grammar (PEG) - περιγράφει ένα CFG όσον αφορά τους κανόνες αναγνώρισης . Αυτοί είναι κανόνες που μπορούν να χρησιμοποιηθούν για την αντιστοίχιση έγκυρων φράσεων στη γλώσσα.

Ο φορμαλισμός PEG έχει το πλεονέκτημα έναντι του EBNF ότι η χαρτογράφηση σε έναν αναλυτή είναι ξεκάθαρη και μπορεί εύκολα να αυτοματοποιηθεί.

Το ακόλουθο είναι ένα απλό PEG που αφαιρείται από τη σελίδα της Wikipedia που περιγράφει μαθηματικούς τύπους που εφαρμόζουν τις βασικές τέσσερις λειτουργίες σε μη αρνητικές

ακέραιοι.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Στα απλά αγγλικά, μπορούμε να το διαβάσουμε ως:

  • Expr είναι ένα Sum
  • Sumείναι μια Productακολουθείται από μηδέν ή περισσότερες υπο-μοτίβα που αποτελούνται από ένα «+» ή «-» ακολουθούμενο από έναProduct
  • Productείναι μια Valueακολουθείται από μηδέν ή περισσότερες υπο-μοτίβα που αποτελούνται από ένα «*» ή «/» ακολουθούμενο από έναValue
  • Valueείναι είτε ένα ή περισσότερα μέλη του συνόλου χαρακτήρων {0, .. 9} ή είναι μια ανοιχτή παρένθεση "(" ακολουθούμενη από μια Exprπαρένθεση κλεισίματος ")".

Γεννήτριες ανάλυσης έναντι ανάλυσης βιβλιοθηκών

Υποθέτοντας ότι δεν είστε ο τύπος του ατόμου που του αρέσει να ανακαλύπτει ξανά τον τροχό (όχι ότι υπάρχει κάτι λάθος με αυτό), υπάρχουν γενικά δύο επιλογές για τη δημιουργία ενός προγράμματος ανάλυσης:

1. Χρησιμοποιήστε μια γεννήτρια parser - ένα εργαλείο που δημιουργεί τον πηγαίο κώδικα για έναν αναλυτή από έναν αφηρημένο ορισμό του parser. Μερικά δημοφιλή παραδείγματα σε JavaScript περιλαμβάνουν Jison, PEG.js, Nearley και ANTLR.

2. Χρησιμοποιήστε μια βιβλιοθήκη ανάλυσης - μια βιβλιοθήκη που επιτρέπει την έκφραση των κανόνων ανάλυσης ως API. Μερικά παραδείγματα στο JavaScript περιλαμβάνουν το Myna, το Parsimmon και το Chevrotain.

Η προτίμησή μου είναι να χρησιμοποιώ βιβλιοθήκες ανάλυσης, επειδή είναι πιο κατανοητές, εντοπισμένες σφαλμάτων, συντηρήσεις και προσαρμογές.

Γράφοντας αναλυτές σε TypeScript / JavaScript χρησιμοποιώντας το Myna Parsing Library

Πρόσφατα, ένα έργο στο οποίο δούλευα (η γλώσσα Heron) απαιτούσε μια βιβλιοθήκη ανάλυσης που θα μπορούσε να εκτελεστεί στο πρόγραμμα περιήγησης. Βρήκα την πολυπλοκότητα και τα γενικά έξοδα των υπαρχουσών βιβλιοθηκών πολύ μεγάλη. Δεδομένου ότι είχα προηγούμενη εμπειρία στη συγγραφή βιβλιοθηκών ανάλυσης σε C ++ και C #, αποφάσισα να γράψω μια βιβλιοθήκη ανάλυσης που ονομάζεται Myna χρησιμοποιώντας TypeScript.

Το Myna χρησιμοποιεί άπταιστη σύνταξη (μέθοδος αλυσίδας) για να διευκολύνει τον ορισμό ενός προγράμματος ανάλυσης ως σύνολο κανόνων (sub-parser) που μοιάζουν με μια γραμματική PEG.

Το ακόλουθο παράδειγμα είναι από το repo Myna GitHub:

Από δέντρο σύνταξης σκυροδέματος (CST) έως αφηρημένο δέντρο σύνταξης (AST)

Όταν ένας αναλυτής επεξεργάζεται την είσοδο, κάθε κανόνας που ταιριάζει με επιτυχία (γνωστή και ως παραγωγή γραμματικής) μπορεί να αντιστοιχιστεί σε έναν κόμβο στο δέντρο ανάλυσης. Αυτή η κυριολεκτική χαρτογράφηση των κανόνων παραγωγής σε κόμβους ενός δέντρου είναι ένα συγκεκριμένο δέντρο σύνταξης (CST).

Σε ορισμένες περιπτώσεις, το CST είναι περιορισμένης χρήσης, καθώς περιέχει πολλή συντακτική ακαταστασία, για παράδειγμα σχόλια στον πηγαίο κώδικα ή εάν μια κυριολεκτική συμβολοσειρά έχει διπλά εισαγωγικά ή με μοναδικά εισαγωγικά. Μπορεί να περιέχει αποτελέσματα από κανόνες που έχουν δημιουργηθεί για να κάνουν τη γραμματική ευκολότερη στη χρήση, αλλά δεν αντιπροσωπεύουν την επιδιωκόμενη δομή δέντρου για ανάλυση.

Το απλούστερο πράγμα που πρέπει να κάνετε είναι να δημιουργήσετε μόνο κόμβους στο δέντρο εξόδου για συγκεκριμένους κανόνες και να παραλείψετε άλλους κανόνες. Αυτή η απλοποιημένη έκδοση του δέντρου ανάλυσης ονομάζεται δέντρο σύνταξης αφηρημένων (AST) . Μπορεί να εκτελούνται πολλαπλά περάσματα σε ένα AST για να το μετατρέψουν σε εναλλακτικές αναπαραστάσεις AST, για να απλοποιηθούν τα μεταγενέστερα στάδια επεξεργασίας.

Στο Myna, δημιουργείται ένα AST δημιουργώντας κόμβους από κανόνες με την astιδιότητα. Τεχνικά, αυτή η ιδιότητα επιστρέφει έναν νέο κανόνα που έχει ένα εσωτερικό σύνολο ιδιοτήτων που λέει στον αναλυτή να δημιουργήσει έναν κόμβο ανάλυσης στο δέντρο ανάλυσης.

Χρησιμοποιώντας το δημιουργημένο δέντρο σύνταξης Myna abstract

Ακολουθεί ένα παράδειγμα χρήσης ενός αναλυτή που ορίζεται από το Myna στο "Node.JS" για την αξιολόγηση μιας αριθμητικής έκφρασης:

Τελικές λέξεις

Εάν ενδιαφέρεστε να μάθετε περισσότερα σχετικά με τη δημιουργία και τη χρήση προγραμμάτων ανάλυσης, ανεξάρτητα από το αν η βιβλιοθήκη Myna ανταποκρίνεται στις συγκεκριμένες ανάγκες σας, σας προτείνω να αφιερώσετε λίγο χρόνο για να διαβάσετε τον πηγαίο κώδικα της βιβλιοθήκης ανάλυσης Myna.

Το Myna γράφτηκε σε TypeScript (η οποία έχει μια γνωστή σύνταξη για τους περισσότερους προγραμματιστές), περιέχεται σε ένα μόνο αρχείο χωρίς εξαρτήσεις και είναι μικρότερη από 1200 γραμμές συμπεριλαμβανομένης της λεπτομερούς τεκμηρίωσης.

Εάν ενδιαφέρεστε να δείτε το Myna να εφαρμόζεται σε ένα πιο περίπλοκο σενάριο, ρίξτε μια ματιά στη γλώσσα προγραμματισμού Chickadee. Αυτό εφαρμόζεται εξ ολοκλήρου σε TypeScript και εξαρτάται μόνο από τη βιβλιοθήκη ανάλυσης Myna. Το Chickadee είναι μια μικρή γλώσσα προγραμματισμού που έχει σχεδιαστεί ειδικά για να βοηθήσει τους ανθρώπους να μάθουν για τις τεχνικές εφαρμογής των γλωσσών προγραμματισμού.

Εάν σας άρεσε αυτό το άρθρο, ενημερώστε με και σκεφτείτε το να το μοιραστείτε με τους φίλους και τους συναδέλφους σας.