В предыдущей серии мы научились считать выражения вида -2.1+ .355 / (cos(pi % 3) + sin(0.311)). Один из комментариев там предложил посчитать то, что я вынес в заголовок этого поста. Что ж, вызов принят. Как и в предыдущем посте, мы "на пальцах" разбираем устройство простейшего интерпретатора.

Код из конца предыдущего поста: jdoodle.com/ia/KIZ и на всякий случай https://pastebin.com/Ac5BgCFa

Понудим о языке

До сих пор мы имели дело с обычными арифметическими выражениями на общепринятом языке: арабские цифры, десятичные числа, операторы между операндами (инфиксная нотация), все операторы явные, * означает умножение (вряд ли вы рисовали этот символ от руки в тетрадках; это важно и мы к этому вернёмся), всё выражение целиком интерпретируется в числовой ответ.

Здесь же у нас появляется что-то новое и неоднозначное. Давайте внимательно посмотрим на предложенную строку.

a=1; b=2; x=pi/3; abcos(x)

Целиком к одному числу она уже не сводится: интуитивно мы ждём ответа лишь от последней части, которая abcos(x). Предшествующие части больше похожи на перечисление условностей, определяющих значение abcos(x). Но что, если нам дают посчитать cos(pi); cos(pi); cos(pi)? Здесь так же только последняя часть должна что-то выдать или первые две тоже? А если a=1; b=2? Может, такое вообще надо запретить и выбрасывать ошибку? Как формализовать правило?

А ещё неявное (подразумеваемое) умножение. Должно же быть a*b*cos(x), верно? Зачем усложнять всем жизнь? Как быть со всеми вытекающими отсюда неоднозначностями? Кстати в школе все писали b²−4ac и как-то мирились с ними (хотя можно поспорить, что там было негласное правило называть переменные одной буквой).

В любом случае, задавая себе подобные вопросы, на которые нет единственного правильного ответа, мы погружаемся в дизайн языка программирования, пускай очень примитивного. Что неприемлемо в одном месте, может оказаться годным в другом. И в образовательных целях давайте всё-таки реализуем поддержку неявного умножения, а числовой результат возьмём от выражения в последней инструкции, у которой почему-то нет точки с запятой в конце (камни пожалуйста кидайте в огород разработчика этой грамматики).

Test suite

В предыдущем посте мы накопили кучку каверзных и не очень примеров, на которых испытывали интерпретатор.

console.log(new ExpressionCalc('2+2').calc() === 4);
console.log(new ExpressionCalc('2+3-4').calc() === 1);
console.log(new ExpressionCalc('2+2*2').calc() === 6);
console.log(new ExpressionCalc('3+4*5').calc() === 23);
console.log(new ExpressionCalc('3/2+4*5').calc() === 21.5);
console.log(new ExpressionCalc('(2+2)*2').calc() === 8);
console.log(new ExpressionCalc('(02. + 0002.) × 002.000').calc() === 8);
console.log(new ExpressionCalc('3%2').calc() === 1);
console.log(new ExpressionCalc('+1').calc() === 1);
console.log(new ExpressionCalc('-(2+3)').calc() === -5);
console.log(new ExpressionCalc('cos(2*pi)').calc() === 1);
console.log(new ExpressionCalc('-2.1+ .355 / (cos(pi % 3) + sin(0.311))').calc() === -1.8260809473359578);

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

...> node .\index.js
true
true
true
...

Взрослый, но по-прежнему простой набор тестов для компилятора Си может выглядеть как-то так: c-testsuite.

Считаем "2pi": неявное умножение

У нас ещё нет переменных, поэтому поиграемся с предопределёнными именованными константами (e, pi) и скобками. Добавим вот такие кейсы.

console.log(new ExpressionCalc('2pi').calc() === Math.PI * 2);
console.log(new ExpressionCalc('3(5cos(1)2)').calc() === 16.209069176044192);
console.log(new ExpressionCalc('2 2').calc() === 4);
console.log(new ExpressionCalc('(2 + 3) 2').calc() === 10);
console.log(new ExpressionCalc('(2)(2)3(4)\t3').calc() === 144);

Интерпретатор ожидаемо выпадает с ошибкой expected eof, pos=1, token=pi, type=id.

