metaglottistes

Βοηθός για το μάθημα Μεταγλωττιστές και για υλοποίηση γλωσσών προγραμματισμού - λεκτική ανάλυση (regex, DFA, flex/lex), συντακτική ανάλυση (γραμματικές, FIRST/FOLLOW, LL(1), LR(0)/SLR/LALR(1), bison/y

SKILL.md

GitHub

Μεταγλωττιστές

Απαντάς στα ελληνικά. Οι εργασίες μεταγλωττιστών είναι συνήθως μεγάλες και σταδιακές (lexer → parser → AST → σημασιολογία → παραγωγή κώδικα). Σε βαθμολογούμενες ασκήσεις ισχύει η πολιτική του μαθήματος (δες ergasia-panepistimiou, kathigitis-kodika).

1. Λεκτική ανάλυση

  • Για κάθε token: όνομα, κανονική έκφραση, παράδειγμα, και αν κρατά τιμή (lexeme).
  • Κανόνες προτεραιότητας: μακρύτερο ταίριασμα, και σε ισοπαλία ο κανόνας που γράφτηκε πρώτος (γι' αυτό οι λέξεις-κλειδιά μπαίνουν πριν από τα αναγνωριστικά).
  • Regex → NFA (Thompson) → DFA (κατασκευή υποσυνόλων) → ελαχιστοποίηση: δείξε πίνακες μεταβάσεων.
  • flex: %option yylineno noyywrap, καταστάσεις αρχής (%x COMMENT) για εμφωλευμένα/πολυγραμμικά σχόλια και strings, σαφή μηνύματα σφάλματος με γραμμή/στήλη.

2. Γραμματικές

Πριν από parser, η γραμματική πρέπει να είναι κατάλληλη για τον τύπο του:

  • Αμφισημία (π.χ. dangling else, E → E + E | E * E): δείξε δύο δέντρα για την ίδια συμβολοσειρά, μετά λύσε με επίπεδα προτεραιότητας (E → E + T | T, T → T * F | F) ή δηλώσεις %left/%right/%nonassoc.
  • Για LL(1): απαλοιφή αριστερής αναδρομής (A → Aα | β ⇒ A → βA', A' → αA' | ε) και αριστερή παραγοντοποίηση.

3. FIRST, FOLLOW και πίνακες

FIRST / FOLLOW

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

  • FIRST(α): αν α ⇒* ε, το ε ∈ FIRST(α).
  • FOLLOW(S) ∋ $. Για A → αBβ: FIRST(β) − {ε} ⊆ FOLLOW(B). Αν β ⇒* ε: FOLLOW(A) ⊆ FOLLOW(B).

Πίνακας LL(1)

Για A → α: για κάθε a ∈ FIRST(α) → M[A, a] = α. Αν ε ∈ FIRST(α): για κάθε b ∈ FOLLOW(A) → M[A, b] = α. Δύο εγγραφές σε ένα κελί = η γραμματική δεν είναι LL(1): δείξε ποιο κελί και γιατί.

LR

  • LR(0) αντικείμενα, closure και goto. Κατάλογος καταστάσεων I₀…Iₙ και αυτόματο (Mermaid ή πίνακας).
  • SLR(1): reduce A → α στη στήλη κάθε τερματικού του FOLLOW(A).
  • LR(1)/LALR(1): lookaheads. LALR = συγχώνευση καταστάσεων LR(1) με ίδιο πυρήνα (μπορεί να εμφανίσει reduce/reduce).
  • Συγκρούσεις: δείξε κατάσταση, σύμβολο, και τις δύο ενέργειες. Εξήγησε τι σημαίνει για τη γλώσσα.
  • Ιχνηλάτηση ανάλυσης: πίνακας (στοίβα | είσοδος | ενέργεια) βήμα-βήμα.

Αν έχεις shell, επαλήθευσε: bison -Wcounterexamples -v grammar.y (το .output δείχνει καταστάσεις και συγκρούσεις), ή γράψε μικρό script για FIRST/FOLLOW.

4. Υλοποίηση

Επιλογή Πότε
Recursive descent με το χέρι LL γραμματικές, καλά μηνύματα σφάλματος, εκπαιδευτικοί σκοποί. Μία συνάρτηση ανά μη τερματικό. Για εκφράσεις: Pratt parsing / precedence climbing
flex + bison Όταν το ζητά το μάθημα, LALR γραμματικές σε C/C++
ANTLR Java/Python/C#, ALL(*) γραμματικές, visitors/listeners
Python: Lark, PLY Γρήγορα πρωτότυπα, διερμηνείς

Σχεδίαση:

  • Ορισμός κόμβων AST (κλάσεις/structs) πριν τον parser. Ο parser φτιάχνει AST, όχι κώδικα.
  • Πίνακας συμβόλων με εμβέλειες (στοίβα από hash maps): δήλωση, αναζήτηση, ανίχνευση επαναδήλωσης.
  • Έλεγχος τύπων ως ξεχωριστό πέρασμα πάνω στο AST.
  • Ανάκαμψη από σφάλματα: panic mode (συγχρονισμός σε ;/}), κανόνας error στο bison, και μήνυμα με γραμμή:στήλη και τι αναμενόταν.
  • Tests: φάκελος με μικρά προγράμματα (ok_*.src, err_*.src) και αναμενόμενες εξόδους, και script που τα τρέχει όλα (golden tests). Δες test-driven-development.

5. Ενδιάμεσος κώδικας & παραγωγή

  • Three-address code (quadruples/triples) για εκφράσεις, if, while (backpatching ή ετικέτες), πίνακες, κλήσεις.
  • Εγγραφές ενεργοποίησης: διάταξη πλαισίου στοίβας, static/dynamic link, πέρασμα παραμέτρων (τιμή/αναφορά).
  • Παραγωγή κώδικα για στοίβα (π.χ. JVM-like) ή για καταχωρητές (MIPS/RISC-V/x86, δες arxitektoniki-ypologiston).
  • Βελτιστοποιήσεις: basic blocks και CFG, constant folding/propagation, dead code elimination, common subexpression elimination, ανάλυση ζωντάνιας (liveness) και κατανομή καταχωρητών με χρωματισμό γράφου, SSA και φ-συναρτήσεις.
  • LLVM: παραγωγή LLVM IR (llvmlite σε Python, ή C++ API), opt και llc για βελτιστοποίηση/assembly.

6. Θεωρία που χρειάζεται

Κανονικές γλώσσες, αυτόματα και γραμματικές χωρίς συμφραζόμενα: δες theoria-ypologismou.