Wykład Techniki Translacji, informatyka, studia magisterskie 2004

Mirosław Kutyłowski

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)

translacja kierowana składnią: gramatyki atrybutowe, L-atrybuty, translacja top-down i bottom-up dla L-atrybutów
typy: