Creación de Gramáticas #

En el capítulo anterior se vio que la primera misión de un analizador sintáctico es comprobar si una entrada es válida o no. Para ello, previamente hay que especificar mediante una gramática qué es válido y qué no, es decir, hay que definir la sintaxis que deben seguir las entradas válidas.

En dicho capítulo se mostró sólo una visión general del proceso. Se trabajó con gramáticas pero se pasó por alto el cómo crear dichas gramáticas. En este apartado se verá cómo es este proceso.

Construcciones Básicas #

Hacer una gramática puede plantearse como un ejercicio de idea feliz; poner reglas heterogéneas sin seguir ningún criterio hasta que se obtenga el resultado buscado. Pero, en realidad, las gramáticas de los lenguajes comunes tienen estructuras muy parecidas y casi siempre se hacen de manera similar.

Aquí se propondrá, por tanto, una forma más rápida de hacer gramáticas de lenguajes de programación comunes. Haciendo una analogía con la programación estructurada — en la que se plantea que todo algoritmo se puede implementar con tres construcciones (secuencia, selección e iteración) — aquí se plantea que las gramáticas se hagan siguiendo tres construcciones BNF:

• Secuencia. Una secuencia no es más que una sucesión de símbolos que indica el orden en el que deben aparecer. Es la construcción más básica y los demás son casos particulares de este.

  escritura ⟶ `print` expr `;`
  

• Lista. Se utiliza cuando se quiere indicar que una cadena puede aparecer en la entrada varias veces seguidas. En BNF esto se expresa con recursividad.

  programa ⟶ instruccion
          | programa instruccion
  

• Composición. Se usa cuando hay unos elementos atómicos o finales y otros mayores que se crean a partir de estos. El caso más habitual son las expresiones matemáticas.

  expr ⟶ NUM                 // Elemento atómico
          | IDENT             // Elemento atómico
          | expr '*' expr     // Elemento compuesto
          | expr '+' expr     // Elemento compuesto
  

Es importante que, a la hora de hacer una gramática, cada regla siga una y sólo una de estas construcciones. El que una regla tenga una forma que no coincida con ninguna de estas tres (o bien combine elementos de más de una) producirá una gramática que, probablemente, sea más difícil de entender y de implementar.

a ⟶ b ... | c ...

a ⟶ b ...   // Secuencia
a ⟶ c ...   // Secuencia

Ejemplo 0470 #

Enunciado #

Hacer una gramática en BNF de un lenguaje con las siguientes características:

• Un conjunto está formado por uno o más elementos entre paréntesis separados por comas.
• Cada elemento puede ser un número u otro conjunto.
• Los números están formados por dígitos de 1 al 3, pudiendo haber espacios entre ellos. Suponer que el analizador léxico devuelve los tokens UNO, DOS y TRES.
• Los números están formados por un número impar de dígitos y son capicúa.

Ejemplos de entradas válidas serían:

(131)
(3, 222, 12 313)
(12121, 2, (333), (2, 3, 1111111))
(2132312, ( ( (1, 2), 2, 131), 1, 2), 3322233)

Se pide hacer una gramática BNF usando las construcciones anteriores. Anotar en cada regla qué construcción sigue.

Solución #

La gramática pedida sería:

conjunto: '(' elementos ')'                     // Secuencia

elementos: elemento | elementos ‘,’ elemento    // Lista
elemento: num | conjunto                        // Dos secuencias

num: UNO            // Composición
    | DOS
    | TRES
    | UNO num UNO
    | DOS num DOS
    | TRES num TRES