Ako zostaviť tokenizér matematických výrazov pomocou JavaScriptu (alebo iného jazyka)

Pred časom som sa inšpiroval pri vytváraní aplikácie na riešenie konkrétnych druhov matematických úloh. Zistil som, že musím výraz rozobrať do abstraktného syntaxového stromu, a tak som sa rozhodol vytvoriť prototyp v Javascript. Pri práci na syntaktickom analyzátore som si uvedomil, že najskôr musí byť zostavený tokenizer. Prevediem vás, ako si jednu urobiť sami. (Varovanie: je to jednoduchšie, ako sa na prvý pohľad zdá.)

Čo je to Tokenizer?

Tokenizer je program, ktorý rozdeľuje výraz na jednotky nazývané tokeny . Napríklad, ak máme výraz ako „Som veľký vývojár tukov“, mohli by sme ho tokenizovať rôznymi spôsobmi, napríklad:

Používanie slov ako tokenov,

0 => I’m1 => a2 => big3 => fat4 => developer

Používanie znakov iných znakov ako tokenov,

0 => I1 => ‘2 => m3 => a4 => b…16 => p17 => e18 => r

Mohli by sme tiež považovať všetky postavy za tokeny

0 => I1 => ‘2 => m3 => (space)4 => a5 => (space)6 => b…20 => p21 => e22 => r

Máte nápad, že?

Tokenizéry (nazývané tiež lexery) sa používajú pri vývoji kompilátorov pre programovacie jazyky. Pomáhajú prekladaču dať štrukturálny zmysel z toho, čo sa snažíte povedať. V tomto prípade však vytvárame jeden pre matematické výrazy.

Žetóny

Platný matematický výraz pozostáva z matematicky platných tokenov, ktorými by na účely tohto projektu mohli byť literály , premenné , operátory, funkcie alebo oddeľovače funkčných argumentov .

Niekoľko poznámok k vyššie uvedenému:

  • Literál je vymyslený názov pre číslo (v tomto prípade). Povolíme iba čísla v celej alebo desatinnej podobe.
  • Variabilita je druh, na aký ste zvyknutí v matematike: a, b, c, x, y, z. Pre tento projekt sú všetky premenné obmedzené na jednopísmenové názvy (takže nič ako var1 alebo cena ). Jedná sa tak môžeme tokenize výraz, ako ma ako produkt z premenných m a , a ani jeden premenné ma .
  • Prevádzkovatelia konajú podľa literálov a premenných a výsledkov funkcií. Povolíme operátorom +, -, *, / a ^.
  • Funkcie sú „pokročilejšie“ operácie. Zahŕňajú veci ako sin (), cos (), tan (), min (), max () atď
  • Separátor funkčných argumentov je len vymyslený názov pre čiarku, ktorý sa používa v takomto kontexte: max (4, 5) (maximálna jedna z dvoch hodnôt). Nazývame ho Separátor funkčných argumentov, pretože oddeľuje argumenty funkcií (pre funkcie, ktoré obsahujú dva alebo viac argumentov, napríklad max a min ).

Pridáme tiež dva tokeny, ktoré sa zvyčajne nepovažujú za tokeny, ale pomôžu nám s jasnosťou: ľavá a pravá zátvorka . Vieš, čo to je.

Niekoľko úvah

Implicitné násobenie

Implicitné násobenie jednoducho znamená, že umožňuje používateľovi namiesto 5 * x písať „skratkové“ násobenia, napríklad 5x . Ak to posunieme o krok ďalej, umožňuje to aj vykonávanie funkcií ( 5sin (x) = 5 * sin (x) ).

Ešte ďalej umožňuje 5 (x) a 5 (sin (x)). Máme možnosť to povoliť alebo nie. Kompromisy? Jeho nepovolenie by skutočne uľahčilo tokenizáciu a umožnilo by to viacpísmenové názvy premenných (názvy ako price). Ak to umožníte, platforma bude pre používateľa intuitívnejšia, čo predstavuje ďalšiu výzvu, ktorú treba prekonať. Rozhodol som sa to povoliť.

Syntax

