Как стать автором
Обновить

Комментарии 24

В свое время реализовал очень похожий проект: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция), причем тоже родившийся из студенческой или даже школьной идеи.


Почему решили обойтись без грамматики математических выражений и генератора парсера для нее?

Я видел Вашу статью как раз в момент обзора вариантов решения моей задачи. Проблема в моём случае заключается в том, что парсер является лишь малой частью того, над чем приходится работать. Он был призван упростить решения ряда задач. И когда стоял выбор — реализация его на основе механизма грамматик, или влоб — задача свелась либо к реализации конкретно парсера, либо к реализации целого механизма грамматического разора. Первый путь показался на тот момент прямее и проще. Для меня…
В статье освещена, по сути, вторая версия. И как только она себя изживёт, либо докажет ограниченность своей реализации. либо как появится время освоить теорию по грамматическим конструкциям, то безусловно код будет переписан.
Вещь полезная, но (видимо проблема у меня, как автора статьи, в недостаточной формализации исходных предпосылок для создания того что бы тут описано) она требует изучения, доработки, подключения в качестве сторонней библиотеки, либо интеграции всего кода. Даже если она обладает на порядки большей функциональностью, то конечному заказчику она может не подойти только по перечисленным критериям. А использование основных идей и реализации чего-либо по образу и подобию заведомо потребуют дополнительного времени, которого и так нет.
Ну на самом деле она очень проста. Используется идея монадического парсинга. Сколько использую, с доработками особо не сталкивался, а кода там минимум. Я как раз отказался от своего парсера в сторону этой либы и очень доволен результатом.
Если интересно у меня есть ассет для Unity3D который решает аналогичную проблему. Но я пошел по другому пути, через токенизатор, LL(1) парсер и последующий биндинг к AST (System.Linq.Expressions). Но это всё велосипеды т.к. со времен .NET 3.5 в примерах от майкрософт валяется System.Linq.Dynamic который делает то что вы описали.
System.Linq.Dynamic проигрывает в производительности прямой компиляции кода накладными расходами на кэширование. И при достаточно больших объёмах вычислительных задач этот проигрыш будет заметен. Но тем не менее это один из возможны вариантов решения. В ряде случаев он будет даже удобнее. Но опять же, нужен либо готовый работающий из коробки код, либо время на реализацию.
>System.Linq.Dynamic проигрывает в производительности прямой компиляции кода накладными расходами на кэширование.
Эммм, не понял в чем конкретно и как он проигрывает вашему решению. И вы, и он парсит выражения в AST (System.Linq.Expressions), а потом его средствами компилируется. Скорость парсинга может быть разной, но это надо прогнать через бенчмарк.
Пардон! Я имел в виду dynamic в реализации платформы.
Что касается производительности, то это действительно предмет отдельного исследования. Вопрос тут скорее сводиться будет к анализу объёмов генерируемого IL-кода.
Ещё одна причина была изобретения велосипеда: помимо процесса разбора строки и компиляции результатов в нативный код в промежуточных этапах надо всё-таки получить кое-какой контроль над самим объектом мат.выражения: его модификации, простейшие (и не очень) операции с другими мат.выражениями, замена, подстановка переменных, добавление специальных переменных, значения которых были бы вычислимы при каждом вычислении мат.выражения, либо генерировали события, обработчик которого определял бы их значения. Слишком сложные были критерии, что бы заняться адаптацией существующих решений.
Все, что вы описали, делается через модификацию AST уже после парсинга. Есть класс ExpressionVisitor, который позволяет удобно обойти дерево и заменить интересующие узлы.

Очень переусложнено всё и перемешано.


Как минимум, нужно отдельно выделить лексер — тогда упростилось бы решительно всё, начиная от объектной модели и заканчивая логикой самого парсера.


А вообще — очень рекомендую вот эту статью: Pratt Parsers: Expression Parsing Made Easy.

