Inicio

Validación de Entradas

Una vez vista la forma de expresar las estructuras válidas del lenguaje — mediante una gramática — ya se puede ir al siguiente paso: su aplicación a una entrada.

Se tienen, por un lado, unas reglas en BNF que indican qué secuencias de tokens son válidas. Por otro lado, se tiene una entrada formada por una secuencia de tokens que se quiere comprobar si es válida. ¿Cómo se sabe si dicha entrada cumple dichas reglas?

Esto es lo que se verá al final de este capítulo. Pero, antes de ello, se presentarán previamente en este apartado una serie de definiciones que serán necesarias.

Definiciones

Transformación

La base de todos los demás conceptos de este capítulo es el siguiente.

Definición

📖 Se denomina transformación o paso de derivación a la acción de coger uno de los símbolos no-terminales de una cadena y sustituirlo por la parte derecha de una regla que tenga como antecedente a dicho símbolo, obteniendo así una nueva cadena.

Supóngase una gramática G:

s ⟶ a b Z
a ⟶ Y a
a ⟶ X a
a ⟶ ε
b ⟶ ε
b ⟶ W b

Supóngase ahora la cadena X a b Z. Si se toma el símbolo a de dicha cadena y, aplicando la segunda regla a ⟶ Y a, se sustituye dicho símbolo por la parte derecha de la regla, se obtiene la cadena X Y a b Z.

Se dice entonces que la cadena X Y a b Z es una transformación de X a b Z y se expresa con la siguiente notación (nótese que se lee al revés de cómo se escribe):

X a b Z ⟹ X Y a b Z

Nota

📌 Nótese la forma de las dos flecha que han aparecido en este tema:

  • Se utiliza ⟶ para definir una regla o producción de una gramática.
  • Se utiliza ⟹ indica que a la cadena de su izquierda se le ha aplicado una regla para obtener la cadena de la derecha (que se ha realizado una transformación).

Derivación

A partir de la definición anterior, se puede realizar otra más común.

Definición

📖 Una derivación de una cadena es cualquiera de las cadenas que se obtienen a partir de ella aplicando una o más transformaciones (pasos de derivación).

Supóngase una gramática G:

s ⟶ a b Z
a ⟶ Y a
a ⟶ X a
a ⟶ ε
b ⟶ ε
b ⟶ W b

Serían ejemplos de derivaciones de la cadena X a b Z todas las cadenas que están a su derecha en el siguiente ejemplo:

X a b Z ⟹ X Y a b Z ⟹ X Y b Z ⟹ X Y W b Z

Se indica que una cadena es una derivación de otra con el símbolo (que indica que se han producido cero o más transformaciones). Por ejemplo, para indicar que la cadena X Y W b Z es una derivación de X a b Z se expresa de la siguiente manera (nótese que, de nuevo, se lee al revés de cómo se escribe):

X a b Z X Y W b Z

De hecho, en el ejemplo anterior, se pueden ver también las siguientes derivaciones de la misma cadena:

X a b Z X Y a b Z

X a b Z X Y b Z

Sentencia

Una sentencia no es más que un caso particular de derivación.

Definición

📖 Se dice que una cadena t es una sentencia de una gramática G si cumple dos condiciones:

  1. Está formada únicamente por símbolos terminales (en mayúsculas en la notación usada en estos apuntes).
  2. Es una derivación del símbolo inicial s de la gramática (s t).

Como ejemplo, supóngase la gramática G:

s ⟶ a b Z
a ⟶ Y a
a ⟶ X a
a ⟶ ε
b ⟶ ε
b ⟶ W b

Para saber si la cadena X W Z es una sentencia de G, habría que comprobar las dos condiciones anteriores.

  • La primera la cumple ya que la cadena esta formada sólo por terminales.
  • La segunda la cumple por ser una derivación de s (es decir, que se puede partir de dicho símbolo y, haciendo transformaciones, se puede llegar a la cadena). Esta sería la secuencia de transformaciones que lo demuestran:
    s ⟹ a b Z       (por regla 1)
  ⟹ X a b Z     (por regla 3)
  ⟹ X b Z       (por regla 4)
  ⟹ X W b Z     (por regla 6)
  ⟹ X W Z       (por regla 5)

Por tanto, la cadena X W Z es una sentencia de la gramática G.

Nota

📌 No hay que confundir esta acepción de la palabra sentencia con las sentencias de un lenguaje de programación (el if, while, asignación, ...). Aunque se use la misma palabra, se está usando para cosas distintas (de hecho, aunque se estén adelantando acontecimientos, la sentencia tal y como aquí se define se corresponderá con un programa completo y no con una instrucción del mismo)

Lenguaje

Se llega, por fin, al término que da nombre a la asignatura Diseño de Lenguajes de Programación.

Definición

📖 Dada una gramática G, su lenguaje o L(G) es el conjunto de todas sus sentencias.

Es decir, el lenguaje generado por una gramática G es el conjunto de todas las cadenas formadas por terminales a las que se puede llegar a partir del símbolo inicial s.

Supóngase una gramática G:

s ⟶ X a
a ⟶ Y b
a ⟶ ε
b ⟶ W
b ⟶ ε

Su lenguaje L(G) estaría formado por las tres sentencias que se pueden formar:

L(G) = { X, X Y, X Y W }

En este caso, que es una gramática sencilla, ha salido un conjunto finito. Sin embargo, lo habitual en un lenguaje práctico es que sea un conjunto infinito de sentencias.

Pregunta

⏳ Supóngase que se tiene una gramática con la especificación sintáctica del lenguaje Java. ¿Cuál será el lenguaje L(G) de dicha gramática? ¿Cuáles serán sus elementos?

Gramáticas Equivalentes

Supónganse la dos gramáticas G1 y G2 siguientes:

// Gramática G1
s ⟶ s + s
s ⟶ X

// Gramática G2
s ⟶ X mt
mt ⟶ + X mt
mt ⟶ ε

Si se calculan sus respectivos lenguajes, se obtiene lo siguiente:

L(G1) = { X, X + X, X + X + X, X + ... + X }

L(G2) = { X, X + X, X + X + X, X + ... + X }

Por tanto, puede verse que ambas gramáticas, aunque son distintas, generan el mismo lenguaje: una o más X sumadas.

Definición

📖 Se dice que una gramática es equivalente a otra si ambas generan el mismo lenguaje.

De hecho, dado un lenguaje cualquiera, existen infinitas gramáticas que lo generan (todas ellas serán gramáticas equivalentes entre sí).

Validez de una Entrada

Recopilando todas las definiciones del apartado anterior, se puede llegar a la conclusión de que una entrada será válida si pertenece al lenguaje que genera la gramática, es decir, si es una sentencia del mismo. Y la forma de averiguar si es una sentencia es comprobando si se puede llegar desde el símbolo inicial s hasta dicha cadena. Si es así, es una entrada válida.

Esto es lo que hace una analizador sintáctico; es un algoritmo que busca, si existe, dicho camino entre s y la cadena de entrada. Para ello, tiene que decidir qué transformación hay que realizar (qué regla hay que aplicar) en cada paso para poder llegar con éxito al destino.