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

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

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

K

Πεπερασμένο σύνολο καταστάσεων

Σ

Αλφάβητο εισόδου

Γ

Αλφάβητο για τη στοίβα

δ

Σύνολο κινήσεων που εκτελεί το αυτόματο

q₀

Αρχική κατάσταση

Ζ₀

Αρχική σύμβολο της στοίβας

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

• την κατάσταση του ΑΣ,
• το σύμβολο στην κορυφή της στοίβας,
• το σύμβολο εισόδου.

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

1. την υποεντολή της στοίβας
2. την υποεντολή εισόδου
3. την υποεντολή επόμενης κατάστασης

• υποεντολή της στοίβας

  ΒΑΛΕ(χ)

  το χ προστίθεται στη στοίβα

  ΒΓΑΛΕ

  ένα στοιχείο αφαιρείται από τη στοίβα

  ΑΦΗΣΕ

  η στοίβα δε μεταβάλλεται

• υποεντολή εισόδου

  ΠΡΟΧΩΡΑ

  διάβασε ένα νέο στοιχείο από την είσοδο

  ΚΡΑΤΑ

  κράτα το υπάρχον στοιχείο εισόδου

• υποεντολή επόμενης κατάστασης

  ΚΑΤΑΣΤΑΣΗ(S)

  η νέα κατάσταση είναι η S

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

σ1

η κατάσταση του ΑΣ,

σ2

το σύμβολο στην κορυφή της στοίβας,

σ3

το σύμβολο εισόδου,

Σ1

η υποεντολή της στοίβας,

Σ2

η υποεντολή εισόδου,

Σ3

η υποεντολή επόμενης κατάστασης.

• υποεντολή της στοίβας:

  ΑΦΗΣΕ

  η στοίβα δε μεταβάλλεται

• υποεντολή εισόδου:

  ΠΡΟΧΩΡΑ

  διάβασε ένα νέο στοιχείο από την είσοδο

• υποεντολή επόμενης κατάστασης:

  ΚΑΤΑΣΤΑΣΗ(S)

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

Λειτουργία

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

• διαβάσει όλα τα σύμβολα εισόδου και
• η στοίβα περιέχει μόνο το αρχικό της σύμβολο

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

Παράδειγμα

Κ

{Α}

Σ

{'(', ')'}

Γ

{Χ, I}

Δ

{

• δ(Α, Ι, '(') = (ΒΑΛΕ(Ι))
• δ(Α, Χ, '(') = (ΒΑΛΕ(Ι))
• δ(Α, Ι, ')') = (ΒΓΑΛΕ)

}

q₀

A

Z₀

X

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

Γραμματική

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

V_N

αλφάβητο με τα μη τερματικά σύμβολα (non-terminal symbols).

V_T

αλφάβητο με τα τερματικά σύμβολα (terminal symbols).

P

συντακτικοί κανόνες (syntax rules) που αποτελούνται από ζευγάρια (α, β) που συμβολίζονται α -> β. Το α αποτελείται από ένα σύμβολο ενώ το β από μια ακολουθία συμβόλων.

S

Το αρχικό μη τερματικό σύμβολο εκκίνησης.

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

Παράδειγμα

V_N

{SUM, PROD, NUM}

V_T

{0, 1, +, *}

P

{

• NUM ->1,
• NUM ->0,
• SUM -> SUM + PROD
• SUM -> PROD
• PROD -> PROD * NUM
• PROD -> NUM

}

S

SUM

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

• Μια παραγωγή μπορεί να παρασταθεί από ένα συντακτικό δένδρο (syntax tree).
• Η κορυφή του δένδρου είναι το αρχικό σύμβολο.
• Τα φύλλα του δένδρου περιέχουν τα τερματικά σύμβολα της συμβολοσειράς.
• Οι εσωτερικοί κόμβοι του δένδρου αντιστοιχούν στους κανόνες της γραμματικής.
• Ο πατέρας κάθε κόμβου αποτελεί το δεξί μέρος του κανόνα.

Παράδειγμα

                SUM
            PROD + 0
           1 * 0

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

Τύπου 0: ελεύθερη

με κανόνες της μορφής σ->τ όπου:

• σ ανήκει V⁺
• τ ανήκει V^*

Τύπου 1: γραμματική με συμφραζόμενα (context sensitive grammar)

με κανόνες της μορφής μΑν->μχν όπου:

• μ, ν ανήκουν V^*
• χ ανήκει V⁺
• Α ανήκει V_N

Τύπου 2: γραμματική χωρίς συμφραζόμενα (context free grammar)

με κανόνες της μορφής Α->χ όπου:

• χ ανήκει V^*
• Α ανήκει V_N

Οι γραμματικές αυτές μπορούν να ορίσουν συχνά τη σύνταξη μιας γλώσσας.

Τύπου 3: κανονική γραμματική (regular grammar)

με κανόνες της μορφής Α->α ή Α->αΒ όπου:

• χ ανήκει V^*
• Α, Β ανήκουν V_N
• α ανήκει V_Τ ή είναι το κενό σύμβολο

Οι γραμματικές αυτές μπορούν να ορίσουν συχνά τα λεκτικά στοιχεία μιας γλώσσας.

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

• Τα τερματικά σύμβολα περικλείονται σε μονά εισαγωγικά.
• Οι συντακτικοί κανόνες τελειώνουν με .
• Η παραγωγή συμβολίζεται με ::=
• παραγωγή Α ή Β ως: Α | Β
• προαιρετικά στοιχεία ως: [Α]
• επανάληψη μία ή περισσότερες φορές ως: Α+
• επανάληψη καμία ή περισσότερες φορές ως: Α*
• παρενθέσεις επιτρέπουν τον ορισμό της σειράς παραγωγής

Παράδειγμα

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.

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

• Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 37-50. Συμμετρία 1993.

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms, pages 335–361. Addison-Wesley, 1974.
• International Organization for Standardization, Geneva, Switzerland. Information technology — Syntactic metalanguage – Extended BNF, 1996. ISO/IEC 14977-1996.

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:27 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».