Aj keď nevytvárame programovací jazyk, potrebujeme mať nejaké pravidlá o tom, čo robí platný výraz, aby používatelia vedeli, čo majú zadať, a my vedeli, čo si majú naplánovať. Aby bol výraz platný, musia byť matematické tokeny kombinované podľa týchto pravidiel syntaxe. Tu sú moje pravidlá:

  1. Tokeny môžu byť oddelené od 0 alebo viacerých medzier medzi znakmi
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

Inými slovami, na medzery nezáleží (okrem viacznakového tokenu, ako je Literal 22).

2. Argumenty funkcií musia byť v zátvorkách ( sin (y) , cos (45) , nie sin y , cos 45 ). (Prečo? Z reťazca odstránime všetky medzery, takže chceme vedieť, kde funkcia začína a končí bez toho, aby sme sa museli venovať nejakej „gymnastike“.)

3. Implicitné násobenie je povolené iba medzi literálmi a premennými alebo literálmi a funkciami v uvedenom poradí (to znamená, že literály sú vždy na prvom mieste) a môžu byť so zátvorkami alebo bez nich. To znamená:

  • a (4) sa bude považovať za volanie funkcie a nie za * 4
  • A4 nie je povolené
  • 4a a 4 (a) sú v poriadku

Teraz poďme do práce.

Dátové modelovanie

Pomáha vám mať v hlave ukážkový výraz, ktorý si to môžete vyskúšať. Začneme niečím základným: 2y + 1

Očakávame pole, ktoré obsahuje rôzne tokeny vo výraze spolu s ich typmi a hodnotami. V tomto prípade teda očakávame:

0 => Literal (2)1 => Variable (y)2 => Operator (+)3 => Literal (1)

Najskôr definujeme triedu tokenov, ktorá nám uľahčí prácu:

function Token(type, value) { this.type = type; this.value = value}

Algoritmus

Ďalej si vytvorme kostru našej funkcie tokenizéra.

Náš tokenizer prejde každým znakom strpoľa a vytvorí tokeny na základe hodnoty, ktorú nájde.

[Upozorňujeme, že predpokladáme, že používateľ nám dá platný výraz, takže v rámci tohto projektu preskočíme akúkoľvek formu overovania.]

function tokenize(str) { var result=[]; //array of tokens // remove spaces; remember they don't matter? str.replace(/\s+/g, "");
 // convert to array of characters str=str.split("");
str.forEach(function (char, idx) { if(isDigit(char)) { result.push(new Token("Literal", char)); } else if (isLetter(char)) { result.push(new Token("Variable", char)); } else if (isOperator(char)) { result.push(new Token("Operator", char)); } else if (isLeftParenthesis(char)) { result.push(new Token("Left Parenthesis", char)); } else if (isRightParenthesis(char)) { result.push(new Token("Right Parenthesis", char)); } else if (isComma(char)) { result.push(new Token("Function Argument Separator", char)); } });
 return result;}

The code above is fairly basic. For reference, the helpers isDigit() , isLetter(), isOperator(), isLeftParenthesis(), and isRightParenthesis()are defined as follows (don’t be scared by the symbols — it’s called regex, and it’s really awesome):

function isComma(ch) { return (ch === ",");}
function isDigit(ch) { return /\d/.test(ch);}
function isLetter(ch) { return /[a-z]/i.test(ch);}
function isOperator(ch) -
function isLeftParenthesis(ch) { return (ch === "(");}
function isRightParenthesis(ch) { return (ch == ")");}

[Note that there are no isFunction(), isLiteral() or isVariable() functions, because we testing characters individually.]

So now our parser actually works. Try it out on these expressions: 2 + 3, 4a + 1, 5x+ (2y), 11 + sin(20.4).

All good?

Not quite.

You’ll observe that for the last expression, 11 is reported as two Literal tokens instead of one. Also sin gets reported as three tokens instead of one. Why is this?

Let’s pause for a moment and think about this. We tokenized the array character by character, but actually, some of our tokens can contain multiple characters. For example, Literals can be 5, 7.9, .5. Functions can be sin, cos etc. Variables are only single-characters, but can occur together in implicit multiplication. How do we solve this?

Buffers

