Автор: Колесник Сергей aka John Frost
ICQ: 488-251
E-mail: john-frost@ya.ru

jf_calc_1.rar [69.82 Kb] (cкачиваний: 176)

Тебе никогда не приходило в голову узнать, как же все таки создаются языки программирования (ЯП). На них пишутся сложнейшие вычислительные системы, создаются операционные системы и виртуальные машины. На них создана программа, в которой вот и набран этот текст.
Мы с тобой не хуже всяких бородатых преподов в инсте, утверждающих, что создать свой ЯП чрезвычайно сложно, и не под силу обычному кодеру. И сейчас я расскажу, объясню и покажу, как можно легко и просто написать свой собственный язык, не имея никаких специализированных познаний в этой области. А в конце мы еще и накодим небольшую программку на своем собственном языке и с гордостью сможем показывать ее друзьям и удивленным учителям информатики. Так вперед же, вперед к запретным знаниям, вперед к кодингу проги, на которой, потом можно будет тоже кодить!
Кстати, чтобы не было недопонимания, целью этой статьи является написание интерпретатора, а не компилятора, во первых это легче и понятней, во вторых это даже, имхо, интересней. И еще, алгоритм создания этого интерпретатора я придумал сам, методом проб и ошибок, он не претендует на звание самого быстрого или алгоритмически правильного, я просто хочу показать как решил поставленную задачу. Поэтому, если есть какие-то претензии к функционалу конечного продукта – оставьте их при себе, если знаете как сделать лучше, то сделайте, с удовольствием выложу ваше творение на сайте. А это просто пример для обучения.

Первым делом анализаторы, но, а интерпретаторы потом.
Представим себе выражение вида «x2=((0-b)+D^(1/2))/(2*a);», вот примерно то, что дальше было бы разумно делать:
1)Вычислить выражение находящиеся справа от знака присваивания.
А) Заменить все переменные в выражении на их значения.
Б) Вычислить выражение в соответствие с приоритетам операций (скобки,умножение, деление и т.д.)
2) Присвоить полученное значение переменной слева.
Получается, что нам надо научить программу понимать и обрабатывать выражения записанные человеком, приводить их к виду понятному для компьютера. Что-то вроде упрощения.
Этим занимается часть кода, под названием синтаксический анализатор выражений. Отправной точкой в анализе является лексема. Все выражение, разбивается на множество лексем разных видов. Вот посмотрим на этот текст «IF a1==5 THEN x=3+7*5 ELSE x=(3-7)*2», подумаем, на какие лексемы его можно разбить: IF – команда, пробел – разделитель, а1 – переменная, == - логическое выражение, пробел – разделитель, THEN – команда, х –переменная, = - разделитель, 3 – число, + - разделитель и т.д. Давайте выясним какие типы лексем нам понадобятся:
1)Number – число, необходимо для каких-либо логических или алгебраических операций
2)Delimeter – разделитель, служит для разделения команд, чисел и переменных. К ним относятся +-*/()^:;<>!= и пробел.
3)Logic – логические типы, служат для выполнения каких-либо логических условий, к ним относятся равно ==, не равно !=, больше или равно >= и меньше или равно <=.
4)Variable – переменная. Можно записывать в нее значения и считывать, необходима для выполнения условий и математических операций.
5)Command – команда, такая как IF или GOTO. Позволяют менять логику выполнения программы, в зависимости от сложившихся условий. К тому же команды являются зарегистрированными словами, и их именами нельзя будет называть переменные.
Так, теперь мы обладаем нужной информацией для написания класса лексемы.

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

Разберем теперь поподробней что же мы тут делаем. Наш метод принимает текст и возвращает ArrayList, в котором и будут все полученные лексемы. Перебираем посимвольно текст, если находим символ из разряда разделителя, то смотрим что у нас было, от найденного символа до прошлого разделителя, если это число, то добавляем в ArrayList лексему типа число и ее значение:

Если это не число (начинается с символа, а не цифры), то проверяем является ли это переменной либо командой и заносим в результирующий массив:

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

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

Затем мы записываем сам разделить в массив лексем, исключая при этом точку с запятой ; и пробел, т.к. они нам не нужны будут.


Математика-шматематика
На лексемы мы уже разобрали, теперь напишем метод, который будет высчитывать простейшие арифметические операции, по их приоритету, но без скобок и переменных. Т.е. это будет самый нижний уровень упрощения, он будет вычислять уже то, что было упрощенно от скобок и переменных. Упрощению подлежат три лексемы, левый операнд, оператор и правый операнд. Например “3+7+9”, тут пять лексем, три числа и два разделителя. Сначала подлежат упрощению первые три, а именно “3+7”, результат будет 10, значит мы уже получим вот такую последовательность “10+9”, упростим ее и в конечном итоге останется всего лишь “19”.
Вырисовывается алгоритм упрощения:
1)Находим лексему-разделитель
2)Вычисляем выражение
3)Заносим результат в левый операнд, а лексему-разделитель и правый операнд удаляем из списка лексем.
В коде это выглядит так:


Так, простые выражения анализировать и решать научились, теперь научимся разбирать выражения со скобками. Делается это в принципе легко – создаем объект типа stack, он может хранить в себе данные, по типу последним вошел, первым вышел. Зачем это нужно? Да вот зачем, нам нужно выделить выражение между скобками. Делается это элементарно, перебираем все лексемы, открывающиеся скобки заносим в стек, а если находим закрывающуюся скобку, то просто достаем последнюю найденную открывающуюся и вуаля – у нас в руках простое выражение, которое мы уже научились вычислять.
Единственное что я объясню позже – так это упрощение переменных, а пока просто не обращай внимание на эту строчку.

Добавляем переменные
Настало время, объяснить то, о чем я еще в самом начале упоминал – о переменных. Переменные нуждаются в управлении, добавлении, получении значения и т.д. Поэтому мы напишем свой менеджер переменных, который и будет этим всем заниматься. Кстати, небольшое отступление, когда я начал интересоваться вопросом как добавить переменные в выражения, я наткнулся на пример Г. Шилдта, известного писателя книг по кодингу. У него было показано как добавить переменные только с именами от A до Z, т.е. всего 26 переменных, с фиксированными однобуквенными именами. Конечно, этого в принципе должно хватить и всё такое, но хочется, чтобы все было как-то “по взрослому”. И поэтому я решил поделиться с тобой информацией о том, как сделать возможным добавление любого кол-ва переменных, с любыми именами, и они будут использоваться сразу после того места, где вы впервые их заюзаете, т.е. объявлять не надо. Тип переменных по умолчанию double, но если у тебя будет желание – можешь добавить разные типы, просто ради компактности, и чтобы не забивать мозги, пока ввел только числовые переменные, хотя ввести текст будет делом 10 минут – ну пусть это будет твои домашним заданием
Я уже говорил, что написание такого менеджера просто? Так вот, это не правда. Написание такого менеджера чрезвычайно просто . Подумаем, из чего состоит переменная – из имени и значения. Какой же вывод? А вывод вот в чем – для хранения данных в формате ключ-значение подойдет объект hashtable. Теперь мы можем просто очень просто написать метод для добавления переменной:

А методы для записи значения в переменную и чтения значения из него будут такими:

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

Вот вообщем-то и все, вот таким простым способом мы создали функциональный менеджер переменных. Можно даже остановиться на текущем результате и получить клевый калькулятор с поддержкой переменных. Но мы пойдем до конца, и все-таки сделаем интерпретатор.
Продолжение здесь.