СОЗДАНИЕ ЯЗЫКА ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ АБСТРАКТНЫХ СИНТАКСИЧЕСКИХ ДЕРЕВЬЕВ

Введение

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

Цель работы: создать язык программирования с использованием синтаксических деревьев.

Задачи:

1. Познакомиться с таким понятием, как интерпретатор. Проанализировать алгоритм работы интерпретатора

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

3. Углубиться в терминологию теории графов. Познакомиться с абстрактным синтаксическим деревом 

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

Что такое интерпретатор?

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

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

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

Интерпретаторы делятся на два типа:

1. Простой интерпретатор анализирует и тут же выполняет (собственно интерпретация) программу покомандно (или построчно), по мере поступления её исходного кода на вход интерпретатора. Его достоинство - мгновенная реакция. Недостаток — такой интерпретатор обнаруживает ошибки в тексте программы только при попытке выполнения команды (или строки) с ошибкой.

2. Интерпретатор компилирующего типа - это система из компилятора, переводящего исходный код программы в промежуточное представление, например, в байт-код или p-код, и собственно интерпретатора, который выполняет полученный промежуточный код (так называемая виртуальная машина). Его достоинство – большее быстродействие выполнения программ (за счёт выноса анализа исходного кода в отдельный, разовый проход, и минимизации этого анализа в интерпретаторе). Недостатки — большее требование к ресурсам и требование на корректность исходного кода.

Алгоритм работы интерпретатора:

1.прочитать инструкцию

2.проанализировать инструкцию и определить соответствующие действия

3.выполнить соответствующие действия

У интерпретатора есть как плюсы, так и минусы.

К плюсам относятся:

• Большая переносимость интерпретируемых программ
• Как правило, более совершенные и наглядные средства диагностики ошибок в исходных кодах
• Меньшие размеры кода по сравнению с машинным кодом

К минусам в свою очередь относятся:

• Интерпретируемая программа не может выполняться отдельно без программы – интерпретатора
• Интерпретируемая программа выполняется медленнее
• Практически отсутствует оптимизация кода

Выбор языка программирования.

Приведем два совета по выбору необходимого языка программирования:

1. Интерпретируемый язык программирования крайне рекомендуется писать на компилируемом ЯП (C, C++, Swift, Rust)

2. Компилируемый язык программирования можно писать на интерпретируемом языке программирования (Python, JavaScript)

В качестве мета-языка нами был выбран язык программирования Rust. И вот несколько преимуществ данного языка перед остальными:

1. Компилируемость
2. Высокая производительность
3. Возможность писать код в функциональном стиле и применять парсер-комбинаторы
4. Удобство подключения различных библиотек
5. Безопасность

Пришло время обратиться к графам. Давайте познакомимся поближе с некоторыми определениями в теории графов.

Дерево - это связный граф, не содержащий циклов.

Ориентированное дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями

Помеченное дерево порядка n - дерево порядка n, вершинам которого взаимно однозначно соответствуют числа от 1 до n.

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

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

Код программы:

while b != 0 

if a > b

a:= a - b 

else 

b:=  b - a

return a

Пояснение к коду:

Пока переменная b не равна 0 (while b != 0 ) будет проверяться условие a>b. Если это условие будет истиной, то произойдет присваивание a:= a - b.

В противном случае произойдет присваивание b:=  b - a. Алгоритм будет продолжать работу до тех пор, пока b не станет равным нулю. В конце программа вернет нам переменную а.

Теперь же давайте посмотрим на эту же программу, только в представлении абстрактного синтаксического дерева.

Рисунок 1. Представление работы кода программы в виде абстрактного синтаксического дерева

Чтобы двигаться дальше, нам необходимо дать несколько особо важных определений, к которым мы будем обращаться, а именно:

1. Терминал или терминальный символ - объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение
2. Нетерминал или нетерминальный символ - объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения
3. Формальная грамматика в теории формальных языков - способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита
4. Контекстно-свободная грамматика - частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка и не имеющими конкретного символьного значения)
5. BNF - Backus–Naur form или Backus normal form (BNF) это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории

Пример работы нашего интерпретатора:

Простые математические вычисления:

Подсчитаем  a * b / (a + b/2),

где a = 5, b = 10

>> first = 5

Line: Assignment("first", Constant(Number(5.0)))

Evaluated: Ok(None)

>> second = 10

Line: Assignment("second", Constant(Number(10.0)))

Evaluated: Ok(None)

>> first * second / ( first + second / 2)

Line: BinaryOperation(Multiply, Variable("first"), BinaryOperation(Divide, Variable("second"), BinaryOperation(Plus, Variable("first"), BinaryOperation(Divide, Variable("second"), Constant(Number(2.0))))))

Evaluated: Ok(Number(5.0))

Программа отработала и выдала ответ: 5

Вычисление n-ного числа Фибоначчи

 >> fn fib(a) { if a == 0 { 0; } else { if a == 1 { 1; } else { fib(a-1) + fib(a-2); }; }; }

Line: Function("fib", Function { parameters: ["a"], body: Block([IfElse(BinaryOperation(Equal, Variable("a"), Constant(Number(0.0))), Block([Constant(Number(0.0))]), Some(Block([IfElse(BinaryOperation(Equal, Variable("a"), Constant(Number(1.0))), Block([Constant(Number(1.0))]), Some(Block([BinaryOperation(Plus, Call("fib", [BinaryOperation(Minus, Variable("a"), Constant(Number(1.0)))]), Call("fib", [BinaryOperation(Minus, Variable("a"), Constant(Number(2.0)))]))])))])))]) })

Evaluated: Ok(None)

>> fib(15)

Line: Call("fib", [Constant(Number(15.0))])

Evaluated: Ok(Number(610.0))

Программа отработала и выдала ответ: 610

Вывод:

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

Приведем немного статистики по затратам времени на поиск чисел Фибоначчи:

Таблица 1.

Таблица времени, затраченного на подсчет чисел Фибоначчи нашим интерпретатором.

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

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

Список литературы:

1. Додонова Л.Н. Конспект лекций по дисциплине «Теория конечных графов и ее применения». Самара, 2019
2. Ссылка на репозиторий, где расположен код нашего языка программирования - https://github.com/tataRinaz/SP
3. “Программирование на языке Rust”  Блэнди Джим, Орендорф Джейсон
4. “Advanced Compiler Design and Implementation” Стивен Мукник