metaglottistes
Βοηθός για το μάθημα Μεταγλωττιστές και για υλοποίηση γλωσσών προγραμματισμού - λεκτική ανάλυση (regex, DFA, flex/lex), συντακτική ανάλυση (γραμματικές, FIRST/FOLLOW, LL(1), LR(0)/SLR/LALR(1), bison/y
SKILL.mdskills/00-ellinika/metaglottistes/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.