Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов, страница 2

Метод заключается в следующем.1. Каждому символу строки Si ставится в соответствие индекс Ni по алгоритму:N[0]:=0J:=1Цикл-пока S[J]≠’_’Если S[J] = ‘(‘ или S[J] = <операнд>тоN[J]:=N[J-1] +1иначе N[J]:=N[J-1] -1Все-еслиJ:=J+1Все-циклN[J]:=02.Определяется наибольшее значение индекса в структуре вида k(k-1)k илипри наличии скобок (k-1)k(k-1)k(k-1) и строится соответствующая тройка.3.

Обработанные символы вместе со скобками удаляются, и на их место ставитсязначение N=k-1.4. Операции 2, 3 повторяются до завершения выражения.Пример. (((a+b)*c)+d)/ka) S:( ( (a+ b)*c )+d) /kN: 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 1 0=> T1 = a+bОглавление8b) S:( ( T1 * c ) + d ) / kN: 0 1 2 3 2 3 2 1 2 1 0 1 0c) S:( T2 + d ) / kN: 0 1 2 1 2 1 0 1 0d) S:=> T2 = T1*c=> T3 = T2+dT3 / kN: 0 1 0 1 0=> T4 = T3/kНедостаток метода – требование полной скобочной структуры. Как правило, для этого используется специальная программа, которая вставляет скобки.Решение прочих проблем компиляции было не таким простым. Первые компиляторыявлялись крайне сложными программами, написание которых требовало неординарныхспособностей, и содержали большое количество ошибок.

Так первый компилятор языкаFortran потребовал 18 человеко-лет работы. С тех пор разработаны систематические технологии решения многих задач компиляции, предложен соответствующий инструментарий, в результате чего небольшой компилятор может стать темой курсового проекта.Оглавление9Контрольные вопросы1.Назовите основные типы программ, включающих элементы трансляторов. Пояс-ните их различия.Ответ.2.Назовите основные этапы процесса компиляции.

Уточните задачи каждого эта-па.Ответ3.В чем заключается метод Рутисхаузера?ОтветОглавление102Основные положения теории формальных грамматик2.1Формальная грамматика и формальный языкПредложения любого языка строятся из символов алфавита.Алфавит – непустое конечное множество символов, используемых для записипредложений языка. Например, множество арабских цифр, знаки «+» и «-»: A ={0,1,2,3,4,5,6,7,8,9,+,-} – алфавит для записи целых десятичных чисел, например: «-365»,«78», «+45».Строка – любая последовательность символов алфавита, расположенных один задругим.

Строки в теории формальных языков обозначаются строчными греческими буквами: α, β, γ … . Строка, содержащая 0 символов, называется пустой и обозначается символами e, ε или λ.Множество всех составленных из символов алфавита A строк, в которое входит пустая строка, обозначают A*. Множество всех составленных из символов алфавита Aстрок, в которое не входит пустая строка, обозначают A+. Откуда: A* = A+ ∪ {e}.Формальным языком L в алфавите A называют произвольное подмножество множества A*. Таким образом, язык определяется как множество допустимых предложений.Задать язык L в алфавите A значит либо перечислить все включаемые в него предложения, либо указать правила их образования. Перечисление бесконечно большого количества предложений невозможно.

Определение правил образования предложений осуществляют с использованием абстракций формальных грамматик.Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил – правил продукции. Она определяется как четверка:G = (VT, VN, P, S),где VT – алфавит языка или множество терминальных (незаменяемых) символов;VN – множество нетерминальных (заменяемых) символов – вспомогательный алфавит, символы которого обозначают допустимые понятия языка, VT ∩ VN = ∅;V = VT ∪ VN – словарь грамматики;P – множество порождающих правил – каждое правило состоит из пары строк (α, β),где α ∈ V+ – левая часть правила, β ∈ V* – правая часть правила: α → β, где строка αдолжна содержать хотя бы один нетерминал;S ∈ VN – начальный символ – аксиома грамматики.Оглавление11Для описания синтаксиса языков с бесконечным количеством различных предложений используют рекурсию.

