Миронов С.В. Языки программирования и трансляции
Содержание:
Фазы трансляции на примере. Лексический анализ. Синтаксический анализ. Семантический анализ. Генерация промежуточного кода. Оптимизация кода. Генерация целевого кода.
Множества. Операции над множествами. Отношения. Отношение порядка. Вложение частичного порядка в линейный. Пример.
Формальные языки. Алфавит и цепочки. Операции над языками. Способы определения языков: конструкторы и распознаватели. Грамматики. Отношение выводимости. Определение языка грамматикой.
Классификация грамматик по Хомскому. Грамматики типа 3 (праволинейные, леволинейные, регулярные, автоматные). Грамматики типа 2 (контекстно-свободные, безконтекстные). Грамматики типа 1 (контекстно-зависимые, неукорачиваемые). Схема распознавателя.
Регулярные языки. Регулярные множества. Регулярные выражения. Уравнения с регулярными коэффициентами. Решение СПУРК. Праволинейные грамматики.
Конечные автоматы. Конечный автомат для праволинейного языка. Праволинейная грамматика для автоматного языка. Лемма о накачке для регулярные языков. Эквивалентность состояний.
Дерево вывода. Рекурсия и грамматике. Алгоритм устранения левой рекурсии. Пример. Нормальная форма Грейбах. Пример приведения грамматики к нормальной форме Грейбах. Нормальная форма Хомского. Пример.
Автоматы с магазинной памятью. Пример работы. Язык, допускаемый МП-автоматом опустошением магазина. Расширенные МП-автоматы. Построение МП-автомата по РМП-автомату.
(Для ознайомлення з повним текстом статті необхідно залогінитись)