Безусловно текстовый парсер строго академически должен работать на основе унифицированного лексера и описания правил лексики. Но беда в том, что во-первых, нужен готовый работающий код, во-вторых, нужен подконтрольный код, в-третьих, нужно минимизировать использование сторонних библиотек (вообще желателен единый исполнительный файл, да ещё и минимального размера).
А вот за ссылку отдельное спасибо!
нужно минимизировать использование сторонних библиотек (вообще желателен единый исполнительный файл, да ещё и минимального размера)

А зачем такие ограничения, если не секрет, причем на .NET платформе? Если нужен один исполняемый файл, то можно воспользоваться Cosuta, ILMerge или аналогичным инструментом для объединения сборок. Первый, кстати, умеет сжимать зависимости.

У нас лет 7 назад был проект реализации пилотажных приборов для отладочных целей на борту. Там был очень медленный индустриальный комп с очень малыми объёмами пространства вообще подо всё. Кроме того, в ряде случаев встают вопросы сертификации кода по разным критериям. И доказывать, что здесь необходима дополнительная сборка бывает достаточно увлекательно.
Ну это было в горах, зачем такие же требования предъявлять проектам, где не требуется такого? :) Ну а интернализировать зависимости не так сложно, благо почти все есть на GitHub под лояльными лицензиями ;)

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


По коду же есть следующие замечания:


  • слишком много комментариев, но еще хуже закоменченный код. Тяжело читать;
  • комменты в коде лучше на английском писать;
  • много реализованных математических функций. Нельзя разве было использовать какой-нибудь Math.NET? Опять таки зачем писать свой BigInteger и Complex, если существует встроенная реализация, а также наверняка есть сторонние NuGet пакеты;
  • не следует смешивать код обработки математических функций и других модулей, особенно GUI контролов;
  • лучше все же исправить опечатки, мозолящие глаза (Parce -> Parse, Evulation -> Evaluation), а также унифицировать использование пробелов и табов.

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

По коду — ссылка в статье ведёт в пространство имён самого парсера. Остальная часть проекта — это в основном всё, что так, или иначе пришлось самостоятельно реализовывать по причинам невозможности использования сторонних библиотек, либо по причинам хобби. Так что код в целом всего проекта ни разу не претендует на завершённость. И мало вероятно когда-то таким будет.
Что касается использования сторонних пакетов, то не всегда есть такая возможность, не всегда есть именно то, что нужно, либо не всегда есть только то, что нужно.
Ну и да — опечатки, ошибки…
Внесу свои пять копеек насчёт парсинга. Есть у меня один маленький проект — написанный на D компилятор игрушечного языка программирования, в котором пока есть только числа, строки и функции (вызываются как в Haskell — аргументы функции передаются без скобок), но нет никаких классов и т.п.

https://bitbucket.org/bytefu/mico

Зато там есть и лексер (src/lexer.d), и рекурсивно-нисходящий парсер (src/parser.d), в сумме менее 700 строк кода. На выходе парсера получается AST, которое при желании можно сразу интерпретировать. Код, на мой взгляд, достаточно понятный, но разбор бинарных выражений сделан компактно, одним методом — вместо него, для простоты, можно сделать отдельные методы разбора для каждого вида арифметических операторов и вызывать их друг из друга, как и остальные — parseLambda(), parseFuncallExpr() и т.п.

А вообще, парсинг я изучал по какой-то уже устаревшей книге Герберта Шилдта, где он описывал создание интерпретатора Small BASIC. Нагуглить её проблематично, но если найдёте (или его другой интерпретатор — Little C), будет ещё лучше — там вся суть парсинга изложена достаточно просто и подробно.
Благодарю. Если будет дан дальнейших ход разработки парсера (видимо уже третья версия), то Ваш опыт не будет лишним.
В бытность мою ассистентом на кафедре сталкивался с подобной проблемой. Единственное что могу подсказать — не изобретать велосипед и не придумывать свой алфавит, а взять TeX и парсить из TeX'овского представления. Там по крайней мере понятен синтаксис и даже есть проверка ввода, чтобы юзер-музер не ввел sin(x и подобную кракобяку
С TeX'овской разметкой сейчас отдельное направление разработки. Если подскажете готовый работающий код разбора и рендринга, буду премного благодарен!
Один вопрос возник, после прочтения статьи: почему останавливается именно на древовидном представлении выражения, а не разворачивается до стека?
Все таки по мне стек более удобный для дальнейшей обработки, да и сгенерировать исполняемые методы через Reflection гораздо проще будет.
Плюс условные переходы/циклы превращают дерево в сеть, а стек остается неизменным, только вводится операнд условного перехода.

