Sådan opbygges en matematisk ekspressionstokenizer ved hjælp af JavaScript (eller ethvert andet sprog)

For længe siden blev jeg inspireret til at oprette en app til løsning af bestemte typer matematiske problemer. Jeg opdagede, at jeg var nødt til at analysere udtrykket i et abstrakt syntaks-træ, så jeg besluttede at bygge en prototype i Javascript. Mens jeg arbejdede på parseren, indså jeg, at tokeniseren først skulle bygges. Jeg leder dig gennem, hvordan du selv laver en. (Advarsel: det er lettere end det ser ud i starten.)

Hvad er en Tokenizer?

En tokenizer er et program, der opdeler et udtryk i enheder kaldet tokens . For eksempel, hvis vi har et udtryk som "Jeg er en stor fedtudvikler", kunne vi tokenisere det på forskellige måder, såsom:

Brug af ord som tokens,

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

Brug af tegn, der ikke er mellemrum som tokens,

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

Vi kunne også overveje alle tegn som tokens for at få

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

Du får ideen, ikke?

Tokenizers (også kaldet lexers) bruges i udviklingen af ​​compilers til programmeringssprog. De hjælper kompilatoren med at give strukturel mening ud af, hvad du prøver at sige. I dette tilfælde bygger vi dog en til matematiske udtryk.

Poletter

Et gyldigt matematisk udtryk består af matematiske gyldige tokens, som i forbindelse med dette projekt kan være bogstaver , variabler , operatører, funktioner eller funktionsargumentadskillere .

Et par bemærkninger til ovenstående:

  • En bogstavelig er et smukt navn på et nummer (i dette tilfælde). Vi tillader kun tal i hel eller decimal form.
  • En variabel er den slags, du er vant til i matematik: a, b, c, x, y, z. I dette projekt er alle variabler begrænset til navne på et bogstav (så intet som var1 eller pris ). Dette er, så vi kan tokenisere et udtryk som ma som produktet af variablerne m og a , og ikke en enkelt variabel ma .
  • Operatører handler om litteratur og variabler og resultaterne af funktioner. Vi tillader operatører +, -, *, /, og ^.
  • Funktioner er “mere avancerede” operationer. De inkluderer ting som synd (), cos (), tan (), min (), max () osv
  • En funktionsargumentudskiller er bare et fancy navn til et komma, der bruges i en sammenhæng som denne: max (4, 5) (den maksimale af de to værdier). Vi kalder det en funktionsargumentudskiller, fordi den, ja, adskiller funktionsargumenter (for funktioner, der tager to eller flere argumenter, såsom maks og min ).

Vi tilføjer også to tokens, der normalt ikke betragtes som tokens, men som hjælper os med klarhed: venstre og højre parentes . Du ved hvad de er.

Et par overvejelser

Implicit multiplikation

Implicit multiplikation betyder simpelthen at lade brugeren skrive “stenografi” multiplikationer, såsom 5x , i stedet for 5 * x . Hvis du tager det et skridt videre, tillader det også at gøre det med funktioner ( 5sin (x) = 5 * sin (x) ).

Endnu længere tillader det 5 (x) og 5 (sin (x)). Vi har mulighed for at tillade det eller ej. Afvejninger? Hvis det ikke tillades, ville det faktisk gøre tokenisering lettere og muliggøre navne på flere bogstaver (navne som price). At lade det gøre platformen mere intuitiv for brugeren og godt giver en ekstra udfordring at overvinde. Jeg valgte at tillade det.

Syntaks

Mens vi ikke opretter et programmeringssprog, skal vi have nogle regler om, hvad der gør et gyldigt udtryk, så brugerne ved, hvad de skal indtaste, og vi ved, hvad de skal planlægge. I nøjagtige termer skal matematiske tokens kombineres i henhold til disse syntaksregler for at udtrykket skal være gyldigt. Her er mine regler:

  1. Tokens kan adskilles med 0 eller flere tegn i mellemrummet
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

Med andre ord betyder afstand ikke noget (undtagen inden for et tegn med flere tegn som den bogstavelige 22).

2. Funktionsargumenter skal være i parentes ( sin (y) , cos (45) , ikke sin y , cos 45 ). (Hvorfor? Vi fjerner alle mellemrum fra strengen, så vi vil vide, hvor en funktion starter og slutter uden at skulle lave noget "gymnastik".)

3. Implicit multiplikation er kun tilladt mellem bogstaver og variabler eller bogstaver og funktioner i den rækkefølge (det vil sige, at bogstaver altid kommer først) og kan være med eller uden parenteser. Det betyder:

  • a (4) behandles som et funktionsopkald snarere end et * 4
  • a4 er ikke tilladt
  • 4a og 4 (a) er OK

Lad os nu komme på arbejde.

Datamodellering

Det hjælper med at have et prøveudtryk i hovedet for at teste dette på. Vi starter med noget grundlæggende: 2y + 1

Hvad vi forventer er en matrix, der viser de forskellige tokens i udtrykket sammen med deres typer og værdier. Så i denne sag forventer vi:

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

Først definerer vi en token-klasse for at gøre tingene lettere:

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

Algoritme

Lad os derefter bygge skelet til vores tokenizer-funktion.

Vores tokenizer gennemgår hver karakter i strarrayet og bygger tokens baseret på den værdi, den finder.

[Bemærk, at vi antager, at brugeren giver os et gyldigt udtryk, så vi springer enhver form for validering over hele dette projekt.]

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;}

Koden ovenfor er ret grundlæggende. For reference, hjælperne isDigit(), isLetter(), isOperator(), isLeftParenthesis(), og isRightParenthesis()er defineret som følger (ikke være bange ved symbolerne - det hedder regex, og det er virkelig fantastisk):

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 == ")");}

[Bemærk, at der ikke er nogen isFunction () , isLiteral () eller isVariable () funktioner, fordi vi tester tegn individuelt.]

Så nu fungerer vores parser faktisk. Prøv det på disse udtryk: 2 + 3, 4a + 1, 5x + (2y), 11 + sin (20.4).

Alt godt?

Ikke helt.

Du bemærker, at 11 for det sidste udtryk rapporteres som to bogstavelige tokens i stedet for en. Også sinbliver rapporteret som tre brikker i stedet for én. Hvorfor er det?

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?”

Kantsager til dette kan omfatte negative tal og lignende. Du kører også tests på funktionen. Hvis du i slutningen er tilfreds, kan du måske begynde at finde ud af, hvordan du kan forbedre det.

Tak for læsningen. Klik på det lille hjerte for at anbefale denne artikel, og del, hvis du nød det! Og hvis du har prøvet en anden tilgang til opbygning af en matematisk tokenizer, så lad mig det vide i kommentarerne.