Ανάλυση σύνταξης: Τύποι ανάλυσης μεταγλωττιστή από πάνω προς τα κάτω και από κάτω προς τα πάνω

Η ανάλυση σύνταξης στη διαδικασία σχεδίασης μεταγλωττιστή έρχεται μετά τη φάση της Λεξικής ανάλυσης. Είναι επίσης γνωστό ως Δέντρο ανάλυσης ή Συντακτικό δέντρο. Το Parse Tree αναπτύσσεται με τη βοήθεια προκαθορισμένης γραμματικής της γλώσσας. Ο αναλυτής σύνταξης ελέγχει επίσης εάν ένα δεδομένο πρόγραμμα πληροί τους κανόνες που υπονοούνται από μια γραμματική χωρίς πλαίσιο. Εάν ικανοποιεί, τότε ο αναλυτής δημιουργεί το δέντρο ανάλυσης αυτού του προγράμματος πηγής. Διαφορετικά, θα εμφανίσει μηνύματα σφάλματος.

Γιατί χρειάζεστε το Syntax Analyser;

• Ελέγξτε αν ο κώδικας είναι γραμματικός έγκυρος
• Ο συντακτικός αναλυτής σάς βοηθά να εφαρμόσετε κανόνες στον κώδικα
• Σας βοηθά να βεβαιωθείτε ότι κάθε ανοιγόμενο στήριγμα έχει την αντίστοιχη ισορροπία κλεισίματος
• Κάθε δήλωση έχει έναν τύπο και ότι ο τύπος πρέπει να υπάρχει

Σημαντική ορολογία του αναλυτή σύνταξης

Σημαντικές ορολογίες που χρησιμοποιούνται στη διαδικασία ανάλυσης σύνταξης:

• Πρόταση: Μια πρόταση είναι μια ομάδα χαρακτήρων πάνω από κάποιο αλφάβητο.

• Λεξικό: Ένα λεξικό είναι η συντακτική μονάδα κατώτερου επιπέδου μιας γλώσσας (π.χ. σύνολο, αρχή).

• Διακριτικό: Το token είναι απλώς μια κατηγορία λεξημάτων.

• Λέξεις-κλειδιά και δεσμευμένες λέξεις – Είναι ένα αναγνωριστικό που χρησιμοποιείται ως σταθερό μέρος της σύνταξης μιας δήλωσης. Είναι μια δεσμευμένη λέξη που δεν μπορείτε να χρησιμοποιήσετε ως όνομα ή αναγνωριστικό μεταβλητής.

• Θόρυβος λέξεις – Οι λέξεις θορύβου είναι προαιρετικές οι οποίες εισάγονται σε μια δήλωση για να βελτιώσουν την αναγνωσιμότητα της πρότασης.

• Σχόλια – Είναι πολύ σημαντικό μέρος της τεκμηρίωσης. Εμφανίζεται κυρίως με, /* */, ή//Κενό (κενά)

• Διαχωριστές – Είναι ένα συντακτικό στοιχείο που σηματοδοτεί την αρχή ή το τέλος κάποιας συντακτικής ενότητας. Όπως μια δήλωση ή έκφραση, "αρχή"…"τέλος" ή {}.

• Σετ χαρακτήρα – ASCII, Unicode

• Αναγνωριστικά – Είναι ένας περιορισμός στο μήκος που σας βοηθά να μειώσετε την αναγνωσιμότητα της πρότασης.

• Operaσύμβολα tor – + και – εκτελεί δύο βασικές αριθμητικές πράξεις.
• Συντακτικά στοιχεία της Γλώσσας

Γιατί χρειαζόμαστε την ανάλυση;

Μια ανάλυση ελέγχει επίσης ότι η συμβολοσειρά εισόδου είναι καλοσχηματισμένη και, αν όχι, την απορρίπτει.

Ακολουθούν σημαντικές εργασίες που εκτελεί ο αναλυτής στο σχεδιασμό του μεταγλωττιστή:

• Σας βοηθά να εντοπίσετε όλους τους τύπους συντακτικών σφαλμάτων
• Βρείτε τη θέση στην οποία προέκυψε το σφάλμα
• Σαφής και ακριβής περιγραφή του σφάλματος.
• Συνεχίστε την ανάκτηση από σφάλμα και βρείτε περαιτέρω σφάλματα στον κώδικα.
• Δεν πρέπει να επηρεάζει τη μεταγλώττιση των «σωστών» προγραμμάτων.
• Η ανάλυση πρέπει να απορρίψει μη έγκυρα κείμενα αναφέροντας συντακτικά σφάλματα

Τεχνικές ανάλυσης

Οι τεχνικές ανάλυσης χωρίζονται σε δύο διαφορετικές ομάδες:

• Ανάλυση από πάνω προς τα κάτω,
• Ανάλυση από κάτω προς τα πάνω

