Especificación Sintáctica #

Como se comentó en el apartado anterior, la primera tarea del analizador sintáctico es el reconocimiento de estructuras, es decir, la validación de la entrada. Este apartado se centrará en dicha tarea del analizador.

Para saber si la entrada es válida se tiene que especificar de alguna manera qué es válido y qué no. Es decir, esta fase necesita una serie de reglas que indiquen qué estructuras tienen el lenguaje, qué componentes tienen cada una y en qué orden pueden aparecer.

Por ejemplo:

• Una sentencia condicional debe comenzar por if, después viene una condición entre paréntesis obligatorios, luego llaves (obligatorias si hay más de una sentencia y opcionales si sólo hay una sentencia), ...
• Una definición de variable comienza por el tipo de la variable, luego debe venir el nombre y tiene que acabar en punto y coma.

Lo que se verá en este apartado es la notación en la que se escribirán dichas reglas.

Reglas en Lenguaje Natural #

En el tema anterior se vio que especificar las reglas léxicas mediante el lenguaje natural era problemático. En el análisis sintáctico ocurre algo parecido.

Supóngase que se quiere establecer en lenguaje natural las reglas que dicten cómo es una expresión aritmética como la siguiente:

(3 + 4) * 5

Las reglas podrían ser:

1. Las expresiones utilizan notación infija.
2. El número de paréntesis abiertos será siempre mayor o igual que el de paréntesis cerrados excepto al final de la expresión, en donde tendrán que ser iguales.

Aunque parecen suficientemente claras, podría plantearse una entrada como la siguiente:

3 (+ 4 *) 5

La entrada anterior se pretendía que fuera inválida. Sin embargo, cumple ambas reglas. Por tanto, habría que replantearse las mismas. Al igual que ocurría en el tema anterior, no es cuestión de ir añadiendo más reglas a medida que vayan apareciendo casos. El problema esencial es la ambiguedad del lenguaje natural.

Por ello, se recurrirá de nuevo a los metalenguajes: lenguajes que nos sirven para definir de forma precisa (sin ambiguedades) y concisa las reglas de un lenguaje. En concreto, los metalenguajes que se usarán en esta fase son las Gramáticas Libres de Contexto (GLC) en notación BNF y EBNF y, cuando se llegue a la construcción del árbol, las Gramáticas Abstractas (GAb).

Gramáticas Libres de Contexto (GLC) #

Las gramáticas libres de contexto (GLC), o gramáticas de tipo 2 en la jerarquía de Chomsky, ya se han visto en otras asignaturas de la carrera, por lo que aquí sólo se hará un rápido repaso.

Una GLC (o simplemente gramática a partir de ahora) no es más que un conjunto de cuatro elementos:

G = { VT, VN, s, P }

Dichos elementos son:

• VT es un conjunto de símbolos terminales (en nuestro caso, serían los tokens que llegan del analizador léxico).
• VN es un conjunto de símbolos no-terminales. Son las estructuras que hay en el lenguaje (que se formarán a partir de los símbolos terminales y de otras estructuras).
• s, que es un símbolo no-terminal, es el símbolo inicial. Es la estructura superior que incluirá a todas las demás.
• P es un conjunto de reglas de producción (o producciones) formadas por un símbolo no-terminal en el antecedente (a la izquierda de la flecha) y una secuencia de símbolos (terminales y/o no-terminales) en el consecuente. Las reglas son las que nos dicen cómo se forman los símbolos no-terminales de VN a partir de otros símbolos.

Un ejemplo de una gramática libre de contexto sería la gramática G siguiente:

G   = { VT, VN, programa, P }

Donde a continuación se describen cada uno de sus componentes:

VT = { IDENT IF THEN ELSE = (  ) NUM  +  * }

VN = { programa, instrucciones, instr, expr }

P = {
    programa ⟶ instrucciones

    instrucciones ⟶ instr
                  | instrucciones instr

    instr ⟶ IDENT = expr
          | IDENT ( expr )
          | IF expr THEN instr ELSE instr

    expr ⟶ NUM
         | expr + expr
         | expr * expr
}

En el no-terminal instrucciones puede observarse que, dado que las GLC no tienen los operadores de repetición que se vieron en el analizador léxico ('+' y '*'), la solución equivalente aquí es utilizar la recursividad para indicar repetición de elementos (en concreto, la gramática indica que instrucciones es una secuencia de una o más instr).

a ⟶ b
   | c

a ⟶ b
a ⟶ c

Para reafirmar la razón de usar metalenguajes, se pueden plantear las siguientes preguntas:

• Este lenguaje, así descrito ¿permitiría asignación múltiple del estilo a = b = 0?
• ¿Permitiría un if sin else?
• ¿Permitiría poner if anidados?

Puede observarse que se puede responder a ellas sin ningún tipo de ambiguedad.

Notación BNF #

La notación más común para expresar gramáticas libres de contexto es la notación BNF (Backus-Naur Form). En ella no se definen expresamente cada uno de los elementos de la gramática, sino que sólo se incluyen las reglas de producción y el resto de los elementos de la gramática se deducen de ellas.

La gramática anterior en BNF sería:

programa ⟶ instrucciones

instrucciones ⟶ instr
              | instrucciones instr

instr ⟶ IDENT '=' expr
      | IDENT '(' expr ')'
      | IF expr THEN instr ELSE instr

expr ⟶ NUM
     | expr '+' expr
     | expr '*' expr

De ahí, se deducen el resto de los elementos de la GLC:

• VT, los tokens, son aquellos todos símbolos que estén en mayúsculas o entrecomillados.
• VN, los no-terminales (estructuras), son todos aquellos símbolos en los antecedentes de las reglas (programa, instrucciones, instr y expr).
• s, el símbolo inicial, será el antecedente de la primera regla (programa).

Notación EBNF #

La notación EBNF es una extensión de la BNF (de hecho, su nombre proviene de Extended BNF),

En concreto, la extiende añadiendo cuatro operadores:

La gramática anterior, expresada en EBNF, podría simplificar las dos primeras reglas de la gramática (instr y expr seguirán igual):

programa ⟶ instr+

instr ⟶ IDENT '=' expr
      | IDENT '(' expr ')'
      | IF expr THEN instr ELSE instr

expr ⟶ NUM
     | expr '+' expr
     | expr '*' expr

Aunque EBNF sea más cómoda que BNF, esta última es más utilizada en textos y herramientas y, por tanto, se debe de ser capaz de entender y crear una especificación en dicha notación. Por ejemplo, si se desea saber el formato de un fichero JSON, se encontrará que ésta está en BNF.

En esta asignatura se usará una notación u otra indistintamente en función de cual sea más adecuada para cada situación.