Как да изградим математически токенизатор с помощта на JavaScript (или на друг език)

Източник: Wikimedia Commons

Преди време се вдъхнових да създам приложение за решаване на конкретни видове математически проблеми. Открих, че трябва да анализирам израза в абстрактно синтаксично дърво, затова реших да изградя прототип в Javascript. Докато работех върху парсера, разбрах, че първо трябва да се изгради токенизаторът. Ще ви преведа как да направите сами. (Предупреждение: по-лесно е, отколкото изглежда в началото.)

Какво е токенизатор?

Токенизаторът е програма, която разбива израз на единици, наречени маркери. Например, ако имаме израз като „Аз съм голям дебел разработчик“, бихме могли да го използваме по различни начини, като например:

Използвайки думи като символи,

0 => Аз съм
1 => a
2 => голям
3 => мазнини
4 => разработчик

Използвайки символи без празно пространство като символи,

0 => аз
1 => „
2 => m
3 => a
4 => b
...
16 => п
17 => е
18 => r

Бихме могли също така да разгледаме всички знаци като символи, които да вземем

0 => аз
1 => „
2 => m
3 => (интервал)
4 => a
5 => (интервал)
6 => b
...
20 => п
21 => е
22 => r

Имате идея, нали?

Токенизаторите (наричани още лексери) се използват при разработването на компилатори за езици за програмиране. Те помагат на компилатора да направи структурен смисъл от това, което се опитвате да кажете. В този случай обаче ние изграждаме такъв за математически изрази.

Знаците

Валиден математически израз се състои от математически валидни маркери, които за целите на този проект могат да бъдат литерали, променливи, оператори, функции или разделители на аргументи на функции.
Няколко бележки към горното:

  • А Literal е фантастично име за число (в случая). Ще разрешаваме числа само в цяла или десетична форма.
  • Променливата е вида, с който сте свикнали в математиката: a, b, c, x, y, z. За този проект всички променливи са ограничени до имена с една буква (така че нищо като var1 или цена). Това е така, че можем да токенизираме израз като ma като произведение на променливите m и a, а не на една единствена променлива ma.
  • Операторите действат върху литерали и променливи и резултатите от функциите. Ще разрешим на операторите +, -, *, / и ^.
  • Функциите са „по-напреднали“ операции. Те включват неща като sin (), cos (), tan (), min (), max () и т.н.
  • Функционален разделител на аргументи е просто фантазирано име за запетая, използвано в контекст като този: max (4, 5) (максималната една от двете стойности). Наричаме го функционален аргумент сепаратор, защото той, добре, разделя аргументите на функциите (за функции, които вземат два или повече аргумента, като max и min).

Ще добавим и два маркера, които обикновено не се считат за маркери, но ще ни помогнат с яснота: Лява и дясна пареза. Знаеш какви са тези.

Малко съображения

Неявно умножение

Подразбиращото се умножение просто означава да се позволи на потребителя да пише „стенограми“ умножения, като например 5x, вместо 5 * x. Правейки го стъпка по-нататък, той също така позволява да прави това с функции (5sin (x) = 5 * sin (x)).

Още повече, че позволява 5 (x) и 5 ​​(sin (x)). Имаме възможност да го разрешим или не. Компромиси? Ако не го разрешите, всъщност би направило токенизирането по-лесно и би позволило имена на променливи с много букви (имена катоprice). Разрешаването му прави платформата по-интуитивна за потребителя и, добре, осигурява допълнително предизвикателство за преодоляване. Избрах да го позволя.

Синтаксис

Докато ние не създаваме език за програмиране, трябва да имаме някои правила за това какво прави валиден израз, така че потребителите да знаят какво да въведат и ние знаем за какво да планираме. По-точно казано, математическите символи трябва да се комбинират съгласно тези правила за синтаксис, за да бъде валиден изразът. Ето моите правила:

  1. Токените могат да бъдат разделени с 0 или повече знака на празно пространство
2 + 3, 2 +3, 2 + 3, 2 + 3 са всичко наред
5 x - 22, 5x-22, 5x- 22 са всичко наред

С други думи, разстоянието няма значение (освен в рамките на много символи като Literal 22).

2. Аргументите за функция трябва да бъдат в скоби (sin (y), cos (45), а не sin y, cos 45). (Защо? Ще премахваме всички интервали от низа, така че искаме да знаем къде дадена функция започва и завършва, без да се налага да правим някаква „гимнастика“.)