Ανάλυση από πάνω προς τα κάτω

Στην ανάλυση από πάνω προς τα κάτω, η κατασκευή του δέντρου ανάλυσης ξεκινά από τη ρίζα και στη συνέχεια προχωρά προς τα φύλλα.

Δύο τύποι ανάλυσης από πάνω προς τα κάτω είναι:

1. Προγνωστική ανάλυση:

Η προγνωστική ανάλυση μπορεί να προβλέψει ποια παραγωγή θα πρέπει να χρησιμοποιηθεί για να αντικαταστήσει τη συγκεκριμένη συμβολοσειρά εισόδου. Ο προγνωστικός αναλυτής χρησιμοποιεί σημείο πρόβλεψης, το οποίο δείχνει προς τα επόμενα σύμβολα εισόδου. ΠίσωtracΟ king δεν αποτελεί πρόβλημα με αυτήν την τεχνική ανάλυσης. Είναι γνωστή ως LL(1) Parser

2. Αναδρομική ανάλυση καθόδου:

Αυτή η τεχνική ανάλυσης αναλύει αναδρομικά την είσοδο για να δημιουργήσει ένα δέντρο prase. Αποτελείται από πολλές μικρές συναρτήσεις, μία για κάθε μη τερματικό στη γραμματική.

Ανάλυση από κάτω προς τα πάνω

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

Σφάλμα – Μέθοδοι ανάκτησης

Συνήθη σφάλματα που παρουσιάζονται κατά την ανάλυση στο λογισμικό συστήματος

• Λεξιλογικός: Όνομα ενός λανθασμένα πληκτρολογημένου αναγνωριστικού
• Συντακτικό: μη ισορροπημένη παρένθεση ή λείπει ερωτηματικό
• Σημασιολογικό: ασύμβατη εκχώρηση τιμής
• λογικός: Απεριόριστος βρόχος και μη προσβάσιμος κωδικός

Ένας αναλυτής θα πρέπει να είναι σε θέση να ανιχνεύει και να αναφέρει οποιοδήποτε σφάλμα εντοπίστηκε στο πρόγραμμα. Έτσι, όποτε παρουσιαζόταν σφάλμα ο αναλυτής. Θα πρέπει να μπορεί να το χειριστεί και να συνεχίσει να αναλύει την υπόλοιπη είσοδο. Ένα πρόγραμμα μπορεί να έχει τους ακόλουθους τύπους σφαλμάτων σε διάφορα στάδια της διαδικασίας μεταγλώττισης. Υπάρχουν πέντε κοινές μέθοδοι ανάκτησης σφαλμάτων που μπορούν να εφαρμοστούν στον αναλυτή

Ανάκτηση κατάστασης κατάστασης

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

Ανάκτηση σε λειτουργία πανικού

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

Ανάκτηση σε επίπεδο φράσης

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

Παραγωγές σφαλμάτων

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

Παγκόσμια Διόρθωση

• Ο μεταγλωττιστής θα πρέπει να κάνει όσο το δυνατόν λιγότερο αριθμό αλλαγών κατά την επεξεργασία μιας λανθασμένης συμβολοσειράς εισόδου. Δεδομένης της λανθασμένης συμβολοσειράς εισαγωγής a και της γραμματικής c, οι αλγόριθμοι θα αναζητήσουν ένα δέντρο ανάλυσης για μια σχετική συμβολοσειρά b. Όπως ορισμένες εισαγωγές, διαγραφές και τροποποιήσεις που απαιτούνται για τη μετατροπή του α σε b είναι όσο το δυνατόν λιγότερες.

Γραμματική

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

Κανόνες Γραμματικής Μορφής

• Το μη τερματικό σύμβολο πρέπει να εμφανίζεται στα αριστερά της τουλάχιστον μιας παραγωγής
• Το σύμβολο στόχου δεν πρέπει ποτέ να εμφανίζεται στα δεξιά του::= οποιασδήποτε παραγωγής
• Ένας κανόνας είναι αναδρομικός εάν το LHS εμφανίζεται στο RHS του

Σημειογραφικές Συμβάσεις

Το σύμβολο συμβολικών συμβάσεων μπορεί να υποδεικνύεται κλείνοντας το στοιχείο σε αγκύλες. Είναι μια αυθαίρετη ακολουθία περιπτώσεων του στοιχείου που μπορεί να υποδειχθεί περικλείοντας το στοιχείο σε αγκύλες ακολουθούμενες από ένα σύμβολο αστερίσκου, { … }*.

Είναι μια επιλογή της εναλλακτικής που μπορεί να χρησιμοποιήσει το σύμβολο εντός του ενιαίου κανόνα. Μπορεί να περικλείεται με παρένθεση ([,] ) όταν χρειάζεται.

Δύο τύποι συμβολαιογραφικών συμβάσεων περιοχής Τερματικό και μη τερματικά

