1.1. Пример работы
2. Теория
2.1. Транслятор, виды трансляторов
2.2. Этапы трансляции
2.3. Формальные грамматики
2.4. Аналитические грамматики
2.5. Лексический анализ. Синтаксический анализ
Реализовать переводчик с латыни на русский и с русского на латынь. Переводчик должен уметь транслировать 2-3 фразы. Лексемами являются морфемы слов исходного и целевого языка.
1.1. Пример работы
Транслятор — программа или техническое средство, выполняющее трансляцию программы. Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати текст программы и т. д. Понятие трансляции относится как к формальным компьютерным языкам, так и естественным.
Виды трансляторов:
- Диалоговый транслятор — транслятор, обеспечивающий использование языка программирования в режиме разделения времени
- Синтаксически-ориентированный транслятор — транслятор, получающий на вход описание синтаксиса и семантики языка, текст на описанном языке и выполняющий трансляцию в соответствии с заданным описанием.
- Однопроходной транслятор — транслятор, создающий объектный модуль при однократном последовательном чтении исходного кода (за один проход).
- Многопроходной транслятор — транслятор, создающий объектный модуль после нескольких чтений исходного кода (за несколько проходов).
- Оптимизирующий транслятор — транслятор, выполняющий оптимизацию создаваемого кода перед записью в объектный файл.
- Тестовый транслятор — транслятор, получающий на вход исходный код и выдающий на выходе изменённый исходный код.
- Обратный транслятор — транслятор, выполняющий преобразование машинного кода в текст на каком-либо языке программирования (дизассемблер, декомпилятор).
Цель трансляции — преобразование текста с одного языка на язык, понятный адресату.
2.2. Этапы трансляции
Процесс компиляции, как правило, состоит из нескольких этапов: * лексический анализ - в процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов. Лексема — последовательность допустимых символов языка программирования, имеющая смысл для транслятора. * синтаксический анализ - процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой. * семантический анализ - это метод обработки информации на естественном языке, анализирующий взаимосвязь между коллекцией документов и терминами в них встречающимися, сопоставляющий некоторые факторы (тематики) всем документам и терминам. * создание на основе результатов анализов промежуточного кода * оптимизация промежуточного кода * создание объектного кода, в данном случае машинного
2.3. Формальные грамматики
Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.
Терминальный символ — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
Нетерминальный символ — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
грамматика определяется следующими характеристиками:
N — набор (алфавит) нетерминальных символов
P — набор правил вида: «левая часть» -> «правая часть», где:
«левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
«правая часть» — любая последовательность терминалов и нетерминалов
S — стартовый (или начальный) символ грамматики из набора нетерминалов.
Пример: wiki
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):
- тип 0. неограниченные грамматики — возможны любые правила
- тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
- тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
- тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.
2.4. Аналитические грамматики
Аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.
2.5. Лексический анализ. Синтаксический анализ
Традиционно принято организовывать процесс лексического анализа, рассматривая входную последовательность символов как поток символов. При такой организации процесс самостоятельно управляет выборкой отдельных символов из входного потока.
Распознавание лексем в контексте грамматики обычно производится путём их идентификации (или классификации) согласно идентификаторам (или классам) токенов, определяемых грамматикой языка. При этом любая последовательность символов входного потока (лексема), которая согласно грамматике не может быть идентифицирована как токен языка, обычно рассматривается как специальный токен-ошибка.
Лексический анализатор (lexer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.
Как правило, результатом синтаксического анализа является синтаксическое строение предложения, представленное либо в виде дерева зависимостей.
Простейший способ реагирования на некорректную входную цепочку лексем — завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.
Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:
- он должен ясно и точно сообщать о наличии ошибок;
- он должен обеспечивать быстрое восстановление после ошибки, чтобы продолжать поиск других ошибок;
- он не должен существенно замедлять обработку корректной входной цепочки.