7

Hm, esto es independiente del idioma, preferiría hacerlo en C# o F #, pero esta vez me interesa más la pregunta "¿Cómo funcionaría eso de todos modos?".¿Cómo codificaría un analizador de fórmulas complejas manualmente?

Lo que quiero lograr ist:

a) quiero aprender que - se trata de mi ego esta vez, es para un proyecto divertido donde quiero mostrar mi mismo que soy una muy buena en este cosas

b) Sé un poquito acerca de EBNF (aunque todavía no sé cómo funciona la precedencia del operador en EBNF - Irony.NET lo hace bien, he comprobado los ejemplos, pero esto es un poco ominoso para yo)

c) Mi analizador debería ser capaz de tomar esto: 5 * (3 + (2 - 9 * (5/7)) + 9) por ejemplo y darme los resultados correctos

d) Para ser franco, este parece ser el mayor problema al escribir un compilador o incluso un intérprete para mí. No tendría problemas para generar código de ensamblador de 64 bits (PUEDO escribir el ensamblador manualmente), pero el analizador de fórmulas ...

e) Otra idea: incluso computadoras simples (como mi antiguo Sharp 1246S con solo 2kB de RAM)) puede hacer eso ... no puede ser tan difícil, ¿verdad? E incluso muy, muy viejos lenguajes de programación tienen evaluación de fórmula ... BASIC es de 1964 y ya podían calcular el tipo de fórmula que presenté como ejemplo

f) Algunas ideas, algunas inspiraciones serían realmente suficientes - Simplemente no tengo ni idea de cómo hacer la precedencia del operador y los paréntesis, SÍ, SÍ, sé que implica un AST y que muchas personas usan una pila

Entonces, ¿qué opinas?

Respuesta

5

Deberías ir aprender sobre Recursive Descent parsers.

Comprobar a cabo un ejercicio Código de golf en hacer precisamente esto, 10 formas diferentes:

Code Golf: Mathematical expression evaluator (that respects PEMDAS)

Varias de estas soluciones "golf" son programas de análisis descendente recursivo simplemente codificados de diferentes maneras.

Descubrirá que el análisis de solo expresiones es de lejos el más fácil de que hay en un compilador. Analizar el resto del lenguaje es más difícil, pero es mucho más difícil entender cómo interactúan los elementos del código y cómo generar un buen código.

Puede que también le interese saber cómo expresar un analizador usando BNF y cómo hacer algo con ese BNF. Aquí está un example of how to parse and manipulate algebra symbolically con un BNF explícito y un AST implícito como base. Esto no es lo que tradicionalmente hacen los compiladores, pero la maquinaria que lo hace se basa profundamente en la tecnología del compilador.

+0

¡Oh, eso ayuda mucho! No estoy del todo seguro acerca de "más fácil" todavía, pero ... ;-) – StormianRootSolver

+0

Code golf no es la mejor manera de aprender a hacer algo como esto. O, de hecho, para aprender cualquier cosa que no sea código de golf. Pero tienes razón en que el análisis de expresiones no es la parte más difícil. –

+0

En general, el código de golf no lo es. Sin embargo, varias de las respuestas están codificadas con bastante claridad, y como no son muy largas, se puede aprender mucho de ellas. –

1

Tradicionalmente, los procesadores de fórmulas de las computadoras utilizan la notación POSTFIX. Usan una pila, abren 2 elementos como operandos, abren el tercer elemento como operador y presionan el resultado.

Lo que quiere es un convertidor de notación INFIX a POSTFIX que es realmente bastante simple. Una vez que estés en el proceso de postfix es lo más simple que harás.

+0

s/pop 2 elementos como operadores/pop 2 elementos como operandos – tpdi

+0

¡Notación de Postfix! Sí, lo intentaré primero! ¡Gracias! :-) – StormianRootSolver

+0

Lo que dijo que quería hacer era expresiones * infix *, no postfix. –

1

Para un analizador basado en pila implementado en PHP que utiliza el algoritmo de playa de vías de Djikstra para convertir infija a la notación de sufijo, y con soporte para funciones con un número variable de argumentos, se puede ver en la fuente para el motor PHPExcel cálculo

Cuestiones relacionadas