Посоветуйте парсер
От: SergASh  
Дата: 13.02.17 15:09
Оценка:
Ищу библиотеку для парсинга выражений и (не)равенств.
Должна поддерживать
  • четыре арифметических операции
  • скобки
  • операции сравнения на равенство и неравенство
  • логические операции AND и OR
  • числовые константы
  • переменные, подойдут обычные правила именования идентификаторов в ЯП

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

    Нугет полон подобного, но учитывая популярность этой тематики в академии большей частью оно сделано студентами, и качество там никакое.

    Мне понравилось как вот тут сделано. https://github.com/KirillOsenkov/MathParser
    Но там только арифметические операции.

    Посоветуйте если кто чем-то таким пользовался.
    Спасибо
  • Re: Посоветуйте парсер
    От: AndrewVK Россия http://blogs.rsdn.org/avk
    Дата: 13.02.17 17:02
    Оценка: 4 (1)
    Здравствуйте, SergASh, Вы писали:

    SAS>Посоветуйте если кто чем-то таким пользовался.


    antlr + пример калькулятора из поставки. Допиливаешь до нужного состояния грамматику и вперед.
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
    AVK Blog
    Re: Посоветуйте парсер
    От: Kolesiki  
    Дата: 13.02.17 21:19
    Оценка:
    Здравствуйте, SergASh, Вы писали:

    SAS>Посоветуйте если кто чем-то таким пользовался.


    PEGNet — PEG парсер со всеми стандартными плюшками + регэкспы. Калькулятор вроде вашего пишется за час.
    Re[2]: Посоветуйте парсер
    От: AndrewVK Россия http://blogs.rsdn.org/avk
    Дата: 14.02.17 07:48
    Оценка:
    Здравствуйте, Kolesiki, Вы писали:

    K>PEGNet — PEG парсер со всеми стандартными плюшками + регэкспы. Калькулятор вроде вашего пишется за час.


    1 Branch
    1 Tag
    0 Forks
    1 Watcher

    4 коммита и полное отсутствие документации. Отличный, в общем, совет!
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
    AVK Blog
    Re: Посоветуйте парсер
    От: Sinatr Германия  
    Дата: 15.02.17 08:05
    Оценка:
    Здравствуйте, SergASh, Вы писали:

    SAS>и, что тоже важно, не поддерживать больше ничего. Нужно это дело для валидации выражений перед тем,

    SAS>как они будут использованы в другой системе. Вычислять их не требуется.

    Если синтаксис берется из "другой системы", то нельзя ли эту систему или ее часть и использовать для данной задачи? Попытка вычислить результат — это тоже своего рода валидация, выкинет исключение или не выкинет.

    Вслушайтесь: "посоветуйте либу ... только это, это, это и ничего больше". Звучит маловероятно для либы.
    ---
    ПроГLамеры объединяйтесь..
    Re: Посоветуйте парсер
    От: Vladek Россия Github
    Дата: 15.02.17 10:21
    Оценка:
    Здравствуйте, SergASh, Вы писали:

    Если
    SAS>Нужно это дело для валидации выражений перед тем,
    SAS>как они будут использованы в другой системе. Вычислять их не требуется.
    тогда вот этого
    SAS>Нугет полон подобного, но учитывая популярность этой тематики в академии большей частью оно сделано студентами, и качество там никакое.
    будет вполне достаточно.
    Re[2]: Посоветуйте парсер
    От: SergASh  
    Дата: 15.02.17 10:54
    Оценка:
    S>Если синтаксис берется из "другой системы", то нельзя ли эту систему или ее часть и использовать для данной задачи? Попытка вычислить результат — это тоже своего рода валидация, выкинет исключение или не выкинет.

    Можно, но страшно. Её можно положить если вместо выражения подсунуть что-то хитрое.

    S>Вслушайтесь: "посоветуйте либу ... только это, это, это и ничего больше". Звучит маловероятно для либы.


    Перечень допустимых операторов и их приоритет бывают настраиваемые, если это соответствующим образом спроектированная библиотека.
    Re: Посоветуйте парсер
    От: Arsen.Shnurkov  
    Дата: 15.02.17 21:00
    Оценка: :)
    SAS>Посоветуйте если кто чем-то таким пользовался.

    Тебе уже самый правильный совет дали — возьми генератор парсеров, например Pliant и напиши на нём. Я понимаю, что это потребует времени. Но это вполне обозримая и решаемая задача. Я бы тебе написал, но думаю, что у тебя недостаточно навыков в области заключения договоров подряда и оплаты заказных работ.
    Re[2]: Посоветуйте парсер
    От: WolfHound  
    Дата: 16.02.17 14:45
    Оценка: 6 (1)
    Здравствуйте, AndrewVK, Вы писали:

    AVK>antlr + пример калькулятора из поставки. Допиливаешь до нужного состояния грамматику и вперед.

    1)Тогда уж лучше нитру.
    2)Генератор парсера для этой задачи это из пушки по воробьям.
    Вот такого за глаза хватит.
    Большая часть кода библиотека.
    Тут реализован PEG parser с расширением, позволяющим легко разбирать операторы с приоритетами.
    В принципе этим кодом можно парсить что угодно. Но не рекомендую. На выражениях он гарантированно линейный, но на более сложных грамматиках можно на экспоненту попасть.
    Для более сложных случаев нужно брать нитру.
      Скрытый текст
    Грамматика в функции Main.

    using System;
    using System.Collections.Generic;
    
    namespace SimpleParser
    {
      public abstract class Parser
      {
        public abstract int Parse(int startPos, string text);
      }
    
      public class IntParser : Parser
      {
        public override int Parse(int startPos, string text)
        {
          int pos = startPos;
          while (pos < text.Length && char.IsDigit(text[pos]))
            ++pos;
          if (pos == startPos)
            return -1;
          else
            return pos;
        }
      }
    
      public class StringParser : Parser
      {
        private string _str;
        public StringParser(string str)
        {
          _str = str;
        }
    
        public override int Parse(int startPos, string text)
        {
          int pos = startPos;
          int endPos = startPos + _str.Length;
          if (endPos > text.Length)
            return -1;
    
          for (int i = 0; i < _str.Length; ++i)
            if (text[startPos + i] != _str[i])
              return -1;
    
          return endPos;
        }
      }
    
      public class ChoiceParser : Parser
      {
        private Parser AsParser(object rule)
        {
          var parser = rule as Parser;
          if (parser != null)
            return parser;
          else if (rule is string)
            return new StringParser((string)rule);
          else
            throw new NotSupportedException();
        }
    
        public void Add(params object[] rules)
        {
          var left = rules[0] as RestrictedParser;
          var parsers = new List<Parser>();
          if (left == null)
          {
            for (int i = 0; i < rules.Length; ++i)
              parsers.Add(AsParser(rules[i]));
            _prefixParsers.Add(parsers.ToArray());
          }
          else
          {
            for (int i = 1; i < rules.Length; ++i)
              parsers.Add(AsParser(rules[i]));
            _postfixParsers.Add(new PostfixParser(left.BindingPower, parsers.ToArray()));
          }
        }
    
        private List<Parser[]> _prefixParsers = new List<Parser[]>();
        private List<PostfixParser> _postfixParsers = new List<PostfixParser>();
    
        private Dictionary<int, RestrictedParser> _parserCache = new Dictionary<int, RestrictedParser>();
        public RestrictedParser Get(int bindingPower)
        {
          RestrictedParser parser;
          if (!_parserCache.TryGetValue(bindingPower, out parser))
          {
            parser = new RestrictedParser(bindingPower, this);
            _parserCache[bindingPower] = parser;
          }
          return parser;
        }
    
        private struct PostfixParser
        {
          public int LeftBindingPower { get; }
          public Parser[] Parsers { get; }
    
          public PostfixParser(int LeftBindingPower, Parser[] Parsers)
          {
            this.LeftBindingPower = LeftBindingPower;
            this.Parsers = Parsers;
          }
        }
    
        public class RestrictedParser : Parser
        {
          public int BindingPower { get; }
          public ChoiceParser BaseParser;
          public RestrictedParser(int BindingPower, ChoiceParser BaseParser)
          {
            this.BindingPower = BindingPower;
            this.BaseParser = BaseParser;
          }
    
          private int Parse(int startPos, string text, Parser[] parsers)
          {
            int pos = startPos;
            foreach (var parser in parsers)
            {
              pos = parser.Parse(pos, text);
              if (pos < 0)
                return pos;
            }
            return pos;
          }
    
          public override int Parse(int startPos, string text)
          {
            int pos = -1;
            foreach (var prefix in BaseParser._prefixParsers)
            {
              int newPos = Parse(startPos, text, prefix);
              if (newPos > 0)
              {
                pos = newPos;
                break;
              }
            }
            if (pos < 0)
              return -1;
    
            Console.Write(new string(' ', startPos));
            Console.WriteLine(text.Substring(startPos, pos - startPos));
    
            int curPos = pos;
            while (true)
            {
              int prevPos = curPos;
              foreach (var postfix in BaseParser._postfixParsers)
                if (postfix.LeftBindingPower > BindingPower)
                {
                  int newPos = Parse(curPos, text, postfix.Parsers);
                  if (newPos > curPos)
                  {
                    curPos = newPos;
                    break;
                  }
                }
              if (curPos == prevPos)
                break;
              Console.Write(new string(' ', startPos));
              Console.WriteLine(text.Substring(startPos, curPos - startPos));
            }
            return curPos;
          }
        }
    
        public override int Parse(int startPos, string text)
        {
          return Get(0).Parse(startPos, text);
        }
      }
    
      class Program
      {
        static void Main(string[] args)
        {
          var expr = new ChoiceParser();
          expr.Add(new IntParser());
          expr.Add("x");
          expr.Add("(", expr, ")");
          expr.Add("+", expr.Get(1000));
          expr.Add("-", expr.Get(1000));
          expr.Add(expr.Get(10), "+", expr.Get(10));
          expr.Add(expr.Get(10), "-", expr.Get(10));
          expr.Add(expr.Get(20), "*", expr.Get(20));
          expr.Add(expr.Get(20), "/", expr.Get(20));
          foreach (string s in new string[] { "*x", "+x", "x", "x+-x", "x-+x", "x+x", "x*123-123/x", "x*(123-123)/x", "x*123-x12", "x*x-(x+x)", "x*x+(x+)", "x*x/(x+12)"})
          {
            var pos = expr.Parse(0, s);
            Console.WriteLine("{0}, {1}, {2}", s, pos, pos == s.Length);
            Console.WriteLine();
          }
        }
      }
    }
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
    Пусть это будет просто:
    просто, как только можно,
    но не проще.
    (C) А. Эйнштейн
    Re[3]: Посоветуйте парсер
    От: AndrewVK Россия http://blogs.rsdn.org/avk
    Дата: 16.02.17 18:45
    Оценка:
    Здравствуйте, WolfHound, Вы писали:

    AVK>>antlr + пример калькулятора из поставки. Допиливаешь до нужного состояния грамматику и вперед.

    WH>1)Тогда уж лучше нитру.

    Нитру с ее немерлевым API на выхлопе парсера?

    WH>2)Генератор парсера для этой задачи это из пушки по воробьям.


    Если человек про парсеры почти ничего не слышал — в самый раз.

    WH>Тут реализован PEG parser с расширением, позволяющим легко разбирать операторы с приоритетами.


    Я тут вижу Пратта, а не ПЕГ.
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
    AVK Blog
    Re[4]: Посоветуйте парсер
    От: WolfHound  
    Дата: 16.02.17 18:58
    Оценка:
    Здравствуйте, AndrewVK, Вы писали:

    AVK>Нитру с ее немерлевым API на выхлопе парсера?

    АПИ там вполне C#ный. За этим специально следили.

    WH>>Тут реализован PEG parser с расширением, позволяющим легко разбирать операторы с приоритетами.

    AVK>Я тут вижу Пратта, а не ПЕГ.
    Плохо смотришь. Это гибрид. Там реализован приоритетный выбор. Те альтернативы проверяются в порядке добавления. И после того как первая разобралась остальные не проверяются.
    Добавить классы, которые реализуют предикаты и циклы тривиально.
    Плюс есть возможность завести множество правил. Что Пратт не позволяет.
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
    Пусть это будет просто:
    просто, как только можно,
    но не проще.
    (C) А. Эйнштейн
    Re: Посоветуйте парсер
    От: Икс Россия  
    Дата: 16.02.17 19:04
    Оценка: -1 :))
    Здравствуйте, SergASh, Вы писали:

    SAS>Ищу библиотеку для парсинга выражений и (не)равенств.

    SAS>Должна поддерживать
    SAS>....

    SAS>Посоветуйте если кто чем-то таким пользовался.


    Головой, без неё никак
    сайтом http://regexr.com/
    notepad++

    SAS>Спасибо


    На здоровье

    ps сначала тоже как и Вы пытался найти волебную палочку, потратил полдня, не нашёл. Затем на упомянутом сайте за полчаса освоил regex и теперь могу распарсить в уме поток мыслей 13 летнего юноши, который случайно увидел голую попу.
    Отредактировано 16.02.2017 19:10 Икс . Предыдущая версия .
    Re[2]: Посоветуйте парсер
    От: WolfHound  
    Дата: 16.02.17 19:20
    Оценка: +1
    Здравствуйте, Икс, Вы писали:

    Икс>Головой, без неё никак

    Икс>сайтом http://regexr.com/
    Икс>notepad++
    Это про тебя.
    http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags
    ... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
    Пусть это будет просто:
    просто, как только можно,
    но не проще.
    (C) А. Эйнштейн
    Re[3]: Посоветуйте парсер
    От: Икс Россия  
    Дата: 16.02.17 19:28
    Оценка: -1
    Здравствуйте, WolfHound, Вы писали:

    WH>Здравствуйте, Икс, Вы писали:


    Икс>>Головой, без неё никак

    Икс>>сайтом http://regexr.com/
    Икс>>notepad++
    WH>Это про тебя.
    WH>http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags

    (\w+) ага
    Re[4]: Посоветуйте парсер
    От: VladD2 Российская Империя www.nemerle.org
    Дата: 16.02.17 20:49
    Оценка:
    Здравствуйте, AndrewVK, Вы писали:

    AVK>Нитру с ее немерлевым API на выхлопе парсера?


    АПИ весь на классах. Ни одного нимерлового типа там не использовано. АСТ генерируется тоже в виде обычных классов донета. Для обхода можно использовать посетители. Ну, для такой задачи достаточно методов определяемых для правил. Вот пример того самого вычислителя выражений:
    https://github.com/rsdn/nitra/blob/master/Grammars/Samples/Calculator/Sample.Calc/SimpleCalc.nitra
    Есть что-то непонятное?
      [StartRule]
      syntax Expr
      {
        Value() : double;
        missing Value = double.NaN;
    
        | [SpanClass(Number)]
          Num        = Digits              { override Value = double.Parse(GetText(this.Digits)); }
        | Call       = Id '(' Id Id ')'    { override Value = 42.0; }
        | Rounds     = '(' Expr ')'        { override Value = Expr.Value(); }
    
        precedence Additive:
        | Add        = Expr sm '+' sm Expr { override Value = Expr1.Value() + Expr2.Value(); }
        | Sub        = Expr sm '-' sm Expr { override Value = Expr1.Value() - Expr2.Value(); }
    
        precedence Multiplicative:
        | Mul        = Expr sm '*' sm Expr { override Value = Expr1.Value() * Expr2.Value(); }
        | Div        = Expr sm '/' sm Expr { override Value = Expr1.Value() / Expr2.Value(); }
        | Mod        = Expr sm '%' sm Expr { override Value = Expr1.Value() % Expr2.Value(); }
    
        precedence Power:
        | Pow        = Expr sm '^' sm Expr right-associative
                                           { override Value = System.Math.Pow(Expr1.Value(), Expr2.Value()); }
    
        precedence Unary:
        | Neg        = '-' Expr            { override Value = -Expr.Value(); }
      }


    WH>>2)Генератор парсера для этой задачи это из пушки по воробьям.

    AVK>Если человек про парсеры почти ничего не слышал — в самый раз.

    Учитывая, что Вольфхаунд привел реализацию того, что ему нужно это вряд ли может быть проблемой.

    WH>>Тут реализован PEG parser с расширением, позволяющим легко разбирать операторы с приоритетами.

    AVK>Я тут вижу Пратта, а не ПЕГ.

    +1

    PEG — это вообще формализм грамматики. Но тут и PackRat, так как нет мемоизации. Это рекурсивный спуск с приоритетами. Забыл как мужика завали, что его изобрел.
    Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
    Re[3]: Посоветуйте парсер
    От: SergASh  
    Дата: 16.02.17 22:38
    Оценка:
    Здравствуйте, WolfHound, Вы писали:

    За пример спасибо, правда я уже на антлре сделал. Нитру не решился
     
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.