View on GitHub

dituoi_agp

Αρχές Γλωσσών Προγραμματισμού

3. Περιγραφή συντακτικού και σημασιολογίας

3.1 Εισαγωγή

3.2 Το γενικό πρόβλημα της περιγραφής του συντακτικού

Λέξημα (lexeme)

Λεκτική μονάδα (token)

Παράδειγμα: Ποια είναι τα λεξήματα και ποιες οι λεκτικές μονάδες για τον ακόλουθο κώδικα;

index = 2 * count + 17;
Λέξημα Λεκτική μονάδα
index αναγνωριστικό
= σύμβολο_ίσον
2 ακέραια_τιμή
* τελεστής πολλαπλασιασμού
count αναγνωριστικό
+ τελεστής πρόσθεσης
17 ακέραια_τιμή
; ερωτηματικό

3.2.1 Μηχανισμοί αναγνώρισης γλωσσών (recognizers)

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

3.2.2 Μηχανισμοί παραγωγής γλωσσών (generators)

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

3.3 Επίσημες μέθοδοι περιγραφής συντακτικού

3.3.1 Μορφή Μπάκους-Νάουρ και γραμματικές χωρίς συμφραζόμενα

H BNF (Backus Naur Form) και οι CFG (Context Free Grammars) είναι ισοδύναμοι τρόποι περιγραφής του συντακτικού μιας γλώσσας.

3.3.1.1 Γραμματικές χωρίς συμφραζόμενα

3.3.1.2 Προέλευση της μορφής Μπάκους-Νάουρ

3.3.1.3 Βασικές έννοιες BNF

Παράδειγμα ορισμού της εκχώρησης ως BNF (σε μια υποθετική γλώσσα προγραμματισμού):

<assign> -> <var> = <expression>

Παράδειγμα πρότασης που περιγράφεται από τον παραπάνω κανόνα:

total = subtotal1 + subtotal2

Παράδειγμα κανόνων BNF με δύο RHS

<if_stmt> -> if (<logic_expr>) <stmt>
           | if (<logic_expr>) <stmt> else <stmt>
<stmt> -> <single_stmt>
        | begin <stmt_list> end

3.3.1.4 Περιγραφή λιστών

Ο ορισμός λιστών μεταβλητού μήκους γίνεται στην BNF με αναδρομή (το μη-τερματικό στο LHS εμφανίζεται ξανά στο RHS)

<identifier_list> -> identifier
                   | identifier, <identifier_list>

3.3.1.5 Γραμματικές και παραγωγές

Ένα παράδειγμα γραμματικής

<program> -> <stmts>
<stmts> -> <stmt> 
         | <stmt> ; <stmts>
<stmt> -> <var> = <expr>
<var> -> a | b | c | d
<expr> -> <term> + <term> 
        | <term> - <term>
<term> -> <var> | const

Παραγωγή της πρότασης a = b + const (χρησιμοποιώντας αριστερότερες παραγωγές)

<program>   => <stmts>              <-- sentential form
            => <stmt>               <-- sentential form
            => <var> = <expr>       <-- sentential form
            => a = <expr>           <-- sentential form
            => a = <term> + <term>  <-- sentential form
            => a = <var> + <term>   <-- sentential form
            => a = b + <term>       <-- sentential form
            => a = b + const        <-- sentence (μόνο τερματικά σύμβολα)

Ένα ακόμα παράδειγμα γραμματικής (για απλές προτάσεις εκχώρησης)

<assign> -> <id> = <expr>
<id>     -> A | B | C
<expr>   -> <id> + <expr>
          | <id> * <expr>
          | ( <expr> )
          | <id>

Παραγωγής της πρότασης A = B * (A + C)

<assign>    => <id> = <expr>
            => A = <expr>
            => A = <id> * <expr>
            => A = B * <expr>
            => A = B * ( <expr>)
            => A = B * ( <id> + <expr>)
            => A = B * ( A + <expr>)
            => A = B * ( A + <id>)
            => A = B * ( A + C )

3.3.1.6 Δένδρα συντακτικής ανάλυσης

Παράδειγμα: Το parse tree για την πρόταση A = B * (A + C)

3.3.1.7 Ασάφεια

Μια γραμματική που παράγει μια προτασιακή μορφή για την οποία υπάρχουν δύο ή περισσότερα διακριτά δένδρα συντακτικής ανάλυσης λέμε ότι είναι ασαφής (ambiquous).

Παράδειγμα ασαφούς γραμματικής

<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <expr>
        | <expr> * <expr>
        | ( <expr>)
        | <id>

Για την πρόταση

A = B + C * A

