Описание входного языка транслятора
Трансляторы
Основные понятия и определения.
Теория формальных языков
Лекция 12
Алфавит - набор допустимых в языке элементарных знаков.
Слова - элементарные конструкции языка, цепочки знаков. Слова в языке неделимы. Бывают слова из одного символа. Словарный состав языка - это лексика языка.
Предложения - объединения слов и других предложений (в языках программирования операторы).
Синтаксис языка - описание правильных предложений.
Грамматика языка - совокупность правил описания правильных предложений.
Семантика языка - описание смысла предложений (то есть значений слов и их связей).
Метаязык - язык, предназначенный для описания другого языка.
Метасинтаксический язык - язык, предназначенный для описания синтаксиса другого языка.
Транслятор (языковой процессор) - это программа, которая переводит текст программы с одного языка на другой. При этом изменению подлежат алфавит, лексика и синтаксис, но сохраняется семантика.
Язык, на котором написана исходная программа называется входным языком.
Существует два вида трансляторов - интерпретатор и компилятор.
Обычно (и условно) разбивают процесс трансляции на лексический анализ, синтаксический анализ, семантический анализ и синтез объектной программы.
Исторически первым метасинтаксическим языком был язык БНФ (Бэкусова нормальная форма).
Основные символы языка и <металингвистические переменные>.
Правили грамматики записываются в виде предложения <левая часть>::=<правая часть>, где ::= - металингвистический символ, означающий «определяется как». Используется связка |, означающая «или».
Например десятичное целое число в языке Паскаль:
(1). <десятичное число>::=<число без знака>|+<число без знака>|-<число без знака>
(2). <число без знака>::=<цифра>|<число без знака><цифра> - Рекурсия!
(3). <цифра>::=0|1|2|3|4|5|6|7|8|9
Расширенная БНФ:
· Необязательный элемент [ ]
· Альтернативные элементы вертикально в {}
· Необязательные альтернативные элементы вертикально в [ ]
· Повторяющиеся элементы ... (многоточием)
· Ключевые слова подчеркиваются
Например десятичное целое число в языке Паскаль:
(1). ; (2).
БНФ не могут описать контекстно-зависимые свойства языка (нельзя дважды описать одну и ту же переменную).