вторник, 21 октября 2008 г.

Электронная таблица с помощью ANTLR

В рамках тестового задания для одной компании ;) мне  надо было реализовать простую электронную таблицу. Простую-то простую, но поддерживающую адресацию отдельных ячеек (A1), диапазонов (A1:Z1), вычисление как простых арифмитических операций ( +, –, *, /), так и функций (SUM, MIN, MAX) и выражений свертки (REDUCE). Последнее описывает действия выполняемые над диапазоном ячеек с использованием накопленного (агрегатного) и текущих значений, например REDUCE(A1:Z1, 1, X*Y) вычислит произведение всех ячеек из диапазона A1:Z1.

Но прежде чем вычислить что-то, надо понять что – т.е. распарсить текстовый вход и построить на основе него AST (Abstract Syntax Tree) – абстрактное синтаксическое дерево. Т.е. независимую от какого-то языка модель описывающую небоходимый набор выражений, и только потом спроецировать ее (реализовать) на конкретном языке программирования и вычислить. Или необязательно программирования, и необязательно вычислить – а например просто распечатать в структурированном виде.

Так вот, для этого незаменимым и эффективным инструментом оказался ANTLR. Универсальный генератор лексеров и парсеров. С помощью специального языка можно описать грамматику вашего языка (в моем случае формулы вичисления и адресации ячеек) и получить готовые исходники на вашем языке программирования (C#, Java, C и т.д.) для его лексического и синтаксичесго анализа.

Ну а после того как разобранное дерево выражений было готово – построить его вычисление было уже делом техники. В технику входило использование LINQ Expressions и лямбд из .NET 3.5 :).

Комментариев нет: