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

Какая работа у парсера? Довольно просто. Он анализирует выражение. (Ага.) Хорошо, вообще-то Википедия дает хороший ответ:

Синтаксический анализатор - это программный компонент, который принимает входные данные (часто текст) и строит структуру данных - часто какое-то дерево синтаксического анализа, абстрактное синтаксическое дерево или другую иерархическую структуру - предоставляя структурное представление входных данных, проверяя правильность синтаксиса в процессе . Синтаксическому анализу могут предшествовать или следовать другие шаги, или они могут быть объединены в один шаг. Парсеру часто предшествует отдельный лексический анализатор, который создает токены из последовательности вводимых символов.

Итак, по сути, вот чего мы пытаемся достичь:

math expression => [parser] => some data structure (we'll get to this in a bit)

Давайте немного забегаем вперед: «… Парсеру часто предшествует отдельный лексический анализатор, который создает токены из последовательности вводимых символов». Речь идет о созданном ранее токенизаторе. Итак, наш синтаксический анализатор будет получать не исходное математическое выражение, а массив токенов. Итак, теперь у нас есть:

math expression => [tokenizer] => list of tokens => [parser] => some data structure

Для токенизатора нам пришлось придумывать алгоритм вручную. Для парсера мы будем реализовывать уже существующий алгоритм, алгоритм маневрового двора. Помните некоторую структуру данных выше? С помощью этого алгоритма наш синтаксический анализатор может предоставить нам структуру данных, называемую абстрактным синтаксическим деревом (AST), или альтернативное представление выражения, известное как обратная польская нотация (RPN).

Обратная польская запись

Начну с РПН. Снова из Википедии, RPN - это математическая запись, в которой каждый оператор следует за всеми своими операндами. Вместо, скажем, 3 + 4, RPN будет 3 4 +. Странно, я знаю. Но по правилу оператор должен стоять после всех своих операндов.

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

Algebraic: 3 - 4                        RPN: 3 4 -

Algebraic: 3 - 4 + 5                    RPN: 3 4 - 5 +

Algebraic: 2^3                          RPN: 2 3 ^

Algebraic: 5 + ((1 + 2) × 4) − 3        RPN: 5 1 2 + 4 * + 3 -

Algebraic: sin(45)                      RPN: 45 sin

Algebraic: tan(x^2 + 2*x + 6)           RPN: x 2 ^ 2 x * + 6 + tan

Поскольку оператор должен стоять после своих операндов, RPN также известен как постфиксная нотация, а наша «обычная» алгебраическая нотация называется инфиксной.

Как вы оцениваете выражение в RPN? Я использую простой алгоритм:

Прочтите все токены слева направо, пока не дойдете до оператора или функции. Зная, что оператор / функция принимает n аргументов (например, для +, n = 2; для cos () , n = 1), оцените последние n предыдущих аргументов с помощью оператора / функции и замените их все (оператор / функция + операнды) результатом. Продолжайте, как и раньше, пока не закончатся операторы / функции для чтения. Единственный оставшийся токен (буквальный или переменный) - это ваш ответ.

(Это упрощенный алгоритм, который предполагает, что выражение является допустимым. Пара индикаторов того, что выражение недействительно, - это если у вас осталось более одного токена в конце или если последний оставшийся токен является оператором / функцией.)

Итак, для чего-то вроде 5 1 2 + 4 * + 3 -:

read 5
read 1
read 2
read +. + is an operator which takes 2 args, so calculate 1+2 and replace with the result (3). The expression is now 5 3 4 * + 3 -
read 4
read *. * is an operator which takes two args, so calculate 3*4 and replace with the result, 12. The expression is reduced to 5 12 + 3 -
read +. + is an operator which takes two args, so calculate 5+12, replace by the result, 17. Now, we have 17 3 -
read 3
read -. - is an operator which takes two args, so calculate 17-3. The result is 14.

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

Абстрактные синтаксические деревья

Определение из Википедии может быть не слишком полезным для многих из нас: «древовидное представление абстрактной синтаксической структуры исходного кода, написанного на языке программирования». В этом случае мы можем рассматривать AST как структуру данных, которая представляет математическую структуру выражения. Это лучше видно, чем сказано, поэтому давайте нарисуем грубую диаграмму. Я начну с AST для простого выражения 3 + 4:

  [+]
 /   \
[3] [4]

Каждый [] представляет узел в дереве. Таким образом, вы можете сразу увидеть, что два токена объединяются оператором +.

Более сложное выражение, 5 + ((1 + 2) * 4) - 3:

           [-]
          /   \
        [+]    \___[3]   
       /  \
 [5]__/   [*]
         /   \
        [+]  [4]
       /   \  
     [1]  [2]

Ах, прекрасное маленькое синтаксическое дерево. Он идеально связывает все токены и операторов. Вы можете видеть, что вычислить это выражение намного проще - просто следуйте дереву.

Итак, чем полезен AST? Это поможет вам правильно представить логику и структуру выражения, облегчая вычисление выражения. Например, чтобы оценить приведенное выше выражение, на нашем сервере мы могли бы сделать что-то вроде этого:

result = binaryoperation(+, 1, 2)
result = binaryoperation(*, result, 4)
result = binaryoperation(+, 5, result)
result = binaryoperation(-, result, 3)
return result

Другими словами, для каждого узла оператора (или функции), с которым сталкивается оценщик / компилятор / интерпретатор, он проверяет, сколько существует ветвей, а затем оценивает результаты всех этих ветвей с помощью оператора.

Ладно, ускоренный курс окончен, теперь вернемся к нашему парсеру. Наш синтаксический анализатор преобразует (токенизированное) выражение в RPN, а затем в AST. Итак, приступим к его реализации.

Алгоритм маневрового двора

Вот полная версия алгоритма RPN (из нашего друга Википедии), модифицированная для соответствия нашему токенизатору:

Пока есть жетоны, которые нужно прочитать:

1. Прочтите жетон. Назовем это t

2. Если t является литералом или переменной, поместите его в очередь вывода.

3. Если t - функция, поместите ее в стек.

4. Если t - это разделитель аргументов функции (запятая), вставлять операторы из стека в очередь вывода до тех пор, пока маркер наверху стека не станет левой круглой скобкой.

5. Если t - оператор:

а. в то время как маркер оператора o находится наверху стека операторов и либо t является левоассоциативным и имеет приоритет меньше или равен приоритету o, либо t является правоассоциативным и имеет приоритет меньше, чем у o, pop o из стека операторов в очередь вывода;

б. в конце итерации поместите t в стек операторов.

6. Если маркер представляет собой левую круглую скобку, поместите его в стек.

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

8. Если токен наверху стека является функцией, поместите его в очередь вывода.

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

Выход.

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

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

Вы заметите пару вещей:

  • Нам нужны две структуры данных: стек для хранения функций и операторов и очередь для вывода. Если вы не знакомы с этими двумя структурами данных, вот руководство для вас: если вы хотите получить значение из стека, вы начинаете с последнего, которое вы вставили, тогда как для очереди вы начинаете с первого, которое вы Путин.
// we'll use arrays to represent both of them
var outQueue=[];
var opStack=[];
  • Нам нужно знать ассоциативность операторов. Ассоциативность просто означает, в каком порядке выражение, содержащее несколько операций одного типа, сгруппировано без скобок. Например, 2 + 3 + 4 канонически вычисляется слева направо (2+ 3 = 5, затем 5 + 4 = 9), поэтому + имеет левую ассоциативность. Сравните это с 2 ^ 3 ^ 4, которое оценивается как 2 ^ 81, а не 8 ^ 4. Таким образом, ^ имеет правую ассоциативность. Мы упакуем ассоциативности операторов, с которыми мы хорошо знакомы, в Javascriptobject:
var assoc = {
  "^" : "right",
  "*" : "left",
  "/" : "left",
  "+" : "left",
  "-" : "left"
 };
  • Нам также необходимо знать приоритет операторов. Приоритет - это своего рода ранжирование, присваиваемое операторам, поэтому мы можем знать, в каком порядке они должны оцениваться, если они появляются в одном и том же выражении. Операторы с более высоким приоритетом оцениваются первыми. Например, * имеет более высокий приоритет, чем +, поэтому 2 + 3 * 4 оценивается как 2 + 12, а не 5 * 4, если не используются круглые скобки. + и - имеют одинаковый приоритет, поэтому 3 + 5 - 2 можно оценить как 8–2 или 3 + 3. Опять же, мы упакуем приоритеты операторов в объект:
var prec = {
  "^" : 4,
  "*" : 3,
  "/" : 3,
  "+" : 2,
  "-" : 2
 };

Теперь давайте обновим наш Token класс, чтобы мы могли легко получить доступ к приоритетам и ассоциативности с помощью методов:

Token.prototype.precedence = function() {
  return prec[this.value];
 };
 
 Token.prototype.associativity = function() {
  return assoc[this.value];
 };
  • Нам нужен метод, который позволяет нам заглядывать в стек (чтобы проверить верхний элемент, не удаляя его), и метод, который позволяет нам извлекать из стека ( получить и удалить элемент вверху). К счастью, в массивах Javascript уже есть метод pop(), поэтому все, что нам нужно сделать, это реализовать метод peek(). (Помните, что для стеков верхний элемент - это тот, который мы добавили последним.)
Array.prototype.peek = function() {
  return this.slice(-1)[0]; //retrieve the last element of the array
 };

Итак, вот что у нас есть:

function tokenize(expr) {
  ...   // just paste the tokenizer code here
}
function parse(inp){
 var outQueue=[];
 var opStack=[];
Array.prototype.peek = function() {
  return this.slice(-1)[0];
 };
var assoc = {
  "^" : "right",
  "*" : "left",
  "/" : "left",
  "+" : "left",
  "-" : "left"
 };
var prec = {
  "^" : 4,
  "*" : 3,
  "/" : 3,
  "+" : 2,
  "-" : 2
 };
Token.prototype.precedence = function() {
  return prec[this.value];
 };
 
 Token.prototype.associativity = function() {
  return assoc[this.value];
 };
 //tokenize
 var tokens=tokenize(inp);
 tokens.forEach(function(v) {
   ...   //apply the algorithm here
 });
 return outQueue.concat(opStack.reverse());  // list of tokens in RPN
}

Я не буду вдаваться в подробности реализации алгоритма, поэтому не утомляю вас. Это довольно простая задача, практически дословный перевод алгоритма в код, так что в итоге вот что у нас есть:

Функция toString просто форматирует наш список токенов RPN в читаемый формат.

И мы можем протестировать наш синтаксический анализатор инфиксов в постфикс:

var rpn = parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3");
console.log(toString(rpn));

Выход:

3 4 2 * 1 5 - 2 3 ^ ^ / +

РПН !!

Пора посадить дерево

Теперь давайте изменим наш синтаксический анализатор, чтобы он возвращал AST.

Чтобы сгенерировать AST вместо RPN, нам нужно внести несколько изменений:

  • Мы создадим объект, представляющий узел в нашем AST. У каждого узла есть значение и две ветви (которые могут быть null):
function ASTNode(token, leftChildNode, rightChildNode) {
   this.token = token.value;
   this.leftChildNode = leftChildNode;
   this.rightChildNode = rightChildNode;
}
  • Второе, что мы сделаем, это изменим нашу структуру выходных данных на стек. Хотя фактический код для этого - просто изменить строку var outQueue = [] на var outStack = [] (потому что она остается массивом), ключевое изменение заключается в нашем понимании и обработке этого массива.

Итак, как будет работать наш алгоритм преобразования инфиксов в AST? По сути, тот же алгоритм, с небольшими изменениями:

  1. Вместо того, чтобы помещать токен Literal или Variable в наш outQueue, мы помещаем новый узел, значение которого является токеном, и чьи ветви null на наш outStack
  2. Вместо того, чтобы извлекать токен оператора / функции из opStack, мы заменяем два верхних узла на outStack одним узлом, значением которого является токен, и эти два являются его ветвями. Давайте создадим функцию, которая сделает это:
Array.prototype.addNode = function (operatorToken) {
  rightChildNode = this.pop();
  leftChildNode = this.pop();
  this.push(new ASTNode(operatorToken, leftChildNode, rightChildNode));
 }

3. Наш синтаксический анализатор должен теперь вернуть единственный узел, узел наверху нашего AST. Две его ветви будут содержать два дочерних узла, чьи ветви будут содержать их потомков, и так далее, рекурсивным образом. Например, для такого выражения, как 3 + 4 * 2 / (1–5) ^ 2 ^ 3, мы ожидаем, что структура нашего выходного узла будет такой (в горизонтальной форме):

+ => 3 => null
       => null
  => / => * => 4 => null
                 => null
            => 2 => null
                 => null
       => ^ => - => 1 => null
                      => null
                 => 5 => null
                      => null
            => ^ => 2 => null
                      => null
                 => 3 => null
                      => null

На схеме выше = ›представляют ветви узла (верхний узел - это левая ветвь, нижний - правая ветвь). Каждый узел имеет две ветви, а узлы в конце дерева указывают на null

Итак, если мы сложим все это вместе, вот код, который мы получим:

И если мы это продемонстрируем:

//a little hack I put together so it prints out in a readable form
ASTNode.prototype.toString = function(count) {
   if (!this.leftChildNode && !this.rightChildNode)
     return this.token + "\t=>null\n" + Array(count+1).join("\t") + "=>null";
   var count = count || 1;
   count++;
   return this.token + "\t=>" + this.leftChildNode.toString(count) + "\n" + Array(count).join("\t") + "=>" + this.rightChildNode.toString(count);
};
var ast = parse("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3");
console.log("" + ast);

И результат:

Медленно, но верно мы приближаемся к пониманию того, что движет компиляторами и интерпретаторами! По общему признанию, работа с современными языками программирования и их наборами инструментов намного сложнее, чем то, что мы рассматривали до сих пор, но я надеюсь, что это окажется легким для понимания введением в них. Как отмечали многие люди, существуют инструменты для автоматической генерации токенизаторов и парсеров, но часто приятно знать, как что-то на самом деле работает.

Концепции, которые мы рассмотрели в этой и предыдущей статьях, являются очень интересными темами в области информатики и теории языков. Мне еще многое предстоит узнать о них, и я призываю вас продолжить и исследовать их, если они вас заинтересуют. И напишите мне, чтобы я знал о ваших успехах. Мир!