προκύπτουν δύο διαφορετικά δένδρα συντακτικής ανάλυσης:

3.3.1.8 Προτεραιότητα τελεστών

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

Παράδειγμα σαφούς γραμματικής

<assign> -> <id> = <expr>
<id> -> A | B | C
<expr> -> <expr> + <term>
        | <term>
<term> -> <term> * <factor>
        | <factor>
<factor> -> ( <expr> )
          | <id>

Παραγωγή της πρότασης A = B + C * A (αριστερότερες παραγωγές)

<assign>    => <id> = <expr>
            => A = <expr>
            => A = <expr> + <term>
            => A = <term> + <term>
            => A = <factor> + <term>
            => A = <id> + <term>
            => A = B + <term>
            => A = B + <term> * <factor>
            => A = B + <factor> * <factor>
            => A = B + <id> * <factor>
            => A = B + C * <factor>
            => A = B + C * <id>
            => A = B + C * A

Παραγωγή της πρότασης A = B + C * A (με δεξιότερες παραγωγές)

<assign>    => <id> = <expr>
            => <id> = <expr> + <term>
            => <id> = <expr> + <term> * <factor>
            => <id> = <expr> + <term> * <id>
            => <id> = <expr> + <term> * A
            => <id> = <expr> + <factor> * A
            => <id> = <expr> + <id> * A
            => <id> = <expr> + C * A
            => <id> = <term> + C * A
            => <id> = <factor> + C * A
            => <id> = <id> + C * A
            => <id> = B + C * A
            => A = B + C * A

Το δένδρο συντακτικής ανάλυσης που προκύπτει (και για τις δύο περιπτώσεις).

Κάθε παραγωγή με σαφή γραμματική έχει ένα και μοναδικό δένδρο συντακτικής ανάλυσης. Ωστόσο το ίδιο δένδρο συντακτικής ανάλυσης μπορεί να προκύψει από διαφορετικές παραγωγές μιας σαφούς γραμματικής.

3.3.1.9 Προσεταιριστικότητα τελεστών

Όταν μια έκφραση περιλαμβάνει δύο τελεστές που έχουν την ίδια προτεραιότητα (π.χ. * και /) τότε απαιτείται ένας σημασιολογικός κανόνας προκειμένου να καθοριστεί ποιος τελεστής θα πρέπει να έχει προτεραιότητα (π.χ. A / B * C). O κανόνας αυτός ονομάζεται προσεταιριστικότητα.

Η προσεταιριστικότητα τελεστών μπορεί να καθορίζεται μέσω της γραμματικής.

Η ακόλουθη γραμματική είναι ασαφής

<expr> -> <expr> + <expr> 
        | <id>

Η ακόλουθη γραμματική είναι σαφής (ορίζει αριστερή προσεταιριστικότητα).

<expr> -> <expr> + <id> 
        | <id>

Παρατηρήστε ότι ο κανόνας είναι αριστερά αναδρομικός.

Η ακόλουθη γραμματική είναι σαφής (ορίζει δεξιά προσεταιριστικότητα).

<factor> -> <exp> ^ <factor>
          | <exp>
<exp> -> ( <expr> )
       | id

Παρατηρήστε ότι ο 1ος κανόνας είναι δεξιά αναδρομικός.

3.3.1.10 Μια ασαφής γραμματική για το if-else

Γραμματική (ασαφής)

<if_stmt> ->    if (<logic_expr>) <stmt>
                if (<logic_expr>) <stmt> else <stmt>
<stmt> -> <if_stmt>

Πρόταση

if (<logic_expr>) if (<logic_expr>) <stmt> else <stmt>

Δένδρα συντακτικής ανάλυσης (δύο λόγω ασαφούς γραμματικής)

Γραμματική (σαφής)

<stmt> -> <matched> | <unmatched>
<matched>   -> if (<logic_expr>) <matched> else <matched>
            | any non-if statement
<unmatched> -> if (<logic_expr>) <stmt>
            | if (<logic_expr>) <matched> else <unmatched>

Για την πρόταση

if (<logic_expr>) if (<logic_expr>) <stmt> else <stmt>

υπάρχει ένα μόνο δένδρο συντακτικής ανάλυσης για την παραπάνω πρόταση

3.3.2 Εκτεταμένη BNF (Extended BNF)

Η εκτεταμένη BNF δεν ενισχύει την περιγραφική δύναμη της BNF, απλά αυξάνει την ευκολία ανάγνωσης και γραφής του.Τρεις επεκτάσεις:

  1. Προαιρετικά τμήματα του RHS τοποθετούνται σε αγκύλες []