We can fix this by implementing a buffer. Two, actually. We’ll use one buffer to hold Literal characters (numbers and decimal point), and one for letters (which covers both variables and functions).

How do the buffers work? When the tokenizer encounters a number/decimal point or letter, it pushes it into the appropriate buffer, and keeps doing so until it enters a different kind of operator. Its actions will vary based on the operator.

For instance, in the expression 456.7xy + 6sin(7.04x) — min(a, 7), it should go along these lines:

read 4 => numberBuffer read 5 => numberBuffer read 6 => numberBuffer read . => numberBuffer read 7 => numberBuffer x is a letter, so put all the contents of numberbuffer together as a Literal 456.7 => result read x => letterBuffer read y => letterBuffer + is an Operator, so remove all the contents of letterbuffer separately as Variables x => result, y => result + => result read 6 => numberBuffer s is a letter, so put all the contents of numberbuffer together as a Literal 6 => result read s => letterBuffer read i => letterBuffer read n => letterBuffer ( is a Left Parenthesis, so put all the contents of letterbuffer together as a function sin => result read 7 => numberBuffer read . => numberBuffer read 0 => numberBuffer read 4 => numberBuffer x is a letter, so put all the contents of numberbuffer together as a Literal 7.04 => result read x => letterBuffer ) is a Right Parenthesis, so remove all the contents of letterbuffer separately as Variables x => result - is an Operator, but both buffers are empty, so there's nothing to remove read m => letterBuffer read i => letterBuffer read n => letterBuffer ( is a Left Parenthesis, so put all the contents of letterbuffer together as a function min => result read a=> letterBuffer , is a comma, so put all the contents of letterbuffer together as a Variable a => result, then push , as a Function Arg Separator => result read 7=> numberBuffer ) is a Right Parenthesis, so put all the contents of numberbuffer together as a Literal 7 => result

Complete. You get the hang of it now, right?

We’re getting there, just a few more cases to handle.

This is the point where you sit down and think deeply about your algorithm and data modeling. What happens if my current character is an operator, and the numberBuffer is non-empty? Can both buffers ever simultaneously be non-empty?

Putting it all together, here’s what we come up with (the values to the left of the arrow depict our current character (ch) type, NB=numberbuffer, LB=letterbuffer, LP=left parenthesis, RP=right parenthesis

loop through the array: what type is ch?
digit => push ch to NB decimal point => push ch to NB letter => join NB contents as one Literal and push to result, then push ch to LB operator => join NB contents as one Literal and push to result OR push LB contents separately as Variables, then push ch to result LP => join LB contents as one Function and push to result OR (join NB contents as one Literal and push to result, push Operator * to result), then push ch to result RP => join NB contents as one Literal and push to result, push LB contents separately as Variables, then push ch to result comma => join NB contents as one Literal and push to result, push LB contents separately as Variables, then push ch to result
end loop
join NB contents as one Literal and push to result, push LB contents separately as Variables,

Two things to note.

  1. Notice where I added “push Operator * to result”? That’s us converting the implicit multiplication to explicit. Also, when emptying the contents of LB separately as Variables, we need to remember to insert the multiplication Operator in between them.
  2. At the end of the function’s loop, we need to remember to empty whatever we have left in the buffers.

Translating It to Code

Putting it all together, your tokenize function should look like this now:

We can run a little demo:

var tokens = tokenize("89sin(45) + 2.2x/7");tokens.forEach(function(token, index) { console.log(index + "=> " + token.type + "(" + token.value + ")":});

Wrapping It Up

This is the point where you analyze your function and measure what it does versus what you want it to do. Ask yourself questions like, “Does the function work as intended?” and “Have I covered all edge cases?”

Medzi okrajové prípady môže patriť záporné číslo a podobne. Spustíte tiež testy tejto funkcie. Ak ste na konci spokojní, môžete začať hľadať možnosti, ako to vylepšiť.

Vďaka za prečítanie. Kliknite na srdiečko, aby ste odporučili tento článok, a zdieľajte, ak sa vám páčil! A ak ste vyskúšali iný prístup k vytvoreniu matematického tokenizéra, dajte mi vedieť v komentároch.