Описание входного языка транслятора

Трансляторы

Основные понятия и определения.

Теория формальных языков

Лекция 12

Алфавит - набор допустимых в языке элементарных знаков.

Слова - элементарные конструкции языка, цепочки знаков. Слова в языке неделимы. Бывают слова из одного символа. Словарный состав языка - это лексика языка.

Предложения - объединения слов и других предложений (в языках программирования операторы).

Синтаксис языка - описание правильных предложений.

Грамматика языка - совокупность правил описания правильных предложений.

Семантика языка - описание смысла предложений (то есть значений слов и их связей).

Метаязык - язык, предназначенный для описания другого языка.

Метасинтаксический язык - язык, предназначенный для описания синтаксиса другого языка.

Транслятор (языковой процессор) - это программа, которая переводит текст программы с одного языка на другой. При этом изменению подлежат алфавит, лексика и синтаксис, но сохраняется семантика.

Язык, на котором написана исходная программа называется входным языком.

Существует два вида трансляторов - интерпретатор и компилятор.

Обычно (и условно) разбивают процесс трансляции на лексический анализ, синтаксический анализ, семантический анализ и синтез объектной программы.

Исторически первым метасинтаксическим языком был язык БНФ (Бэкусова нормальная форма).

Основные символы языка и <металингвистические переменные>.

Правили грамматики записываются в виде предложения <левая часть>::=<правая часть>, где ::= - металингвистический символ, означающий «определяется как». Используется связка |, означающая «или».

Например десятичное целое число в языке Паскаль:

(1). <десятичное число>::=<число без знака>|+<число без знака>|-<число без знака>

(2). <число без знака>::=<цифра>|<число без знака><цифра> - Рекурсия!

(3). <цифра>::=0|1|2|3|4|5|6|7|8|9

Расширенная БНФ:

· Необязательный элемент [ ]

· Альтернативные элементы вертикально в {}

· Необязательные альтернативные элементы вертикально в [ ]

· Повторяющиеся элементы ... (многоточием)

· Ключевые слова подчеркиваются

Например десятичное целое число в языке Паскаль:

(1). ; (2).

БНФ не могут описать контекстно-зависимые свойства языка (нельзя дважды описать одну и ту же переменную).