Αντί για:

<if_stmt> -> if (<expression>) <statement>
           | if (<expression>) <statement> else <statement>

σε EBNF γράφουμε:

<if_stmt> → if (<expression>) <statement> [else <statement>]
  1. Χρήση αγκυλών {} υποδηλώνουν ότι το τμήμα που εσωκλείεται μπορεί να επαναλαμβάνεται απεριόριστα ή να αποκλειστεί εντελώς

Αντί για:

<identifier_list> -> identifier
                   | identifier, <identifier_list>

σε EBNF γράφουμε:

<identifier_list> -> identifier {, identifier}
  1. Χρήση παρενθέσεων και τελεστή για να υποδηλώσει δυνατότητα επιλογής ενός στοιχείου από μια ομάδα στοιχείων

Αντί για:

<term> -> <term> * <factor>
        | <term> / <factor>
        | <term> % <factor>

σε EBNF γράφουμε:

<term> -> <term> (* | / | %) <factor>

Παράδειγμα γραμματικής σε BNF και ισοδύναμης σε EBNF

BNF

<expr> -> <expr> + <term>
        | <expr> - <term>
        | <term>
<term> -> <term> * <factor>
        | <term> / <factor>
        | <factor>
<factor> -> <exp> ^ <factor>
          | <exp>
<exp> -> (<expr>)
       | id

EBNF (ισοδύναμο με το παραπάνω σε BNF)

<expr> -> <term> {(+ | -) <term>}
<term> -> <factor> {(* | /) <factor>}
<factor> -> <exp> { ^ <exp>}
<exp> -> (<expr>) | id

Επιπλέον παραλλαγές στην EBNF

3.3.3 Γραμματικές και recognizers

Δεδομένης της γραμματικής μιας γλώσσας χωρίς συμφραζόμενα, μπορεί να κατασκευαστεί αυτόματα ένας αναγνωριστικός (recognizer) μηχανισμός για προγράμματα της γλώσσας. Συνεπώς, η κατασκευή του συντακτικού αναλυτή για μια νέα γλώσσα μπορεί να αυτοματοποιηθεί με εργαλεία λογισμικού όπως το yacc, το bison κ.α.

3.4 Γραμματικές χαρακτηριστικών (ή κατηγορικές γραμματικές)

Μια γραμματική χαρακτηριστικών (attribute grammar) είναι μια γραμματική που επιτυγχάνει να να περιγράψει τη δομή μιας γλώσσας προγραμματισμού καλύτερα από μια γραμματική χωρίς συμφραζόμενα.

3.4.1 Στατική σημασιολογία

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

3.4.2 Βασικές έννοιες

Οι γραμματικές χαρακτηριστικών είναι γραμματικές χωρίς συμφραζόμενα στις οποίες έχουν προστεθεί:

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

3.4.3 Ορισμός γραμματικών χαρακτηριστικών

Μια γραμματική χαρακτηριστικών είναι μια γραμματική χωρίς συμφραζόμενα όπου:

  1. Για κάθε σύμβολο γραμματικής υπάρχει ένα σύνολο τιμών χαρακτηριστικών Α(Χ).
  2. Για κάθε κανόνα γραμματικής υπάρχει ένα σύνολο συναρτήσεων που ορίζουν χαρακτηριστικά μη-τερματικών του κανόνα
  3. Για κάθε κανόνα υπάρχει ένα σύνολο κατηγορημάτων που πρέπει να ελέγχονται για να διασφαλιστεί η συνέπεια των χαρακτηριστικών

Έστω ένας κανόνας:

Χ0 -> Χ1 ... Χn

Τα λεγόμενα συντιθέμενα χαρακτηριστικά (synthesized attributes) ορίζονται από συναρτήσεις της μορφής:

S(X0) = f(A(X1), ..., A(Xn))

Δηλαδή, η τιμή ενός συντιθέμενου χαρακτηριστικού σε έναν κόμβο του δένδρου συντακτικής ανάλυσης εξαρτάται μόνο από τιμές χαρακτηριστικών σε κόμβους παιδιά αυτού του κόμβου.

Τα λεγόμενα κληρονομούμενα χαρακτηριστικά (inherited attributes) ορίζονται από συναρτήσεις της μορφής:

I(Xj) = f(A(X0), ..., A(Xn)) για 1 <= j <= n

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

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

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

3.4.4 Εσωτερικά χαρακτηριστικά (intrinsic attributes)

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

3.4.5 Παραδείγματα γραμματικών χαρακτηριστικών

Έστω το ακόλουθο συντακτικό μιας γλώσσας

