Jak vytvořit tokenizer matematického výrazu pomocí JavaScriptu (nebo jiného jazyka)

Zdroj: Wikimedia Commons

Před časem jsem se nechal inspirovat sestavením aplikace pro řešení konkrétních druhů matematických problémů. Zjistil jsem, že musím rozebrat výraz do abstraktního stromu syntaxe, a tak jsem se rozhodl postavit prototyp v Javascriptu. Při práci na syntaktickém analyzátoru jsem si uvědomil, že tokenizer musí být nejprve postaven. Provedu vás, jak to udělat sami. (Varování: je to jednodušší, než na první pohled.)

Co je Tokenizer?

Tokenizer je program, který rozdělí výraz na jednotky nazývané tokeny. Pokud například máme výraz jako „Jsem velký vývojář tuků“, můžeme jej tokenizovat různými způsoby, například:

Pomocí slov jako tokenů

0 => Já jsem
1 => a
2 => velký
3 => tuk
4 => vývojář

Použití znaků bez mezery jako tokenů,

0 => I
1 => ‘
2 => m
3 => a
4 => b
…
16 => p
17 => e
18 => r

Mohli bychom také považovat všechny postavy za tokeny

0 => I
1 => ‘
2 => m
3 => (mezera)
4 => a
5 => (mezera)
6 => b
…
20 => p
21 => e
22 => r

Získáte nápad, že?

Tokenizéry (nazývané také lexery) se používají při vývoji kompilátorů pro programovací jazyky. Pomáhají kompilátoru pochopit strukturální smysl toho, co se snažíte říct. V tomto případě však budujeme jeden pro matematické výrazy.

Tokeny

Platný matematický výraz se skládá z matematicky platných tokenů, které pro účely tohoto projektu mohou být oddělovače literálů, proměnných, operátorů, funkcí nebo argumentů funkcí.
Několik poznámek k výše uvedenému:

  • Literál je fantastické jméno pro číslo (v tomto případě). Povolíme pouze čísla v celé nebo desetinné podobě.
  • Proměnná je druh, na který jste v matematice zvyklí: a, b, c, x, y, z. U tohoto projektu jsou všechny proměnné omezeny na jednopísmenná jména (takže nic jako var1 nebo cena). To je proto, že můžeme vyjádřit výraz jako ma jako součin proměnných ma a ne jednu jedinou proměnnou ma.
  • Operátoři jednají podle literálů a proměnných a výsledků funkcí. Povolíme operátorům +, -, *, / a ^.
  • Funkce jsou „pokročilejší“ operace. Zahrnují věci jako sin (), cos (), tan (), min (), max () atd
  • Oddělovač argumentů funkcí je jen ozdobný název pro čárku, který se používá v kontextu jako je tento: max (4, 5) (maximální jedna ze dvou hodnot). Říkáme tomu separátor argumentů funkcí, protože dobře odděluje argumenty funkcí (pro funkce, které přijímají dva nebo více argumentů, například max a min).

Přidáme také dva tokeny, které se obvykle nepovažují za tokeny, ale pomohou nám to s jasností: Levá a Pravá závorka. Víš, co to je.

Pár úvah

Implicitní násobení

Implicitní násobení jednoduše znamená umožnit uživateli psát „krátkosrsté“ násobení, například 5x, místo 5 * x. Pokud to uděláme o krok dále, umožňuje to také pomocí funkcí (5sin (x) = 5 * sin (x)).

Ještě dále umožňuje 5 (x) a 5 (sin (x)). Máme možnost to povolit nebo ne. Kompromisy? Pokud by to nebylo povoleno, tokenizace by ve skutečnosti usnadňovala a umožnila by názvy proměnných s více písmeny (jména likeprice). Jeho povolení učiní platformu intuitivnější pro uživatele a navíc poskytuje další výzvu k překonání. Rozhodl jsem se, že to dovolím.

Syntax

I když nevytváříme programovací jazyk, potřebujeme určitá pravidla o tom, co vytváří platný výraz, takže uživatelé vědí, do čeho mají vstoupit a víme, na co plánovat. Přesně řečeno, matematické tokeny musí být kombinovány podle těchto syntaktických pravidel, aby byl výraz platný. Zde jsou moje pravidla:

  1. Žetony mohou být odděleny 0 nebo více mezerami
2 + 3, 2 +3, 2 + 3, 2 + 3 jsou v pořádku
5 x 22, 5 x 22, 5 x 22 jsou v pořádku

Jinými slovy, na mezerách nezáleží (s výjimkou znaku s více znaky, jako je Doslovný 22).

2. Argumenty funkcí musí být v závorkách (sin (y), cos (45), nikoli sin y, cos 45). (Proč? Z řetězce odstraníme všechny mezery, takže chceme vědět, kde funkce začíná a končí, aniž bychom museli dělat nějakou „gymnastiku“.)

3. Implicitní násobení je povoleno pouze mezi literály a proměnnými, nebo literály a funkcemi, v tomto pořadí (tj. Literály jsou vždy na prvním místě) a může být s nebo bez závorek. To znamená:

  • a (4) bude považováno spíše za volání funkce než * 4
  • a4 není povoleno
  • 4a a 4 (a) jsou v pořádku

Teď pojďme do práce.

Modelování dat

Pomůže to mít vzorový výraz ve vaší hlavě, aby se to otestovalo. Začneme něčím základním: 2 let + 1

Očekáváme pole, které uvádí různé tokeny ve výrazu, spolu s jejich typy a hodnotami. V tomto případě tedy očekáváme:

0 => doslovný (2)
1 => Proměnná (y)
2 => Operátor (+)
3 => doslovný (1)

Nejprve definujeme třídu tokenů, abychom věci usnadnili:

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

Algoritmus

Dále vytvořme kostru naší funkce tokenizéru.

Náš tokenizer projde každou postavou pole str a sestaví tokeny na základě nalezené hodnoty.

[Pamatujte, že předpokládáme, že nám uživatel poskytne platný výraz, takže během tohoto projektu vynecháme jakoukoli formu ověřování.]

funkční tokenize (str) {
  var result = []; // pole tokenů
  
  // odstranit mezery; vzpomínáš, že na tom nezáleží
  str.replace (/ \ s + / g, "");
  // převést na pole znaků
  str = str.split ("");
str.forEach (funkce (char, idx) {
    if (isDigit (char)) {
      result.push (nový token ("doslovný", char));
    } jinak pokud (isLetter (char)) {
      result.push (new Token ("Variable", char));
    } jinak pokud (isOperator (char)) {
      result.push (new Token ("Operator", char));
    } jinak pokud (isLeftParenthesis (char)) {
      result.push (nový token („Levá závorka“, char));
    } jinak pokud (isRightParenthesis (char)) {
      result.push (new Token ("Right Parenthesis", char));
    } jinak pokud (isComma (char)) {
      result.push (new Token ("Function Argument Separator", char));
    }
  });
  návratový výsledek;
}

Výše uvedený kód je dosti základní. Pro informaci jsou pomocníci Digit (), isLetter (), isOperator (), isLeftParenthesis () a isRightParenthesis () definovány následovně (nebojte se symbolů - nazývá se regex a je to opravdu úžasné):

funkce isComma (ch) {
 návrat (ch === ",");
}
funkce isDigit (ch) {
 návrat /\d/.test(ch);
}
funkce isLetter (ch) {
 return /[a-z]/i.test(ch);
}
funkce isOperator (ch) {
 return /\+|-|\*|\/|\^/.test(ch);
}
funkce isLeftParenthesis (ch) {
 návrat (ch === "(");
}
funkce isRightParenthesis (ch) {
 návrat (ch == ")");
}

[Všimněte si, že neexistují žádné funkce isFunction (), isLiteral () nebo isVariable (), protože testujeme znaky jednotlivě.]

Nyní náš parser skutečně funguje. Vyzkoušejte tyto výrazy: 2 + 3, 4a + 1, 5x + (2r), 11 + hřích (20,4).

Vše dobré?

Ne tak docela.

Všimněte si, že u posledního výrazu je 11 hlášeno jako dva doslovné znaky místo jednoho. Také hřích je hlášen jako tři žetony místo jednoho. Proč je to?

Zastavme se na chvíli a přemýšlejte o tom. Ukládali jsme token znaku pole po znaku, ale ve skutečnosti mohou některé z našich tokenů obsahovat více znaků. Například literály mohou být 5, 7,9, 0,5. Funkce mohou být hřích, cos atd. Proměnné jsou pouze znaky, ale mohou se vyskytovat společně v implicitním násobení. Jak to vyřešíme?

Nárazníky

Můžeme to vyřešit implementací vyrovnávací paměti. Vlastně dva. Použijeme jednu vyrovnávací paměť k uchování doslovných znaků (čísla a desetinná tečka) a jednu pro písmena (pokrývající proměnné i funkce).

Jak fungují vyrovnávací paměti? Když tokenizer narazí na číslo / desetinná tečka nebo písmeno, vtlačí je do příslušné vyrovnávací paměti a bude to dělat, dokud nevstoupí na jiný druh operátora. Jeho akce se budou lišit v závislosti na provozovateli.

Například ve výrazu 456,7xy + 6sin (7,04x) - min (a, 7) by mělo jít podle těchto řádků:

