En programación informática e informática , " munch máximo " o " coincidencia más larga " es el principio de que al crear alguna construcción, se debe consumir la mayor cantidad posible de entrada disponible.
El primer uso conocido de este término lo realizó RGG Cattell en su tesis doctoral [1] sobre la derivación automática de generadores de código para compiladores .
Por ejemplo, la sintaxis léxica de muchos lenguajes de programación requiere que los tokens se construyan a partir del máximo número posible de caracteres del flujo de entrada. Esto se hace para resolver el problema de la ambigüedad inherente en expresiones regulares de uso común como [a-z]+(una o más letras minúsculas). [2]
El término también se utiliza en los compiladores en la etapa de selección de instrucciones para describir un método de "mosaico", que determina cómo un árbol estructurado que representa un programa en un lenguaje intermedio debe convertirse en código de máquina lineal . Un subárbol completo podría convertirse en una sola instrucción de máquina, y el problema es cómo dividir el árbol en "mosaicos" que no se superpongan, representando cada uno de ellos una instrucción de máquina. Una estrategia eficaz es simplemente crear un mosaico del subárbol más grande posible en cualquier punto dado, lo que se denomina "munch máximo". [3]
En algunas situaciones, el "masticón máximo" conduce a resultados indeseables o poco intuitivos. Por ejemplo, en el lenguaje de programación C , la declaración x=y/*z;(sin ningún espacio en blanco) probablemente conducirá a un error de sintaxis ya que la /*secuencia de caracteres (involuntariamente) inicia un comentario que no termina o termina con el token final de algún comentario real*/ posterior no relacionado. (los comentarios en C no se anidan). Lo que realmente se quiso decir en la declaración fue asignar a la variable el resultado de dividir el valor entre el valor obtenido al desreferenciar el puntero ; este sería un código válido. Se puede indicar haciendo uso de espacios en blanco o usando .xy zx=y/(*z);
Otro ejemplo, en C++ , utiliza los caracteres "corchete angular" <y >en la sintaxis para la especialización de plantilla , pero dos >caracteres consecutivos se interpretan como el operador de desplazamiento a la derecha>> . [4] Antes de C++ 11, el siguiente código produciría un error de análisis, porque se encontraba el token del operador de desplazamiento a la derecha en lugar de dos tokens entre corchetes en ángulo recto:
std :: vector < std :: vector < int >> my_mat_11 ; //Incorrecto en C++03, correcto en C++11. std :: vector < std :: vector < int >> my_mat_03 ; //Correcto en C++03 o C++11. El estándar C++ 11 adoptado en agosto de 2011 modificó la gramática para que un token de desplazamiento a la derecha se acepte como sinónimo de un par de corchetes en ángulo recto (como en Java ), lo que complica la gramática pero permite el uso continuo del munch máximo. principio. De todos modos, se tuvo que agregar una excepción a la regla de masticación máxima para abordar la secuencia <::que puede aparecer en las plantillas. En ese caso, a menos que la secuencia sea seguida por :o >el carácter <se interprete como su propio token en lugar de parte del token <:.
Los investigadores de lenguajes de programación también han respondido reemplazando o complementando el principio de masticación máxima con otras tácticas de desambiguación léxica. Un enfoque es utilizar "restricciones de seguimiento", que en lugar de tomar directamente la partida más larga, impondrán algunas restricciones sobre qué personajes pueden seguir una partida válida. Por ejemplo, estipular que las cadenas coincidentes [a-z]+no pueden ir seguidas de un carácter alfabético logra el mismo efecto que maximal munch con esa expresión regular. [5] (En el contexto de las expresiones regulares, el principio de munch máximo se conoce como avaricia y se contrasta con la pereza ). Otro enfoque es mantener el principio de munch máximo pero subordinarlo a algún otro principio, como el contexto ( p. ej. , el token de desplazamiento a la derecha en Java no coincidiría en el contexto de una expresión genérica , donde no es sintácticamente válido). [6]