Комментарии 24
В свое время реализовал очень похожий проект: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция), причем тоже родившийся из студенческой или даже школьной идеи.
Почему решили обойтись без грамматики математических выражений и генератора парсера для нее?
В статье освещена, по сути, вторая версия. И как только она себя изживёт, либо докажет ограниченность своей реализации. либо как появится время освоить теорию по грамматическим конструкциям, то безусловно код будет переписан.
Эммм, не понял в чем конкретно и как он проигрывает вашему решению. И вы, и он парсит выражения в AST (System.Linq.Expressions), а потом его средствами компилируется. Скорость парсинга может быть разной, но это надо прогнать через бенчмарк.
Очень переусложнено всё и перемешано.
Как минимум, нужно отдельно выделить лексер — тогда упростилось бы решительно всё, начиная от объектной модели и заканчивая логикой самого парсера.
А вообще — очень рекомендую вот эту статью: Pratt Parsers: Expression Parsing Made Easy.
А вот за ссылку отдельное спасибо!
нужно минимизировать использование сторонних библиотек (вообще желателен единый исполнительный файл, да ещё и минимального размера)
А зачем такие ограничения, если не секрет, причем на .NET платформе? Если нужен один исполняемый файл, то можно воспользоваться Cosuta, ILMerge или аналогичным инструментом для объединения сборок. Первый, кстати, умеет сжимать зависимости.
Согласен с комментом выше. Статью тяжеловато читать, т.к. слишком много подробностей и не используется общепринятая терминология парсинга. Большое количество вставок кода не помогают лучше прояснить суть.
По коду же есть следующие замечания:
- слишком много комментариев, но еще хуже закоменченный код. Тяжело читать;
- комменты в коде лучше на английском писать;
- много реализованных математических функций. Нельзя разве было использовать какой-нибудь Math.NET? Опять таки зачем писать свой BigInteger и Complex, если существует встроенная реализация, а также наверняка есть сторонние NuGet пакеты;
- не следует смешивать код обработки математических функций и других модулей, особенно GUI контролов;
- лучше все же исправить опечатки, мозолящие глаза (Parce -> Parse, Evulation -> Evaluation), а также унифицировать использование пробелов и табов.
Несмотря на замечания, статья вписывается в тематику хабра, а идея имеет право на существование. Плюсанул статью.
Что касается использования сторонних пакетов, то не всегда есть такая возможность, не всегда есть именно то, что нужно, либо не всегда есть только то, что нужно.
Ну и да — опечатки, ошибки…
https://bitbucket.org/bytefu/mico
Зато там есть и лексер (src/lexer.d), и рекурсивно-нисходящий парсер (src/parser.d), в сумме менее 700 строк кода. На выходе парсера получается AST, которое при желании можно сразу интерпретировать. Код, на мой взгляд, достаточно понятный, но разбор бинарных выражений сделан компактно, одним методом — вместо него, для простоты, можно сделать отдельные методы разбора для каждого вида арифметических операторов и вызывать их друг из друга, как и остальные — parseLambda(), parseFuncallExpr() и т.п.
А вообще, парсинг я изучал по какой-то уже устаревшей книге Герберта Шилдта, где он описывал создание интерпретатора Small BASIC. Нагуглить её проблематично, но если найдёте (или его другой интерпретатор — Little C), будет ещё лучше — там вся суть парсинга изложена достаточно просто и подробно.
Все таки по мне стек более удобный для дальнейшей обработки, да и сгенерировать исполняемые методы через Reflection гораздо проще будет.
Плюс условные переходы/циклы превращают дерево в сеть, а стек остается неизменным, только вводится операнд условного перехода.
PS. Как говорил один мой преподаватель:
— Каждый программист обязан написать 3 программы в своей жизни:
1. Hello World
2. Свою СУБД или CMS
3. Свой ЯП
Требования: .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 в момент исполнения (собственно, из-за этого и разрабатывалось, чтобы не гадить в память и не устраивать фризы на сборке в юнити).
Парсер математических выражений C# — опыт дилетанта