PS. Как говорил один мой преподаватель:
— Каждый программист обязан написать 3 программы в своей жизни:
1. Hello World
2. Свою СУБД или CMS
3. Свой ЯП
https://github.com/Leopotam/LeopotamGroupLibraryUnity/tree/master/Assets/LeopotamGroup/Scripting
Требования: .Net fw3.5, из внешних зависимостей — только пара классов unity3d, которые можно безболезненно выпилить (и адаптировать под чистый проект, т.е. зависимостей нет), 5 файликов (ScriptManagerBase.cs, ScriptVM.cs, Types.cs, Internal/Scanner.cs, Internal/Parser.cs), сканер и парсер сгенерены с помощью Coco/R.
Чтобы опубликовать функции из хост-системы в скрипт, нужно их зарегистрировать:
using LeopotamGroup.Scripting;
using UnityEngine;

namespace LeopotamGroup.Examples.ScriptingTest {
    class MyScriptManager : ScriptManagerBase<MyScriptManager> {
        protected override void OnAttachHostFunctions (ScriptVM vm) {
            base.OnAttachHostFunctions (vm);
            // Registering our custom methods for access from scripts.
            vm.RegisterHostFunction ("test_sqrt", OnSqrt);
            vm.RegisterHostFunction ("test_echo", OnTest);
        }

        protected override void OnRuntimeError (string errMsg) {
            Debug.LogError ("Script error: " + errMsg);
            base.OnRuntimeError (errMsg);
        }

        ScriptVar OnSqrt (ScriptVM vm) {
            var count = vm.GetParamsCount ();
            var v = vm.GetParamByID (0);
            if (count < 1 || !v.IsNumber) {
                vm.SetRuntimeError ("(nValue) parameter required");
                return new ScriptVar ();
            }
            return new ScriptVar (Mathf.Sqrt (v.AsNumber));
        }

        ScriptVar OnTest (ScriptVM vm) {
            var count = vm.GetParamsCount ();
            if (count != 1) {
                vm.SetRuntimeError ("test_echo function requires only one parameter");
                return new ScriptVar ();
            }
            var v = vm.GetParamByID (0);
            Debug.Log ("OnTest callback called with parameter: " + v.AsString);
            return v;
        }
    }
}

Колбеки функций сильно похожи на таковые в lua — можно узнать количество параметров, можно запросить любой из них, нужно вернуть значение, пусть даже и undefined.
Ну и тест-скрипт: https://github.com/Leopotam/LeopotamGroupLibraryUnity/blob/master/Assets/LeopotamGroup.Examples/Scripting/Resources/Scripts/TestScript.txt

Особенности: синтаксис максимально простой javascript подобный, всего 3 типа (number, string, undefined), нет поддержки вложенных скоупов (уровень видимости — функция, входящие переменные являются так же локальными, нет глобальных переменных, только функции скрипта + хост-функции), произвольное количество параметров с необязательной инициализацией (undefined по умолчанию, как в js), исполнение мгновенное — нет трансляции в байткод виртуальной машины, отсутствие возможной блокировки потока выполнения (нет циклов, вызов возможен только для хост-функций + отложенный вызов скрипт-функций после завершения текущей). Если не трогать конкатенацию строк в скрипте — нулевой GC allocation в момент исполнения (собственно, из-за этого и разрабатывалось, чтобы не гадить в память и не устраивать фризы на сборке в юнити).
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории