Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: LXXXIX Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 11 мая 2020 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Глушков А.А., Ахметзянов Р.Р. СОЗДАНИЕ ЯЗЫКА ПРОГРАММИРОВАНИЯ ПРИ ПОМОЩИ АБСТРАКТНЫХ СИНТАКСИЧЕСКИХ ДЕРЕВЬЕВ // Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ: сб. ст. по мат. LXXXIX междунар. студ. науч.-практ. конф. № 5(88). URL: https://sibac.info/archive/technic/5(88).pdf (дата обращения: 28.06.2022)
Проголосовать за статью
Конференция завершена
Эта статья набрала 409 голосов
Дипломы участников
Диплом Интернет-голосования

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

Глушков Артем Александрович

студент, Самарский университет им. С.П. Королёва,

РФ, г. Самара

Ахметзянов Риназ Рафикович

студент, Самарский университет им. С.П. Королёва,

РФ, г. Самара

Додонова Наталья Леонидовна

научный руководитель,

канд. физ.-мат. наук, доц., Самарский университет им. С.П. Королёва,

РФ, г. Самара

Введение

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

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

Задачи:

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.

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

Число

Затраченное на подсчет время

15 

7.1252ms 

20 

66.832ms 

 25

626.7385ms 

30

6.9655459s

 

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

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

 

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

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

Комментарии (3)

# Игорь Полуэктов 20.05.2020 14:29
Хорошая работа, наглядно демонстрирует принцип работы интерпретатора. Отдельного уважения заслуживает использование раста.
# Максим 22.05.2020 04:28
Обстоятельная работа, отлично демонстрирует принципы построения АСД
# Валерия 22.05.2020 22:56
Добротная работа, жалко, что в статье не описаны парсер-комбинаторы, которые применяются в работе

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом