algorithm - Analizador de ecuación(expresión) con precedencia?
parsing equation (22)
Desarrollé un analizador de ecuaciones usando un algoritmo de pila simple que manejará operadores binarios (+, -, |, &, *, /, etc.), operadores unarios (!) Y paréntesis.
El uso de este método, sin embargo, me deja con todo lo que tiene la misma precedencia: se evalúa de izquierda a derecha independientemente del operador, aunque la precedencia se puede aplicar mediante paréntesis.
Entonces, ahora "1 + 11 * 5" devuelve 60, no 56 como cabría esperar.
Si bien esto es adecuado para el proyecto actual, quiero tener una rutina de propósito general que pueda usar para proyectos posteriores.
Editado por claridad:
¿Qué es un buen algoritmo para analizar ecuaciones con precedencia?
Me interesa algo sencillo de implementar y entiendo que puedo codificarme para evitar problemas de licencia con el código disponible.
Gramática:
No entiendo la pregunta de gramática. He escrito esto a mano. Es tan simple que no veo la necesidad de YACC o Bison. Simplemente necesito calcular cadenas con ecuaciones como "2 + 3 * (42/13)".
Idioma:
Estoy haciendo esto en C, pero estoy interesado en un algoritmo, no en una solución específica de idioma. C es un nivel suficientemente bajo como para que sea fácil convertirlo a otro idioma si surge la necesidad.
Ejemplo de código
Publiqué el código de prueba para el analizador de expresiones simples del que estaba hablando anteriormente. Los requisitos del proyecto se modificaron y nunca necesité optimizar el código para el rendimiento o el espacio, ya que no se incorporó al proyecto. Está en la forma verbosa original, y debe ser fácilmente comprensible. Si hago algo más con eso en términos de precedencia del operador, probablemente elijo el macro hack porque coincide con el resto del programa en simplicidad. Si alguna vez uso esto en un proyecto real, iré por un analizador más compacto / rápido.
Pregunta relacionada
-Adán
El camino difícil
Quieres un analizador de descenso recursivo .
Para obtener prioridad, debe pensar de forma recursiva, por ejemplo, utilizando su secuencia de muestra,
1+11*5
para hacerlo manualmente, tendrías que leer el 1 , luego ver el más y comenzar una nueva "sesión" de análisis recursivo comenzando con 11 ... y asegurarte de analizar el 11 * 5 en su propio factor, produciendo un análisis árbol con 1 + (11 * 5) .
Todo esto se siente tan doloroso incluso para intentar explicar, especialmente con la impotencia añadida de C. See, después de analizar el 11, si el * fuera en realidad un +, tendrías que abandonar el intento de hacer un término y en su lugar analizar el 11 sí mismo como un factor. Mi cabeza ya está explotando. Es posible con la estrategia decente recursiva, pero hay una mejor manera ...
La manera fácil (correcta)
Si usa una herramienta GPL como Bison, probablemente no tenga que preocuparse por los problemas de licencia, ya que el código C generado por bison no está cubierto por la GPL (IANAL, pero estoy bastante seguro de que las herramientas GPL no fuerzan la GPL código / binarios generados; por ejemplo, Apple compila código como por ejemplo, Aperture con GCC y lo venden sin tener que indicar el código GPL).
Descargue Bison (o algo equivalente, ANTLR, etc.).
Por lo general, hay un código de muestra en el que puede ejecutar bison y obtener el código C deseado que demuestra esta calculadora de cuatro funciones:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Mire el código generado, y vea que esto no es tan fácil como parece. Además, las ventajas de usar una herramienta como Bison son: 1) aprendes algo (especialmente si lees el libro del Dragón y aprendes sobre las gramáticas), 2) evitas que los NIH intenten reinventar la rueda. Con una verdadera herramienta generadora de analizadores, en realidad tiene la esperanza de escalar más adelante, mostrando a otras personas que usted sabe que los analizadores son el dominio de las herramientas de análisis.
Actualizar:
La gente de aquí ha ofrecido muchos buenos consejos. Mi única advertencia contra omitir las herramientas de análisis o simplemente usar el algoritmo de Shunting Yard o un analizador de voz recursivo enrollado a mano es que los pequeños lenguajes de juguete 1 algún día pueden convertirse en grandes lenguajes con funciones (sin, cos, log) y variables, condiciones y para bucles.
Flex / Bison puede ser excesivo para un intérprete pequeño y simple, pero un analizador sintáctico puede causar problemas cuando se deben hacer cambios o se deben agregar características. Su situación variará y tendrá que usar su juicio; simplemente no 1 [2] y construya una herramienta que no sea adecuada.
Mi herramienta favorita para analizar
La mejor herramienta del mundo para el trabajo es la biblioteca Parsec (para analizadores de voz recursivos) que viene con el lenguaje de programación Haskell. Se parece mucho a BNF , o como una herramienta especializada o lenguaje específico de dominio para el análisis (código de muestra [3]), pero de hecho es solo una biblioteca común en Haskell, lo que significa que compila en el mismo paso de compilación que el resto de su código Haskell, y puede escribir código Haskell arbitrario y llamarlo dentro de su analizador, y puede mezclar y combinar otras bibliotecas, todas en el mismo código . (Incrustar un lenguaje de análisis como este en un lenguaje distinto de Haskell da como resultado un montón de cruces sintácticos, por cierto. Lo hice en C # y funciona bastante bien, pero no es tan bonito y conciso).
Notas:
1 Richard Stallman dice, en Por qué no deberías usar Tcl
La principal lección de Emacs es que un lenguaje para extensiones no debe ser un mero "lenguaje de extensión". Debe ser un lenguaje de programación real, diseñado para escribir y mantener programas sustanciales. ¡Porque la gente querrá hacer eso!
[2] Sí, estoy marcado por el uso de ese "lenguaje".
También tenga en cuenta que cuando presenté esta entrada, la vista previa era correcta, pero el analizador SO menos que adecuado comió mi etiqueta de anclaje cercano en el primer párrafo , lo que demuestra que los analizadores no son algo con lo que se debe jugar, porque si usa expresiones regulares y uno lo piratea probablemente obtendrá algo sutil y pequeño mal .
[3] Fragmento de un analizador Haskell usando Parsec: una calculadora de cuatro funciones extendida con exponentes, paréntesis, espacios en blanco para multiplicación y constantes (como pi y e).
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (/x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
¿Has pensado en utilizar Boost Spirit ? Le permite escribir gramáticas similares a EBNF en C ++ de esta manera:
group = ''('' >> expression >> '')'';
factor = integer | group;
term = factor >> *((''*'' >> factor) | (''/'' >> factor));
expression = term >> *((''+'' >> term) | (''-'' >> term));
Actualmente estoy trabajando en una serie de artículos construyendo un analizador de expresiones regulares como una herramienta de aprendizaje para patrones de diseño y programación legible. Puedes echar un vistazo a readablecode . El artículo presenta un uso claro del algoritmo de yardas de maniobras.
Al hacer su pregunta, no hay necesidad de recursividad alguna. La respuesta es tres cosas: notación de Postfix más algoritmo de yarda de maniobra más evaluación de expresión de Postfix:
1). Notación de Postfix = inventado para eliminar la necesidad de especificación de precedencia explícita. Lea más en la red, pero aquí está lo esencial: expresión infija (1 + 2) * 3, mientras que a los humanos les resulta fácil de leer y procesar para computar a través de la máquina. ¿Que es? Regla simple que dice "reescribir la expresión guardando en caché en precedencia, luego siempre procesarla de izquierda a derecha". Entonces, infijo (1 + 2) * 3 se convierte en un postfijo 12 + 3 *. POST porque el operador se coloca siempre DESPUÉS de los operandos.
2). Evaluar la expresión de postfix. Fácil. Lee los números de la cadena de postfijo. Empujarlos en una pila hasta que se vea a un operador. Verifique el tipo de operador: ¿unario? ¿binario? ¿terciario? Pop tantos operandos de la pila como sea necesario para evaluar este operador. Evaluar. ¡Devuelve el resultado a la pila! Y estás casi hecho. Sigue haciéndolo hasta que stack tenga solo una entrada = valor que busques.
Vamos a hacer (1 + 2) * 3 que está en postfix es "12 + 3 *". Lea el primer número = 1. Introdúzcalo en la pila. Lea a continuación. Número = 2. Empujarlo en la pila. Lea a continuación. Operador. ¿Cúal? +. ¿Que tipo? Binary = necesita dos operandos. Pop stack dos veces = argright es 2 y argleft es 1. 1 + 2 es 3. Presione 3 nuevamente en la pila. Lea a continuación de la cadena postfix. Es un número. 3. Presione. Lea a continuación. Operador. ¿Cúal? *. ¿Que tipo? Binary = necesita dos números -> pop stack dos veces. Primero ingrese en argright, segunda vez en argleft. Evaluar la operación - 3 veces 3 es 9. Empujar 9 en la pila. Lee el siguiente postfix char. Es nulo. Fin de la entrada. Pop stack onec = esa es tu respuesta.
3). Shunting Yard se utiliza para transformar la expresión infija humana (fácilmente) legible en expresión de postfijo (también es fácil de leer para humanos después de un poco de práctica). Fácil de codificar manualmente. Ver comentarios arriba y netos.
Aquí hay un buen artículo sobre cómo combinar un analizador de bajada recursiva simple con un análisis de precedencia de operador. Si ha estado escribiendo analizadores recientemente, debería ser muy interesante e instructivo para leer.
Aquí puede encontrar una solución de Python que usa pyparsing. El análisis de la notación infija con varios operadores con precedencia es bastante común, por lo que pyparsing también incluye el generador de expresiones operatorPrecedence. Con él, puede definir fácilmente expresiones booleanas usando "Y", "O", "NO", por ejemplo. O puede ampliar su aritmética de cuatro funciones para usar otros operadores, como! para factorial, o ''%'' para módulo, o agregue operadores P y C para calcular permutaciones y combinaciones. Puede escribir un analizador de infijo para la notación de matriz, que incluye el manejo de operadores ''-1'' o ''T'' (para inversión y transposición). El operador Ejemplo de precedencia de un analizador sintáctico de 4 funciones (con ''!'' Arrojado por diversión) está here y un analizador y evaluador con más funciones está here .
Ayudaría si pudieras describir la gramática que estás usando actualmente para analizar. ¡Parece que el problema podría estar ahí!
Editar:
El hecho de que no entiendas la pregunta gramatical y de que "hayas escrito esto a mano" muy probablemente explica por qué estás teniendo problemas con las expresiones del formulario "1 + 11 * 5" (es decir, con precedencia del operador) . La búsqueda en Google de "gramática para expresiones aritméticas", por ejemplo, debería arrojar algunos buenos indicadores. Tal gramática no necesita ser complicada:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
Haría el truco, por ejemplo, y se puede aumentar de manera trivial para encargarse de algunas expresiones más complicadas (incluyendo funciones, por ejemplo, o poderes, ...).
Sugiero que eche un vistazo a this hilo, por ejemplo.
Casi todas las introducciones a gramáticas / análisis tratan expresiones aritméticas como un ejemplo.
Tenga en cuenta que el uso de una gramática no implica en absoluto el uso de una herramienta específica ( a la Yacc, Bison, ...). De hecho, sin dudas ya estás usando la siguiente gramática:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(o algo por el estilo) sin saberlo!
Depende de qué tan "general" quieras que sea.
Si quieres que sea realmente muy general, como ser capaz de analizar funciones matemáticas, así como sin (4 + 5) * cos (7 ^ 3) probablemente necesitarás un árbol de análisis sintáctico.
En el cual, no creo que una implementación completa sea adecuada para ser pegada aquí. Sugeriría que eches un vistazo al infame " Libro del dragón ".
Pero si solo quieres soporte de precedencia , entonces puedes hacer eso convirtiendo primero la expresión a formulario de postfix en el que un algoritmo que puedes copiar y pegar debería estar disponible desde google o creo que puedes codificarlo tú mismo con un binario árbol.
Cuando lo tienes en forma de postfijo, entonces es pan comido a partir de entonces ya que ya entiendes cómo ayuda la pila.
El algoritmo del patio de maniobras es la herramienta adecuada para esto. Wikipedia es realmente confuso sobre esto, pero básicamente el algoritmo funciona así:
Digamos que quieres evaluar 1 + 2 * 3 + 4. Intuitivamente, "sabes" que primero tienes que hacer el 2 * 3, pero ¿cómo obtienes este resultado? La clave es darse cuenta de que cuando está escaneando la cadena de izquierda a derecha, evaluará a un operador cuando el operador que lo sigue tenga una precedencia menor (o igual a). En el contexto del ejemplo, esto es lo que quieres hacer:
- Mira: 1 + 2, no hagas nada.
- Ahora mira 1 + 2 * 3, aún no hagas nada.
- Ahora mira 1 + 2 * 3 + 4, ahora sabes que 2 * 3 tiene que ser evaluado porque el siguiente operador tiene menor precedencia.
¿Cómo implementa esto?
Desea tener dos pilas, una para números y otra para operadores. Empujas números a la pila todo el tiempo. Compara cada operador nuevo con el que se encuentra en la parte superior de la pila, si el que se encuentra en la parte superior tiene mayor prioridad, lo levantas de la pila del operador, extraes los operandos de la pila de números, aplicas el operador y presionas el resultado en la pila de números. Ahora repites la comparación con el operador de la parte superior de la pila.
Volviendo al ejemplo, funciona así:
N = [] Ops = []
- Leer 1. N = [1], Ops = []
- Leer +. N = [1], Ops = [+]
- Leer 2. N = [1 2], Ops = [+]
- Leer
*. N = [1 2], Ops = [+ *] - Leer 3. N = [1 2 3], Ops = [+ *]
- Leer +. N = [1 2 3], Ops = [+ *]
- Pop 3, 2 y ejecuta 2
*3, y envía el resultado a N. N = [1 6], Ops = [+] -
+se deja asociativo, por lo que también quiere mostrar 1, 6 y ejecutar el signo +. N = [7], Ops = []. - Finalmente, presione el [+] en la pila del operador. N = [7], Ops = [+].
- Pop 3, 2 y ejecuta 2
- Leer 4. N = [7 4]. Ops = [+].
- Se ha agotado la entrada, por lo que quiere vaciar las pilas ahora. Sobre el cual obtendrás el resultado 11.
Ahí, eso no es tan difícil, ¿verdad? Y no hace invocaciones a ninguna gramáticas o generadores de analizadores sintácticos.
Encontré esto en la lista de PIC sobre el algoritmo de Shunting Yard :
Harold escribe:
Recuerdo haber leído, hace mucho tiempo, un algoritmo que convertía expresiones algebraicas a RPN para una fácil evaluación. Cada valor infijo, operador o paréntesis estaba representado por un vagón de ferrocarril en una pista. Un tipo de automóvil se dividió en otra pista y el otro continuó recto. No recuerdo los detalles (¡obviamente!), Pero siempre pensé que sería interesante codificar. Esto está de vuelta cuando escribía el código de ensamblaje 6800 (no 68000).
Este es el "algoritmo del jardín de maniobras" y es lo que la mayoría de los analizadores de máquinas usan. Ver el artículo sobre análisis en Wikipedia. Una forma fácil de codificar el algoritmo del jardín de maniobras es usar dos pilas. Una es la pila "push" y la otra la pila "reduce" o "result". Ejemplo:
pstack = () // empty rstack = () input: 1 + 2 * 3 precedence = 10 // la reducción más baja = 0 // no se reduce
start: token ''1'': isnumber, poner en pstack (push) token ''+'': isoperator establecer precedence = 2 si precedence <previous_operator_precedence luego reducir () // ver abajo poner ''+'' en pstack (push) token ''2'' : isnumber, poner pstack (push) token ''*'': isoperator, establecer precedence = 1, poner pstack (push) // verificar precedencia como // encima de token ''3'': isnumber, poner en pstack (push) end of entrada, necesidad de reducir (objetivo es vacío pstack) reducir () // hecho
para reducir, extraer elementos de la pila de inserción y colocarlos en la pila de resultados, siempre intercambie los 2 elementos superiores en pstack si son de la forma ''operador'' ''número'':
pstack: ''1'' ''+'' ''2'' '' '' ''3'' rstack: () ... pstack: () rstack: ''3'' ''2'' '' '' ''1'' ''+''
si la expresión hubiera sido:
1 * 2 + 3
entonces el disparador de reducción habría sido la lectura del token ''+'' que tiene menor precendencia que el ''*'' ya empujado, por lo que habría hecho:
pstack: ''1'' '' '' ''2'' rstack: () ... pstack: () rstack: ''1'' ''2'' '' ''
y luego presionó ''+'' y luego ''3'' y finalmente se redujo:
pstack: ''+'' ''3'' rstack: ''1'' ''2'' '' '' ... pstack: () rstack: ''1'' ''2'' '' '' ''3'' ''+''
Entonces, la versión corta es: números de empuje, cuando los operadores de empuje verifican la precedencia del operador anterior. Si era más alto que el del operador que debe empujarse ahora, primero reduzca, luego presione el operador actual. Para manejar parens, simplemente guarde la precedencia del operador ''anterior'' y ponga una marca en el pstack que le indique al reductor algorythm que deje de reducir cuando resuelva el interior de un par de pares. El paren de cierre desencadena una reducción al igual que el final de la entrada, y también elimina la marca paren abierta del pstack, y restaura la precedencia de ''operación anterior'' para que el análisis pueda continuar después del punto donde permaneció. Esto se puede hacer con recursión o sin (sugerencia: use una pila para almacenar la precedencia anterior cuando encuentre un ''('' ...). La versión generalizada de esto es usar un generador de analizador implementado el algoritmo de yarda de derivación, f.ex. usando yacc o bison o taccle (tcl analog de yacc).
Peter
-Adán
Escribí un analizador de expresiones en F # y publiqué sobre esto aquí . Utiliza el algoritmo de yarda de derivación, pero en lugar de convertir de infijo a RPN, agregué una segunda pila para acumular los resultados de los cálculos. Maneja correctamente la precedencia del operador, pero no admite operadores unarios. Escribí esto para aprender F #, no para aprender el análisis de la expresión, sin embargo.
Hace mucho tiempo, inventé mi propio algoritmo de análisis, que no pude encontrar en ningún libro sobre análisis (como el Libro del Dragón). Mirando los indicadores del algoritmo de Shunting Yard, veo el parecido.
Hace aproximadamente 2 años, hice una publicación al respecto, completa con el código fuente de Perl, en http://www.perlmonks.org/?node_id=554516 . Es fácil transferir a otros idiomas: la primera implementación que hice fue en el ensamblador Z80.
Es ideal para el cálculo directo con números, pero puede usarlo para producir un árbol de análisis sintáctico si es necesario.
Actualización Debido a que más personas pueden leer (o ejecutar) Javascript, he vuelto a implementar mi analizador en Javascript, después de que se haya reorganizado el código. El analizador completo tiene menos de 5k de código Javascript (alrededor de 100 líneas para el analizador sintáctico, 15 líneas para una función de envoltura), incluidos informes de errores y comentarios.
Puede encontrar una demostración en vivo en http://users.telenet.be/bartl/expressionParser/expressionParser.html .
// operator table
var ops = {
''+'' : {op: ''+'', precedence: 10, assoc: ''L'', exec: function(l,r) { return l+r; } },
''-'' : {op: ''-'', precedence: 10, assoc: ''L'', exec: function(l,r) { return l-r; } },
''*'' : {op: ''*'', precedence: 20, assoc: ''L'', exec: function(l,r) { return l*r; } },
''/'' : {op: ''/'', precedence: 20, assoc: ''L'', exec: function(l,r) { return l/r; } },
''**'' : {op: ''**'', precedence: 30, assoc: ''R'', exec: function(l,r) { return Math.pow(l,r); } }
};
// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };
// input for parsing
// var r = { string: ''123.45+33*8'', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
var startOffset = r.offset;
var value;
var m;
// floating point number
// example of parsing ("lexing") without aid of regular expressions
value = 0;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
if(r.string.substr(r.offset, 1) == ".") {
r.offset++;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
}
if(r.offset > startOffset) { // did that work?
// OK, so I''m lazy...
return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
} else if(r.string.substr(r.offset, 1) == "+") { // unary plus
r.offset++;
return parseVal(r);
} else if(r.string.substr(r.offset, 1) == "-") { // unary minus
r.offset++;
return negate(parseVal(r));
} else if(r.string.substr(r.offset, 1) == "(") { // expression in parens
r.offset++; // eat "("
value = parseExpr(r);
if(r.string.substr(r.offset, 1) == ")") {
r.offset++;
return value;
}
r.error = "Parsing error: '')'' expected";
throw ''parseError'';
} else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name
// sorry for the regular expression, but I''m too lazy to manually build a varname lexer
var name = m[0]; // matched string
r.offset += name.length;
if(name in vars) return vars[name]; // I know that thing!
r.error = "Semantic error: unknown variable ''" + name + "''";
throw ''unknownVar'';
} else {
if(r.string.length == r.offset) {
r.error = ''Parsing error at end of string: value expected'';
throw ''valueMissing'';
} else {
r.error = "Parsing error: unrecognized value";
throw ''valueNotParsed'';
}
}
}
function negate (value) {
return -value;
}
function parseOp(r) {
if(r.string.substr(r.offset,2) == ''**'') {
r.offset += 2;
return ops[''**''];
}
if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
return ops[r.string.substr(r.offset++, 1)];
return null;
}
function parseExpr(r) {
var stack = [{precedence: 0, assoc: ''L''}];
var op;
var value = parseVal(r); // first value on the left
for(;;){
op = parseOp(r) || {precedence: 0, assoc: ''L''};
while(op.precedence < stack[stack.length-1].precedence ||
(op.precedence == stack[stack.length-1].precedence && op.assoc == ''L'')) {
// precedence op is too low, calculate with what we''ve got on the left, first
var tos = stack.pop();
if(!tos.exec) return value; // end reached
// do the calculation ("reduce"), producing a new value
value = tos.exec(tos.value, value);
}
// store on stack and continue parsing ("shift")
stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
value = parseVal(r); // value on the right
}
}
function parse (string) { // wrapper
var r = {string: string, offset: 0};
try {
var value = parseExpr(r);
if(r.offset < r.string.length){
r.error = ''Syntax error: junk found at offset '' + r.offset;
throw ''trailingJunk'';
}
return value;
} catch(e) {
alert(r.error + '' ('' + e + ''):/n'' + r.string.substr(0, r.offset) + ''<*>'' + r.string.substr(r.offset));
return;
}
}
Implementé un analizador de descenso recursivo en Java en el proyecto MathEclipse Parser . También podría usarse como un módulo de Google Web Toolkit
Otro recurso para el análisis de precedencia es la entrada del analizador de precedencia del operador en Wikipedia. Cubre el algoritmo de yarda de desviación de Dijkstra, y un algoritmo alternativo de árbol, pero más notablemente cubre un algoritmo de sustitución de macros realmente simple que puede implementarse trivialmente delante de cualquier analizador ignorante de precedencia:
#include <stdio.h>
int main(int argc, char *argv[]){
printf("((((");
for(int i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(argv[i]){
case ''^'': printf(")^("); continue;
case ''*'': printf("))*(("); continue;
case ''/'': printf("))/(("); continue;
case ''+'': printf(")))+((("); continue;
case ''-'': printf(")))-((("); continue;
}
}
printf("%s", argv[i]);
}
printf("))))/n");
return 0;
}
Invocarlo como:
$ cc -o parenthesise parenthesise.c
$ ./parenthesise a /* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
Lo cual es asombroso en su simplicidad, y muy comprensible.
Publiqué una fuente para un evaluador matemático Java (1 clase, <10 KiB) ultracompacto en mi sitio web. Este es un analizador de descenso recursivo del tipo que causó la explosión craneal para el póster de la respuesta aceptada.
Es compatible con precedencia completa, paréntesis, variables nombradas y funciones de argumento único.
Sé que esta es una respuesta tardía, pero acabo de escribir un pequeño analizador que permite que todos los operadores (prefijo, postfijo e infijo -izquierda, infija-derecha y no asociativa) tengan precedencia arbitraria.
Voy a ampliar esto para un lenguaje con soporte DSL arbitrario, pero solo quería señalar que uno no necesita analizadores personalizados para la precedencia del operador, uno puede usar un analizador generalizado que no necesita tablas en absoluto, y solo busca la precedencia de cada operador como aparece. La gente ha estado mencionando analizadores de Pratt personalizados o analizadores de yarda de derivación que pueden aceptar entradas ilegales; este no necesita ser personalizado y (a menos que exista un error) no aceptará entradas incorrectas. No está completo en cierto sentido, fue escrito para probar el algoritmo y su entrada está en una forma que necesitará algún preprocesamiento, pero hay comentarios que lo dejan en claro.
Tenga en cuenta que faltan algunos tipos comunes de operadores, por ejemplo, el tipo de operador utilizado para indexar, es decir, tabla [índice] o llamar a una función función (expresión-parámetro, ...) Voy a agregar esos, pero pienso en ambos como postfijo operadores donde lo que viene entre los delimeters ''['' y '']'' o ''('' y '')'' se analiza con una instancia diferente del analizador de expresiones. Lamento haber dejado eso, pero la parte del postfijo está en - agregar el resto probablemente casi duplicará el tamaño del código.
Como el analizador es solo 100 líneas de código de raqueta, quizás debería pegarlo aquí, espero que esto no sea más de lo que permite .
Algunos detalles sobre decisiones arbitrarias:
Si un operador de postfleto de baja precedencia está compitiendo por los mismos bloques de infijo que un operador de prefijo de baja precedencia, el operador de prefijo gana. Esto no aparece en la mayoría de los lenguajes, ya que la mayoría no tiene operadores de baja prioridad de posfijo. - por ejemplo: ((datos a) (izquierda 1 +) (pre 2 no) (datos b) (post 3!) (izquierda 1 +) (datos c)) es a + no b! + c donde no es una operador de prefijo y! es operador de posfijo y ambos tienen precedencia menor que + por lo que quieren agrupar de formas incompatibles como (a + no b!) + c o como + (no b! + c) en estos casos el operador de prefijo siempre gana, por lo que segundo es la forma en que analiza
Los operadores de nunes asociativos están realmente ahí para que no tengas que fingir que los operadores que devuelven tipos diferentes a los que toman tienen sentido juntos, pero sin tener diferentes tipos de expresión para cada uno es un kludge. Como tal, en este algoritmo, los operadores no asociativos se niegan a asociarse no solo consigo mismos sino con cualquier operador con la misma precedencia. Ese es un caso común, ya que <<= ==> = etc. no se asocian entre sí en la mayoría de los idiomas.
La cuestión de cómo los diferentes tipos de operadores (izquierda, prefijo, etc.) rompen vínculos con la precedencia es algo que no debería surgir, porque realmente no tiene sentido dar a los operadores de diferentes tipos la misma precedencia. Este algoritmo hace algo en esos casos, pero ni siquiera me molesto en averiguar qué es exactamente porque esa gramática es una mala idea en primer lugar.
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as ''((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value ''())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type ''post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type ''post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type ''left) (handle-infix process-prec 0))
((eq? input-type ''right) (handle-infix process-prec 1))
((eq? input-type ''nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type ''pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type ''data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type ''grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)
Sugeriría hacer trampa y usar el Algoritmo de yarda de derivación . Es un medio fácil de escribir un analizador simple tipo calculadora y tiene prioridad en la cuenta.
Si quiere tokenizar apropiadamente cosas y tener variables, etc. involucradas, entonces seguiría adelante y escribiría un analizador de descenso recursivo como lo sugirieron otros aquí; sin embargo, si simplemente necesita un analizador de estilo calculador, entonces este algoritmo debería ser suficiente :-)
Lancé un analizador de expresiones basado en el algoritmo Shunting Yard de Dijkstra , bajo los términos de Apache License 2.0 :
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Muy buena explicación de diferentes enfoques:
- Reconocimiento de descendencia recursiva
- El algoritmo del patio de maniobras
- La solución clásica
- Precedence climbing
Escrito en lenguaje simple y pseudo-código.
Me gusta ''precedence climbing'' uno.
Algorithm could be easily encoded in C as recursive descent parser.
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - ''0'');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != ''*'')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != ''+'')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(/"%s/") == %d/n", expression, eval_expression(expression).value);
return 0;
}
next libs might be useful: yupana - strictly arithmetic operations; tinyexpr - arithmetic operations + C math functions + one provided by user; mpc - parser combinators
Explicación
Let''s capture sequence of symbols that represent algebraic expression. First one is a number, that is a decimal digit repeated one or more times. We will refer such notation as production rule.
number -> [0..9]+
Addition operator with its operands is another rule. It is either number or any symbols that represents sum "*" sum sequence.
sum -> number | sum "+" sum
Try substitute number into sum "+" sum that will be number "+" number which in turn could be expanded into [0..9]+ "+" [0..9]+ that finally could be reduced to 1+8 which is correct addition expression.
Other substitutions will also produce correct expression: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
Bit by bit we could resemble set of production rules aka grammar that express all possible algebraic expression.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
To control operator precedence alter position of its production rule against others. Look at grammar above and note that production rule for * is placed below + this will force product evaluate before sum . Implementation just combines pattern recognition with evaluation and thus closely mirrors production rules.
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != ''*'')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
Here we eval term first and return it if there is no * character after it this is left choise in our production rule otherwise - evaluate symbols after and return term.value * product.value this is right choise in our production rule ie term "*" product
Here is a simple case recursive solution written in Java. Note it does not handle negative numbers but you can do add that if you want to:
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == ''('') bracketCounter++;
else if(c == '')'') bracketCounter--;
else if((c == ''+'' || c == ''-'') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == ''*'' || c == ''/'') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == ''('' && exp.charAt(exp.length()-1) == '')'')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case ''+'':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case ''-'':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case ''*'':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case ''/'':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}