En programación informática y ciencias de la computación , el principio de " maximal munch " o " longest match " es que cuando se crea una construcción se debe consumir la mayor cantidad posible de la 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" (determinar 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 entero puede convertirse en una sola instrucción de máquina, y el problema es cómo dividir el árbol en "mosaicos" que no se superpongan, cada uno de los cuales representa una instrucción de máquina. Una estrategia eficaz es simplemente hacer un mosaico del subárbol más grande posible en cualquier punto dado, lo que se llama "combinación máxima". [3]
En algunas situaciones, la "compresión máxima" conduce a resultados indeseables o poco intuitivos. Por ejemplo, en el lenguaje de programación Cx=y/*z; , la declaración (sin ningún espacio en blanco) probablemente conducirá a un error de sintaxis ya que la /*secuencia de caracteres (sin intención) inicia un comentario que no está terminado o que termina con el token final */de algún comentario real posterior no relacionado (los comentarios en C no se anidan). Lo que realmente se quería decir con la declaración era asignar a la variable xel resultado de dividir el valor en ypor el valor obtenido al desreferenciar el puntero z ; esto sería un código válido. Se puede indicar haciendo uso de espacios en blanco o usando x=y/(*z);.
Otro ejemplo, en C++ , utiliza los caracteres de "corchete angular" <y >en la sintaxis para la especialización de plantillas , 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 encuentra el token del operador de desplazamiento a la derecha en lugar de dos tokens de corchete angular 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 de modo que un token de desplazamiento a la derecha se acepta como sinónimo de un par de corchetes angulares rectos (como en Java ), lo que complica la gramática pero permite el uso continuo del principio de munch máximo. De todos modos, se tuvo que agregar una excepción a la regla de munch máximo para tratar 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 munch máximo con otras tácticas de desambiguación léxica. Un enfoque es utilizar "restricciones de seguimiento", que en lugar de tomar directamente la coincidencia más larga pondrá algunas restricciones sobre qué caracteres pueden seguir a una coincidencia válida. Por ejemplo, estipular que las cadenas que coinciden [a-z]+no pueden ser seguidas por un carácter alfabético logra el mismo efecto que el munch máximo con esa expresión regular. [5] (En el contexto de expresiones regulares, el principio de munch máximo se conoce como avaricia y se contrasta con pereza ). Otro enfoque es mantener el principio de munch máximo pero hacerlo subordinado a algún otro principio, como el contexto ( por ejemplo , el token de desplazamiento a la derecha en Java no coincidiría en el contexto de una expresión genérica , donde es sintácticamente inválido). [6]