číst 4 => numberBuffer
 číst 5 => numberBuffer
 číst 6 => numberBuffer
 číst. => numberBuffer
 číst 7 => numberBuffer
 x je dopis, takže celý obsah numberbufferu dejte dohromady jako doslovný výsledek 456.7 =>
 číst x => letterBuffer
 přečtěte y => letterBuffer
 + je Operátor, takže veškerý obsah letterbufferu odstraňte samostatně jako Proměnné x => výsledek, y => výsledek
 + => výsledek
 číst 6 => numberBuffer
 s je dopis, takže dát celý obsah numberbuffer dohromady jako doslovný 6 => výsledek
 číst s => letterBuffer
 přečtěte si i => letterBuffer
 číst n => letterBuffer
 (Jedná se o levou závorku, takže celý obsah letterbufferu dejte dohromady jako funkci sin => result
 číst 7 => numberBuffer
 číst. => numberBuffer
 číst 0 => numberBuffer
 číst 4 => numberBuffer
 x je písmeno, takže celý obsah numberbufferu dejte dohromady jako doslovný výsledek 7.04 =>
 číst x => letterBuffer
 ) je pravá závorka, takže veškerý obsah letterbufferu odstraňte samostatně jako výsledek proměnných x =>
 - je operátor, ale oba vyrovnávací paměti jsou prázdné, takže není co odstranit
 přečtěte m => letterBuffer
 přečtěte si i => letterBuffer
 číst n => letterBuffer
 (Jedná se o levou závorku, takže celý obsah letterbufferu dejte dohromady jako funkci min => výsledek
 přečtěte a => letterBuffer
 , je čárka, takže veškerý obsah letterbufferu dejte dohromady jako proměnnou a => výsledek, poté stiskněte jako oddělovač funkcí Arg = = výsledek
 číst 7 => numberBuffer
 ) je pravá závorka, takže celý obsah numberbufferu dejte dohromady jako doslovný výsledek 7 =>

Kompletní. Teď to pochopíš, že?

Dostáváme se tam, jen pár dalších případů, které musíme vyřídit.

To je místo, kde si sednete a hluboce přemýšlíte o svém algoritmu a modelování dat. Co se stane, když je moje současná postava operátorem a číslo numberufuffer není prázdné? Mohou být oba nárazníky někdy současně neprázdné?

Když to dáme dohromady, tady je to, s čím jsme přišli (hodnoty nalevo od šipky znázorňují náš aktuální typ znaku (ch), NB = numberbuffer, LB = letterbuffer, LP = levá závorka, RP = pravá závorka)

smyčka přes pole:
  jaký je typ ch?
číslice => tlačit ch na NB
  desetinná tečka => tlačit ch do NB
  letter => spojit NB obsah jako jeden doslovný a tlačit k výsledku, pak tlačit ch k LB
  operator => spojit obsah NB jako jeden doslovný a tlačit k výsledku NEBO zatlačit obsah LB samostatně jako proměnné, poté stisknout ch k výsledku
  LP => spojit LB obsah jako jednu funkci a tlačit na výsledek NEBO (spojit obsah NB jako jeden doslovný a tlačit na výsledek, stisknout Operator * na výsledek), pak stiskem ch na výsledek
  RP => spojit obsah NB jako jeden doslovný a tlačit na výsledek, posunout obsah LB odděleně jako proměnné, poté stisknout ch na výsledek
  čárka => spojit obsah NB jako jeden doslovný a tlačit na výsledek, posunout obsah LB odděleně jako proměnné, poté stisknout ch na výsledek
koncová smyčka
spojit obsah NB jako jeden doslovný a usilovat o výsledek, posunout obsah LB samostatně jako proměnné,

Dvě věci na vědomí.

  1. Všimněte si, kam jsem přidal „push Operator * to result“? Převedeme implicitní násobení na explicitní. Také při vyprazdňování obsahu LB samostatně jako proměnných musíme mít na paměti, že mezi ně vložíme operátora multiplikace.
  2. Na konci smyčky funkce si musíme pamatovat na vyprázdnění všeho, co jsme nechali v bufferech.

Překlad do kódu

Když to dáte dohromady, vaše funkce tokenize by nyní měla vypadat takto:

Můžeme spustit malou ukázku:

var tokeny = tokenize ("89sin (45) + 2,2x / 7");
tokens.forEach (funkce (token, index) {
  console.log (index + "=>" + token.type + "(" + token.value + ")":
});
To jo! Všimněte si přidaných * s pro implicitní násobení

Zabalení

To je místo, kde analyzujete svou funkci a měříte, co dělá, a co chcete dělat. Zeptejte se sami sebe, například: „Funguje funkce tak, jak bylo zamýšleno?“ A „Pokryla jsem všechny okrajové případy?“

Hraniční případy by mohly zahrnovat záporná čísla a podobně. Spustíte také testy funkce. Pokud jste na konci spokojeni, můžete začít hledat, jak ji vylepšit.

Děkuji za přečtení. Kliknutím na malé srdce doporučte tento článek a sdílejte jej, pokud se vám to líbilo! A pokud jste vyzkoušeli jiný přístup k vytvoření matematického tokenizéru, dejte mi vědět v komentářích.