Определение Цепочка b Î (VTÈVN)* выводима из цепочки в грамматике (обозначается aÞ*b), если существует последовательность цепочек (n³0) такая, что .

Такая последовательность непосредственно выводимых цепочек называется выводом или цепочкой вывода.

Вывод называется правосторонним (левосторонним), если в нем на каждом шаге вывода правило грамматики применяется всегда к крайнему правому (левому) нетерминальному символу в цепочке.

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

ПримерГрамматика G₁=({0, 1}, {A, S}, P₁, S), где множество Р состоит из правил вида: 1) S® 0A1;2)0A® 00A1;3) A®e.

В грамматике G₁ SÞ*000111, т.к. существует вывод .

4.2. Дерево разбора

Графическим способом отображения процесса разбора цепочек является дерево разбора (или дерево вывода).

Определение дерево разбора грамматики называется дерево, которое соответствует некоторой цепочке вывода и удовлетворяет следующим условиям:

- каждая вершина дерева обозначается символом грамматики ;

- корнем дерева является вершина, обозначенная начальным символом грамматики S;

- листьями дерева (концевыми вершинами) являются вершины, обозначенные терминальными символами грамматики или символом пустой строки e;

- если некоторый узел дерева обозначен символом , а связанные с ним узлы – символами , то в грамматике существует правило

Дерево разбора можно построить двумя способами: сверху вниз и снизу вверх. Низходящее:

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

Восходящее: Построение дерева вывода снизу вверх начинается с листьев дерева. В качестве листьев выбираются терминальные символы конечной цепочки вывода, которые на первом шаге построения образуют последний уровень (слой) дерева. Построе­ние дерева идет по слоям. На втором шаге построения в грамматике выбирается правило, правая часть которого соответствует крайним символам в слое дерева (крайним правым символам при правостороннем выводе и крайним левым — при левостороннем). Выбранные вершины слоя соединяются с новой вершиной, которая выбирается из левой части правила. Новая вершина попадает в слой де рева вместо выбранных вершин. Построение дерева закончено, если достигнута корневая вершина (обозначенная целевым символом), а иначе надо вернуться ко второму шагу и повторить его над полученным слоем дерева.

Поскольку все известные языки программирования имеют нотацию записи «сле­ва — направо», компилятор также всегда читает входную программу слева на­право (и сверху вниз, если программа разбита на несколько строк). Поэтому для построения дерева вывода методом «сверху вниз», как правило, используется левосторонний вывод, а для построения «снизу вверх» — правосторонний вывод. На эту особенность компиляторов стоит обратить внимание. Нотация чтения программ «слева направо» влияет не только на порядок разбора программы компилятором (для пользователя это, как правило, не имеет значения), но и ни порядок выполнения операций — при отсутствии скобок большинство равноправных операций выполняются в порядке слева направо, а это уже имеет существенное значение.

5.Преобразования грамматик

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

Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V₀ = {S}; i = 1.

2. V_i = {x | x Î (VT È VN), в P есть A®axb и AÎV_i-1, a,bÎ(VTÈVN)^*} È V_i-1.

3. Если V_i ¹ V_i-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = V_i Ç VN;
VT’ = V_i Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: символ A Î VN называется бесплодным в грамматике
G = (VT, VN, P, S), если множество { a Î VT^* | A Þ a} пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Метод:

Рекурсивно строим множества N₀, N₁, ...

1. N₀ = Æ, i = 1.

2. N_i = {A | (A ® a) Î P и a Î (N_i-1 È VT)^*} È N_i-1.

3. Если N_i ¹ N_i-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

(1) обнаруживаются и удаляются все бесплодные нетерминалы.

(2) обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

6.Теория трансляции. Основные понятия и определения

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

Результатом работы транслятора будет результирующая программа, но только в том случае, если текст исходной программы является правильным — не со­держит ошибок с точки зрения синтаксиса и семантики входного языка. Если исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы транслятора будет сообщение об ошибке (как правило, с допол­нительными пояснениями и указанием места ошибки в исходной программе). В этом смысле транслятор сродни переводчику, например, с английского, которому подсунули неверный текст.

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

Таким образом, компилятор отличается от транслятора лишь тем, что его ре­зультирующая программа всегда должна быть написана на языке машинных ко­дов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке — возможен, например, транслятор программ с языка Pascal на язык С. Соответственно, всякий компилятор являет­ся транслятором, но не наоборот — не всякий транслятор будет компилятором. Например, упомянутый выше транслятор с языка Pascal на С компилятором яв­ляться не будет.

Ассемблер – компилятор, который переводит каждую команду исходной программы в одну машинную команду.

Интерпретатор — это программа, которая воспринимает входную программу на исходном языке и выполняет ее.

В отличие от трансляторов интерпретаторы не порождают результирующую про­грамму (и вообще какого-либо результирующего кода) — и в этом принципиаль­ная разница между ними. Интерпретатор, так же как и транслятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семанти­кой входного языка. Таким образом, результатом работы интерпретатора будет результат, заданный смыслом исходной программы, в том случае, если эта про­грамма правильная, или сообщение об ошибке, если исходная программа неверна.

Общая схема работы компилятора

Основные функции компилятора:

1) проверка исходной цепочки символов на принадлежность к входному языку;

2) генерация выходной цепочки символов на языке машинных команд или ассемблере.

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

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

