Celem wykładu i ćwiczeń laboratoryjnych jest przybliżenie tematyki parsowania i przetwarzania języków formalnych oraz kompilacji. Student zostanie zapoznany z podstawowymi pojęciami oraz technikami stosowanymi w parserach i kompilatorach.

15 godz.

- 1. Pojęcia podstawowe: język naturalny, język formalny, sposoby opisu języka, semiotyka, semantyka, lingwistyka, alfabet.
2. Gramatyka, wyprowadzalność, klasyfikacja gramatyk (wg Chomskiego).
3. Automat ze stosem, gramatyki kontekstowe.
4. Automat skończony, zbiory regularne, języki regularne, wyrażenia regularne.
5. Gramatyki regularne, prawo- i lewostronnie liniowe.
6. Maszyna Turinga, funkcje rekurencyjne, języki rekurencyjne.
7. Translator, kompilator, interpreter. Struktura kompilatora.
8. Budowa kompilatora. Analiza leksykalna i składniowa. Skaner. Parser.
9. Generator analizatorów leksykalnych LEX.
10. Gramatyki i parsery LL(k), LR (k), SLR(1), LALR(k).

15 godz.

1. Drzewo rozbioru syntaktycznego, odtwarzanie wywodu prawo- i lewostronnego (3).
2. Konstrukcja automatu ze stosem dla gramatyki bezkontekstowej (3).
3. Konstrukcja automatu skończonego na podstawie wyrażenia regularnego (3).
4. Algorytmy rozpoznawania tokenów (2).
5. Programowa realizacja automatu skończonego (4).

01. Aho A., Sethi R., Ullman J.D., Kompilatory: reguły, metody i narzędzia, WNT, Warsza-wa, 2002.
02.Aho, A., Ullman J.D., The Theory of Parsing, Translation and Compiling, vol. 1, Prentice Hall, 1972.
03. Blikle A., Automaty i gramatyki, PWN, Warszawa, 1971.
04. Foster J.M., Automatyczna analiza składniowa, 1976.
05. Grieg D., Konstrukcja translatorów dla maszyn cyfrowych, 1984.
06. Hopcroft J.T, Ullman J.D., Wprowadzenie do teorii automatów, języków i obliczeń, PWN, Warszawa, 2003.