Αυτόματα στοίβας και γραμματικές

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Αυτόματα στοίβας

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

Τα αυτόματα στοίβας (ΑΣ) ορίζονται από την εξάδα Μ = (Κ, Σ, Γ, δ, q0, Z0)

K
Πεπερασμένο σύνολο καταστάσεων
Σ
Αλφάβητο εισόδου
Γ
Αλφάβητο για τη στοίβα
δ
Σύνολο κινήσεων που εκτελεί το αυτόματο
q0
Αρχική κατάσταση
Ζ0
Αρχική σύμβολο της στοίβας

Κάθε εντολή του ΑΣ ονομάζεται κίνηση (move). Η κίνηση ορίζεται από:

Όταν σε κάθε τριάδα αντιστοιχεί μια το πολύ κίνηση τότε το αυτόματο λέγεται ντετερμινιστικό αυτόματο στοίβας (ΝΑΣ) (deterministic stack automaton (DSA)). Αντίθετα, αν για κάποιες τιμές της δ υπάρχουν πολλές πιθανές κινήσεις τότε το αυτόματο καλείται μη ντετερμινιστικό αυτόματο στοίβας (ΜΑΣ) (non-deterministic stack automaton (NSA)). (Οι λέξη ντετερμινιστικό που εμφανίζεται στην ελληνική βιβλιογραφία είναι συνώνυμη με τη λέξη αιτιοκρατικό).

Η λειτουργία του ΑΣ ορίζεται από τρεις υποεντολές που εκτελούνται διαδοχικά:

  1. την υποεντολή της στοίβας
  2. την υποεντολή εισόδου
  3. την υποεντολή επόμενης κατάστασης
Οι εντολές μπορούν να εκτελέσουν τις παρακάτω λειτουργίες:

Παράσταση κινήσεων

Κάθε εντολή κίνησης έχει τη μορφή: δ(σ1, σ2, σ3) = (Σ1, Σ2, Σ3) όπου:
σ1
η κατάσταση του ΑΣ,
σ2
το σύμβολο στην κορυφή της στοίβας,
σ3
το σύμβολο εισόδου,
Σ1
η υποεντολή της στοίβας,
Σ2
η υποεντολή εισόδου,
Σ3
η υποεντολή επόμενης κατάστασης.
Αν δεν προσδιορίζεται μια εντολή τότε αυτή υπονοείται ως εξής:

Λειτουργία

Αν ένα ΑΣ τότε θεωρούμε πως το ΑΣ αναγνώρισε τη συμβολοσειρά εισόδου.

Ένα ΜΑΣ όταν φτάσει σε στάδιο που δεν ορίζεται κίνηση οπισθοδρομεί μέχρι ένα στάδιο που να μπορέσει να εκτελέσει μια εναλλακτική κίνηση.

Παράδειγμα

Ορίζουμε ένα αυτόματο Μ = (Κ, Σ, Γ, δ, q0, Z0) ως εξής:
Κ
{Α}
Σ
{'(', ')'}
Γ
{Χ, I}
Δ
{ }
q0
A
Z0
X

Το αυτόματο αυτό αναγνωρίζει ζυγισμένα ζευγάρια παρενθέσεων.

Γραμματική

Τη σύνταξη των γλωσσών την ορίζουμε με γραμματικές.

Μια γραμματική ορίζεται από την τετράδα: G = (VN, VT, P, S):

VN
αλφάβητο με τα μη τερματικά σύμβολα (non-terminal symbols).
VT
αλφάβητο με τα τερματικά σύμβολα (terminal symbols).
P
συντακτικοί κανόνες (syntax rules) που αποτελούνται από ζευγάρια (α, β) που συμβολίζονται α -> β. Το α αποτελείται από ένα σύμβολο ενώ το β από μια ακολουθία συμβόλων.
S
Το αρχικό μη τερματικό σύμβολο εκκίνησης.

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

Παράδειγμα

G = (VN, VT, P, S):
VN
{SUM, PROD, NUM}
VT
{0, 1, +, *}
P
{ }
S
SUM

Συντακτικό δένδρο

Παράδειγμα

                SUM
            PROD + 0
           1 * 0

Ιεραρχία γραμματικών

Ανάλογα με τους συντακτικούς κανόνες που περιέχει μια γραμματική ορίζεται η ιεραρχία γραμματικών του Chomsky
Τύπου 0: ελεύθερη
με κανόνες της μορφής σ->τ όπου:
Τύπου 1: γραμματική με συμφραζόμενα (context sensitive grammar)
με κανόνες της μορφής μΑν->μχν όπου:
Τύπου 2: γραμματική χωρίς συμφραζόμενα (context free grammar)
με κανόνες της μορφής Α->χ όπου: Οι γραμματικές αυτές μπορούν να ορίσουν συχνά τη σύνταξη μιας γλώσσας.
Τύπου 3: κανονική γραμματική (regular grammar)
με κανόνες της μορφής Α->α ή Α->αΒ όπου: Οι γραμματικές αυτές μπορούν να ορίσουν συχνά τα λεκτικά στοιχεία μιας γλώσσας.

Συμβολισμός EBNF

Ο συμβολισμός EBNF (Extended Backus-Naur Form) μας επιτρέπει να ορίσουμε με περιεκτικό τρόπο μια γραμματική:

Παράδειγμα

expr	::= term ('+' term |'-' term) *
term	::= factor ('*' factor |'/' factor) *
factor	::= digit | '-' factor | '(' expr ')' 
digit	::= '0' | '1' | '2' | '3' |'4' | '5' | '6' | '7' | '8' | '9'

Ασκήσεις

  1. Να ορίσετε σε EBNF τη σύνταξη του ορισμού δομών (structure) της C.

Βιβλιογραφία