Данные этапы состоят из более мелких стадий, называемых фазами. Состав фаз и их взаимодействие зависит от конкретной реализации компилятора. Но в том или ином виде в каждом компиляторе выделяются следующие фазы:

1) лексический анализ;

2) синтаксический анализ;

3) семантический анализ;

4) подготовка к генерации кода;

5) генерация кода.

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

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

Общая схема работы компилятора представлена на рисунке 4.3.

7.Лексический анализ

8.О недетерминированном разборе

При анализе по Диаграмме состояний для регулярной грамматики может оказаться, что из одного состояния выходит несколько дуг, ведущих в разные состояния, но помеченных одним и тем же символом.

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

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

Недетерминированный конечный автомат (НКА) – это пятерка

( K, T, δ , H, S ) , где

K - конечное множество состояний;

T - конечное множество допустимых входных символов;

δ - отображение множества K ´ T в множество подмножеств K;

H Ì K - конечное множество начальных состояний (у нас одно!);

S Ì K - конечное множество заключительных состояний (у нас одно!).

δ (A,t) = {B1,B2,...,Bn} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний Bi, i = 1, 2, ... ,n.

9.Задачи лексического анализа

Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики.

ЛА необязательный этап компиляции, но желательный по следующим причинам:

1) замена идентификаторов, констант, ограничителей и служебных слов лексемами делает программу более удобной для дальнейшей обработки;

2) ЛА уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии;

3) если будет изменена кодировка в исходном представлении программы, то это отразится только на ЛА.

В процедурных языках лексемы обычно делятся на классы:

1) служебные слова;

2) ограничители;

3) числа;

4) идентификаторы.

Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таблицы лексем, k - номер лексемы в таблице.

Входные данные ЛА - текст транслируемой программы на входном языке.

Выходные данные ЛА - файл лексем в числовом представлении.

ПримерДля модельного языка М таблица служебных слов будет иметь вид:

1) program; 2) var; 3) int; 4) bool; 5) begin; 6) end; 7) if; 8) then; 9) else; 10) while; 11) do; 12) read; 13) write; 14) true; 15) false.

Таблица ограничителей содержит:

1) . ; 2) ; ; 3) , ; 4) : ; 5) := ; 6) (; 7) ) ; 8) + ; 9) - ; 10) * ; 11) / ; 12) Ú; 13) Ù ; 14) Ø ; 15) = ; 16) > ; 17) <.

Таблицы идентификаторов и чисел формируются в ходе лексического анализа.

ПримерОписать результаты работы лексического анализатора для модельного языка М.

Входные данные ЛА: program var k, sum: int; begin k:=0;…

Выходные данные ЛА: (1, 1) (1, 2) (4, 1) (2, 3) (4, 2) (2, 4) (1, 3) (2, 2) (1, 5) (4, 1) (2, 5) (3, 1) (2, 2)…

10.Лексический анализатор

Определение Лексический анализатор (ЛА) – это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку – лексемы.

11.Синтаксический и семантический анализ

На этапе синтаксического анализа нужно установить, имеет ли цепочка лексем структуру, заданную синтаксисом языка, и зафиксировать эту структуру. Следовательно, снова надо решать задачу разбора: дана цепочка лексем, и надо определить, выводима ли она в грамматике, определяющей синтаксис языка. Однако структура таких конструкций как выражение, описание, оператор и т.п., более сложная, чем структура идентификаторов и чисел. Поэтому для описания синтаксиса языков программирования нужны более мощные грамматики, чем регулярные. Обычно для этого используют укорачивающие контекстно-свободные грамматики (УКС-грамматики), правила которых имеют вид A ® a, где A Î VN,
a Î (VT È VN)^*. Грамматики этого класса, с одной стороны, позволяют достаточно полно описать синтаксическую структуру реальных языков программирования; с другой стороны, для разных подклассов УКС-грамматик существуют достаточно эффективные алгоритмы разбора.

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

Существуют табличные методы анализа ([3]), применимые ко всему классу КС-грамматик и требующие для разбора цепочек длины n времени cn³ (алгоритм Кока-Янгера-Касами) либо cn² (алгоритм Эрли). Их разумно применять только в том случае, если для интересующего нас языка не существует грамматики, по которой можно построить анализатор с линейной временной зависимостью.

Алгоритмы анализа, расходующие на обработку входной цепочки линейное время, применимы только к некоторым подклассам КС-грамматик. Рассмотрим один из таких методов.

12.Метод рекурсивного спуска

Один из эффективных методов синтаксического анализа – метод рекурсивного спуска. В основе метода рекурсивного спуска лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответствует построению дерева разбора цепочки сверху вниз (от корня к листьям).

ПримерДана грамматика с правилами . Требуется выполнить анализ строки cabca^.

Левосторонний вывод цепочки имеет вид:

.

Нисходящее дерево разбора цепочки представлено на рисунке 2.6.

Рисунок 4.4 – Дерево нисходящего разбора цепочки cabca^

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

ПримерПостроим синтаксический анализатор методом рекурсивного спуска для грамматики из примера 2.8.

Введем следующие обозначения:

1) СH – текущий символ исходной строки;

2) gc – процедура считывания очередного символа исходной строки в переменную СH;

3) Err - процедура обработки ошибок, возвращающая по коду соответствующее сообщение об ошибке.

С учетом введенных обозначений, процедуры синтаксического разбора будут иметь вид.

procedure S;

begin

A; B;

if CH<>¢^¢ then ERR

end;

procedure A;

begin

if CH=¢a¢ then gc