Metalenguajes #

Necesidad de los Metalenguajes #

Queda ahora determinar en qué notación se expresan los patrones. El lenguaje natural (el español, por ejemplo) no es adecuado debido a su ambigüedad. Supóngase la siguiente definición:

¿Sería entonces un literal real válido uno como el siguiente?

.5

Con la regla anterior podría surgir la duda de si es válido o debería haber un cero antes del punto. El problema es que diferentes implementaciones del lenguaje podrían seguir distintas interpretaciones creando incompatibilidad.

Podría pensarse que el problema es la brevedad de la definición. Sin embargo, el extender la definición para añadir más casos especiales no es ninguna garantía de éxito (no se sabría si quedarían más casos aún por contemplar). Y, aunque se consiguiera, sería a cosa de aumentar su extensión y dificultar así su comprensión.

Por tanto, se necesita una notación que tenga dos propiedades:

• Precisión. Que ante cualquier entrada no haya duda de si es válida o no para ese token.
• Concisión. Que la regla sea lo más compacta posible para facilitar su entendimiento e implementación.

Esto es lo que ofrecen los metalenguajes. Un metalenguaje es un lenguaje que se caracteriza porque aquello que describe es otro lenguaje. Se caracterizan por las dos propiedades que se necesitan: precisión y concisión. Y, además, suelen ser fácilmente implementables, ya que están ampliamente estudiados y suelen existir varias técnicas para llevar sus especificaciones a código.

Sin embargo, no hay un metalenguaje que sirva para todo. En un traductor hay que definir distintos aspectos (el orden en el que pueden aparecer los tokens, las operaciones válidas sobre las expresiones, ...) y, por tanto, se usan distintos metalenguajes para describir más eficazmente cada aspecto por separado. En el caso del análisis léxico, lo que se necesita es un metalenguaje qué indique qué secuencias de caracteres son válidas y, estas últimas, cómo se clasifican en tokens. Los dos metalenguajes más usados para reglar esos aspectos son los autómatas finitos y las expresiones regulares.

Autómatas Finitos #

Los autómatas finitos ya han sido vistos en otras asignaturas de la carrera. Si se necesita repasar los conceptos, puede verse el cuaderno didáctico Lenguajes, Gramáticas y Autómatas (Juan-Manuel Cueva Lovelle).

Para realizar una especificación léxica mediante el metalenguaje de autómatas finitos (es decir, que los patrones estén descritos en dicha notación), lo que habría que hacer es crear un autómata finito por cada token del lenguaje.

Por ejemplo, en la siguiente especificación léxica se definen los autómatas de los tokens LITENT (literal entero), IDENT (identificador) e IF (token al que sólo pertenece la propia palabra reservada if). Lo siguiente sería el autómata finito de un literal real (token LITREAL). Puede comprobarse la ventaja de usar un metalenguaje. Con el patrón anterior no se tiene ya la duda anterior de si el lexema .5 es válido o no. Siguiendo el autómata desde el estado inicial, se ve que sí lo es ya que se llega a un estado final.

Expresiones Regulares #

Las expresiones regulares son otro metalenguaje para describir patrones léxicos. Tienen la misma expresividad que los autómatas finitos (es decir, todo lo que se puede expresar con uno se puede expresar con el otro y viceversa).

Sin embargo, tienen las siguientes ventajas frente a los autómatas finitos:

• Al ser texto, se pueden realizar con cualquier editor de texto (aunque sea el bloc de notas). No requiere un editor gráfico, como ocurre con los autómatas finitos.
• Un patrón especificado mediante una expresión regular ocupa mucho menos espacio que el autómata equivalente.

Es por estas razones por las que, aunque para explicar ciertos conceptos los autómatas son más visuales, las expresiones regulares son tan utilizadas.

Operadores #

Aunque existen infinidad de variantes de las expresiones regulares (cada lenguaje de programación y herramienta tiene la suya), los operadores básicos que todas contemplan son:

En cuanto a su prioridad, sería la siguiente:

1. Operación de cierre y cierre positivo
2. Concatenación
3. Alternativa

Supóngase el siguiente patrón:

pa+

Este patrón reconocería como lexemas válidos aquellos que empiezan por una p y son seguidos por una o más veces la a (el + sólo afecta a la a, ya que la concatenación tiene menos prioridad que el cierre positivo).

pa paa paaa paaaa...

Si se quisiera cambiar la prioridad de los operadores, habría que utilizar paréntesis. Por ejemplo, para indicar que se quiere repetir la p tantas veces como la a, habría que utilizar paréntesis de la siguiente manera:

(pa)+

Especificación #

Para realizar una especificación léxica mediante el metalenguaje de expresiones regulares, lo que habría que hacer es crear una expresión regular por cada token del lenguaje.

Ejemplo de especificación léxica:

Puede comprobarse de nuevo la ventaja de usar un metalenguaje. Con el patrón anterior de LITREAL no se tiene tampoco duda de si el lexema .5 es válido o no. En este caso, tal y como se ha definido en este ejemplo, no sería válido.