Teoria kompilacji 1

RSS

Cel przedmiotu

Celem wykładu jest przedstawienie studentom teoretycznych i praktycznych podstaw budowy kompilatorów. Podejście bazujące na gramatykach bezkontekstowych i translacji kierowanej składnią wykorzystywane jest do zaprezentowania konstrukcji i działania przedniej części kompilatora (ang. front end).

Program wykładu

Translatory, kompilatory, interpretery. Główne moduły funkcjonalne translatora. Analiza leksykalna. Skaner. Specyfikacja, rozpoznawanie symboli leksykalnych w oparciu o niedeterministyczny połączony automat skończony oraz deterministyczny automat skończony, implementacja skanera. Generator analizatorów leksykalnych Lex. Analiza syntaktyczna. Parser. Gramatyki LL(k). Projektowanie i implementacja parsera LL(1) metodą procedur rekurencyjnych. Gramatyki LR(k). Parser LR(1). Parser SLR(1), projektowanie parsera redukującego w oparciu o gramatyki niejednoznaczne. Parser LALR(1). Generator analizatorów syntaktycznych Yacc. Parser oparty o gramatyki z pierwszeństwem operatorów. Analiza semantyczna. Gramatyki atrybutowane. Translacja kierowana składnią. Gramatyki S-atrybutowane, obliczenia wstępujące definicji S-atrybutowanych. Gramatyki L-atrybutowane, obliczenia zstępujące i wstępujące definicji L-atrybutowanych. Obliczenia rekurencyjne definicji L-atrybutowanych. Analiza definicji kierowanych składnią. Obliczenia rekurencyjne dla drzewa rozbioru.

Charakterystyka pozostałych zajęć

W przedmiocie prowadzone są ćwiczenia laboratoryjne poświęcone głównie implementacji analizatorów leksykalnych i syntaktycznych, z elementami translacji kierowanej składnią, z wykorzystaniem generatorów Lex i Yacc. Realizowane jest także kilka spotkań o charakterze audytoryjnym, wyjaśniających szczegóły algorytmów analizy leksykalnej, parsingu oraz prezentujących projektowanie i badanie gramatyk atrybutowanych.

Bibliografia

1. Aho A. V., Sethi R., Ullman J. D.: Kompilatory. Reguły, metody i narzędzia, WNT, 2002
2. Waite W., Goos G.: Konstrukcja kompilatorów, WNT, 1989.
3. Hopcroft J. E., Motwani R., Ullman J. D.: Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2005
4. Hopgood F.R.A. – Metody kompilacji. 1982.

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards