John W. Backus, el papi de la BNF (Backus-Naur Form)

REGLAS PARA DESCRIBIR LA SINTAXIS DE LENGUAJES DE PROGRAMACION
Pau Mora Murie
Sergio Merino Martíne
Lisardo Fernández Cordeiro
abstrayéndose
    La inquietud ante lo que se presenta como evidente y la intolerancia a lo establecido, ha generado no pocos quebraderos de cabeza a los afortunados portadores de estas singulares actitudes vitales.
    De hecho, avanzar no es gratis, exigiendo arduos esfuerzos y momentos complejos, rebosantes de encrucijadas de rodeo imposible, requiriendo valientes abordajes sin salvavidas reglamentario.
    El resultado de estos ingentes esfuerzos se puede apreciar en el desarrollo de lenguajes de programación que sigue un ritmo imparable, gozando de una salud que para sí querrían muchas economías. Unos orientados y especializados en entornos muy concretos, otros con afán de popularidad y casi todos ellos con un denominador común: su definición aplicando una sintaxis según las reglas concretas que, en los albores de la computación, marcó un hombre de aspecto tranquilo y talento excepcional: John W. Backus.
introducción marcadamente biográfica
    Para la mayor ciudad del estado de Pensilvania, Filadelfia, el 3 de diciembre de 1924 era un día como otro cualquiera. Los nacimientos se apuntaban rigurosamente, con pluma y buen pulso, en el libro de registros pertinente. Uno de ellos fue el de John W. Backus. En el seno de una acomodada familia, creció su inquietud por los aspectos más teóricos de la ciencia que le brindaba su padre.
    La medicina, la química y el derecho lo vieron pasar por sus faldas pero recibieron escaso interés. La matemática ofrecía el grado suficiente de creatividad que demandaba John Backus acogiendo su enorme inspiración.
    Con la licenciatura bajo el brazo, aprovechando una visita a las instalaciones de IBM, consigue un trabajo de programador de la SSEC –una de las primeras computadoras de IBM-. Apenas unos años después y tras dejar tras de sí una mejora muy importante en el trabajo de la máquina con números en coma flotante, decide presentar una opción de desarrollo de un nuevo lenguaje para la programación de la novedosa máquina IBM704, formalizando el nacimiento de los lenguajes de alto nivel y el compilador complementario, con FORTRAN.
    Tras el desarrollo de FORTRAN, John Backus centra su atención en aspectos más teóricos de la programación, Así, partiendo de las gramáticas libres de contexto o incontextuales, desarrolla un modelo a partir de la Forma Normal de Chomsky con el que se pueda describir la sintaxis de cualquier lenguaje de programación, concluyendo en la denominada BNF o Forma Normal de Backus, que tras las mejoras aportadas por el danés Peter Naur, pasaría a conocerse como Backus-Naur Form.
warm-up… gramáticas incontextuales
    Recordemos que una gramática, dentro de la teoría formal de lenguajes, se define como:
G = {VT , VN, S, P}
donde:
VT es el alfabeto o vocabulario terminal.
VN es el alfabeto no terminal.
P  es el conjunto de producciones de la forma
α β | β ϵ V*, α ϵ V*V+V*(V = VT VN)
 S ϵVN  es la variable inicial de las producciones o axioma
    La gramática libre de contexto o incontextual, se define como una gramática formal donde cada una de las producciones siguen la regla siguiente:
A → α    | A ϵ VN, α ϵ V*
    De tal manera que tendremos a la izquierda de la producción una sola variable no terminal y a la derecha cualquier cosa… Entiéndase esto último como concatenación de símbolos de los alfabetos mencionados. No vaya a poner el lector rebelde, un plato de tortilla a la vinagreta.
la notación BNF
    Tal como argumenta Knuth D.E., BNF es más una adaptación de una forma normal a la computación que una forma normal en sí misma, puesto que implicaría establecer restricciones sobre como debe ser escrita la propia gramática, tal y como reflejan FNC y FNG.
    Sin embargo, BNF revela potencia e importancia a la hora de definir lenguajes de programación, pues a partir de unos pocos metasímbolos (::= “se define como”, | “o”, <>), provee una vía concisa para describir posibles combinaciones de elementos constituyentes, lo que se convierte en una ventaja para implementar lenguajes de programación, al mostrar con exactitud como construir la estructura recursiva de los datos para el árbol sintáctico.
    Veamos un ejemplo sobre una sentencia de asignación de un lenguaje tipo PASCAL:  A := A + B
<sent_asig> ::= <var> := <expresion>
<expresion> ::= <expresion> + <termino>  <expresion> – <termino>  <termino>
<termino> ::= <termino> * <factor> <termino> / <factor> <factor>
<factor> ::= ( <expresion> ) <var> | <num>
<var> ::= A  B  C  D  …  Z
<num> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Y su bonito árbol de derivación:


BNF definida por sí misma
    Sirva como curiosidad, la descripción del concepto de BNF utilizando su propia sintaxis:
<syntax>::= <rule> [<syntax>]
<rule> ::=<whitespace> «<» <rule-name>«>» <whitespace> «::=“ expression> <whitespace><line-end>
<expression>::= <whitespace> <or-expression>
<or-expression>::= <whitespace> <list-expression>[ «|» <or-expression> ]
<list-expression>::= <whitespace> («<» <rule-name>«>» | <QUOTE> <text><QUOTE> | «(» <expression>«)» | «[» <expression>«]») [<list-expression>]
<whitespace>::= [» » <whitespace>]
<line-end>::= [<whitespace>] <EOL> [<line-end>]
    Donde se debe identificar <EOL> como final de línea o retorno de carro, <QUOTE> como el caracter “comillas” y <rule-name> y <text> como nombre literal o texto de una regla declarada. No deja de ser interesante observar que no hay una cantidad de espacios en blanco fijada para realizar una interpretación correcta de la regla.
el resto de la historia
    Tal vez el lector más acomodado considere ésta una historia ardua de peregrinaje largo y complejo pero con un final feliz de descanso merecido.
    Lejos de ello, John W. Backus falleció a los 83 años empeñado en encontrar un modelo adecuado para sacar a la programación del barro en el que se encuentra, intentando dotar de una dimensión más rica a lo que él mismo denominó lenguajes de  alto nivel.
conclusión
    Siempre, las palabras de los sabios han servido de inspiración y guía en los albores de cualquier actividad, máxime en temas de procelosa envergadura como este. Así, nada mejor para concluir que las del propio personaje sobre el que gira este trabajo:
“Creo que los lenguajes de programación convencionales son para los pájaros. Son sólo extensiones de la máquina de von Neumann, y mantienen nuestras narices a ras de suelo, tratando con palabras individuales, direcciones de memoria, y todo tipo de estupideces como esas.”.
…y en eso anda enfrascado el universo computacional, mientras la matemática y la informática se devanan en la búsqueda del santo grial del primer paso: será un modelo matemático el que defina los nuevos lenguajes o quizá ocurra al revés… mientras tanto, nada más fiable que una buena Forma Normal para conducir sin riesgos.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *