[c02 Конкурс "Parser"], Правила и условия Опции

[volvo]

Тема конкурса:
Разбор и вычисление значения арифметического выражения, полученного программой в run-time в виде строки

Часто на форумах задают один и тот же вопрос: "Как построить график функции, причем функцию задать не перед компиляцией программы, а уже во время ее выполнения?" Вот именно этому и будет посвящено данное соревнование: реализации модуля, который разбирает введенное пользователем выражение, а потом (по запросу из основной программы) вычисляет значение этого выражения. Выражение представляет собой функцию многих аргументов (ограничим количество аргументов в данном соревновании: 26, по числу заглавных букв латинского алфавита).

Обрабатываемая грамматика:
Expr ::= Frac | '(' Expr ')'
Frac ::= Mul '+' Frac | Mul '-' Frac
Mul ::= Term '*' Powr | Term '/' Powr
Powr ::= Term '^' Powr
Term ::= 'Number' | '-' Term | '(' Expr ')' | 'ID' '(' Expr ')'

где
Number - вещественное число, записанное в НЕэкспоненциальной форме (1.2345; 2.434; 23656.9876).
ID - один из идентификаторов функций, которые разрешены в выражениях:
функции без аргументов:
pi - значение числа Пи
функции одного аргумента:
sin, cos, tan, ctg (тригонометрические функции, параметр - в радианах), arcsin, arccos, arctan, arcctg (обратные тригонометрические функции, результат - в радианах), sinh, cosh (гиперболический синус и косинус), exp (e^x), ln (натуральный логарифм), lg (десятичный логарифм), sqrt (квадратный корень)
функции двух аргументов:
log(base, x) - вычисление логарифма от X по основанию base; min(x, y) и max(x, y) - возвращают соответственно минимальный или максимальный из аргументов.

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

Задачей участника является написание модуля, содержащего следующие типы и функции:

1. Тип TFormula (как будет описываться этот тип - с использованием ООП или без него - все равно, ни за использование Объектно Ориентированного Программирования, ни за отказ от его использования призовые очки начисляться не будут); реализация должна предоставлять возможность одновременного использования нескольких переменных, имеющих тип TFunction.
   .
2. Функция, имеющая прототип:
   

   function setFunction(var f: TFunction; const s: string): boolean;
   

   в случае реализации конкурсной задачи на Object Pascal/Delphi, или
   

   int setFunction(TFunction &f, const char *s);
   

   при реализации на С++
   
   Функция должна получить строку s, "разобрать" ее, и сохранить в том виде, который (по мнению конкурсанта) обеспечит наиболее быстрое вычисление значения выражения, заданного строкой (выражение будет вычисляться очень много раз, поэтому здесь действительно важна скорость). Вся дальнейшая работа будет производиться через переменную f. Как результат функции возвращается код ошибки (0 = нет ошибки, функция завершилась успешно).
   .
3. Функция, имеющая прототип:
   

   procedure setVarFunction(var f: TFunction; ch: Char; value: Double): boolean;
   

   
   

   void setVarFunction(TFunction &f, char ch, double value);
   

   , которая установит для "выражения", переданного первым параметром, значение переменной с именем ch в значение value. То есть, чтобы установить значение переменной "A" (в выражении f) в 12.345, потребуется вызвать
   

   setVar(f, 'A', 12.345);
   

   
   .
4. Функция, имеющая прототип:
   

   function calcFunction(var f: TFunction; var errCode: integer): double;
   

   
   

   double calcFunction(TFunction &f, int &errCode);
   

   , которая вычислит и вернет значение выражения, сохраненного в переменной f, учитывая, что значения переменных (присутствующих в выражении) устанавливались при помощи setVarFunction. В случае невозможности вычисления значения выражения (встретилось вычисление квадратного корня из отрицательного числа, деление на 0, и т.д.) в переменной errCode должен вернуться ненулевой код ошибки (значение errCode = 0 после вызова calcFunction означает, что значение было вычислено успешно)
   .
5. Функция, имеющая прототип:
   

   procedure resetFunction(var f: TFunction);
   

   
   

   void resetFunction(TFunction &f);
   

   , которая корректно освободит память, выделенную при создании переменной f. Внимание: функция resetFunction должна оставить возможность повторного использования переменной f, то есть, в результате работы фрагмента:
   

   setFunction(f, 'X+4*Y-2.235');
   setVarFunction(f, 'X', 12.7); setVarFunction(f, 'Y', 34.56);
   value := calcFunction(f, err);
   resetFunction(f);
   setFunction(f, 'X+4*Y-2.235');
   setVarFunction(f, 'X', 12.7); setVarFunction(f, 'Y', 34.56);
   value := calcFunction(f, err);
   resetFunction(f);
   

   в переменную value должен быть дважды занесен один и тот же результат...

Штрафные баллы начисляются за:

1. предупреждения при компиляции программы. Все "конкурсанты" будут компилироваться при помощи Дельфи 2009/FPC 2.2.2 (для программ на Object Pascal) или C++ Builder 2009/GCC (для программ на C/C++) с максимальным уровнем предупреждений. Если программа не компилируется ни одним из перечисленных компиляторов, она снимается с соревнований. Еще одна убедительная просьба: не "закладываться" на трюки, допустимые только в одном, определенном компиляторе (особенно это касается С++, естественно, и его расширений от GCC).
   .
2. аварийное завершение программы. В случае, если в выражении встречается недопустимая операция, программа должна продолжить выполнение, для этого был введен признак ошибки (параметр errCode в функции calcFunction), а не завершаться аварийно.
   .
3. утечки памяти. После выполнения программы вся динамически выделенная память должна быть возвращена системе (при условии правильных вызовов setFunction/resetFunction в тестовой программе, разумеется).
   .

Дополнительные баллы:

1. четко структурированная (и желательно - прокомментированная) программа.

А теперь - о том, чего использовать нельзя:

1. Код должен быть написан без использования дополнительных библиотек (естественно, и без специальных библиотек, занимающихся парсингом выражений и их вычислением; соревнование предназначено не для того, чтобы выяснить, кто лучше пользуется поисковиками (я тоже умею ими пользоваться), а для того, чтобы каждый мог попробовать себя в написании непростого проекта - а этот проект действительно не простой)
   .
2. Код должен быть написан на выбранном языке программирования полностью, ассемблерные вставки категорически запрещены.
   .
3. Запрещено использование внешних компиляторов с тем, чтобы собрать из переданной строки исходный файл, откомпилировать его, и каким-то образом использовать полученные бинарные файлы для вычисления результата, равно как запрещен вообще запуск каких бы то ни было внешних программ
   .
4. При решении задачи на С++ просьба не использовать Boost, поскольку он на данный момент НЕ является стандартной библиотекой языка.
   .

Участие в конкурсе
Участником Конкурса может стать любой человек, зарегистрированный на Форуме "Все о Паскале" не менее, чем за месяц до объявления Конкурса, и имеющий как минимум 15 профильных сообщений (то есть не в разделе Свободное Общение) на нем.

Решения просьба высылать мне до 01.05.2009 (1 мая 2009) в PM в виде архива (с указанием "Конкурс Parser" в заголовке сообщения). Архив должен содержать только исходные тексты в файле с соответствующими расширениями (*.CPP и *.HPP для С++, и *.PAS для Дельфи и FPC). Если хотите - можете указать, каким компилятором предпочтительно проверять программу. Бинарники рассматриваться не будут ни в коем случае, только исходники.

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

Тестовая программа оценивает скорость вычисления выражений модулем, участвующим в конкурсе. Не рассчитывайте на небольшое количество вызовов setFunction/resetFunction и setVarFunction/calcFunction. Они будут вызываться очень много раз (программа будет тестироваться на 18-ти функциях (плюс бонус), для построения графика каждой из которых понадобится как минимум 3 переменных типа TFunction, и как минимум 360 тысяч вызовов setVarFunction и calcFunction для каждой из этих переменных. Самый сложный тест подразумевает 5 переменных и более 2 миллионов итераций по каждой из них). Реализация TFunction, выполнившая данные тесты за минимальное время, и имеющая минимум штрафных баллов, считается победителем конкурса. (Возможно - если участников будет достаточно много - победитель будет определяться для каждого языка программирования)

К этому сообщению присоединены три упрощенных тестовых программы - две на Object Pascal-е и на С++ (файлы в кодировке Unicode !!! test_pp.zip содержит программу для FPC; test_dpr.zip - для Дельфи 2009; программа из test_cpp.zip компилируется как в Builder 2009, так и в GCC /с минимальными изменениями - необходимо заменить реализацию rdtsc/), в которых можно посмотреть, каким образом осуществляется инициализация выражения, вычисление его значения и его удаление. Для того, чтобы увидеть ожидаемые результаты работы программы, ее надо запустить без изменений. Для тестирования своего модуля нужно добавить его к программе и изменить

define NOCONTEST
define EXAMPLE

на

define CONTEST
define NOEXAMPLE

Сопровождение Конкурса.

К этому Конкурсу относятся также все темы этого раздела, в заголовке которых присутствует запись [c02 Конкурс "Parser"]:

• тема "[c02 Конкурс "Parser"] Прием работ". Здесь будут появляться сообщения по мере поступления работ через PM на имя пользователя Volvo.
  .
• тема "[c02 Конкурс "Parser"] Обсуждение". Здесь пользователи могут обсуждать все, что относится к Конкурсу (вопросы по правилам, условиям, протекание конкурса, возникшие проблемы) Просьба решения не публиковать и вообще воздержаться от разговоров про реализацию.
  .
• тема "[c02 Конкурс "Parser"] Результаты". Эта тема только появится после того, как истечет срок подачи заявок и все полученные программы будут протестированы.
  .

Ответственный за проведение Конкурса - volvo