3. Неявно умножение е позволено само между литерали и променливи, или литерали и функции, в този ред (тоест литералите винаги са на първо място) и могат да бъдат със или без скоби. Това означава:

  • a (4) ще се третира като извикване на функция, а не като * 4
  • a4 не е позволено
  • 4а и 4 (а) са ОК

Сега, нека да работим

Моделиране на данни

Помага да имате примерен израз в главата си, за да тествате това. Ще започнем с нещо основно: 2y + 1

Това, което очакваме е масив, който изброява различните символи в израза, заедно с техните типове и стойности. Така че за този случай очакваме:

0 => Буквално (2)
1 => Променлива (y)
2 => Оператор (+)
3 => Буквално (1)

Първо ще дефинираме клас Token, за да улесним нещата:

функция Token (тип, стойност) {
   this.type = type;
   this.value = стойност
}

алгоритъм

На следващо място, нека изградим скелета на нашата токенизатор функция.

Нашият токенизатор ще премине през всеки символ от масива str и ще изгради маркери въз основа на стойността, която намира.

[Обърнете внимание, че приемаме, че потребителят ни дава валиден израз, така че ще пропуснем всяка форма на валидиране в целия този проект.]

функция tokenize (str) {
  вар резултат = []; // масив от маркери
  
  // премахване на интервали; помниш ли, че нямат значение?
  str.replace (/ \ s + / g, "");
  // преобразуване в масив от знаци
  ул = str.split ( "");
str.forEach (функция (char, idx) {
    ако (isDigit (char)) {
      result.push (нов Token ("Literal", char));
    } else if (isLetter (char)) {
      result.push (нов Token ("Променлива", char));
    } else if (isOperator (char)) {
      result.push (нов Token ("Оператор", char));
    } else if (isLeftParenthesis (char)) {
      result.push (нов токен ("Ляв парентез", char));
    } else if (isRightParenthesis (char)) {
      result.push (нов токен ("Дясна парента", char));
    } else if (isComma (char)) {
      result.push (нов Token ("Функция Разделител на аргументи", char));
    }
  });
  възвратен резултат;
}

Кодът по-горе е доста основен. За справка, помощниците еDigit (), isLetter (), isOperator (), isLeftParenthesis () и isRightParenthesis () са дефинирани по следния начин (не се плашете от символите - нарича се регекс и е наистина страхотно):

функция еComma (ch) {
 връщане (ch === ",");
}
функция еDigit (ch) {
 връщане /\d/.test(ch);
}
функция еLetter (ch) {
 връщане / evidencea-zSense/i.test(ch);
}
функция е Оператор (ch) {
 връщане /\+|-|\*|\/|\^/.test(ch);
}
функция е LeftParenthesis (ch) {
 връщане (ch === "(");
}
функция еRightParenthesis (ch) {
 връщане (ch == ")");
}

[Обърнете внимание, че няма функции isFunction (), isLiteral () или isVariable (), защото тестваме символите поотделно.]

Така че сега нашият парсер действително работи. Опитайте го с тези изрази: 2 + 3, 4a + 1, 5x + (2y), 11 + sin (20.4).

Всичко е наред?

Не точно.

Ще забележите, че за последния израз 11 се отчита като два буквални маркера вместо един. Също така грехът се отчита като три символа вместо един. Защо е това?

Нека спрем за момент и помислим за това. Токенизирахме символа на масива по характер, но всъщност някои от нашите символи могат да съдържат няколко знака. Например литералите могат да бъдат 5, 7.9, .5. Функциите могат да бъдат sin, cos и променливите са само единични знаци, но могат да се появят заедно в неявно умножение. Как да решим това?

Буфери

Можем да поправим това чрез прилагане на буфер. Две, всъщност. Ще използваме един буфер за задържане на буквени букви (числа и десетична запетая) и един за букви (който обхваща както променливи, така и функции).

Как работят буферите? Когато токенизаторът срещне число / десетична запетая или буква, той го бута в съответния буфер и продължава да прави това, докато не влезе в друг вид оператор. Действията му ще варират в зависимост от оператора.

Например в израза 456.7xy + 6sin (7.04x) - min (a, 7), той трябва да върви по тези линии:

