Компилятор выражений

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

    Пример:
       выражение: «x + 10 == 5 * y / (1 + z*2)»;
       требуется уметь вычислять это выражение для любых значений x, y и z.

    И конечно при этом надо учитывать приоритеты операторов.

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

    Решение на Java, но может быть легко переведено на другие языки.



    Сначала о том, что мы получаем на выходе после компиляции строки. Это объект Expression (выражение) с методом execute(Map vars). Объект древовидный, в узлах операторы на листьях переменные или константы. По примеру, думаю все понятно:

    «x + 1 < y / (1+2)» =>

    [ "<" ]
        [ "+" ]
            [ x ]
            [ 1 ]
        [ "/" ]
            [ y ]
            [ "+" ]
                [ 1 ]
                [ 2 ]


    Узлы этого дерева бывают:
    • Бинарными — оператор и два операнда (+, -, == и т.д.)
    • Унарными— оператор и один операнд (отрицание и унарный минус)
    • Переменная — листовой узел с именем переменной
    • Строка
    • Число


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

    Теперь самое интересное — компиляция.
    Попробую рассказать понятно для хабралюдей незнакомых с конечными автоматами и грамматиками.
    Для ясности разберем простейшие выражения, которые могут содержать только числа, знаки «+», «-» и скобки Например 10 — (3 + 2 — (10 — 5)).

    Запишем формально:

    Выражение: Слагаемое [+ / - Слагаемое] *
    Слагаемое: число | (Выражение)


    Произносится так:
    Выражение есть Слагаемое, плюс-минус Слагаемое (вот это «плюс-минус Слагаемое» может повторяться от нуля до любого числа раз).
    Слагаемое есть число или Выражение в скобках.

    Алгоритм обработки глядя на формальную запись получается такой:

    построитьВыражение:
        X1 = построитьСлагаемое()

        пока в потоке «+» или «-»
            X2 = построитьСлагаемое();
            X1 = БинарныйУзел ( «+» или «-», X1, X2)
        конец цикла
        вернуть X1
    конец

    построитьСлагаемое:
        если в потоке '('
            X = построитьВыражение()
            вернуть X
        иначе
            вернуть число
    конец



    В приведенном компиляторе используется более сложная грамматика:

    S0 : S1 [ || S1] *
    S1: S2 [ && S2] *
    S2: S3 | ! S3
    S3: S4 | S4 == S4 | S4 != S4 | S4 <= S4 | S4 < S4 | S4 >= S4 | S4 > S4
    S4: S5 [«+» или «-» S5] *
    S5: S6 [«*» или «.» S6] *
    S6: 'string' | var | number | null | (S0) | - var | - number | - (S0)


    И собственно код:

    import java.util.Map;

    /**
    * Вычислимое Выражение
    */
    public abstract class Expression {
      
      /** Вычислить выражение для даных значений переменных */
      public abstract Object execute(Map<String, Object> values) throws Exception;
      
      
      /** Узел дерева — «Число» */
      static class Num extends Expression {
        private final long value;
        
        public Num(long x) {
          value = x;
        }
        
        @Override
        public Object execute(Map<String, Object> values) {
          return value;
        }
      }
      
      /** Узел дерева — «Строка» */
      static class Str extends Expression {
        private final String value;
        
        public Str(String x) {
          value = x;
        }
        
        @Override
        public Object execute(Map<String, Object> values) {
          return value;
        }
      }  

      /** Узел дерева — «Переменная» */
      static class Var extends Expression {
        private final String name;
        
        public Var(String name) {
          this.name = name;
        }
        
        @Override
        public Object execute(Map<String, Object> values) {
          return values.get(name);
        }
      }
      
      
      /** Узел дерева — «Унарный оператор» */
      static class Unary extends Expression {
        private final Expression expr;
        private final boolean not;
        
        public Unary(Expression e, String oper) {
          expr = e;
          not = "!".equals(oper);
        }
        
        @Override
        public Object execute(Map<String, Object> values) throws Exception {
          Object o = expr.execute(values);
          if(not)
            return !(Boolean)o;
          else
            return -(Long)o;
        }
      }  
      
      

      /** Узел дерева — «Бинарный оператор» */
      static class Binary extends Expression {
        private final Expression x1;
        private final Expression x2;
        private final String op;
        
        public Binary(Expression x1, Expression x2, String op) {
          this.x1 = x1;
          this.x2 = x2;
          this.op = op;
        }

        @Override
        public Object execute(Map<String, Object> values) throws Exception {
          Object o1 = x1.execute(values);
          Object o2 = x2.execute(values);
          
          Class type = commonType(o1, o2);
          
          if(type == String.class)
            return execStr(o1 != null? o1.toString() : null, o2 != null ? o2.toString() : null);
          else if(type == Long.class)
            return execNum((Long)o1, (Long)o2);
          else
            return execBool((Boolean)o1, (Boolean)o2);
        }
        
        private Class commonType(Object o1, Object o2) {
          if(o1 == null || o2 == null || o1 instanceof String || o2 instanceof String)
            return String.class;
          if(o1 instanceof Long && o2 instanceof Long)
            return Long.class;
          return Boolean.class;
        }
        
        private Object execStr(String s1, String s2) throws Exception {
          if("==".equals(op))
            return (Boolean)(s1 == null ? s2 == null : s1.equals(s2));
          if("!=".equals(op))
            return (Boolean)(s1 == null ? s2 != null : !s1.equals(s2));
          if("+".equals(op))
            return (String)(s1 == null ? s2 : s1 + (s2 == null ? "" : s2));
          throw new Exception("Illegal String operator: " + op);
        }

        private Object execBool(boolean q1, boolean q2) throws Exception {    
          if("&&".equals(op))
            return q1 && q2;
          if("||".equals(op))
            return q1 || q2;
          if("==".equals(op))
            return q1 == q2;
          if("!=".equals(op))
            return q1 != q2;
          throw new Exception("Illegal Boolean operator: " + op);
        }

        private Object execNum(long n1, long n2) throws Exception {    
          if("==".equals(op))
            return (Boolean)(n1 == n2);
          if("!=".equals(op))
            return (Boolean)(n1 != n2);
          if("<".equals(op))
            return (Boolean)(n1 < n2);
          if("<=".equals(op))
            return (Boolean)(n1 <= n2);
          if(">".equals(op))
            return (Boolean)(n1 > n2);
          if(">=".equals(op))
            return (Boolean)(n1 >= n2);
          if("+".equals(op))
            return (Long)(n1 + n2);
          if("-".equals(op))
            return (Long)(n1 - n2);
          if("*".equals(op))
            return (Long)(n1 * n2);
          if("/".equals(op))
            return (Long)(n1 / n2);
          
          throw new Exception("Illegal Long operator: " + op);
        }
      }
    }

    * This source code was highlighted with Source Code Highlighter.


    И сам компилятор:

    import java.util.HashMap;
    import java.util.Map;

    import org.junit.Test;
    import static org.junit.Assert.assertTrue;

    /** Компилятор выражений */
    public class ExpressionBuilder {
      
      private String expression; // Строка с исходным выражением
      private int p = 0; // текущая позиция
      
      public static Expression build(String expression) {
        ExpressionBuilder builder = new ExpressionBuilder(expression);
        builder.skip(" ");
        Expression expr = builder.build(0);
        return expr;
      }
      
      private ExpressionBuilder(String expression) {
        this.expression = expression;
      }
      
      
      /** Построить узел выражения */
      Expression build(int state) {
        if(lastState(state)) {
          Expression ex = null;
          boolean isMinus = startWith("-");
          if(isMinus)
            skip("-");

          if(startWith("(")) {
            skip("(");
            ex = build(0);
            skip(")");
          }
          else
            ex = readSingle();
          if(isMinus)
            ex = new Expression.Unary(ex, "-");
          return ex;
        }
        
        boolean unarNot = state == 2 && startWith("!");
        if(unarNot)
          skip("!");
        
        /* Строим первый операнд */
        Expression a1 = build(state+1);
        if(unarNot)
          a1 = new Expression.Unary(a1, "!");
        
        // строим последущие операнды
        String op = null;
        while((op = readStateOperator(state)) != null) {
          Expression a2 = build(state + 1);
          a1 = new Expression.Binary(a1, a2, op);
          
        }
        return a1;
      }
      
      private static String [][] states = new String[][] {
        {"||"},
        {"&&"},
        {"!"},
        { "<=", ">=", "==", "!=", "<", ">"},
        {"+", "-"},
        {"*", "/"},
        null
      };
      
      private boolean lastState(int s) {
        return s+1 >= states.length;
      }
      
      private boolean startWith(String s) {
        return expression.startsWith(s, p);
      }
      
      private void skip(String s) {
        if(startWith(s))
          p+= s.length();
        while(p < expression.length() && expression.charAt(p) == ' ')
          p++;
      }
      
      
      private String readStateOperator(int state) {
        String[] ops = states[state];
        for(String s : ops) {
          if(startWith(s)) {
            skip(s);
            return s;
          }
        }
        return null;
      }
      
      /**
       * считываем из потока "простое" значение (имя переменной, число или строку)
       * @return
       */
      private Expression readSingle() {
        int p0 = p;
        // чиатем из потока строку
        if(startWith("'") || startWith("\"")) {
          boolean q2 = startWith("\"");
          p = expression.indexOf(q2 ? '"' : '\'', p+1);
          Expression ex = new Expression.Str(expression.substring(p0+1, p));
          skip(q2 ? "\"" : "'");
          return ex;
        }
        
        // в потоке не строка => число или переменная
        while(p < expression.length()) {
          if(!(Character.isLetterOrDigit(expression.charAt(p))))
            break;
          p++;
        }
        
        Expression ex = null;
        if(p > p0) {
          String s = expression.substring(p0, p);
          skip(" ");
          try{
            // из потока прочитали число
            long x = Long.parseLong(s);
            return new Expression.Num(x);
          }
          catch(Exception e){}
          
          if("null".equals(s))
            return new Expression.Str(null);
          
          // не строка, не число и не null — значит переменная
          return new Expression.Var(s);
          
        }
        return null;
      }
      
      
      
      
      
      // для юнит-тестов
      public ExpressionBuilder(){}
      
      @Test
      public void testBuilder() throws Exception {
        String str = "qwerty";
        long n1 = 10;
        long n2 = 5;
        
        Map<String, Object> map = new HashMap<String, Object>();
        map.put("str", "str");
        map.put("n1", n1);
        map.put("n2", n2);
        
        Expression e = ExpressionBuilder.build("str != 'qwerty' && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3))");
        Boolean a = (Boolean) e.execute(map);
        Boolean b = !"qwerty".equals(str) && n1 / n2 >= 3 * (n2 + 10 / n1 * (2+3));
        assertTrue(a == b);
      }
    }


    * This source code was highlighted with Source Code Highlighter.


    Спасибо за внимание!
    Share post

    Comments 66

      0
      Спасибо большое за решение! Разберусь, перепишу на си и буду использовать в своих лабораторных =)
      • UFO just landed and posted this here
          0
          Уж поверьте, читаю по мере возможности. Вот в следующем семестре будем проектирование компиляторов проходить, сделаю статью про это, если кто-нибудь не напишет.
            +3
            Ахо, Сети, Ульман уже написали статью «про это». Большую такую.
              0
              В следующем семестре будем проходить таблицу умножения, сделаю статью про это, если кто-нибудь не напишет
                0
                =) Прошу прощения, не думал, что эта задача для вас окажется такой тривиальной. Просто мне она интересна.
                  0
                  Да? о чем тогда вообще на Хабре пишут? ;)
                  • UFO just landed and posted this here
            0
            Польская Инверсная Запись? Чувствуется что похоже, только загримировано. Так же формальные правила для построения дерева операций, которое потом обходится для вычисления.

            Или алгоритм построения дерева никак с ней не связан?
              +2
              Если посмотреть на дерево из примера без отступов то вы как раз польскую запись и увидите.
              Ну в общем да — огурцы с одной грядки :)
          • UFO just landed and posted this here
              –1
              может просто озадачить любой интерперетатор джаваскрипта, а в нем позвать eval?
                0
                чето как то слишком сложно всё… слишком на низком уровне что ли.
                  +2
                  > чето как то слишком сложно всё… слишком на низком уровне что ли.

                  Наоборот (если вы про автоматизированные средства построения сканеров и парсеров, типа javacc). Здесь вам не надо самому строить парсеры для LL / LR (1) — грамматик, здесь вы просто описываете формальную грамматику. Да, понадобится знать регулярные выражения, но, все же, это более эффективно и позволит избежать ошибок.

                  > Ох уж эти велосипедисты

                  Ну, есть и работы научные и академические, а не только прикладные-потребительские. Кто-то же за вас написал эти автоматизаторы :) Кому-то просто потреблять — мало, им нужно знать, как это работает. И «изобретение велосипеда» — это отличное подтверждение практикой изученной теории.
                    +2
                    В университете — да.
                    А если этим будет заниматься мой подчинённый в рабочее время — настучу по голове.
                      +1
                      > В университете — да.
                      > А если этим будет заниматься мой подчинённый в рабочее время — настучу по голове.

                      Да не только в университетах. Просто условно все задачи можно разделить на:

                      — задачи на инструментарий (написание языков, сред, фреймворков, виджетов и т.д.)
                      — прикладные задачи «на данные», с использованием уже готовых вещей из первого пункта.

                      Естественно, для выполнения первых нужны более глубокие знания — как в конкретной технологии, так и в общей, фундаментальной.

                      Все это вытекает из усиления абстракций, habrahabr.ru/blogs/webdev/45552/#comment_1152704 — здесь кратко говорил об этом.

                      И не только в университетах, есть и такие «работы», на которых «подчиненные» пишут для потребителей усиленные абстракции. Далее некоторые потребители сами становятся созидателями (относительно нового уровня абстракции). Вы пользуетесь каким-нибудь фреймворками? Их разве в университетах написали? Нет, так же люди ходят на работу, так же им деньги за это платят.
                        0
                        Вы пытаетесь делать слишком далеко идущие выводы :)

                        Я говорю о конкретной простой вещи. Если я попрошу подчинённого добавить в проект компилятор арифметических выражений, а он мне принесёт что-то вроде вышенаписанного, у меня будут большие сомнения по поводу его вменяемости.

                        То, что В ПРИНЦИПЕ было бы неплохо уметь писать фреймворки и т.п. — ясно и так. Я лишь против изобретения велосипедов в конкретных случаях.
                          +1
                          > Вы пытаетесь делать слишком далеко идущие выводы :)

                          Я никогда не пытаюсь ;) (либо делаю, либо нет) я лишь размышляю, и делаю выводы (а далеко идущие или нет — это уже другой вопрос)

                          Да, все зависит лишь от задач конторы. Если у вас прикладные задачи, для которых уже написано тонна готовых решений — нет смысла писать на «ассемблере» интернет-магазин ;)

                          Если же контора занимается разработкой новых подходов, способных «осчастливить человечество», то — у них и цели здесь другие. Но они так же — работаю и получают зарплату (и, если оценивать справедливо, — получают больше прикладных программистов, поскольку и знаний применяют больше)

                          По поводу же велосипедов — тоже от уровня и требований зависит. К примеру, у меня в JS всегда свой фреймворк был написан (который легче и быстрее всех этих Prototype'ов.js, jQuery и т.д.).

                          А полностью подавлять инициативу и самообразование подчиненных — тоже не стоит (иначе — наймите лучше «кодеров» (программистов без собственной мысли), которые будут просто выполнять приказы, не двигаясь ни вправо, ни влево, а не программистов). Наоборот, компания должна сопутствовать образованию своих сотрудников.

                          Но, другое дело, когда эти «научные изыскания» совсем не связанны с работой — тогда да, здесь уже другой разговор (и вы имеете в виду именно этот случай; я понимаю).
                  +1
                  или jflex + cup (агалоги Си-шных flex'a и bison'a, который часто используются для этих целей) — так же строят сканер и парсер по заданным формальным грамматикам.
                    0
                    Antlr весьма неплох.
                    0
                    Вычислимое — Вычисляемое!
                    И да, зачем изобретать велосипед? «Всё уже украдено до нас».
                      0
                      Про «вычислимое — вычисляемое» можно поспорить. Вычислимое — которое может быть вычислено. Вычисляемое — находящееся в процессе вычисления. Мне кажется первое больше по смыслу подходит.

                      Про велосипед — согласен. Почему-то не получилось быстро найти готового решения (nanodust, спасиба за инфу!) вот и сделал сам. И мне кажется, что как информация для развития эта статья вполне подходит.
                      +3
                      Никогда не любил этот метод :(
                      Если нужно просто вычислить значение выражения – то куда проще делать это просто в 2 стека.
                      Старый добрый алгоритм, который значительно проще чем разбиение на дерево.

                      Если кому интересно если есть те, кто не знает могу рассказать. :)
                        +1
                        Давай ^.^
                          +1
                          Интересно, рассказывайте :)
                            0
                            Расскажите про два стека!
                            Только мне кажется, что я знаю про что вы ,-)
                            И я вам сразу хочу напомнить, что автор поста обходится одним стеком (для хранения локальных переменных) и его подход позволяет не следить за стеком вручную — следит язык. Мне очень интересно посмотреть, как вы будете отлаживаться, вылавливать ошибки, тестировать… как от малейшей оплошности вашу аж двустековую машину будет развозить в разные стороны…
                            Кроме того, метод, про который тут рассказано — это классика (реалиация странновата, правда; всё было бы проще и стройнее, если бы операции хранились бы не в виде сточек, а в виде объектов, но это уже частности и детали).
                              0
                              Эм… я не смог найти у автора стек… возможно, плохо искал…
                              Метод в 2 стека не мой. Это классическое решение задачи на С.
                              Разумеется, можно всё запихать в 1 стек, но в оригинале использовалось 2.

                              Завтра днём опишу и выложу :)
                              А сейчас у меня 5 утра и спать хочицо :)
                                0
                                Каждый вызов функции — это работа со стеком. Но вы правы — неявная, и вы её не видете. Именно неявность гарантирует, что pop-ов будет солько же, сколько push-ей, и всё будет вовремя и хорошо. А явная работа со стеком — это жуткое болото. Ещё написать такое можно, но вот поддерживать, развивать… не дай бог. Поэтому закладывать сразу стековы дизайн можно только если вы (а) пишите что-то очень маленькое на один день, (б) для вас очень важно быстродействие (обычно стек быстрее) или (ц) вы просто самоубийца :-)
                                  0
                                  эм… мы наверно о разных стеках разговариваем… :)
                                  в общем минут через 15 выложу пост :)
                              0
                              Вы случайно не про метод рекурсивного спуска? Где стек представляет из себя стек вызова функций разбора + стек символов текста.
                              +3
                              C YACC не нужно изобретать велосипед, к нему к тому же есть java-обертка.
                                +1
                                Если бы не дата рождения, подумал бы что автор просто лабу по программированию делал :)
                                  0
                                  Я помню мы лабы такие делали на первых курсах, правда на паскале :)
                                    –2
                                    хе-хе… точно :)
                                    году в 97-98м я в шутку написал подобную лабу в виде обертки, которая принимала выражение, оборачивала паскалем, компилировала с помощью строчного компилятора и запускала скомпиленную прогу которая выдавала ответ. после чего убедил препода что лаба должна быть засчитана т.к. четких ограничений не налагалось а задание было сформулировано так что мой метод тоже подходил :))) в итоге препод меня на лабы перестал пускать, это была «последняя капля». ставил «автомат» лишь бы меня не видеть :D
                                      0
                                      нихуёвый eval, я приблизительно так же делал для реализации метода градиентного спуска на C ^_^
                                    +3
                                    Я против велосипедов, но я за такие пуликации. Слава тем, кто пишет быстро, используя уже готовые библиотеки; но дважды слава тем, то знает, как эти библиотеки устроены, какие алгоритмы используют.
                                    Недостаток статьи — очень много кода. Было бы полезней привести пример разбора выражений только с двумя операциями (скажем, сложение и умножение). И понять было бы проще и расширить проще.
                                    Ну и надо было всё называть своими именами. Автор, как я понял, использует метод рекурсивного спуска.
                                      0
                                      Хм, думаю встраивание логики вычисления выражения в классы, описывающие AST, не есть хорошо. Вообще, для таких случаев в языках без алгебраических типов и сопоставления с образцом используют паттерн «посетитель». Да и использовать строки для хранения типа операторов, как-то не очень… Собственно, то же касается bool'а для того, чтобы определять, унарный ли это минус или not. Кстати, не стоит делать поля элементов AST private'ами.

                                      Не совсем правильно называть приведённую штуку «компилятором выражений». Скорее всего, это лексический + синтаксический анализаторы + вычислитель (evaluator). Всё-таки компилятор должен порождать код или байт-код, а тут интерпретируется сразу AST.

                                      Наконец, скажу одно слово: ANTLR (в дополнение к упомянутому yacc'у).
                                        0
                                        Круто, сюда прикрутить парочку методов многомерной оптимизации и получим утилтку для нахождения корней скалярной функции векторного аргумента.
                                          0
                                          Друзья, по-моему, вы загоняетесь по поводу использования ANTLR-ов и тому подобных решений. Всё намного проще: java-source.net/open-source/expression-languages
                                            +14
                                            Вот набросал на прологе что-то похожее
                                            integer(I) -->
                                                    digit(D0),
                                                    digits(D),
                                                    { number_chars(I, [D0|D])
                                                    }.

                                            digits([D|T]) -->
                                                    digit(D), !,
                                                    digits(T).
                                            digits([]) -->
                                                    [].

                                            digit(D) -->
                                                    [D],
                                                    { code_type(D, digit)
                                                    }.

                                            alnum([H | T]) :- code_type(H, alnum), alnum(T), !.
                                            alnum([]).

                                            identifier(A) -->
                                                [H | T],
                                                {
                                                 code_type(H, alpha),
                                                 alnum(T),
                                                 string_to_atom([H | T], A)
                                                }.

                                            expression0(Expr) -->
                                                integer(Expr),
                                                !.

                                            expression0(Expr) -->
                                                identifier(Expr),
                                                !.

                                            expression0(Expr) -->
                                                "(",
                                                expression(Expr),
                                                ")".

                                            operand(+) --> "+".
                                            operand(-) --> "-".
                                            operand(*) --> "*".
                                            operand(/) --> "/".

                                            expression(Expr) -->
                                                expression0(Expr0),
                                                operand(Op),
                                                expression(Expr1),
                                                {Expr =.. [Op, Expr0, Expr1]},
                                                !.

                                            expression(Expr) -->
                                                expression0(Expr).

                                            eval(Str, Vars, Res) :-
                                                phrase(expression(Expr), Str),
                                                eval0(Expr, Vars, Res).

                                            eval0(Expr, Vars, Res) :-
                                                Expr =.. [Op, Arg1, Arg2],
                                                eval0(Arg1, Vars, Arg1Evaled),
                                                eval0(Arg2, Vars, Arg2Evaled),
                                                Expr1 =.. [Op, Arg1Evaled, Arg2Evaled],
                                                Res is Expr1,
                                                !.

                                            eval0(N, _, N) :- number(N), !.
                                            eval0(K, Vars, V) :- member(K=V, Vars).
                                                


                                            Как работает:
                                            ?- eval("(2+(6/3)*a)*(4+123-b)", [a=2,b=122], Res).
                                            Res = 30.
                                              0
                                              А для чего phrase?
                                              Работать ведь будет если и только последние 3 определения оставить, или я ошибаюсь?
                                                0
                                                в данном случае phrase нужен чтоб распарсить строку в прологовский терм.
                                                3 ?- Str = "(2+(6/3)*a)*(4+123-b)", phrase(expression(Expr),Str).
                                                Str = [40, 50, 43, 40, 54, 47, 51, 41, 42|...],
                                                Expr = (2+6/3*a)* (4+ (123-b)).


                                                  0
                                                  Ясно.
                                                  Хотя конечно как по мне, малой величине кода тут по большей части способствует то, что основную работу берут на себя =… и is
                                              +1
                                              помню легко это делал на С# на втором курсе, сначала переводя все в польскую нотацию (по заданию), а потом регэкспом
                                                +5
                                                Не верю. Польскую нотацию нельзя разобрать регекспом.
                                                Она относится к контекстно свободным грамматикам и для разобра требует бесконечное (в общем случае) количество состояний. А регексп определеяет конечный(!) автомат. То есть машину с конечным количеством состояний. Регекспом можно ограничться только если ограничить количество волженных конструкций; но уже при глубине 3 регексп становится нечеловеческим.
                                                Так-что, вы либо что-то путаете, либо вы на втором курсе рассматривали очень упрощённый и ограниченный случай.
                                                  +3
                                                  Он не путает. Современные Perl-style регексы это не регулярные выражения.
                                                    +1
                                                    Гм. И ими таки можно разобрать КС-грамматику? А примерчик? Серьёзно, я вот листаю доку и ничего, не укладывающегося в регулярную грамматику, не вижу. Способа разобрать хотя бы скобочное выражение — тоже.
                                                      +3
                                                      Backreference'ы в Перловских регексах уже какбэ убивают «регулярность», вот это:

                                                      (.*)\1

                                                      не регулярное выражение, и не контекстно-свободная грамматика.

                                                      Тут еще такая штука: в большинстве реализаций используется backtracking, а не DFA, и этот самый backtracking дает жуткое время выполнения в некоторых особых случаях.
                                                +1
                                                Замените первое предложение на фразу про образовательные цели и статья приобритет качественно другой окрас.
                                                  +3
                                                  Кроме указанных выше jflex/antlr и прочих можно взять готовую библиотеку, например www.japisoft.com/formula/.
                                                    0
                                                    А есть ли библиотека делающая подобное на C или на худой конец на C++?
                                                    Спасибо.
                                                      0
                                                      flex (сканер) + bison (парсер)
                                                        0
                                                        Если C++ — худой конец, то, конечно, Spirit рекомендовать сложно, но всё же. С такими «калькуляторными» примерами он неплохо справляется.
                                                        0
                                                        Если забыть про стандартный грамматический подход, то интересный алгоритм разбора выражений с прописывал Грис в книге про компиляторы.
                                                        Заводятся два стека, на одном операции, на другом выражения. В определённый момент разбора с обоих стеков снимаются вершины, комбинируются и перекладываются на второй.
                                                          0
                                                          Этот подход и есть — стандартный. Просто сейчас в качестве одного из стеков(магазина) используется стек функций.
                                                            0
                                                            Алгоритм-то стандартный, но мне лично проще думать в терминах AST и рекурсивного спуска, с которыми можно работать не только в операторной грамматике.
                                                          0
                                                          Я когда надо было вычислять выражения в приложении генерировал простенький исходник и компилировал его gcc, ответ писал в файл. Решение некрасивое, но быстрое.
                                                            0
                                                            Я, наверное, поздно, но нечто подобное мне доводилось делать на Haskell. Получилось короче, чем приведенный выше на Прологе. Кому-нить интересно?
                                                              0
                                                              Напиши, интересно. Можно даже отдельным постом с пояснениями. Так понимаю, в хаскеле используя Parsec?
                                                                0
                                                                смотри ниже… что-то я не нашел подсветки для Haskell
                                                                  0
                                                                  спасибо.
                                                                  хе-хе, чисто субъективно, на прологе проще, выразительнее =)
                                                                    0
                                                                    Не знаю, мне сложно судить. Для того, чтобы оценить выразительность, надо знать оба языка, а Пролог как-то не привелось посмотреть.

                                                                    Но, если на первый взгляд, можно убрать некрасивую функцию makeLatex — и получится сравнимо.
                                                              0
                                                              Простенькая программа, разбирающая выражения при помощи стандартной библиотеки компилятора GHC, и преобразующая их в формат Latex. Использовать ее предполагалось в интерактивном режиме компилятора для разбора выражений а ля Matlab на лету и вставки в исходник диплома.

                                                              Это был вроде как эксперимент, я потом сравнивал результат с довольно своим ж уродливым кодом на Elisp и ужасался своим страданиям.

                                                              В общем-то, если нужно тупо вычислять выражения, то получится раза в полтора меньше. :-)

                                                              module Parser (runExpr) where

                                                              import IO
                                                              — import System
                                                              import Text.ParserCombinators.Parsec
                                                              import Text.ParserCombinators.Parsec.Expr hiding (Operator)

                                                              data Tree a = Leaf a
                                                              | Sum (Tree a) (Tree a)
                                                              | Substract (Tree a) (Tree a)
                                                              | Multiply (Tree a) (Tree a)
                                                              | Divide (Tree a) (Tree a)
                                                              | Power (Tree a) (Tree a)
                                                              deriving Show

                                                              type ExprTree = Tree String

                                                              type Operator = (ExprTree -> ExprTree -> ExprTree)

                                                              (+!) :: Operator
                                                              (+!) a b = Sum a b

                                                              (-!) :: Operator
                                                              (-!) a b = Substract a b

                                                              (*!) :: Operator
                                                              (*!) a b = Multiply a b

                                                              (/!) :: Operator
                                                              (/!) a b = Divide a b

                                                              (^!) :: Operator
                                                              (^!) a b = Power a b

                                                              run :: Show a => Parser a -> String -> IO ()
                                                              run p input
                                                              = case (parse p "" input) of
                                                              Left err -> do{ putStr «parse error at „
                                                              ; print err
                                                              }
                                                              Right x -> print x

                                                              runExpr :: String -> String
                                                              runExpr input
                                                              = case (parse expr “» input) of
                                                              Left err -> show err
                                                              Right x -> (makeLatex x)

                                                              expr :: Parser ExprTree
                                                              expr = buildExpressionParser table factor
                                                              <?> «expression»

                                                              table = [[op "^" (^!) AssocLeft]
                                                              ,[op "*" (*!) AssocLeft, op "/" (/!) AssocLeft]
                                                              ,[op "+" (+!) AssocLeft, op "-" (-!) AssocLeft]]
                                                              where
                                                              op s f assoc
                                                              = Infix (do{ string s; return f}) assoc

                                                              factor :: Parser ExprTree
                                                              factor = do{ char '('
                                                              ; x < — expr
                                                              ; char ')'
                                                              ; return x
                                                              }
                                                              <|> symbol
                                                              <?> «simple expression»

                                                              symbol :: Parser ExprTree
                                                              symbol = do{ s < — letter
                                                              ; ss < — many (alphaNum <|> char '_')
                                                              ; return (Leaf (s:ss))
                                                              }
                                                              <?> «symbol»

                                                              makeLatex :: ExprTree -> String
                                                              makeLatex x = case x of
                                                              (Leaf name) ->
                                                              case (parse subsymbolParser "" name) of
                                                              Left err -> «Subsymbol parse error»
                                                              Right x -> x
                                                              (Sum l r ) -> (makeLatex l) ++ " + " ++ (makeLatex r)
                                                              (Substract l r) -> (makeLatex l) ++ " — " ++ (makeLatex r)
                                                              (Multiply l r) -> (makeLatex l) ++ " \\cdot " ++ (makeLatex r)
                                                              (Divide l r) -> "\\frac{" ++ (makeLatex l) ++ "}{" ++ (makeLatex r) ++ "}"
                                                              (Power l r) -> "(" ++ (makeLatex l) ++ ")" ++ "^{" ++ (makeLatex r) ++ "}"

                                                              subsymbolParser :: Parser String
                                                              subsymbolParser = do{ m < — many1 alphaNum
                                                              ; do{char '_'; s < — (many alphaNum)
                                                              ; return (m ++ "_{" ++ s ++ "}")
                                                              }
                                                              <|> return m
                                                              }
                                                                0
                                                                Ндаа. Я умный :) Был по крайней мере. Нам в педвузе на практике задали сделать калькулятор. Так вот я извратился и сделал что-то такое. Правда с меньшим числом классов и сильно рекурсивными функциями.
                                                                Это потом когда появился инет и я прочитал книгу дракона я понял что сделал через .. очень странную реализацию классического парсера. Жаль, конечно, что изобретал велосипед, но я все равно горд собой, что додумался этого сам.
                                                                Кстати кроме книги дракона я наткнулся на сайт softcraft.ru, на есть котором довольно понятные уроки по грамматикам и трансляторам. Это если кому тема интересна.
                                                                .

                                                                Only users with full accounts can post comments. Log in, please.