Компиляторы. Формальные языки и грамматики

Транслятор – это программа, кот-ая переводит входную программу на скодном (входном) языке в эквивалентную ей на результирующем (выходном языке)

Компилятор – это транслятор, кот-ый осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на ассемлере.

Компилятор должен выполнять анализ исходной программы, а затем синтез объектной программы.Сначала исходная программа раскладывается на составные части, затем из них строятся части эквивалентной объектной программы. Для этого на этапе анализа компилятор строит несколько таблиц, которые затем используются как при анализе, так и при синтезе.

 

Цепочки символов. Операции над цепочками символов

Алфавит - это конечное множество символов, которое в дальнейшем будем обозначать V. Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Далее цепочки символов будем обозначать греческими буквами: a, b, g, …

Цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.

Более формально цепочка символов в алфавите V определяется следующим образом:

(1) e - цепочка в алфавите V;

(2) если a - цепочка в алфавите V и a - символ этого алфавита, то a a - цепочка в алфавите V;

(3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Длиной цепочки называется число составляющих ее символов. Например, если a = abcdefg, то длина a равна 7. Длину цепочки a будем обозначать | a |. Длина e равна 0.

Основной операцией над цепочками символов является операция конкатенации - это дописывание второй цепочки в конец первой, т.е. если a и b - цепочки, то цепочка ab называется их конкатенацией. Например, если a = ab и b = cd, то ab = abcd. Для любой цепочки a всегда ae = ea = a.

Операция конкатенации не обладает свойством коммутативности, т.е. ab¹ba, но обладает ассоциативностью (ab)g = a(bg).

Обращением (или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки a будем обозначать a^R.

Например, если a = abcdef, то a^R = fedcba. Для пустой цепочки: e = e^R.

Для операции обращения справедливо следующее равенство "a,b: (ab)^R = b^Ra^R.

N-ой степенью цепочки a (будем обозначать aⁿ) называется конкатенация n цепочек a. a⁰ = e; aⁿ = aa^n-1 = a^n-1a.

Понятие языка. Формальное определение языка. Методы задания языков

В общем случае язык - это заданный набор символов и правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов. Основой любого естественного или искусственного языка является алфавит, определяющий набор допустимых символов языка.

Язык в алфавите V - это подмножество цепочек конечной длины из множества всех цепочек над алфавитом V. Из этого определения следует два вывода: во-первых, множество цепочек языка не обязано быть конечным; во-вторых, хотя каждая цепочка символов, входящих в язык, обязана иметь конечную длину, эта длина может быть сколь угодно большой и формально ничем не ограничена.

Все существующие языки попадают под это определение. Большинство реальных естественных и искусственных языков содержат бесконечное множество цепочек. Часто цепочку символов, принадлежащую заданному языку, называют предложением языка.

Обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e. Например, если V = {0,1}, то V* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.

Обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e. Следовательно, верно равенство V* = V⁺ È { e }

Известно несколько различных способов описания языков:

1. Перечислением всех допустимых цепочек языка.

2. Указанием способа порождения цепочек языка (заданием грамматики языка).

3. Определением метода распознавания языка.

Первый из методов является чисто формальным и на практике не применяется, т.к. большинство языков содержат бесконечное число допустимых цепочек и перечислить их просто невозможно.

Второй способ предусматривает некоторое описание правил, с помощью которых строятся цепочки языка. Тогда любая цепочка, построенная с помощью этих правил из символов алфавита языка, будет принадлежать заданному языку.

Более всего интересующий нас третий способ предусматривает построение некоторого логического устройства (распознавателя) - автомата, который на входе получает цепочку символов, а на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку. Например, читая этот текст, вы сейчас в некотором роде выступаете в роли распознавателя (надеемся, что ответ о принадлежности текста русскому языку будет положительным).

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: