Создание транслятора

Тема: «Создание трансляторов»

Выполнил: Джиджоев Владислав,

                     ученик 8 класса

                     МБОУ-лицей г. Владикавказ

Научный руководитель: Джаноян Елена Владимировна,

                                           учитель информатики

                                           МБОУ-лицей г.Владикавказ

Владикавказ, 2013

Содержание

Введение ……………………………………………………………………………..….. 3

Языки программирования ………………………………………………………….….. 5

Трансляторы ……………………………………………………………………….….…. 7

Язык программирования MatLang ……………………………….……………………. 11

Интерпретатор языка MatLang ………………………………………………………… 12

Заключение ……………………………………………………………………………… 14

Литература ………………………………………………………………………………. 15

Приложение …………………………………………………………………………..… 16

Введение

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

        Трансляторы делятся на 2 вида: компиляторы и интерпретаторы. Компилятор – это транслятор, целевым языком которого является машинный код, исполняемый процессором. Например, компилятор С++ переводит код на С++ в команды исполняемые процессором. Компилятор Pascal переводит код на языке Pascal в команды процессора. Важное примечание: компилятор не производит исполнение программы, а только переводит её. Интерпретатор же производит анализ исходного кода, но вместо перевода в целевой язык, он исполняет программу, записанную на исходном языке.

Язык программирования (ЯП) – это формальная знаковая система, предназначения для записи компьютерных программ. Язык программирования определяет набор лексических, семантических и синтаксических правил, определяющих внешний вид программы и команды, выполняемые исполнителем (компьютером).

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

        Первым языком программирования стал язык ассемблера. Он является «низкоуровневым языком», т.к. оперирует теми же понятиями и ресурсами, которыми оперирует процессор. Фактически, ассемблер, это запись программ не нулями и единицами, а мнемониками машинных команд. Тем не менее, создание данного языка является величайшим событием в истории IT-индустрии.

        Затем появился первый «высокоуровневый» язык программирования. Это был FORTRAN. Высокоуровневые языки отличаются наличием абстракций от реального процессора. FORTRAN был разработан специально для выполнения математических вычислений. Затем стало появляться много других ЯП и концепций программирования: структурное программирование, процедурное программирование, логическое программирование, объектно-ориентированное программирование и т.д.

        Я стал заниматься темой построения компиляторов потому, что меня всегда интересует, как устроено то, чем я пользуюсь. Когда мне купили компьютер, я заинтересовался, как он работает. Так я стал программистом. Затем я заметил, что все программисты используют компиляторы, и мне стало интересно, как они работают. Вот так я стал изучать трансляторы.

Языки программирования

        Как уже было сказано, язык программирования (ЯП) – это формальная знаковая система, предназначенная для записи компьютерных программ. Первые языки программирования начали разрабатываться в начале второй половины ХХ века. Сейчас их число приближается к 1500.

        Языки делятся по концепциям, моделям памяти, возможностью интерпретации, типу синтаксиса. Но, для того чтобы создать транслятор языка программирования, его синтаксис нужно описать. Это можно сделать словесно, однако это не очень удобно и не всегда лаконично. А можно использовать метод записи, называемый РБНФ-грамматикой.

        Расширенная Бекус-Наурова Форма (РБНФ) – формальная система записи синтаксиса, в которой одни синтаксические категории определяются через другие. Была разработана Никлаусом Виртом. Является расширением метода записи «БНФ» (Бекус-Наурова форма), использовавшейся до создания РБНФ.

        Описание грамматики в РБНФ является набором правил, определяющим отношения между терминальными символами (терминалами) и нетерминальными символами (нетерминалами).

        Терминалы – это минимальные элементы грамматики, не имеющие собственной структуры, и используемые «как есть». Например, буквы в русском языке, или ключевые слова в языке Си.

        Нетерминалы – это элементы грамматики, имеющие своё имя и структуру. Каждый нетерминал может состоять из терминалов и/или нетерминалов, сочетания которых определяется правилами грамматики. В РБНФ нетерминал имеет собственное имя, представляющее собой строку символов.

        Правила (продукции) в РБНФ имеют такой вид:

        имя = выражение.

где имя – название нетерминала, а выражение – соответствующее правилам РБНФ последовательность терминалов, нетерминалов и специальных знаков. Точка в конце обозначает конец правила.

        Семантика правила РБНФ – нетерминал, заданный именем слева от знака равенства, представляет собой определяемую выражением комбинацию терминалов и нетерминалов (слева от знака «равно»).

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

        Определение выражения в РБНФ состоит всего из 4-х конструкций: конкатенация, выбор, вхождение и повторение.

• Конкатенация не имеет специального обозначения. Она определяется последовательной записью символов в выражении. Правило типа A = BC. обозначает, что нетерминал А состоит из последовательно идущих терминалов Bи C. Элементы конкатенации обычно называют синтаксическими факторами, или просто «факторами».
• Выбор обозначается вертикальной чертой («|»). Правило A = B | C | D. обозначает, что А может состоять либо из B, либо из C, либо из D. Элементы выбора называют синтаксическими термами, или просто «термами».
• Вхождение обозначается парой квадратных скобок. Оно выделяет необязательные элементы выражения. Например, правило A = [B]. означает, что нетерминал А либо пуст, либо состоит из нетерминала В.
• Повторение обозначается парой фигурных скобок. Обозначают конкатенацию любого числа всех элементов в них. Например, выражение A = {B}. подразумевает, что нетерминал А либо пуст, либо представляет собой конкатенацию любого кол-ва B (т.е. A либо пуст, либо состоит из B, или BB, или из BBB и т.д.).
• Дополнительно в РБНФ могут использоваться круглые скобки. Он требуются при группировке операций. Например, правило A = (B|C)(D|E).означает, что Aсостоит из 2-х символов, первым из которых является  В или С, вторым – D или Е.

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

Трансляторы

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

        Обычный транслятор чаще всего состоит из 3-х частей: лексического анализатора, синтаксического анализатора и генератора кода. Но чаще всего в компилятор входит также семантический анализатор и оптимизатор. Рассмотрим работу каждого из них.

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

        Схема работы лексического анализатора:

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

        Пример разбора выражения в синтаксическое дерево:

        Существует 2 типа алгоритмов синтаксического анализа:

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

В данной работе я рассмотрел метод рекурсивного спуска (нисходящий анализ), т. к. он наиболее удобен для ручной реализации.

        Рекурсивный спуск – это эффективный и простой алгоритм распознавания. Он состоит в следующем.

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

GetSym(); // считывание начального символа цепочки

S(); // вызов распознающей процедуры начального нетерминала

if (T_END != token) {/*проверка исчерпания входной цепочки*/

        Error();

}

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

        Каждая анализирующая процедура строится по соответствующему нетерминалу, описанному в РБНФ. Для каждой РБНФ-конструкции K существует правило перевода, которое порождает фрагмент анализатора Pr(K). Правила перевода из РБНФ в текст программы показаны в таблице ниже. В них token – глобальная переменная, указывающая на последнюю прочитанную процедурой GetSym() лексему. Функция first(token, exp) возвращает true, если лексема token является начальной для нетерминала exp. Процедура error() завершает работу программы, сигнализируя пользователю о том, что последовательность символов не принадлежит к языку.

Работа генератора кода и оптимизатора

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

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

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

Язык программирования MatLang

        Язык программирования MatLang разработан мною для автоматизации простых вычислений. Он представляет собой набор математических операторов и функций. В нём также можно использовать переменные.

        Самые простые элементы языка MatLang – числа. В языке нет других типов данных кроме чисел. Причём, числа могут быть как целые, так и дробные. Язык может работать с числами от 2.2250738585072014 x 10−308 до 2.2250738585072009 x 10-308.

        Над числами разрешены следующие математические операторы:

• Сложение(+)
• Вычитание(-)
• Умножение(*)
• Деление(/)
• Возведение в степень(^)

Наверное, смысл этих действий объяснять не стоит.

        Помимо арифметических действий в языке MatLang есть встроенные математические функции, такие как

• Получение квадратного корня (sqrt)
• Нахождение натурального логарифма (log)
• Вычисление синуса (sin).

И другие… Полный список встроенных функций см. в приложении.

        В языке MatLang для группировки математических операторов присутствуют скобки. Также есть возможность получения абсолютного значения для определённого выражения. Для этого данное выражение надо заключить в 2 вертикальные черты(|).

        Также есть возможность использования переменных. Имя переменной может содержать только латинские буквы и цифры без пробелов. Язык чувствителен к регистру, т.е. переменная «х» и переменная «X» – разные переменные.

        Для того чтобы присвоить значение переменной, в языке MatLang есть оператор присваивания (“=”). Справа от него записывается имя переменное, которой нужно присвоить значение слева от оператора.

        Для осуществления ввода/вывода в языке MatLang есть две «волшебные» переменные – read и write. Если записать значение в переменную write, то это значение будет выведено на экран. А если использовать переменную read в выражение, то на её место будет подставлено число, считанное с экрана.

        В принципе, это всё описание языка MatLang. РБНФ-нотация его грамматики есть в приложении.

Интерпретатор языка MatLang        

        Язык MatLang разработан, но для его использования потребовался интерпретатор языка. Интерпретатор был написан мною на C++ в среде Visual Studio 2008.  Его размер – 27 Кб, что отражает простоту языка и работы его интерпретатора. Для его работы требуется ОС Windows XP/Vista/7/8 и пакет Visual C++ 2008 Redistributable.

        Устройство работы интерпретатора простое. Он состоит из лексического и синтаксического анализатора. Синтаксический анализатор работает по методу рекурсивного спуска. Если ему требуется лексема из входной цепочки, то он вызывает процедуру Get() и считывает её из переменной token.Синтаксический анализатор не строит синтаксическое дерево, а сразу исполняет выделенные из входной цепочки команды. Это сделано для того, чтобы ускорить процесс интерпретации, ведь команды языка исполняются без ветвления, линейно.

        Интерпретатор работает в диалоговом режиме. Вы вводите команды построчно, и он сразу же их исполняет. Но есть возможность автоматизации путём перенаправления потоков ввода/вывода.

Заключение

        Разработка трансляторов – сложная, но важная тема в информатике. Ведь без компиляторов невозможно создавать более-менее сложные программы. Создание первого транслятора Fortran’а было революцией в информатике.

        Разработка интерпретатора небольшого языка – такого как MatLang – мой очень важный шаг в изучении теории разработки компиляторов. И я этот шаг прошёл. Я узнал: как работают компиляторы, из каких частей они состоят, способы описания языков программирования, историю создания трансляторов. Самое главное – я разработал свой язык программирования! Который, кстати, хоть и прост, но нередко облегчает мне счёт.

        Впереди много планов по изучению данной темы. Самое главное – я планирую разработать компилятор для подмножества языка Pascal. И я уверен, что мне это удастся!

Литература

1.  Н. Вирт. Построение компиляторов. – ДМК-пресс, 2010.- 192 с.
2.  А. Ахо, Р. Сети, Д. Ульман, М. Лам. Компиляторы: принципы, технологии, инструменты. – Вильямс,2008.- 1184 с.
3.  С. З. Свердлов. Языки программирования и методы трансляции. – Питер, 2007. – 640 с.
4.  A. Ахо, Д. Ульман. Теория синтаксического анализа, перевода и компиляции. – Мир,1978. – 614 с.

Приложение

РБНФ-описание MatLang

letter = “a” | “b” | “c” | … | “x” | “y” | “z”.

identifier = letter {letter}.

atom = identifier [ “(“ pm ”)” ] | number | “(“ pm “)” | “|” pm “|”.

power = atom {“^” atom}.

mdm = power {(“*”|”/”|”%”) power}.

pm = [“+”|”-“] mdm {(“+”|”-“) mdm}.

operator = pm {“=” identifier}.

Список функций языка

acos– вычисляет арккосинус

        asin– вычисляет арксинус

        atan– вычисляет арктангенс

        cbrt – вычисляет кубический корень

        sqrt – вычисляет квадратный корень

        ceil – округляет число до целого с избытком

        floor – округляет число до целого с недостатком

        log – находит натуральный логарифм

        log10 – находит логарифм по основанию 10

        exp – вычисляет экспоненту

        cosh – находит гиперболический косинус

        sinh - находит гиперболический синус

        tanh - находит гиперболический тангенс

        cos – вычисляет синус

        sin – вычисляет косинус

        tan – вычисляет тангенс

        sign – возвращает 0 если число равно нулю, 1 если число больше нуля и -1 если число меньше нуля

        logic – возвращает 1 если число равно нулю, иначе возвращает 0

        exit – совершает выход из программы(параметр значения не имеет)