прочетете 4 => числоBuffer
 прочетете 5 => numberBuffer
 прочетете 6 => numberBuffer
 Прочети . => numberBuffer
 прочетете 7 => numberBuffer
 x е буква, затова сложете цялото съдържание на числовия буфер заедно като резултат от Literal 456.7 =>
 прочетете x => letterBuffer
 прочетете y => letterBuffer
 + е оператор, така че премахнете цялото съдържание на буферния буфер отделно като Променливи x => резултат, y => резултат
 + => резултат
 прочетете 6 => numberBuffer
 s е буква, така че сложете цялото съдържание на числовия буфер заедно като резултат Literal 6 =>
 прочетете s => letterBuffer
 прочетете i => letterBuffer
 прочетете n => letterBuffer
 (е ляв парентез, така че сложете цялото съдържание на буферния бутон заедно като функция sin => резултат
 прочетете 7 => numberBuffer
 Прочети . => numberBuffer
 прочетете 0 => числоBuffer
 прочетете 4 => числоBuffer
 x е буква, затова сложете цялото съдържание на numberbuffer заедно като резултат от Literal 7.04 =>
 прочетете x => letterBuffer
 ) е дясна парентеза, така че премахнете цялото съдържание на буферния буфер отделно като резултат Променливи x =>
 - е Оператор, но и двата буфера са празни, така че няма какво да премахнете
 прочетете m => letterBuffer
 прочетете i => letterBuffer
 прочетете n => letterBuffer
 (е ляв парентез, така че сложете цялото съдържание на буферния бутон заедно като функция min => резултат
 прочетете a => letterBuffer
 , е запетая, така че сложете цялото съдържание на буферния бутон заедно като променлив a => резултат, след което натиснете, като функция за разделяне на аргументи => резултат
 прочетете 7 => numberBuffer
 ) е дясна парентеза, така че сглобете цялото съдържание на числовия буфер заедно като резултат от Literal 7 =>

Завършено. Разберете сега, нали?

Стигаме до там, само още няколко случая за справяне.

Това е моментът, в който сядате и мислите дълбоко за вашия алгоритъм и моделиране на данни. Какво се случва, ако текущият ми герой е оператор, а numberBuffer не е празен? Могат ли и двата буфера едновременно да бъдат непразни?

Събирайки всичко това, ето какво измисляме (стойностите вляво от стрелката изобразяват нашия текущ символ (ch) тип, NB = бройбуфер, LB = букфер, LP = лява скоба, RP = дясна скоба

цикъл през масива:
  какъв тип е ch?
цифра => натиснете ch към NB
  десетична запетая => натиснете ch до NB
  писмо => присъединете съдържанието на NB като един буквален и натиснете, за да постигнете резултат, след това натиснете ch към LB
  operator => присъединете съдържанието на NB като един буквален и натиснете за резултат ИЛИ натиснете LB съдържанието отделно като променливи, след това натиснете ch за резултат
  LP => присъединете съдържанието на LB като една функция и натиснете, за да ИЛИ (присъединете съдържанието на NB като един буквален и натиснете, за да постигнете резултат, натиснете Оператор * за резултат), след това натиснете ch за резултат
  RP => присъединете съдържанието на NB като един Буквал и натиснете за резултат, бутнете LB съдържанието отделно като Променливи, след това натиснете ch, за да постигнете резултат
  запетая => присъединете съдържанието на NB като един буквален и натиснете, за да постигнете резултат, бутнете LB съдържанието отделно като променливи, след това натиснете ch за резултат
краен контур
присъединете съдържанието на NB като един Буквал и натиснете за резултат, избутайте LB съдържанието отделно като Променливи,

Две неща, които трябва да отбележим.

  1. Забележете къде добавих „push Operator * to result“? Това е конвертирането на имплицитното умножение в изрично. Също така, когато изпразваме съдържанието на LB поотделно като променливи, трябва да помним да вмъкнем оператора за умножение между тях.
  2. В края на цикъла на функцията, ние трябва да не забравяме да изпразваме всичко, което сме останали в буферите.

Превеждайки го в код

Събирайки всичко това, функцията ви за токенизиране трябва да изглежда така:

Можем да пуснем малко демо:

var tokens = tokenize ("89sin (45) + 2.2x / 7");
tokens.forEach (функция (токен, индекс) {
  console.log (index + "=>" + token.type + "(" + token.value + ")":
});
Да! Забележете добавените * s за неявните умножения

Опаковане

Това е моментът, в който анализирате функцията си и измервате какво прави тя спрямо това, което искате да прави. Задайте си въпроси като „Работи ли функцията по предназначение?“ И „Покрих ли всички крайни случаи?“

Случаите на ръбовете за това могат да включват отрицателни числа и други подобни. Освен това провеждате тестове за функцията. Ако накрая сте доволни, може да започнете да търсите как можете да го подобрите.

Благодаря за четенето. Моля, кликнете върху малкото сърце, за да препоръчате тази статия, и споделете, ако ви е харесало! И ако сте опитали друг подход за изграждане на математически токенизатор, не ме уведомете в коментарите.