BNF (Forma Normal Backus

 FORMA (NORMAL) DE BACKUS - NAUR (BNF)

Fue la primera notación formal cuyo empleo se ha generalizado para describir la sintaxis de un lenguaje de programación; la creó John Backus en 1960. Los lenguajes de alto nivel como Fortran, Pascal, C, C++ y Algol pueden representarse en BNF.

La notación se adoptó de inmediato para describir Algol 60. Después se supo que Panini había usado unanotación similar a la BNF entre 400 y 200 A.C. para describir las complejas reglas de la Gramática del sánscrito.

Las siglas BNF comenzaron como abreviatura de Backus Normal Form, y después se transformó su interpretación en Backus - Naur Form, para reconocer las contribuciones de este último como editor del informe de ALGOL 60. Una variante surgida posteriormente fue la BNF extendida. Estas dosrepresentaciones, en combinación con los diagramas o esquemas de sintaxis (que son en sí reglas de producción en modo gráfico), pueden utilizarse para expresar la forma como se construyen las partes de los programas en un Lenguaje de programación de alto nivel.

LA BNF ES, ES ESENCIA, UN CAMBIO DE NOMENCLATURA.

Consiste en la aplicación de los siguientes tres criterios para modificar el aspectoque presenta la Gramática, cambiando la notación aprendida en el módulo anterior:
1. Símbolos no terminales: Se delimitan con < >.
2. Composiciones: Se sustituye la flecha por ::=.
3. Composiciones múltiples: Se pueden agrupar con | (o), cuando varias reglas
tienen el mismo valor en el lado izquierdo.

EJEMPLO:
Transformar la siguiente Gramática a la BNF correspondiente.
G = ( {R, S},{a, b}, {R  bR, R  aS, S  bS, S  b} , {R} )
G = ( { , }, {a, b}, { ::= b | a, ::= b | b} , {} )

En el ejemplo anterior se empleó para fines didácticos la conversión a la notación de BNF de una Gramática cuyo enfoque es más matemático que computacional. Ésto resultó inadecuado, ya que se complicó la representación; nótese que la representación en BNF es más extensa en su longitud.
Enrealidad a la BNF se la debe utilizar solamente en casos en los que para nombrar a los símbolos no terminales se deba describir su significado, en vez de emplear una sola letra mayúscula, es decir, cuando tiene un propósito computacional.

EJEMPLO:
Mostrar que la cadena s = -318  L(G), donde G = ( N, T, P, 0 ) con los siguientes:
N = { , , , }
T = { +, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
P= { ::=  ,
::= +  - ,
::=  ,
::= 0 1 2 3 4 5 6 7 8 9 }
0 = { } //Indica lo que produce la Gramática.

La Gramática genera todos los números enteros válidos y nada más. Por tanto produce, por ejemplo 1649, -65, +1000000, etc. pero no -36.2, ni 12., ni 67+.
NOTA: Existen otras variadas Gramáticasequivalentes a la anterior para el mismo propósito.

Derivemos, a partir del símbolo inicial, y basados en la descripción contenida en cada símbolo no terminal, sabremos sin posibilidad de equivocarnos, cómo debe ser la derivación:
  -  - 
-  - 
-3  -31  -318 L.Q.D.M.

Recomendación: Al símbolo inicial se lo debería denominar con una o varias palabras descriptivas sobre lo que sedesea producir en el Lenguaje; por ejemplo, en este caso se lo llamó entero.

La ventaja de emplear, en estas Gramáticas, la BNF es que se puede describir el tipo de cadena que va a ser producida; ésto se logra, dándole el nombre correspondiente al símbolo no terminal. Aunque la descripción sea muy extensa, no importa, ya que con los caracteres < y > delimitamos lo que es un único símbolo; porejemplo, es un único no terminal, descrito con tres palabras.

A los símbolos no terminales se los llama también constructores, y a los terminales tokens o componentes léxicos.

EJEMPLO:
¿De qué frases consta la siguiente Gramática? Considerar como símbolo inicial a .
P = { ::= ,
::= ,
::= | ,
::= . ,
::= Rubén | Sandra,
::= odia | golpea,
::= duerme,
::= a }...