3.2    Metalenguajes formales para describir sintaxis.

La definición formal de la sintaxis de un LP se conoce comúnmente como gramática.

Una gramática se compone de un conjunto de reglas (producciones) que definen las palabras (elementos léxicos) y unidades sintácticas. Una gramática formal es una que usa una notación definida (o metalenguaje) de manera estricta. Aquí veremos dos metalenguajes para describir gramáticas libres del contexto: BNF y diagramas sintácticos.

3.2.1 Gramáticas BNF.

Cuando se considera la estructura de una oración en Español, se le describe por lo general como una secuencia de categorías:

    sujeto | verbo | complemento

Podemos decir que una oración puede ser una oración declarativa o una oración interrogativa, lo que denotamos:

<oración> ::= <declarativa> | <interrogativa>

donde "::=" significa "se define cómo" y "|" significa "o"; comparándolo con el lenguaje usado en las gramáticas formales, las palabras encerradas entre <palabra> son categorías sintácticas o no terminales, es decir deben ser definidas; "::=" equivale a "->" y "|" tiene el mismo significado. Así, por ejemplo, en gramáticas formales:

O -> D | I
S -> S V C
S -> A N
I -> ¿ V S P ?

en nuestro metalenguaje:

<oración> ::= <declarativa> | <interrogativa>
<declarativa> ::= <sujeto> <verbo> <complemento>
<sujeto> ::= <artículo> <nombre>
:
<interrogativa> ::= ¿ <verbo> <sujeto> <predicado> ?
:

Esta notación específica se conoce como BNF (Backus Naur Form) desarrollada por John Backus alrededor de 1960 para la definición de ALGOL.

Para expresar repetición se usa la recursividad, por ejemplo:

<entero> ::= <entero> <dígito> | <dígito>

define a un entero como una secuencia de dígitos, con a lo menos un dígito.

A pesar de su estructura sencilla, BNF sirve para definir casi todos los lenguajes de programación. Las áreas de sintaxis que no pueden definirse con una BNF y tampoco con una gramática libre del contexto, son aquellas que indican dependencia contextual. Por ejemplo, "un arreglo declarado con dos dimensiones, no se puede referenciar con tres subíndices", o "en un comando de atribución, la variable del lado izquierdo debe ser del mismo tipo de la expresión del lado derecho", etc.

Notación BNF extendida: Las extensiones siguientes permiten realizar descripciones más fáciles de los lenguajes:

Se puede indicar un elemento optativo usando [...]
Una selección de alternativas opcionales se puede hacer usando[ | ] ó { | }
Una repetición arbitraria se puede indicar con {...}*

Ejemplo:

<entero> ::= [+|-] <dígito> {<dígito>}*
<identificador> ::= <letra> {<letra> | <dígito>}*

3.2.2 Diagramas sintácticos.

Los diagramas sintácticos son una forma gráfica de expresar la BNF extendida. Cada regla está representada por un camino que va desde la entrada ubicada a la izquierda, hasta la salida, ubicada a la derecha. Cualquier trayecto desde la entrada a la salida representa un string generado por esa regla.

Las categorías sintácticas (no - terminales) se representan por rectángulos y los símbolos terminales por círculos u óvalos. Ejemplo:

Entero

Veamos un ejemplo de asignación con los tres metalenguajes:

  1. En BNF:
<comando asignación> ::= <variable> := <expresión aritmética>
<expresión aritmética> ::= <término> | <expresión aritmética> + <término> | <expresión aritmética> - <término>
<término> ::= <primario> | <término> * <primario> | <término> / <primario>
<primario> ::= <variable> | <número> | (<expresión aritmética>)
<variable> ::= <identificador> | <identificador> [<lista subíndice>]
<lista subíndice> ::= <expresión aritmética> | <lista subíndice> , <expresión aritmética>
  1. En BNF extendida:
<comando asignación> ::= <variable> := <expresión aritmética>
<expresión aritmética> ::= <término> { [+|-] <término> }*
<término> ::= <primario> { [*|/] <primario> }
<primario> ::= <variable> | <número> | (<expresión aritmética>)
<variable> ::= <identificador> | <identificador> [<lista subíndice>]
<lista subíndice> ::= <expresión aritmética> { , <expresión aritmética> }*
  1. En diagramas sintácticos:
Comando asignación.

Comando asignación

Expresión aritmética.

Expresión aritmética

Término.

Término

Primario.

Primario

Variable.

Variable

Lista subíndice.

Lista subíndice