Notacion De Backus-Naur

Notación de Backus-Naur
La notación de Backus-Naur, también conocida por sus denominaciones inglesas Backus-Naur form (BNF), Backus-Naur formalism o Backus normal form, es una metasintaxis usada para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales.
El BNF se utiliza extensamente como notación para las gramáticas de los lenguajes deprogramación de la computadora, de los sistemas de comando y de los protocolos de comunicación, así como una notación para representar partes de las gramáticas de la lengua natural (por ejemplo, el metro en la poesía de Venpa). La mayoría de los libros de textos para la teoría o la semántica del lenguaje de programación documentan el lenguaje de programación en BNF.
Algunas variantes, tales como la AugmentedBackus-Naur form (ABNF) y la Extended Backus–Naur Form (EBNF), tienen su propia documentación.
Contenido * 1 Historia * 2 Introducción * 3 Ejemplo * 4 Otros ejemplos * 5 Variantes * 6 Véase también * 7 Referencias * 8 Enlaces externos |
Historia
La idea de transcribir la estructura del lenguaje con reglas de reescritura se remontan cuando menos al trabajo del gramático indioPanini (hacia el 460 a. C.), que la utilizó en su descripción de la estructura de palabras del idioma sánscrito (algunos incluso han sugerido renombrar BNF a Forma Panini-Backus). Lingüïstas estadounidenses como Leonard Bloomfield y Zellig Harris llevaron esta idea un paso más adelante al tratar de formalizar el lenguaje y su estudio en términos de definiciones formales y procedimientos(1920-1960).
Noam Chomsky, maestro de lingüística de alumnos de teoría de la información del MIT, combinó la lingüística y las matemáticas, tomando esencialmente el formalismo de Axel Thue como la base de su descripción de la sintaxis del lenguaje natural. También introdujo una clara distinción entre reglas generativas (de la gramática libre de contexto) y reglas transformativas (1956).
John Backus, undiseñanor de lenguajes de programación de IBM, adoptó las reglas generativas de Chomsky para describir la sintaxis del nuevo lenguaje de programación IAL, conocido en la actualidad como ALGOL 58 (1959), presentando en el primer Congreso de Computación Mundial (World Computer Congress) el artículo "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMMConference".
Peter Naur, en su reporte sobre ALGOL 60 de 1963, identificó la notación de Backus como la Forma Normal de Backus (Backus Normal Form), y la simplificó para usar un conjunto de símbolos menor, pero a sugerencia de Donald Knuth, su apellido fue agregado en reconocimiento a su contribución, reemplazando la palabra "Normal" por Naur, dado que no se trata de una forma normal en nungún sentido,a diferencia, por ejemplo de la Forma Normal de Chomsky.[1]
Introducción
Una especificación de BNF es un sistema de reglas de derivación, escrito como:
<simbolo> ::= <expresión con símbolos>
donde <símbolo> es un no terminal, y la expresión consiste en secuencias de símbolos o secuencias separadas por la barra vertical, '|', indicando una opción, el conjuntoes una posible substitución para el símbolo a la izquierda. Los símbolos que nunca aparecen en un lado izquierdo son terminales.
Ejemplo
Como ejemplo, considere este BNF para una dirección postal de los EE.UU.
<dirección postal> ::= <nombre> <dirección> <apartado postal>
<personal> ::= <primer nombre> | <inicial> "."<nombre> ::= <personal> <apellido> [<trato>] <EOL>
| <personal> <nombre>
<dirección> ::= [<dpto>] <número de la casa> <nombre de la calle> <EOL>
<apartado postal> ::= <ciudad> "," <código estado> <código postal> <EOL>...