Wykład Techniki Translacji, informatyka,
studia magisterskie 2004
Mirosław Kutyłowski
Poruszone tematy:
- Wstęp: obszar zastosowań metod parsingu i translacji, warstwowa struktura
kompilatorów
- Analiza leksykalna: zadania analizy leksykalnej, lex, konstrukcja
automatu skończonego na podstawie wyrażenia regularnego, zagadnienia optymalizacji
automatów skończonych realizujacych analizę leksykalna,
- Analiza syntaktyczna: parsery top-down, bottom-up i ogólna architektura parsera, ogólne trudności dla języków bezkontekstowych,
- shift-reduce parsing : gramatyki operatorowe-- parsing w oparciu o uogólnione
relacje priorytetów, konstrukcja relacji,
uproszczenia oparte o wartości
liczbowe, niemożność bottom-up shift-reduce parsing dla
pewnych gramatyk,
- parsing z backtracking-iem: lewostronna faktoryzacja, implementacja przy użyciu dwóch stosów, konstrucja programu parsera,
przykład eksponencjalnej złożoności, informacja o granicy górnej,
- parsery predykcyjne top-downsposób działania,
konstrucja tabeli parsera, LL(1), LL(k)
- parsery LR:
LR(0), LR(1), LALR
- translacja kierowana składnią:
gramatyki atrybutowe, L-atrybuty, translacja top-down i bottom-up dla L-atrybutów
- typy: