Несколько месяцев назад в нашем университете нам сказали создать оболочку, подобную Octave, в течение двух недель! Как видите, я понятия не имел, с чего начать.

Даже после того, как я задавал этот вопрос снова и снова, я ломал голову над тем, с чего начать. И срок был почти близок! Я подумал, что есть два варианта: создать жестко запрограммированную программу на C ++ или написать компилятор / интерпретатор с нуля. Я выбрал легкий путь и выбрал первый вариант, но я знал, что это неправильный путь.

После того, как семестровые экзамены были сданы, я решил принять вызов, с которым я не мог справиться изначально. В итоге я создал свой первый интерпретатор, и он работает!

Давайте начнем

Этот пост поможет вам начать создание вашего самого первого интерпретатора. Я подробно расскажу о своей программе и объясню принятые мной дизайнерские решения.

Компилятор против интерпретатора

Компилятор или интерпретатор - это то, что преобразует программы, написанные на языке высокого уровня, в машинный код. Легко, правда! Но в чем именно разница? Компилятор берет весь исходный код и превращает его в машинный код, в то время как интерпретатор принимает исходный код построчно и переводит его в машинный код.

Почему переводчик?

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

Почему не Java или C?

Компилятор быстрее интерпретатора. Поэтому гораздо предпочтительнее писать переводчика на компилируемом языке, а не на интерпретируемом языке. Все Java, C ++, C являются скомпилированными языками, но я специально выбрал C ++ из-за моего знакомства с языком, а также из-за его производительности и богатого набора библиотек.

Этапы устного переводчика

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

Лексер

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

Затем лексер разделит их на отдельные токены и выведет список токенов, который выглядит примерно так.

Парсер

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

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

Оценщик

Оценщик берет AST, созданный анализатором, и оценивает его, чтобы дать окончательный результат. Оценщик просматривает дерево в режиме пост-заказа и выводит окончательный результат.

Калькулятор универсальных сложных сценариев (интерпретатор)

Универсальный калькулятор комплексных сценариев фокусируется на арифметических выражениях, состоящих из чисел, векторов и матриц, а также на арифметических операторах, таких как,

  • + Сложение и унарный плюс
  • - Вычитание и унарный минус
  • * Умножение
  • . * Поэлементное умножение
  • () Группировка чисел

За кулисами

Лексер

Лексический анализатор определяет только токены, перечисленные ниже,

* оператор , -, оператор +, оператор . *, () оператор, оператор [], оператор ,, ; оператор, числа, пробелы.

Чтобы определить, что попадает в какую категорию, сработает простой цикл for / while. Если токен представляет собой +, -, *,. *, (,), добавьте его в список токенов в качестве оператора. Наконец, переместите итератор к следующему элементу входной строки.

Если это белое пространство, тогда история становится немного другой. Итак, в нашем калькуляторе есть числа, векторы и матрицы. Пробел также является разделителем, как запятая для векторов и матриц в Octave. Поэтому, если мы имеем дело только с числами, мы можем игнорировать пробелы. Но если это вектор / матрица, мы должны добавить его в список токенов. Флаг определяет, имеем ли мы дело с вектором / матрицей или числом.

Согласно построенной мной грамматике (которую я немного объясню) после (;), ([), (, ) и перед (;), (,), (]).

Наконец, входная строка просматривается и проверяется на наличие целых и десятичных знаков. Я добавил еще один токен под названием end, чтобы указать конец списка токенов.

Итак, мы закончили с лексером. Один вниз и еще два шага впереди!

Парсер

Анализатор принимает список токенов в качестве входных данных и выводит абстрактное синтаксическое дерево (AST). AST строится в соответствии с предопределенной грамматикой.

Список токенов будет проходить через следующие правила синтаксиса и попутно рекурсивно строить наше AST-дерево. Это называется рекурсивный достойный синтаксический анализ.

Выражение: термин + выражение | Срок-выражение | Срок

Срок: Фактор * Срок | Фактор. * Срок | Фактор

Фактор: число | (Выражение) | [Listexp]

Listexp: Listfactor, Listexp | Listfactor; Listexp | Listfactor

Listfactor: число

Если токен не соответствует ни одному из правил в порядке или если некоторые токены все еще остаются после обработки всего списка токенов, то выдается сообщение об ошибке «Неожиданный токен».

Это основная идея нашего парсера. Отличная работа, ребята! Теперь вы можете сделать передышку, так как все тяжелые вещи не мешают вам.

Оценщик

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

Он делает это, просматривая AST в режиме почтового заказа, то же самое касается обоих методов оценщика. Для кого-то с небольшим опытом обхода деревьев это может сделать довольно легко.

Итак, теперь нам остается только вызвать интерпретатор в нашей основной функции!

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

До моей следующей статьи, удачного кодирования!

Ссылки

Онлайн-демонстрация интерпретатора - https://repl.it/repls/RosybrownEachIntelligence

Репозиторий GitHub - https://github.com/Geesa-Vihara/Octave-Interpreter