Как это исправить? Может, подставлять (додумывать) оператор * на выходе лексера между подряд идущими числами/скобками/идентификаторами, "обманывая" парсер? Да, это сработает здесь, но наверняка сыграет с нами злую шутку при дальнейшем расширении языка. Ведь лексер мало знает о грамматике, и не его дело в этой грамматике хитрить (хотя далее мы без этого не обойдёмся).

Решение лежит на поверхности. Вспомним, что оператор * (токен MULTIPLY) означает умножение и может находиться между числами, скобками, идентификаторами и перед унарным оператором (например, 2*-2). Значит, в отсутствие этого токена можно следующее число/скобку/идентификатор воспринимать как условие для продолжения перебора множителей в term. Унарные операторы в пролёте, т.к. 2*-2 и 2-2 это уже разные вещи.

Введём метод #check, позволяющий проверить текущий токен не переходя к следующему, и с его помощью проверим в #term, нет ли очередного множителя - там же, где обрабатывается явный оператор умножения. То есть мы как бы проверяем, не похож ли очередной токен на начало выражения-множителя, и если похож, то продолжаем обрабатывать умножение.

#check(...types) {
  return types.includes(this.#token?.type);
}

/* ... #accept, #expect, #factor ... */

#term() {
  let result = this.#factor();

  while (true) {
    // было: if (this.#accept(MULTIPLY)) result *= this.#factor();
    if (this.#accept(MULTIPLY) || this.#check(NUMBER, IDENTIFIER, LEFT_PAR)) result *= this.#factor();
    else if (this.#accept(DIVIDE)) result /= this.#factor();
    else if (this.#accept(MOD)) result %= this.#factor();
    else break;
  }

  return result;
}

Пробуем "2pi" и остальные — работает.

Конечно, такой проверкой мы частично дублируем логику метода #factor, а дублирование в общем случае это плохо. Например, если бы в #factor мы добавили поддержку квадратных скобок (в том же значении, что круглые), то открывающую квадратную скобку пришлось бы проверять и в #term, а это можно забыть сделать, особенно если тесты недостаточно проработанные. Но давайте в образовательных целях оставим код простым, пускай и с дублированием.

Переменные

До сих пор переменных у нас не было. pi и e это всего лишь предопределённые константы. Давайте напомню тех.задание:

a=1; b=2; x=pi/3; abcos(x)

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

a=1; b=2; x=pi/3; a*b*cos(x)

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

У нас есть четыре элемента, разграниченных точкой с запятой ; (SEMICOLON). Назовём их инструкциями (statement), а весь текст целиком - программой. Инструкции могут быть инициализацией/присваиванием переменных либо простыми выражениями. Значение последней инструкции считается результатом исполнения программы.

Таблица символов

Для хранения значений переменных нам потребуется таблица символов (symbol table) или память (в контексте интерпретаторов). Кстати в примитивном и неявном виде она у нас уже есть - там, где в #factor обрабатываются идентификаторы. Давайте объявим её более явным образом.

class ExpressionCalc {
  #symbols = {
    pi: Math.PI,
    e: Math.E,
    sin: Math.sin,
    cos: Math.cos,
  };
  #stream;
  #token;
  ...
  #factor() {
    ...
    else if (text = this.#accept(IDENTIFIER)) {
      text = text.toLowerCase();
      const sym = this.#symbols[text];
      if (typeof sym === 'number') result = sym;
      else if (typeof sym === 'function') {
        this.#expect(LEFT_PAR);
        result = sym(this.#expression());
        this.#expect(RIGHT_PAR);
      }
    ...

Дальше в #symbols мы будем записывать значения переменных при присваивании. А сейчас проверим на старых примерах. Работает? Работает. Теперь разберёмся с грамматикой инструкций.

Синтаксис

Итак, программа состоит из инструкций, инструкции могут быть присваиванием (assignment) выражения переменной или просто выражением. Парсер нашего интерпретатора пока знает лишь выражения. Объясним ему что такое инструкция.

Правда, тут есть некоторая неоднозначность. Чисто визуально отличить b=2 от, например, b 2 легко. Но если разбирать это лексема за лексемой, то оба примера начинаются с b, и уже следующий за ней оператор присваивания = определяет смысл конструкции. То есть встретив =, мы должны остальную часть инструкции посчитать и присвоить переменной (записать значение в таблицу символов), но только при условии, что слева от оператора был идентификатор переменной, а не что угодно другое.

Можно рассуждать иначе и не считать присваивание высокоуровневым понятием, которое определяет смысл целой инструкции (statement) и может встречаться в ней лишь единожды. Например, оператор = можно обработать глубже - где мы встречаем идентификатор в #factor. Тогда инструкция будет тем же самым, что и выражение, а мы заодно сможем обрабатывать всякие прикольные неочевидные конструкции типа 2*((a=1)+(b=1)), что должно выдать либо 4, либо неопределённость в зависимости от того, какой смысл мы вкладываем в присваивание как целое (под)выражение.

Из тех.задания неочевидно, какой вариант правильный. Рассмотрим менее строгий второй вариант, потому что он чаще встречается в известных ЯП. Например, в JavaScript присваивание является выражением, и можно сцеплять их одно с другим:

let a; let b; let c;
console.log(a=7); // 7
console.log(a=b=c=7); // 7

Только в отличие от JS наш язык не требует явного объявления переменных через ключевые слова let, var, const и т.п. Они объявляются неявным образом через присваивание.

Напишем свежие тесты:

console.log(new ExpressionCalc('a=7').calc() === 7) // error: unknown id a
console.log(new ExpressionCalc('a=b=c=7').calc() === 7)
console.log(new ExpressionCalc('2*((a=1)+(b=1))').calc() === 4);

Определим новый токен за символом присваивания =. Это делается буквально в две строки.

const
  WS = Symbol('ws'),
  NUMBER = Symbol('num'),
  ...
  EQUAL = Symbol('eq'), // NEW
  ...;

function* tokenize(input) {
  const matchers = [
    ...
    { type: EQUAL, re: /^=/ }, // NEW
    ...
  ];

И ещё одно ветвление в интерпретаторе (в методе #factor), которое даст нам полноценную поддержку присваивания.

else if (text = this.#accept(IDENTIFIER)) {
  text = text.toLowerCase();
  // NEW
  if (this.#accept(EQUAL)) {
    this.#symbols[text] = this.#expression();
  }

Здорово, правда?

Инструкции (statement)

Мы умеем a=b=c=7, но не a=1;b=2. Добавим это в тесты (напомню, что должна получиться двойка) и получим...

Error: expected eof, pos=3, token=;, type=unknown

Расскажем лексеру/токенайзеру про новый токен ; (SEMICOLON). В ошибке после этого увидим ...type=semicolon.

...
SEMICOLON = Symbol('semicolon'),
...
{ type: SEMICOLON, re: /^;/ },

И теперь наконец перейдём на самом верхнем уровне (метод calc) от единственного выражения к циклу по инструкциям.

// было
calc() {
  const result = this.#expression();
  this.#expect(END_OF_FILE);
  return result;
}

// стало
calc() {
  let result;
  do {
    result = this.#expression();
  } while (this.#accept(SEMICOLON));
  this.#expect(END_OF_FILE);
  return result;
}

Настало время проверить a=1; b=2; x=pi/3; a*b*cos(x).

new ExpressionCalc('a=1; b=2; x=pi/3; a*b*cos(x)').calc() == 1.0000000000000002
// true

Ну, почти единичка. Почти ура!

О том, почему не ровно единичка, стоит поговорить отдельно, но не сейчас. Если вкратце, то не хватает точности в промежуточных вычислениях. Будьте аккуратнее с самописанными калькуляторами и вычислением дробей в языках общего назначения. К заветной единице мы ещё попробуем приблизиться. А пока добьём abcos.

abcos(x)

Итак, перед нами неоднозначное непонятное отвратительное abcos(x) из заголовка. Что с этим делать? Ведь лексер проглатывает abcos одним куском и выдаёт это как единственный IDENTIFIER, тогда как мы ждём три отдельных лексемы (a, b, cos).

Давайте снова взглянем на правила лексера:

const matchers = [
  { type: NUMBER, re: /^[0-9\.]+/ },
  { type: PLUS, re: /^\+/ },
  { type: MINUS, re: /^[-−]/ },
  { type: MULTIPLY, re: /^[*×⋅·]/ },
  { type: DIVIDE, re: /^\// },
  { type: MOD, re: /^%/ },
  { type: WS, re: /^[\s]+/ },
  { type: LEFT_PAR, re: /^\(/ },
  { type: RIGHT_PAR, re: /^\)/ },
  { type: IDENTIFIER, re: /^[_a-zA-Z][_a-zA-Z0-9]*/ },
  { type: EQUAL, re: /^=/ },
  { type: SEMICOLON, re: /^;/ },
  { type: END_OF_FILE, re: /^$/ }
];

Очевидно, мы скатываемся в IDENTIFIER, который ничего не знает о переменных. Как с этим быть? Самый простой подход это так называемый lexer hack. Хаком он зовётся потому что информация о переменных передаётся в обратном направлении - от парсера лексеру, чтобы последний мог "разлепить" имена. В нашем случае делается это довольно просто.

function* tokenize(input, sym = {}) { // передаём таблицу символов в лексер
  ...
  while (input) {
    ...
    for (const { type, re } of matchers) {
      let match = re.exec(input.slice(pos))?.[0]; // было const
      if (typeof(match) === 'string') {
        ...
        if (type === IDENTIFIER) { // новый блок
          for (const name in sym) {
            if (match.startsWith(name)) match = name;
          }
        }
      }
    }
    ...
  }

class ExpressionCalc {
  ...
  constructor(input) {
    // даём лексеру доступ к символам
    this.#stream = tokenize(input, this.#symbols);
    ...
  }

То есть, встретив IDENTIFIER, мы сверяемся с именами в таблице символов, и если находим совпадение, то переопределяем match на совпавшую часть, которая короче изначально встреченного идентификатора. Благодаря этому в следующей итерации while мы продолжим разбор где-то внутри того идентификатора, что и даст нам необходимое поведение.

Вы ведь уже добавили пример с abcos в тесты? Ну, хотя бы мысленно.

new ExpressionCalc('a=1; b=2; x=pi/3; abcos(x)').calc() === 1.0000000000000002

Работает!
(pastebin на всякий)

Бонус-трек: 1.0000000000000002

В принципе, можно было остановиться. С точки зрения ЯП общего назначения результат вполне корректный. Но что, если мы делаем более качественный калькулятор, и не хотим быстро сваливаться в особенности нативных floating point?

Это довольно серьёзное требование. Из-за него придётся заменить всю арифметику и отказаться от нативного для JS типа number. Давайте посмотрим, насколько сложно это сделать. С нуля точную арифметику писать, конечно, не будем, а воспользуемся пакетом. Например, decimal.js.

Последовательно заменим нативные арифметические операции JS на эквиваленты decimal.js.

const Decimal = require('decimal.js');

// дальше было-стало

pi: Math.PI
pi: new Decimal(Math.PI),

e: Math.E,
e: new Decimal(Math.E),

sin: Math.sin
sin: d => d.sin(),

cos: Math.cos
cos: d => d.cos(),

result = parseFloat(text);
result = new Decimal(text);

result = +this.#factor();
result = this.#factor();

result = -this.#factor();
result = this.#factor().mul(new Decimal(-1));

if (typeof sym === 'number') result = sym;
if (sym instanceof Decimal) result = sym;

result *= this.#factor();
result = result.mul(this.#factor());

result /= this.#factor();
result = result.div(this.#factor());

result %= this.#factor();
result = result.mod(this.#factor());

result += this.#term();
result = result.add(this.#term());

result -= this.#term();

Тесты тоже придётся немного видоизменить.

console.log(new ExpressionCalc('2+2').calc().eq(new Decimal('4')));
// и т.д.

Конечно, модифицированный код работает. Но заветную единицу из a=1; b=2; x=pi/3; abcos(x) мы так и не получили, хоть и стали к ней ближе.

было:  1.0000000000000002
стало: 1.0000000000000001376

Что с этим делать? В вычислениях с ограниченной точностью - ничего, кроме как округлять результат. Качественно (без округлений) получить единицу можно, пожалуй, символьными вычислениями. Но это уже совсем другой уровень.