Máximo masticar

En programación informática e informática , el principio de " máximo aprovechamiento " o " coincidencia más larga " establece que, al crear alguna estructura, se debe consumir la mayor cantidad posible de datos de entrada disponibles.

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 .

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 expresiones regulares de uso común como [a-z]+(una o más letras minúsculas). ^{[ 2 ]}

El término también se usa en compiladores en la etapa de selección de instrucciones para describir un método de "segmentación": determinar cómo se debe convertir un árbol estructurado que representa un programa en un lenguaje intermedio en código máquina lineal . Un subárbol completo puede convertirse en una sola instrucción de máquina, y el problema radica en cómo dividir el árbol en "segmentos" que no se superpongan, cada uno de los cuales representa una instrucción de máquina. Una estrategia eficaz consiste simplemente en crear un segmento del subárbol más grande posible en cualquier punto dado, lo que se denomina "recorte máximo". ^{[ 3 ]}

En algunas situaciones, el "combustible máximo" conduce a resultados indeseables o poco intuitivos. Por ejemplo, en el lenguaje de programación Cx=y/*z; , la instrucción (sin espacios 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 y no relacionado (los comentarios en C no se anidan). Lo que realmente se pretendía en la instrucción era asignar a la variable xel resultado de dividir el valor en ypor el valor obtenido al desreferenciar el punteroz ; esto sería código válido. Se puede expresar utilizando 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 derecho:>>

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 continuado del principio de máxima munch. De todos modos, se tuvo que añadir una excepción a la regla de máxima munch para manejar la secuencia <::que puede aparecer en las plantillas. En ese caso, a menos que la secuencia vaya seguida de :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 máxima coincidencia con otras tácticas de desambiguación léxica. Un enfoque consiste en utilizar "restricciones de seguimiento", que en lugar de tomar directamente la coincidencia más larga impone restricciones sobre qué caracteres pueden seguir a una coincidencia 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 la máxima coincidencia con esa expresión regular. ^{[ 5 ]} (En el contexto de las expresiones regulares, el principio de máxima coincidencia se denomina codicia y se contrapone a la pereza ). Otro enfoque consiste en mantener el principio de máxima coincidencia, pero subordinarlo 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 ]}

• 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 computadoras . Textos en informática. Londres: Springer. pp. 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, Jürgen J.; Visser, Eelco (2002). "Filtros de desambiguación para analizadores LR generalizados sin escáner". Construcción del compilador . Apuntes de conferencias sobre informática. vol.  2304/2002. Berlín/Heidelberg: Springer. págs. 21 a 44. doi : 10.1007/3-540-45937-5_12 . ISBN  978-3-540-43369-9ISSN 0302-9743​​ 
• Vandevoorde, Daveed (14 de enero de 2005). "Soportes en ángulo recto" . Consultado el 31 de marzo de 2010 .
• Van Wyk, Eric; Schwerdfeger, August (2007). «Análisis contextual para el análisis sintáctico de lenguajes extensibles». Actas de la 6.ª conferencia internacional sobre programación generativa e ingeniería de componentes . Nueva York: ACM. págs. 63-72 . doi : 10.1145/1289971.1289983 . hdl : 11299/217310 . ISBN  9781595938558. S2CID 9145863 .