Cómo construir un tokenizador de expresiones matemáticas usando JavaScript (o cualquier otro idioma)

Programación

Hace algún tiempo, me inspiré para crear una aplicación para resolver tipos específicos de problemas matemáticos. Descubrí que tenía que analizar la expresión en un árbol de sintaxis abstracto, así que decidí construir un prototipo en Javascript. Mientras trabajaba en el analizador, me di cuenta de que el tokenizador tenía que construirse primero. Te explicaré cómo hacer uno tú mismo. (Advertencia: es más fácil de lo que parece al principio).

¿Qué es un Tokenizer?

Un tokenizador es un programa que divide una expresión en unidades llamadas tokens . Por ejemplo, si tenemos una expresión como "Soy un gran desarrollador", podríamos convertirla en token de diferentes formas, como:

Usando palabras como tokens,

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

Usando caracteres que no son espacios en blanco como tokens,

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

También podríamos considerar a todos los personajes como tokens, para obtener

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

Captas la idea ¿cierto?

Los tokenizadores (también llamados lexers) se utilizan en el desarrollo de compiladores para lenguajes de programación. Ayudan al compilador a dar sentido estructural a lo que está intentando decir. En este caso, sin embargo, estamos construyendo uno para expresiones matemáticas.

Tokens

Una expresión matemática válida consta de tokens matemáticamente válidos, que para los propósitos de este proyecto podrían ser literales , variables , operadores, funciones o separadores de argumentos de función .

Algunas notas sobre lo anterior:

  • Un literal es un nombre elegante para un número (en este caso). Permitiremos números en forma entera o decimal solamente.
  • Una variable es el tipo al que estás acostumbrado en matemáticas: a, b, c, x, y, z. Para este proyecto, todas las variables están restringidas a nombres de una letra (así que nada como var1 o price ). Esto es por lo que podemos tokenize una expresión como ma como el producto de las variables m y una , y no uno sola variable ma .
  • Los operadores actúan sobre literales y variables y los resultados de las funciones. Permitiremos los operadores +, -, *, / y ^.
  • Las funciones son operaciones "más avanzadas". Incluyen cosas como sin (), cos (), tan (), min (), max (), etc.
  • Un Separador de Argumentos de Función es solo un nombre elegante para una coma, usado en un contexto como este: max (4, 5) (el máximo de los dos valores). Lo llamamos Separador de argumentos de función porque, bueno, separa los argumentos de función (para funciones que toman dos o más argumentos, como max y min ).

También agregaremos dos tokens que generalmente no se consideran tokens, pero que nos ayudarán con la claridad: paréntesis izquierdo y derecho . Sabes cuáles son esos.

Algunas consideraciones

Multiplicación implícita

La multiplicación implícita simplemente significa permitir al usuario escribir multiplicaciones “taquigráficas”, como 5x , en lugar de 5 * x . Yendo un paso más allá, también permite hacerlo con funciones ( 5sin (x) = 5 * sin (x) ).

Aún más, permite 5 (x) y 5 (sin (x)). Tenemos la opción de permitirlo o no. Compensaciones? No permitirlo en realidad facilitaría la creación de token y permitiría nombres de variables de varias letras (nombres como price). Permitirlo hace que la plataforma sea más intuitiva para el usuario y, bueno, proporciona un desafío adicional que superar. Elegí permitirlo.

Sintaxis

Si bien no estamos creando un lenguaje de programación, necesitamos tener algunas reglas sobre qué hace que una expresión sea válida, para que los usuarios sepan qué ingresar y qué planear. En términos precisos, los tokens matemáticos deben combinarse de acuerdo con estas reglas de sintaxis para que la expresión sea válida. Estas son mis reglas:

  1. Los tokens pueden estar separados por 0 o más caracteres de espacio en blanco
2+3, 2 +3, 2 + 3, 2 + 3 are all OK 5 x - 22, 5x-22, 5x- 22 are all OK

En otras palabras, el espaciado no importa (excepto dentro de un token de varios caracteres como el Literal 22).

2. Los argumentos de la función deben estar entre paréntesis ( sin (y) , cos (45) , no sin y , cos 45 ). (¿Por qué? Eliminaremos todos los espacios de la cadena, por lo que queremos saber dónde comienza y dónde termina una función sin tener que hacer algo de "gimnasia").

3. La multiplicación implícita sólo se permite entre literales y variables , o literales y funciones , en ese orden (es decir, los literales siempre van primero), y puede ser con o sin paréntesis. Esto significa:

  • a (4) se tratará como una llamada de función en lugar de un * 4
  • a4 no está permitido
  • 4a y 4 (a) están bien

Ahora, manos a la obra.

Modelado de datos

Es útil tener una expresión de muestra en la cabeza para probar esto. Empezaremos con algo básico: 2y + 1

Lo que esperamos es una matriz que enumere los diferentes tokens en la expresión, junto con sus tipos y valores. Entonces, para este caso, esperamos:

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

Primero, definiremos una clase Token para facilitar las cosas:

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

Algoritmo

A continuación, construyamos el esqueleto de nuestra función de tokenizador.

Nuestro tokenizador revisará cada carácter de la strmatriz y creará tokens según el valor que encuentre.

[Tenga en cuenta que estamos asumiendo que el usuario nos da una expresión válida, por lo que omitiremos cualquier forma de validación en este proyecto].

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

El código anterior es bastante básico. Como referencia, los ayudantes isDigit(), isLetter(), isOperator(), isLeftParenthesis(), y isRightParenthesis()se definen de la siguiente manera (no te asustes por los símbolos - se llama expresiones regulares, y es realmente impresionante):

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

[Tenga en cuenta que no hay funciones isFunction () , isLiteral () o isVariable () , porque probamos los caracteres individualmente].

Entonces ahora nuestro analizador realmente funciona. Pruébelo con estas expresiones: 2 + 3, 4a + 1, 5x + (2y), 11 + sin (20.4).

¿Todo bien?

No exactamente.

Observará que para la última expresión, 11 se informa como dos tokens literales en lugar de uno. También sinse informa como tres tokens en lugar de uno. ¿Por qué es esto?

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

Edge cases for this could include negative numbers and the like. You also run tests on the function. If at the end you are satisfied, you may then begin to seek out how you can improve it.

Thanks for reading. Please click the little heart to recommend this article, and share if you enjoyed it! And if you have tried another approach for building a math tokenizer, do let me know in the comments.