1.Τερματικά:

• Μικρά γράμματα στο αλφάβητο όπως a, b, c,
• Operaσύμβολα tor όπως +,-, *, κ.λπ.
• Σύμβολα στίξης όπως παρενθέσεις, κατακερματισμός, κόμμα
• 0, 1, …, 9 ψηφία
• Συμβολοσειρές με έντονους χαρακτήρες όπως id ή if, οτιδήποτε αντιπροσωπεύει ένα μόνο τερματικό σύμβολο

2.Μη τερματικά:

• Κεφάλαια γράμματα όπως Α, Β, Γ
• Πλάγια ονόματα με πεζά γράμματα: η έκφραση ή μερικά

Ελεύθερη γραμματική περιβάλλοντος

Μια CFG είναι μια αριστερή αναδρομική γραμματική που έχει τουλάχιστον μία παραγωγή του τύπου. Οι κανόνες σε μια γραμματική χωρίς συμφραζόμενα είναι κυρίως αναδρομικοί. Ένας αναλυτής σύνταξης ελέγχει εάν το συγκεκριμένο πρόγραμμα ικανοποιεί όλους τους κανόνες της γραμματικής χωρίς πλαίσιο ή όχι. Εάν πληροί, αυτοί οι αναλυτές σύνταξης κανόνων μπορούν να δημιουργήσουν ένα δέντρο ανάλυσης για αυτό το πρόγραμμα.

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

Γραμματική Παραγωγή

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

Αριστερά Παραγωγή

Όταν η προτασιακή μορφή εισαγωγής σαρώνεται και αντικαθίσταται με τη σειρά από αριστερά προς τα δεξιά, είναι γνωστή ως παράγωγο προς τα αριστερά. Η προτατική μορφή που παράγεται από την πιο αριστερή παράγωγο ονομάζεται αριστερός-πρόταση.

Σωστός-πιο σωστή Παραγωγή

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

Σύνταξη εναντίον Λεξιλογικού Αναλυτή

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

Μειονεκτήματα της χρήσης Αναλυτών Σύνταξης

• Δεν θα καθορίσει ποτέ εάν ένα διακριτικό είναι έγκυρο ή όχι
• Το Not σάς βοηθά να προσδιορίσετε εάν μια λειτουργία που εκτελείται σε έναν τύπο διακριτικού είναι έγκυρη ή όχι
• Δεν μπορείτε να αποφασίσετε ότι το διακριτικό δηλώνεται και αρχικοποιείται πριν χρησιμοποιηθεί

Περίληψη

• Η συντακτική ανάλυση είναι μια δεύτερη φάση της διαδικασίας σχεδιασμού του μεταγλωττιστή που έρχεται μετά τη λεξιλογική ανάλυση
• Ο συντακτικός αναλυτής σάς βοηθά να εφαρμόσετε κανόνες στον κώδικα
• Πρόταση, Lexeme, Token, Λέξεις-κλειδιά και δεσμευμένες λέξεις, Λέξεις θορύβου, Σχόλια, Οριοθέτες, Σύνολο χαρακτήρων, Αναγνωριστικά είναι μερικοί σημαντικοί όροι που χρησιμοποιούνται στην ανάλυση σύνταξης στην κατασκευή μεταγλωττιστή
• Η ανάλυση ελέγχει ότι η συμβολοσειρά εισόδου είναι καλοσχηματισμένη και, αν όχι, απορρίψτε την
• Οι τεχνικές ανάλυσης χωρίζονται σε δύο διαφορετικές ομάδες: Ανάλυση από πάνω-κάτω, ανάλυση από κάτω-πάνω
• Λεξικά, συντακτικά, σημασιολογικά και λογικά είναι μερικά κοινά σφάλματα που εμφανίζονται κατά τη μέθοδο ανάλυσης
• Η γραμματική είναι ένα σύνολο δομικών κανόνων που περιγράφουν μια γλώσσα
• Το σύμβολο συμβολικών συμβάσεων μπορεί να υποδεικνύεται κλείνοντας το στοιχείο σε αγκύλες
• Μια CFG είναι μια αριστερή αναδρομική γραμματική που έχει τουλάχιστον μία παραγωγή του τύπου
• Η παράγωγη γραμματικής είναι μια ακολουθία γραμματικών κανόνων που μετατρέπει το σύμβολο έναρξης σε συμβολοσειρά
• Ο αναλυτής σύνταξης ασχολείται κυρίως με αναδρομικές κατασκευές της γλώσσας, ενώ ο λεξικός αναλυτής διευκολύνει το έργο του αναλυτή σύνταξης σε DBMS
• Το μειονέκτημα της μεθόδου συντακτικού αναλυτή είναι ότι ποτέ δεν θα καθορίσει εάν ένα διακριτικό είναι έγκυρο ή όχι