При этом если нетерминал в порождающем правиле расположен справа, то рекурсию называют правосторонней, если слева, то – левосторонней, а,если между двумя подстроками, то – вложенной.Пример. Определим грамматику записи десятичных чисел G0:VT = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -};VN = {<целое>, <целое без знака>, <цифра>, <знак>};P = {<целое> → <знак><целое без знака>, <целое> → <целое без знака>,<целое без знака> → <цифра><целое без знака>, //правосторонняя рекурсия<целое без знака> → <цифра>,<цифра> → 0, <цифра> → 1, <цифра> → 2, <цифра> → 3, <цифра> → 4,<цифра> → 5, <цифра> → 6, <цифра> → 7, <цифра> → 8, <цифра> → 9,<знак> → +, <знак> → - };S = <целое>.Для записи правил продукции обычно используют более компактные и наглядныеформы (модели): форму Бэкуса-Наура или синтаксические диаграммы (см.

далее).Форма Бэкуса-Наура (БНФ). БНФ связывает терминальные и нетерминальныесимволы, используя две операции: «::=» – «можно заменить на»; «|» – «или». Основное достоинство – группировка правил, определяющих каждый нетерминал. Нетерминалы приэтом записываются в угловых скобках. Например, правила продукции грамматики,рассмотренной выше можно записать следующим образом:<целое> ::= <знак><целое без знака>|<целое без знака>,<целое без знака> ::= <цифра><целое без знака>|<цифра>(правосторонняя рек.),<цифра > ::= 0|1|2|3|4|5|6|7|8|9,<знак> ::= +| - .Формальная грамматика, таким образом, определяет правила определения допустимых конструкций языка, т.

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

Сентенциальная форма, содержащая только терминальныесимволы, называется допустимой и представляет собой предложение языка.Для обозначения подстановки используют символ «⇒».Пример. Вывод строки «-45»:<целое> ⇒1⇒1<знак><целое без знака> ⇒2⇒2 <знак><цифра><целое без знака>⇒3⇒3 <знак><цифра><цифра> ⇒4⇒4 - <цифра><цифра> ⇒5⇒5 - 4<цифра> ⇒6⇒6- 45Вывод можно представить графически, в видеЦелоесинтаксического дерева, корнем которого является аксиома, а листья – образуют предложение языка (см.

ри-ЗнакЦБЗсунок 1).Неоднозначные грамматики. Существуют грамматики, в которых для одной строки можно построить-Цифра4Цифранесколько деревьев. Такие грамматики называютсянеоднозначными. Разбор неоднозначных грамматик затруднен, поэтому их, если возможно, преобразуют в однозначные или ограничивают правилами.ОглавлениеЦБЗ5Рисунок 1 – Синтаксическое дерево13Пример 1. Строка х+х+х, порождаемая грамматикой с правилами S → S + S и S → x,имеет два дерева разбора (см. рисунок 2, а–б).

Описывающая тот же язык однозначнаяграмматика использует правила: S → S + x и S → x (см. рисунок 2, в).SSSSS+SS+S+SххS+ххахSхбSS++хххвРисунок 2 – Деревья разбора неоднозначной грамматики (а, б) и единственное дерево однозначной (в)Пример 2. Конструкция if <лог. выр.> then <оператор> [else <оператор>] при вложении неполного варианта получается неоднозначной. Поскольку ее преобразование невозможно, разбор ограничен правилом вложенности.Грамматический разбор – процедура построения синтаксического дерева для конкретного предложения языка. Построение такого дерева позволяет однозначно доказать,что анализируемая строка языка является допустимой, т.е.

принадлежит конкретному языку.Грамматический разбор может осуществляться в разной последовательности,причем дерево можно строить как «сверху» – от аксиомы, так и «снизу» – от предложения. Соответственно существуют нисходящий и восходящий методы разбора. При этомпредложения языка можно рассматривать слева направо и наоборот.

