Języki formalne, automaty i translatory

Mariusz Szwoch
PWNT 2008
Cykl Monografie i podręczniki akademickie
Dział Informatyka
ISBN 978-83-918663-8-2
214 str., 55 rys., 37 tab., 42 poz. bibliogr.
Cena detaliczna książki: 40 zł.
Cena studencka książki: 30 zł.
Pobierz formularz zamówień ( .pdf lub .doc).

SŁOWA KLUCZOWE:
AUTOMATY, ANALIZATORY, GRAMATYKI, JĘZYKI, KOMPILATORY, TRANSLATORY, PARSERY, OPERATORY, REGUŁY PRODUKCJI, SYMBOLE, ZMIENNE, ZDANIA.


W książce przedstawiono zagadnienia związane z teorią i praktyką tworzenia procesorów tekstu i translatorów. Część teoretyczna obejmuje zagadnienia języków formalnych, gramatyk i automatów, zaś przedstawione w niej definicje zilustrowane są za pomocą przykładów.
W rozdziale 1 przedstawiono podstawy teoretyczne języków formalnych, gramatyk i automatów, niezbędne do zrozumienia pozostałych rozdziałów książki. Opisane tu zostały gramatyki kontekstowo zależne, automaty liniowo ograniczone, gramatyki swobodne oraz maszyny Turinga. Przedstawiono tezę Churcha oraz problemy związane z rozstrzygalnością i obliczalnością algorytmów. W rozdziale tym podano też krótkie wprowadzenie do teorii tworzenia translatorów, które stanowią najważniejszą dziedzinę zastosowań omawianych teorii. Rozdział 2 poświęcony jest gramatykom regularnym i automatom skończonym. Przedstawiono w nim również powszechnie używane wyrażenia regularne oraz zagadnienia związane z analizą leksykalną. W rozdziale 3 zaprezentowano gramatyki bezkontekstowe oraz automaty ze stosem. Omówiono tam także problemy związane z konstrukcją analizatorów składniowych typu LL oraz LR. Rozdział 4 poświęcony został analizie semantycznej, kontroli typów i postaci pośredniej kodu. Poruszono w nim również zagadnienia związane z optymalizacją i generacją kodu pośredniego i wynikowego.
W części praktycznej przedstawiono zadania realizowane na poszczególnych etapach analizy tekstów i programów komputerowych oraz zasady tworzenia analizatorów za pomocą powszechnie dostępnych narzędzi służących do ich generowania. W rozdziałach 5 i 6 omówiono generatory analizatorów leksykalnych (skanerów) i składniowych (parserów) oraz zasady wykorzystania tych narzędzi przy tworzeniu analizatorów i procesorów tekstu oraz kompilatorów. Rozdział 7 poświęcony jest praktycznym aspektom omawianych zagadnień i zawiera omówienie kilku ciekawych projektów.