Синтаксический разбор арифметических выражений

Дерево выражения

Рассмотрим арифметические выражения с обычным приоритетом операций. Сложение (+) и вычитание (-) имеют равный приоритет и более низкий (выполняются позже), чем умножение (*) с делением (/). Кроме этого, пусть существует унарный минус: -5, или -(3+5), или 3+-5=3+(-5). Несмотря на привычную операционную запись арифметических выражений, соответствующие действия являются функциями. Эти функции или бинарны (имеют два аргумента): plus(x, y) это "x+y" или унарны (один аргумент): inv(x) - это -(x).

Арифметическое выражение представимо в виде дерева. Например, дерево выражения 1*2 + 3*4 в корне имеет операцию сложения "+" и затем две ветви, в каждой из которых происходит умножение "*". В общем случае вызов вложенных друг в друга функций всегда образует дерево: 

   1*2 + 3*4
   plus(mult(1,2), mult(3,4))
Будем описывать арифметическое выражение (функцию) типа op(lf, rt) при помощи структуры вида {op, lf, rt}, где op - это тип операции, lf - первый аргумент, и rt - второй. Так, выражение 1*2+3*4 имеет следующее представление:
{ op: "+",
  lf: { op: "*", lf: { op:"N", lf: 1},  rt: { op:"N", lf: 2}},
  rt: { op: "*", lf: { op:"N", lf: 3},  rt: { op:"N", lf: 4}}
}
Статическая функция calc класса Parser, вычисляющая выражение выглядит следующим образом:
function Parser(){ }
 
Parser.calc = function (expr)
{
   switch(expr.op){
      case "N":                                            // число (Number)
         return expr.lf;
      case "+" :                                           // сложение
         return this.calc(expr.lf) + this.calc(expr.rt);
      case "-" :                                           // вычитание
         return this.calc(expr.lf) - this.calc(expr.rt);
      case "*" :                                           // умножение
         return this.calc(expr.lf) * this.calc(expr.rt);
      case "/" :                                           // деление
         return this.calc(expr.lf) / this.calc(expr.rt);
      case "M" :                                           // унарный минус (Minus)
         return -this.calc(expr.lf);
   }
}
Результат работы этой функции с выражением 1*2+3*4 в виде структуры, приведенной выше, равен 14. Аналогичный вид имеет функция Parser.get(expr), которая печатает выражения в виде строки типа: ((1*2)+(3*4)).

Порождающая грамматика

Синтаксис арифметических выражений (с учетом приоритета операций) будем задавать следующей порождающей грамматикой: 

   E    :-   T1 + E   |  T1 - E  |  T1
   T1   :-   T2 * T1  |  T2 / T1 |  T2
   T2   :-  -T3       |  T3
   T3   :-   N        |  (E)
Грамматика имеет смысл правил, по которым можно делать замены символов E, T1, T2, T3. В процессе таких замен происходит создание (порождение) некоторого арифметического выражения. Дерево начинает строиться с терма E (expression). Его можно заменить на одно из трех выражений (разделённых вертикальной чертой) из первой строки, например на: T1 + E. Затем необходимо сделать две замены для T1 и E, например (T2*T1) + T1. Далее, (T3*T2) + T2 и т.д., пока не доберёмся до числа N, на котором порождение останавливается.

Правила первой строки могут порождать цепочки T1 + T1 + T1 или T1 + T1 - T1 произвольной длины. Повторение терма E в конце правила E :- T1 + E образует "хвостовую" рекурсию, которая и генерит эти цепочки. Аналогичная хвостовая рекурсия стоит в правилах второй строки, определяющей структуру каждого слагаемого. Это даёт выражения вида T2*T2/T2*T2. Будем считать, что операции в таких цепочках выполняются слева направо: T2*(T2/(T2*T2)).

Фактически три терма T1,T2,T3 соответствуют трём уровням приоритета для операций (+ -), (* /) и унарного минуса (-). Подстановка правила T3 :- (E) из последней строки порождает вложенные скобки (..(..)..) любой глубины.

Вещественное число NUM также можно описать при помощи порождающей грамматики: 

   N    :-  I.I | I
   I    :-  D I | D
   D    :-    0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Впрочем, это делать не обязательно и стоит воспользоваться средствами JS для конверации строки в число.

Генерация случайных выражений

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

Parser.getRandE = function (max)
{
   switch(max-- > 0 ? MS.rand(3): 0){
      case 0: return this.getRandT1(max);                           // T1
      case 1: return this.getRandT1(max)+"+"+this.getRandE(max);    // T1+E
      case 2: return this.getRandT1(max)+"-"+this.getRandE(max);    // T1-E
   }
}
Parser.getRandT1 = function (max)
{
   switch(max-- > 0 ? MS.rand(3): 0){
      case 0: return this.getRandT2(max);                           // T2;
      case 1: return this.getRandT2(max)+"*"+this.getRandT1(max);   // T2*T1
      case 2: return this.getRandT2(max)+"/"+this.getRandT1(max);   // T2/T1
   }
}
Parser.getRandT2 = function (max)
{
   if( MS.rand(10) )
      return this.getRandT3(max);                                   // T3;
   return "-"+this.getRandT3(max);                                  // -T3;
}
Parser.getRandT3 = function (max)
{
   if(max-- > 0 ? MS.rand(10): 0)
      return "("+this.getRandE(max)+")";                            // (E)
   return MS.rand(100);                                             // N
}
  • (18/46)/(59)*(32)+(55)/(10)-46/61/72+62*34
  • (48*96+1-26)*(30+98)*39/47/4-(86)+(-3)/44*55-71-76+25
  • (93*38+9)-(42-8)+15*51/55+42*18+94-74
  • 56*(51)/(95)/32+(31+14)
  • (77-92)*(14+61)*-(26)+58*(24)*46/81
  • (95/7)*(16+30)/-(94)/76+(20)+-(49)/33*-79+24--80
  • (19)-(75+76)/(63)*67*10
  • (-10*91-22)*(74)*(15)*77+(92-8)/(15)/81*73+(14)
  • (-40*2)/(-62-12)/(34)*55
  • (9)-(77)/(43)*82/88+(21)+54-54+-65

    • Функция MS.rand(3) возвращает равновероятно 0,1 или 2, т.е. MS.rand(n) равна Math.floor(Math.random()*n). Параметр max устраняет очень длинные рекурсии. После каждого вызова он уменьшается и, когда достигает нуля, вызываются "нерекурсивные" грамматические правила. Функции getRandT2 и getRandT3 несколько отличаются и уменьшают вероятность унарного минуса и повышают вероятность появления скобок.

    Символы вне грамматики

    В арифметическом выражении будем допускать пробельные символы и комментарии: 

    // строчные (до конца строки)
/* блочные - между этими символами */
    Как и всё остальное, их можно описать при помощи грамматики, но эффективнее игнорировать эти символы на этапе сканирования строки. Проще всего использовать регулярные выражения:
    st = st.replace(/\/\/.*/g, " ");          // удаляем строчные комментарии (. - любой, кроме \n)
    st = st.replace(/\/\*[\s\S]*?\*\//g, ""); // удаляем блочные комментарии (нет вложений!)
    st = st.replace(/\s+/g, "");              // удаляем переносы строк и лишние пробелы
    Однако это способ лишает возможности указывать в исходной строке положение синтаксических ошибок (если таковые присутствуют). Поэтому, напишем более громоздкую функцию пропуска незначимых для выражения символов, которая не изменяет строки.

    Если комментариев нет - достаточно следующей функции:

    function Parser()
    {
       this.n = 0;                                             // текущее полжение при парсинге в строке
    }
     
    Parser.skip = function (st)
    {                              // пропускаем пробелы
       while(this.n < st.length && " \t\n\r".indexOf(st.charAt(this.n)) >= 0 )
          this.n++;
       return (this.n < st.length)? this.n: -1;
    }
    Текущее положение анализатора в строке хранится в переменной Parser.n. Функция Parser.skip(st) принимает строку st и возвращает новое положение, после пропуска (начиная с Parser.n) всех пробельных символов (меняя в себе Parser.n). При дохождении до конца строки, она возвращает -1.

    Если есть комментарии, то функцию необходимо усложнить:

    Parser.skip = function (st)
    {
       while(this.n < st.length && " \t\n\r".indexOf(st.charAt(this.n)) >= 0 )
          this.n++;                                            // пропускаем пробелы
       if(this.n >= st.length)
          return -1;                                           // достигли конца строки
     
       if(st.charAt(this.n)==="/" && this.n+1 < st.length){    // возможны комментарии:
     
          if(st.charAt(this.n+1)==="/"){                       // строчный
             this.n += 2;
             while(this.n < st.length && st.charAt(this.n)!=="\n" )
                this.n++;
             return this.skip(st);                             // вские \r и пробелы в начале след.
          }
     
          if(st.charAt(this.n+1)==="*"){                       // блочный
             this.n += 2;
             while(this.n+1 < st.length && (st.charAt(this.n) !== "*" || st.charAt(this.n+1) !== "\/"))
                this.n++;
             this.n += 2;
             return this.skip(st);                             // пробелы после комментариев
          }
       }
      return (this.n < st.length)? this.n: -1;
    }
    Чтобы её протестировать, создадим два элемента textarea с соответствующими id и напишем следующий код:
    var st1  = document.getElementById('skip_src_id').value;
    var st2  = "";
    Parser.n = 0;
    while( Parser.skip(st1) >= 0 )
       st2 += st1.charAt(Parser.n++);
    document.getElementById('skip_des_id').value = st2;

    Результаты работы :

    Отметим, что функция Parser.skip не устраняет вложенные комментарии /* /* */ */. Для этого её необходимо модифицировать, подсчитывая число открывающихся (/*) и закрывающихся (*/) скобок. Впрочем, для языков, поддерживающих строки, необходимо учесть наличие таких последовательностей внутри строк, например: /* " /*" */. Поэтому ограничимся запретом вложенных комментариев.

    Синтаксический разбор

    Перейдём теперь к синтаксическому разбору строки, в результате которого получится дерево выражения. Стартом для парсинга будет служить функция:

    Parser.parse = function (st)
    {
       this.n   = 0;                                           // текущее положение в строке
       this.err = "";                                          // сообщения о синтаксических ошибках
       return this.parseE(st);                                 // возвращает дерево выражения
    }
    Она обнуляет указатель this.n (текущее положение в анализируемой строке) и очищает строку с описанием синтаксических ошибок this.err. Затем вызывается функция парсинга терма E, реализующего грамматику E :- T1 + E | T1 - E | T1
    Parser.parseE = function (st)
    {
       var t1 = this.parseT1(st);                              // вычитываем терм T1
       if(this.skip(st) < 0)                                   // пропускаем пробелы и комметарии
          return t1;                                           // E :- T1 (в конце строки)
     
       switch(st.charAt(this.n)){
          case "+":                                            // E :- T1 + E
              this.n++;
              return {op:"+",  lf:t1,  rt:this.parseE(st) } ;
          case "-":                                            // E :- T1 - E
             this.n++;
              return {op:"-", lf:t1,  rt:this.parseE(st) } ;
       }
       this.err += "\nn="+this.n+"> parseE: no + or - after term T1";
       return t1;                                              // вернём undefined
    }
    После прочтения терма T1, выясняется наличие арифметических знаков + - и, если они есть, читается второй терм, который снова парсится функцией Parser.parseE (хвостовая рекурсия). Ошибка err будет генериться, например, для выражения вида "2 2".

    Аналогично выглядит функция парсинга терма T1 :- T2 * T1 | T2 / T1 | T2:

    Parser.parseT1 = function (st)
    {
       var t2 = this.parseT2(st);                              // вычитываем терм T2
       if(this.skip(st) < 0)                                   // пропускаем пробелы и комметарии
          return t2;                                           // T1 :- T2 (в конце строки)
     
       switch(st.charAt(this.n)){
          case "*":
             this.n++;                                         // T1 :- T2 * T1
             return {op: "*", lf: t2,  rt: this.parseT1(st) };
          case "/":                                            // T1 :- T2 / T1
             this.n++;
             return {op: "/",  lf: t2,  rt: this.parseT1(st) };
       }
     
       return t2;                                              // T1 :- T2 (нет * или /)
    }

    Здесь уже нет обработки синтаксической ошибки, так как после терма T2 не обязательно идёт операция "*" или "/" (может быть "+", "-").

    Похожа и функция для терма Т2, которая выделяет унарный минус. В предыдущих функциях пропуск пробелов в самом начале не вызывался, так как предполагалось, что это сделает Parser.parseT2(st), которая не может применяться к пустому терму. В результате строки типа "2+" сгенерят ошибку.

    Parser.parseT2 = function (st)
    {
       if(this.skip(st) < 0){
          this.err += "\nn="+this.n+"> parseT2: empty term";
          return;
       }
     
       if(st.charAt(this.n) === "-"){
          this.n++;
          return {op: "M", lf: this.parseT3(st) } ;            // T2  :-  -T3
       }
     
       return this.parseT3(st);                                // T2  :-   T3
    }
    Самой громоздкой оказывается функция парсинга последнего терма, которая должна вычитать вещественное число и убедиться, что открытая скобка в правиле "T3:-(E)" закрывается. В результате она имеет три точки в которых происходит генерация сообщения об ошибке. Эта функция использует функцию isdigit(st, n), возвращающую st.charAt(n)>="0" && st.charAt(n)<="9".
    Parser.parseT3 = function (st)
    {
       if(this.skip(st) < 0){                                  // нет терма T3
          this.err += "\nn="+this.n+"> parseT3: empty after unary minus";
          return;
       }
     
       if(st.charAt(this.n)==="(" ){                           // выражение в скобках
          this.n++;
          var expr = this.parseE(st);
          if(this.skip(st)<0 || st.charAt(this.n)!==")")
             this.err += "\nn="+this.n+"> parseT3: no close bracket )";
          else
            this.n++;
          return expr;
       }
     
       if( this.isdigit(st, this.n) ){                         // вычитываем число
          var n1=this.n;
          do  this.n++;                                        // целая часть
          while(this.n < st.length && this.isdigit(st, this.n))
     
          if(this.n < st.length && st.charAt(this.n) === "."){
             this.n++;
             while(this.n < st.length && this.isdigit(st, this.n))
                this.n++;                                      // дробная часть
          }
          return { op:"N", lf: parseFloat(st.substring(n1, this.n)) };
       }
     
       this.err += "\nn="+this.n+"> parseT3: unknown error";
       return;
    }

    Результаты работы :

    Более продвинутая грамматика

    Аналогичным образом можно написать парсер Calc для более продвинутых арифметических выражений, содержащих переменные и функции. Пусть программа состоит из набора выражений, разделённых точеой с запятой, типа: 

       x=5; y=z=8;
   u = x+y;
   sin(z)*exp(cos(u));
   sum(1,2,3,4,x);
    При этом некотрые функции, например, sin(x) имеют фиксированное число аргументов, а некторые sum, min - произвольное. Соответствующая грамматика имеет вид: 
       PRG :-  E; PRG    |   E
   E   :-  V = E     |   T1
   T1  :-  T2 + T1   |   T2 - T1  |  T2
   T2  :-  T3 * T2   |   T3 / T2  |  T3
   T3  :- -T4        |  +T4       |  T4
   T4  :-  NAME(LST) |   T5
   T5  :-  (E)       |   N        |  V
   LST :-   E,LST    |   E
   V   :-   NAME
    Терминальными символами являются N (вещественное число) и V :- NAME (переменная). NAME (как для имени функции, так и для имени переменной) является набором букв, цифр и символов подчёркивания (с цифры начинаться не должен). После парсинга выражение представимо структурой: {op: lf, rt}, где op - тип операции (см. Calc.calc), lf - выражение для первого аргумента, rt - для второго Для функций (op="F") первый аргумент (lf) - это имя функции, а второй (rt) - массив выражений - фактических аргументов функции.

    Результаты её работы :

    Введение в логику <
    > Переобразование логических выражений