Соответственно различают левосторонний и правосторонний разбор. Левосторонний разбор используютчаще, т. к. мы читаем слева направо.Оглавление142.2.1Левосторонний восходящий грамматический разбор(«слева-направо»)Метод разбора «слава-направо» применим, если грамматика не содержит правил справосторонней рекурсией.При осуществлении грамматического разбора сентенциальные формы просматриваются слева направо и последовательно «свертываются» посредством замены подстроки,совпадающей с правой частью правила («основы») на левую часть того же правила.Правила подстановки должны проверяться, начиная с самого сложного, иначе сложные правила никогда не будут применены, и разбор не удастся.В общем случае при разборе возможны возвраты, поскольку может быть выбранонеподходящее правило подстановки.Пример. Разобрать строку «-45»Правила грамматики:<целое> ::= <знак><целое без знака>|<целое без знака>,<целое без знака> ::= <целое без знака><цифра>|<цифра>,<цифра > ::= 0|1|2|3|4|5|6|7|8|9,<знак> ::= +| - .Последовательность получения сентенциальных форм данным методом:<знак> 45<знак> <цифра>5<знак> <цбз>5<целое> 5 – Тупик! Возвращаемся и ищем другой вариант подстановки!<знак><целое>5 – Тупик! Возвращаемся и ищем другой вариант подстановки!<знак> <цбз><цифра><целое> <цифра> – Тупик! Возвращаемся и ищем другой вариант подстановки!<знак> <целое> <цифра> – Тупик! Возвращаемся и ищем другой вариант!<знак> <цбз><целое>Необходимость предусмотреть возможность возвратов требует хранить всю информацию о каждом шаге разбора, что требует много памяти и существенно усложняет процесс написания программы разбора.Оглавление152.2.2Левосторонний нисходящий грамматический разбор («сверху-вниз»)Метод разбора «сверху-вниз» применим, если грамматика не содержит правил слевосторонней рекурсией.Метод предполагает последовательное выдвижение гипотез, начиная с аксиомы, ихдоказательство посредством подбора правил, которым удовлетворяет разбираемый фрагмент, и выдвижения новых гипотез относительно не разобранной части предложения.Правила подстановки также должны проверяться, начиная с самого сложного, иначецель разбора не будет достигнута.При наличии правил с левосторонней рекурсией процедура разбора становится бесконечной.В общем случае при разборе возможны возвраты, поскольку может быть выбранонеподходящее правило подстановки.Пример.

Разобрать строку «-45»Правила грамматики:а) <целое> ::= <знак><целое без знака>|<целое без знака>б) <целое без знака> ::= <цифра><целое без знака>|<цифра>,в) <цифра > ::= 0|1|2|3|4|5|6|7|8|9,г) <знак> ::= +| - .Последовательность разбора:Распознано Текущий символ Цель или подцель Правило Истина?1-Целоеа1да2-Знакг1нетг2да34-54Цбзб1да4Цифрав1-в4нетв5да67-485Цбзб1нет5Цифрав1-в5нетв6да910_Цбзб1нет11_Цифрав1-в10нет12_Цбзб2нет13_Цифрав1-в10нет5Цбзб2да14-45-4Оглавление16155Цифра16в1-в5нетв6даНедостаток метода, как и в предыдущем случае, заключается в том, что в программеразбора следует хранить всю информацию о каждом его шаге.Выбор метода разбора для грамматики определяется видом правил продукции языка.Оглавление172.3Расширенная классификация грамматик ХомскогоВ зависимости от вида правил грамматики различают:тип 0 – грамматики фразовой структуры или грамматики «без ограничений»:α → β, где α ∈V+, β ∈ V*– в таких грамматиках допустимо наличие любыхправил вывода, что свойственно грамматикам естественных языков;тип 1 – контекстно-зависимые (неукорачивающие) грамматики:α → β, где α ∈V+, β ∈ V*, | α | ≤ | β | – в этих грамматиках для правил видаα X β → α x β возможность подстановки строки х вместо символа X определяется присутствием подстрок α и β, т.