<assign> -> <var> = <expr>
<expr> -> <var> + <var>
        | <var>
<var> -> A | B | C

Η στατική σημασιολογία ορίζει ότι οι μεταβλητές είναι δύο τύπων int και real. Όταν υπάρχουν δύο μεταβλητές στη δεξιά πλευρά μιας εκχώρησης, οι μεταβλητές δεν είναι απαραίτητο να είναι του ίδιου τύπου. Ειδικότερα ισχύει ότι:

Τα χαρακτηριστικά των μη-τερματικών συμβόλων είναι:

Η γραμματική χαρακτηριστικών στο σύνολο της είναι η ακόλουθη:

1. Συντακτικός κανόνας: <assign> -> <var> = <expr>
   Σημασιολογικός κανόνας: <expr>.expected_type = <var>.actual_type

2. Συντακτικός κανόνας: <expr> -> <var>[2] + <var>[3]
   Σημασιολογικός κανόνας: <expr>.actual_type =
    if (<var>[2].actual_type = int_type) and (<var>[3].actual_type = int_type) then 
        int_type
    else 
        real_type
    end if
   Κατηγόρημα: <expr>.actual_type == <expr>.expected_type

3. Συντακτικός κανόνας: <expr> -> <var>
   Σημασιολογικός κανόνας: <expr>.actual_type = <var>.actual_type
   Κατηγόρημα: <expr>.actual_type == <expr>.expected_type

4. Συντακτικός κανόνας: <var> -> A | B | C 
   I. Συντακτικός κανόνας: <var> -> A
   Σημασιολογικός κανόνας: <var>.actual_type = look-up(A.value)
   
   II. Συντακτικός κανόνας: <var> -> B 
   Σημασιολογικός κανόνας: <var>.actual_type = look-up(B.value)
   
   III. Συντακτικός κανόνας: <var> ->  C
   Σημασιολογικός κανόνας: <var>.actual_type = look-up(C.value)

Η συνάρτηση look-up ελέγχει αν υπάρχει ένα όνομα μεταβλητής στον πίνακα συμβόλων και επιστρέφει τον τύπο της μεταβλητής

Το δένδρο συντακτικής ανάλυσης για την πρόταση:

A = A + B

είναι το ακόλουθο

Με την ακόλουθη σειρά αποτίμησης είναι δυνατός ο υπολογισμός των χαρακτηριστικών

1. <var>.actual_type <- look-up(A) (κανόνας 4)
2. <expr>.expected_type <- <var>.actual_type (κανόνας 1)
3. <var>[2].actual_type <- look-up(A) (κανόνας 4)
   <var>[3].actual_type <- look-up(B) (κανόνας 4)
4. <expr>.actual_type <- είτε int είτε real (κανόνας 2)
5. <expr>.expected_type == <expr>.actual_type που είναι είτε TRUE είτε FALSE

Αν το Α είναι real και το B είναι int τότε προκύπτει το ακόλουθο επισημειωμένο δένδρο συντακτικής ανάλυσης

3.5 Περιγραφή του νοήματος των προγραμμάτων: Δυναμική σημασιολογία

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

Η μεθοδολογίες και οι συμβολισμοί για τη σημασιολογία επιτρέπουν (σε κάποιο βαθμό):

3.5.1 Λειτουργική σημασιολογία (Operational Semantics)

3.5.1.1 Η βασική διαδικασία

Αρχικά σχεδιάζεται μια ενδιάμεση γλώσσα με κύριο επιθυμητό χαρακτηριστικό τη σαφήνεια. Κάθε δομή της ενδιάμεσης γλώσσας πρέπει να έχει προφανές και σαφές νόημα.

Παράδειγμα λειτουργικής σημασιολογίας για την εντολή for της C

for(expr1;expr2;expr3)
{
    stmts
}

expr1
loop: control = expr2
    if (control == 0) goto out
    stmts
    expr3
    goto loop
out: ...

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

ident = var
ident = un_op var
ident = var bin_op var
goto label
if (var rel_op var) goto label

όπου:

ident = αναγνωριστικό
var = αναγνωριστικό ή σταθερά
un_op = μοναδιαίος τελεστής  
bin_op = δυαδικός τελεστής 
rel_op = συγκριτικός τελεστής

3.5.1.2 Αποτίμηση της λειτουργικής σημασιολογίας

3.5.2 Δηλωτική σημασιολογία (Denotational Semantics)

Αποτίμηση της δηλωτικής σημασιολογίας

3.5.3 Αξιωματική σημασιολογία (Axiomatic Semantics)

Αποτίμηση της αξιωματικής σημασιολογίας