Теория формальных языков и алгоритмы трансляции
Описание
В пособии описаны методы и алгоритмы обработки трансляции арифметических выражений; алгоритм обработки полной скобочной структуры; алгоритм стекового транслятора и формирования польской записи; алгоритмы грамматического разбора сверху вниз, снизу вверх, слева направо. Результаты трансляции (разбора) представляются графически в виде обычных, двоичных и обратных деревьев. Описаны формальные модели грамматик, их свойства; определены правила преобразования языковых конструкций в зависимости от свойств грамматик. Определены понятия синтезирования и сочленения строк, сентенциальной формы, ГФС, специальных классов грамматик (КСГ, КЗГ), локализованной структуры, канонической формы правил подстановки, неоднозначных, эквивалентных и ε-свободных грамматик.
