Patrones de Listas #

De las tres construcciones anteriores, las listas requieren un apartado adicional debido a que tienen distintas variantes.

Tipos de listas #

Allen I. Holub clasificó las listas en cuatro grupos en función de dos criterios:

• Por un lado, por el número mínimo de elementos que requieran. Pueden requirir al menos un elemento (1+) o bien que no requieran ninguno (0+).

• Por otro lado, por la existencia o no de cadenas entre los elementos repetidos. Así, las listas pueden ser sin separadores (ss) o con separadores (cs). Un separador es aquella cadena (aunque generalmente será un sólo token) que se deba intercalar entre dos elementos de la lista.

  Un ejemplo de separador es la coma entre los argumentos de una función.

  f(x, y, z)
  

  Nótese que si hay un sólo elemento no tiene que haber separador; si hay n elementos, deberá haber n-1 separadores.

Combinando esos dos parámetros, se obtienen cuatro tipos de listas, donde e representa al elemento que se quiere repetir y s representa al separador.

Patrones #

Ampliando la tabla original de Holub con una columna para EBNF, en la siguiente tabla se muestran los patrones para obtener las reglas que generen los cuatro tipos de listas anteriores.

Para obtener las reglas de la gramática, basta con instanciar el patrón correspondiente a la fila de la lista deseada sustituyendo:

• e por la cadena concreta que sea el elemento que se repite.
• s por la cadena o carácter que deba ser el separador (si lo hay).
• l será el nombre que se le quiera dar a toda la secuencia de elementos. A veces es simplemente poner en plural el nombre del símbolo e.

Algunas aclaraciones sobre la tabla:

• Se incluyen los patrones en BNF y EBNF. Aunque en EBNF es más compacto, el BNF está más extendido y, por tanto, se debe estar familiarizado con estas estructuras cuando se encuentren en una especificación.
• En BNF se incluyen dos variantes del patrón: una recursiva a izquierda (RI) y otra recursiva a derecha (RD). Deberá usarse una y otra en función de la asociatividad que se quiera dar a los elementos de la lista. Se usará RI cuando se quieran procesar de izquierda a derecha (lo más habitual) y RD cuando se quieran procesar en dirección contraria.
• lOpt es un no-terminal auxiliar que sería la entrada del patrón '0+cs'. El sufijo Opt (del inglés optional) simplemente es un convenio de nombres para indicar que dicho símbolo se puede anular (es opcional). Es decir, cuando en una gramática se vea, por ejemplo, un no-terminal llamado miLista, se asume que debe tener al menos un elemento y si se ve miListaOpt se asume que puede tener cero sin necesidad de ir a su definición. En cualquier caso, este convenio es sólo una sugerencia.

Ejemplo 0480 #

Enunciado #

Sea un lenguaje para la definición de variables.

int a, b;
double x;

Requisitos:

• Sólo hay dos tipos: entero (int) y real (double).
• En una sola definición, pueden definirse varias variables del mismo tipo.
• En un programa puede haber varias definiciones, pero también sería válido que no hubiera ninguna.

Se pide especificar la sintaxis de dicho lenguaje en BNF y en EBNF. Indicar, además, los patrones usados en las listas.

Solución BNF #

Aplicando los patrones anteriores y sustituyendo sus símbolos por los nombres adecuados para este ejercicio, quedaría finalmente esta gramática.

definiciones: ε | definiciones definicion       // lista 0+ss
definicion: tipo nombres ';'                    // secuencia
nombres: IDENT | nombres ',' IDENT              // lista 1+cs

Como puede verse, toda regla sigue alguna de las tres construcciones básicas. Lo cual, a medida que el alumno se familiarice con ellas, hará que cada vez le será más fácil entender y crear cualquier gramática.

En el caso concreto de las listas (reglas 1 y 3) se han aplicado los patrones correspondientes a la versión recursiva a izquierda.

Solución EBNF #

La solución en EBNF sería:

definiciones: definicion*           // lista 0+ss
definicion: tipo nombres ';'        // secuencia
nombres: IDENT (',' IDENT)*         // lista 1+cs

Como puede verse, las construcciones son las mismas, sólo que en el caso de las listas se han tomado los patrones de otra columna de la tabla (la última).