–PAGE_BREAK–Процесс компиляции.
Языки высокого уровня появились в конце 50 начало 60 годов, такие как Фортран, Алгол. Позже Паскаль, Си. Программа которая транслирует любую программу написанную на языке высокого уровня в эквивалентную программу на другом языке (обычно это машинный код) называют компилятором. Два компилятора, реализующие один и тот же язык, на одной и той же машине, могут отличатся хотя бы потому, что разработчики преследовали различные цели при их создании.
Цель:
1. получения эффективного объектного кода программы.
2. Минимизация времени компилирования программы.
3. Разработка небольших объектных программ.
4. Разработка компилятора минимального размера.
5. Создания компилятора обладающий широкими возможностями обнаружения и исправления ошибки.
6. Обеспечение надежности компилятора.
Существует и другой подход, который называется интерпретация, представителем является Basic. Интерпретация состоит в том, что вместо трансляции в машинный код и последующее выполнение программа сначала по операторно транслируется в промежуточный язык, а затем транслируется и выполняется каждый оператор промежуточного языка.
Передать сообщение об ошибках пользователю, часто бывает легче в терминах исходной программы.
Версия программы на языке не редко оказывается компактней, чем машинный код, выдаваемый компилятор.
Изменение части программы не требует перекомпиляции всей программы.
Недостатки:
Медленность работы.
Общая схема обработки языков высокого уровня
Общая структура компилятора
Исходная программа ЯВУ
Лекция (1_11_07) Лексический анализатор – представляет собой первую фазу компилятора. Его основная задача состоит в чтении новых символов и выдачи последовательности лексем. Замена объектов переменной длины символами фиксированной длины. С теоретической точки зрения лексический анализатор не является обязательной частью компилятора. Все его функции могут выполнятся на этапе синтаксического разбора, поскольку полностью регламентированы синтаксисом входного языка. Однако существует несколько причин по которым состав практически всех компиляторов включает лексический анализ.
Применения лексического анализатора упрощает работу с текстом программы, за счет удаления комментариев и пробелов, то есть символов не несущих смысловой нагрузки.
Увеличения эффективности компилятора. Поскольку на чтение исходной программы и разбор ее на лексемы тратится много времени, специальные технологии утилизации и обработки лексем могут существенно повысить производительность компилятора.
Увеличения переносимости компилятора.
Лексема – минимальная единица языка. Исходная программа на ЯВУ представляет собой цепочку образуя последовательность всех листов программы. Язык паскаль использует алфавит, который использует подмножество наборов символа таблицы кодов.
Специальные символы.
Управляющие символы. Некоторые символы расширенного набора кодов включают буквы и кириллицы. Они используются в строках, но не применяются для построения лексем. Среди допустимых для всех языков символов разделителей, благодаря предложения исходной программы разделяются на отдельные слова. В паскале можно выделить несколько категорий лексем:
Минимальная значимая единица текста программ Идентификаторы – последовательность букв и цифр. Стандартными, пред определенными идентификаторами в языке паскаль является: имена встроенных процедур и функций.
Метки – числовые и символьные и отделяются двоеточием.
Числа. Число различают целое — десятичное, вещественное,
Строки – последовательность символов из расширенного набора кодов, заключенная в кавычках.
Синтаксический анализатор
Проверяет является ли программа грамматически правильной, иначе говоря удовлетворяет ли она законам языка программирования, на котором она написана. Синтаксис языка затрагивает только форму языка. Если предложения удовлетворяет нормальным правилам, оно не зависимо от его значения рассматривается как синтаксически правильное.
Формальное определения языков программирования
Под формальным определением языка программирования мы понимает полное описание синтаксиса и семантики. Желательно иметь такое описание.
Сведения о языке содержится в учебниках и руководствах. Часто эти описания не однозначные и не освещают всех тонкостей.
Формальное описание надо для разработчиков компилятора. Синтаксическое определение может задаваться формальными или не формальными способами.
Метаязык (металингвистические символы)
Формальное описания языка.
Метаязык
Использую синтаксические диаграммы
Скобочные конструкции
С помощью множеств
Метаязык
Описание любого формального языка описывается на МЕТО языке. Он может описывать синтез, либо семантику (смысл конструкций), либо все вместе. Для языков программирования наиболее распространенным МЕТО языком для описание синтеза служит нормальная форма БНФ. Перечислим основные понятия и конструкции этого языка:
Терминальный символ – символ, состоящей только из букв алфавита описываемого языка. Одна или несколько букв.
Не терминальный символ – сформулированная на русском или другом языке понятие описываемого языка программирования. Металингвистические переменные. Для того чтобы раскрыть понятие языка обозначаемыми не терминальными символами, используются правила подстановки. U и u – произвольные конечные последовательные цепочки терминальных символов. Знак:: = есть по определению или представляет собой. При описании языков программирования U — это один не терминальный символ. u – любая последовательность терминальных или не терминальных символов раскрывающая сущность не терминального символа с лева.
Символическое имя >:: = |
:: =
По одном из правил определяющие наиболее общих понятий языка строится первым и называется начальным символом языка.
Классификация языков по Хомскому
В основе этой классификации лежит форма левой и правой части правил подстановки. Языки делятся на 4 класса:
0
1
2
3
При чем каждый класс большего номера, является подмножеством каждого класса с меньшим номером.
Класс 0. (Грамматика с фразовой структурой). Не накладывается ни каких ограничений на правила подстановки. Правило имеет вид приведенный выше, где U – произвольная не пустая последовательность терминальных и не терминальных символов. Класс 0 является наиболее мощным языки этого класса могут служить моделью естественных языков.
Класс 1 Контекстно-зависимая грамматика. U1 – нетерминальный символ. X Y u – произвольная цепочка терминальных и нетерминальных символов. Смысл этого правила состоит в том, что замена U на u осуществляется только в контексте X Y. Если длину обозначить, то видна что левая часть всегда меньше чем правая.
Класс 2 Контекстно-свободные грамматики. U ровно один не терминал. Грамматика класса 2 обычно используется для описания синтаксиса языков программирования.
Класс 3 Регулярной грамматикой. U – один не терминал. t – один терминал. n – один не терминал. Грамматика три может использоваться для описания символа простых языков. Используется для сборки лексем. Если б хотя бы одно правило подстановки относится к более высокому классу чем остальные, то и вся грамматика относится к этому классу. Для описания синтаксиса формального языка достаточно задать грамматику с помощью 4 объектов.
S→aS
S→a
S→b
S→bY
Y→bY
Y→b
S →ξ
G3=({a,b},{S,Y},P3,S)
Две грамматики генерирующие один и тот же язык называются эквивалентные грамматики.
Каждая строка, которую можно вывести из начального символа называется сентенциальный символ.
Синтаксические диаграммы.
Другой распространенный способ описания синтаксиса языка является графическим изображениям форм Бекуса Наура. Не терминальные символы записываются на диаграмме прямоугольниках, а терминальные в кружках или овалах.
Пример определения символического имени.
Синтаксический анализ языков программирования.
После того, как на этапе лексического анализа, программа разбивается на ее основные элементы, следующая фаза компилятора должна распознать структуру выражения, состоящая из этих элементов и интерпретировать их. Синтаксический анализ, представляет собой задачу противоположную задачи порождения (вывода). Задача разбора формулируется следующим образом: определить соответствует ли данная конструкция некоторого языка, грамматике этого языка. Является ли данная конструкция правильным предложением языка, то есть не содержит синтаксических ошибок. Различают два типа разбора. Левосторонний и правосторонний.
Левосторонний разбор – на каждом этапе вывода, начиная с первого начального символа языка замещается с помощью одного из порождающих правил грамматики самый левый не терминальный символ в сентенциальной форме.
Если сравнить два вывода, то можно выделить в правостороннем обратный порядок порождающих правил. Так как правосторонний разбор обычно ассоциируется с приведением предложения к начальному символу, а не с генерацией изначального символа.
Синтаксическое дерево разбора
Вывод можно описать и в терминах построения дерева разбора. Дерево представляет собой иерархическую структуру, корень дерева – начальный символ грамматики, узлы промежуточные обычно не терминальные символы, а все остальные узлы не терминальные символы. В большинстве случаев лево и правосторонний разбор и синтаксическое дерево является уникальным. Однако, существуют грамматики, которые имеют более одного дерево разбора, такие грамматики называются не однозначными. Установить неоднозначность является не разрешимой задачей. Не существует алгоритма, который принял бы любую грамматику в качестве входа, и определил однозначна она или нет. Методы разбора могут быть детерминированные и не детерминированные, в зависимости от того, возможен возврат или нет. Не детерминированные методы весьма дорогие с точки зрения памяти и времени., общий перебор.
Лекция 23.11.07 Базовые методы синтаксического анализа.
Вариант построения синтаксического анализа.
Нисходящий разбор — синтаксическое дерево строится от корня к листьям, его отличительная черта является целенаправленность, так как отправляясь от нетерминального символа языка, мы стремимся найти такую подстановку, которая бы привела к части цепочки терминальных символов. Достигается это путем направленного перебора различных вариантов. В списке правил подстановке отыскивается правило, которые в левой части содержат не терминальные символы, а в правой части символы терминальные анализируемого предложения. Если такое правило есть, то дерево не рассчитывается и правило повторяется. Если правило не найдено, то возвращаемся на один или несколько шагов назад, пытаясь изменить выбор сделанный ранее. Процесс разбора заканчивается в одном из двух случае.
Построенное дерево, все листья которого являются терминальными символами и при чтении с лево на право образуют анализируемое предложение. В этом случаи результат положительный, синтаксически рассматриваемое предложение соответствует грамматике языка.
Распознаватель переработал все возможные варианты, но так и не пришел к дереву, значит анализируемое предложение не принадлежит данному языку или содержит ошибку.
«константа»:: = «КФТ» | «знак» «КФТ»
Шаг 1 константа
Шаг 2 КФТ
Восходящий разбор – дерево строится от листьев к корню, то есть алгоритм отправляется от заданной строки, пытается применить правило подстановки с лева на право и все это привести к начальному символу грамматики. Часть строки, которую можно привести к нетерминальному символу называют фразой. Если приведение осуществляется приведением одного правило подстановки, фраза называется непосредственно приводимой. Самая левая непосредственная фраза называется основой. Алгоритм разбора заключается в следующем: в исходном предложении отыскивается основа и приводится к нетерминальному символу. Эта операция применяется до тех пор, пока не получим единый символ и он должен быть начальным символом грамматики. Либо в цепочке не может быть найдена фраза, в этом случаи делается возврат на один или несколько шагов, выбирается другая основа, если все возможные варианты перебраны, а корень дерева так и не построен, делается вывод об наличии ошибки. Восходящий разбор представляет собой перебор вариантов, но они не целенаправленны.
Нисходящие и восходящие методы требуют большого количества перебора. Поэтому требую только детерминированные методы.
Метод рекурсивного спуска – хорошо известный легко реализуемый и детерминированный метод разбора с верху в низ. С его помощью на основании соответствующей грамматике, можно быстро написать синтаксический анализатор. Основное преимущества – скорость создания анализатора. Другое преимущество заключается в соответствии между грамматикой и анализатором, благодаря тому что увеличивается вероятность того, что анализатор правильный. Основной недостаток — медленность, много вызовов. Вручную грамматику изменим, в ведем два нетерминальных символа. По грамматике пишем программу синтаксического анализатора. Lex – функция, которая выделяет лексему.
Лекция 30.11.07 Ll(1) – грамматика
Контекстно-свободные грамматики традиционно служат основой создания синтаксических анализаторов. Для того чтобы построить де терминированный анализатор работающий по принципу сверху в низ используется Ll(1) грамматика. Первая l означает, что исходная строка разбивается с лево на право, вторая буква – левосторонний разбор, а цифра означает, что варианты порождающих правил выбирается с помощью одного предварительного просматриваемого символа.
Определим S-грамматику.
Правая часть порождающего правила начинается с терминала.
В тех случаях, когда в левой части более одного одинаковых не терминала, то соответствующие правые части начинаются с разных терминалов.
Для того что бы грамматика была, необходимым условием является множеством символам предшественников не должно пересекаться. Грамматику называют Ll(1) если для каждого не терминала появляющегося в левой части более одного раза множества направляющих символов соответствующих правил не пересекаются. Возникает вопрос, все ли грамматики. Существует ли алгоритмы, определяющие свойства. Однако, грамматику, можно преобразовать что бы она стала Ll(1).
Что бы заменить левую рекурсию на правую мы упорядочиваем не терминалы.
Факторизация – во многих ситуациях грамматику не обладающих признаками Ll(1) можно преобразовать в грамматику Ll(1). Процесс факторизации нельзя автоматизировать, распространив его на общий случай.
Лекция 07.12.07 Ll(1) – грамматика
После нахождения грамматики, можно перейти к построению синтаксического разбора. Этот этап аналогичен рекурсивному спуску, только здесь исключается многочисленные вызовы процедур, благодаря представлению грамматики в табличном виде. Представим грамматику в виде схемы, номера соответствующие элементам будут являться номерами строк в таблице разбора.
продолжение
–PAGE_BREAK–