En programación de computadoras y ciencias de la computación , " munch máximo " o " coincidencia más larga " es el principio de que cuando se crea una construcción, se debe consumir la mayor cantidad posible de entrada disponible.
El primer uso conocido de este término es por RGG Cattell en su tesis doctoral [1] sobre la derivación automática de generadores de código para compiladores .
Solicitud
Por ejemplo, la sintaxis léxica de muchos lenguajes de programación requiere que los tokens se construyan a partir del número máximo posible de caracteres del flujo de entrada. Esto se hace para resolver el problema de la ambigüedad inherente en las 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 compiladores en la etapa de selección de instrucciones para describir un método de "mosaico", es decir, 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 completo puede convertirse en una sola instrucción de máquina, y el problema es cómo dividir el árbol en "mosaicos" no superpuestos, 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 denomina "munch máximo". [3]
Inconvenientes
En algunas situaciones, el "mordisco 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 inicia un comentario (no intencionado) que no está terminado o terminado por el token final */
de algún texto real posterior no relacionado. comentario (los comentarios en C no se anidan). Lo que realmente se quería decir en la declaración era asignar a la variable x
el resultado de dividir el valor y
entre el valor obtenido al desreferenciar el puntero z
; esto sería un código perfectamente válido (aunque no muy común). Se puede establecer haciendo uso de espacios en blanco o usando x=y/(*z);
.
Otro ejemplo, en C ++ , usa los caracteres de "corchetes angulares" <
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 producía un error de análisis, porque se encuentra el token de operador de desplazamiento a la derecha en lugar de dos tokens de 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 ; // Corregir 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 de la máxima principio de munch.
Alternativas
Los investigadores de lenguajes de programación también han respondido reemplazando o complementando el principio de máxima masticación 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, impondrán algunas restricciones sobre qué personajes pueden seguir una coincidencia válida. Por ejemplo, estipular que la coincidencia de cadenas [a-z]+
no puede ir seguida de un carácter alfabético logra el mismo efecto que el munch máximo con esa expresión regular. [5] (En el contexto de las expresiones regulares, el principio de munch máximo se conoce como codicia 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 inválido). [6]
Referencias
Bibliografía
- Aho, Alfred V .; Lam, Monica S .; Sethi, Ravi; Ullman, Jeffrey D. (2007). Compiladores: principios, técnicas y herramientas (2ª ed.). Boston: Addison-Wesley. ISBN 978-0-321-48681-3.
- Page, Daniel (2009). "Compiladores". Introducción práctica a la Arquitectura de Computadores . Textos en Informática. Londres: Springer. págs. 451–493. doi : 10.1007 / 978-1-84882-256-6_11 . ISBN 978-1-84882-255-9.
- Van den Brand, Mark GJ; Scheerder, Jeroen; Vinju, Jurgen J .; Visser, Eelco (2002). Filtros de desambiguación para analizadores LR generalizados sin escáner . Apuntes de conferencias en Ciencias de la Computación . 2304/2002. Berlín / Heidelberg: Springer. págs. 21–44. doi : 10.1007 / 3-540-45937-5_12 . ISBN 978-3-540-43369-9. ISSN 0302-9743 .
- Vandevoorde, Daveed (14 de enero de 2005). "Soportes en ángulo recto" . Consultado el 31 de marzo de 2010 .
- Van Wyk, Eric; Schwerdfeger, agosto (2007). Escaneo sensible al contexto para analizar idiomas extensibles . GPCE '07: Actas del VI Congreso Internacional de Programación Generativa e Ingeniería de Componentes . Nueva York: ACM. págs. 63–72. doi : 10.1145 / 1289971.1289983 . ISBN 9781595938558.