En informática , la forma Backus-Naur ( / ˌ b æ k ə s ˈ n aʊər / ) (BNF o forma normal de Backus ) es una notación utilizada para describir la sintaxis de lenguajes de programación u otros lenguajes formales . Fue desarrollado por John Backus y Peter Naur . BNF puede describirse como una notación de metasintaxis para gramáticas libres de contexto . La forma Backus-Naur se aplica siempre que se necesitan descripciones exactas de los lenguajes, como en las especificaciones de los lenguajes oficiales, en manuales y libros de texto sobre teoría de lenguajes de programación. BNF se puede utilizar para describir formatos de documentos , conjuntos de instrucciones y protocolos de comunicación .
Con el tiempo, se han creado muchas extensiones y variantes de la notación Backus-Naur original; algunos están exactamente definidos, incluida la forma Backus-Naur extendida (EBNF) y la forma Backus-Naur aumentada (ABNF).
Los BNF describen cómo combinar diferentes símbolos para producir una secuencia sintácticamente correcta. Los BNF constan de tres componentes: un conjunto de símbolos no terminales, un conjunto de símbolos terminales y reglas para reemplazar símbolos no terminales con una secuencia de símbolos. [1] Estas llamadas "reglas de derivación" se escriben como
< símbolo > ::= __expresión__dónde:
<symbol>[2] es una variable no terminal que siempre está encerrada entre el par <>.::=significa que el símbolo de la izquierda debe ser reemplazado por la expresión de la derecha.__expression__consta de una o más secuencias de símbolos terminales o no terminales donde cada secuencia está separada por una barra vertical "|" indicando una elección , siendo el conjunto una posible sustitución del símbolo de la izquierda.Todas las secuencias sintácticamente correctas deben generarse de la siguiente manera:
La aplicación de reglas de esta manera puede producir secuencias cada vez más largas, por lo que muchas definiciones de BNF permiten incluir un símbolo especial de "eliminación" en la especificación. Podemos especificar una regla que nos permita reemplazar algunos símbolos con este símbolo de "eliminar", que pretende indicar que podemos eliminar los símbolos de nuestra secuencia y aún tener una secuencia sintácticamente correcta. [1]
Como ejemplo, considere este posible BNF para una dirección postal de EE. UU .:
< dirección-postal > ::= < parte-nombre > < dirección-calle > < parte-zip > < parte-nombre > ::= < parte-personal > < apellido > < parte-sufijo-opt > < EOL > | < parte-personal > < parte-nombre > <parte-personal> :: = <nombre> | < inicial > "." < dirección-calle > ::= < núm-casa > < nombre-calle > < núm-apt-opt > < EOL > < parte-zip > ::= < nombre-ciudad > "," < código-estado > < código postal > < EOL >< opt-suffix-part > ::= "Sr." | "Jr." | < número romano > | " " <opt-num-apt> :: = " Apt " <apt-num> | "" Esto se traduce al inglés como:
Tenga en cuenta que muchas cosas (como el formato del nombre, el número de apartamento, el código postal y el número romano) no se especifican aquí. Si es necesario, pueden describirse utilizando reglas BNF adicionales.
La idea de describir la estructura del lenguaje utilizando reglas de reescritura se remonta al menos al trabajo de Pāṇini , un antiguo gramático sánscrito indio y venerado erudito del hinduismo que vivió en algún momento entre los siglos VI y IV a.C. [4] [5] Su notación para describir la estructura de las palabras sánscritas es equivalente en poder a la de Backus y tiene muchas propiedades similares.
En la sociedad occidental, la gramática se consideró durante mucho tiempo una materia de enseñanza, más que de estudio científico; Las descripciones eran informales y estaban dirigidas a un uso práctico. En la primera mitad del siglo XX, lingüistas como Leonard Bloomfield y Zellig Harris iniciaron intentos de formalizar la descripción del lenguaje, incluida la estructura de las frases .
Mientras tanto, matemáticos como Axel Thue (en 1914), Emil Post (décadas de 1920 a 1940) y Alan Turing (1936) introdujeron y estudiaron reglas de reescritura de cadenas como sistemas lógicos formales . Noam Chomsky , que enseñaba lingüística a estudiantes de teoría de la información en el MIT , combinó lingüística y matemáticas tomando lo que es esencialmente el formalismo de Thue como base para la descripción de la sintaxis del lenguaje natural . También introdujo una clara distinción entre reglas generativas (las de gramáticas libres de contexto ) y reglas de transformación (1956). [6] [7]
John Backus , diseñador de lenguajes de programación en IBM , propuso un metalenguaje de "fórmulas metalingüísticas" [2] [9] [10] para describir la sintaxis del nuevo lenguaje de programación IAL, conocido hoy como ALGOL 58 (1959). Su notación se utilizó por primera vez en el informe ALGOL 60.
BNF es una notación para las gramáticas libres de contexto de Chomsky. Backus estaba familiarizado con la obra de Chomsky. [11]
Según lo propuesto por Backus, la fórmula definía "clases" cuyos nombres están entre paréntesis angulares. Por ejemplo, <ab>. Cada uno de estos nombres denota una clase de símbolos básicos. [2]
Un mayor desarrollo de ALGOL dio lugar a ALGOL 60 . En el informe del comité de 1963, Peter Naur llamó a la notación de Backus forma normal de Backus . Donald Knuth argumentó que BNF debería leerse más bien como la forma Backus-Naur , ya que "no es una forma normal en el sentido convencional", [12] a diferencia, por ejemplo, de la forma normal de Chomsky . El nombre forma Pāṇini Backus también se sugirió una vez en vista del hecho de que la forma normal de expansión Backus puede no ser precisa y que Pāṇini había desarrollado de forma independiente una notación similar anteriormente. [13]
BNF es descrito por Peter Naur en el informe ALGOL 60 como fórmula metalingüística : [14]
Las secuencias de caracteres encerrados entre corchetes <> representan variables metalingüísticas cuyos valores son secuencias de símbolos. Las marcas "::=" y "|" (estos últimos con el significado de "o") son conectivos metalingüísticos. Cualquier marca en una fórmula, que no sea una variable o un conectivo, se denota a sí misma. La yuxtaposición de marcas o variables en una fórmula significa yuxtaposición de la secuencia denotada.
Otro ejemplo del informe ALGOL 60 ilustra una diferencia importante entre el metalenguaje BNF y una gramática libre de contexto de Chomsky. Las variables metalingüísticas no requieren una regla que defina su formación. Su formación puede describirse simplemente en lenguaje natural entre los corchetes <>. La siguiente especificación de comentarios de la sección 2.3 del informe ALGOL 60 ejemplifica cómo funciona esto:
A los efectos de incluir texto entre los símbolos de un programa, se aplican las siguientes convenciones de "comentarios":
Equivalencia aquí significa que cualquiera de las tres estructuras mostradas en la columna de la izquierda puede ser reemplazada, en cualquier aparición fuera de las cadenas, por el símbolo que se muestra en la misma línea en la columna de la derecha sin ningún efecto sobre la acción del programa.
Naur cambió dos de los símbolos de Backus por caracteres comúnmente disponibles. El ::=símbolo era originalmente un :≡. El |símbolo era originalmente la palabra " o " (con una barra encima). [9] : 14
BNF es muy similar a las ecuaciones de álgebra booleana en forma canónica que se utilizan, y se utilizaban en ese momento, en el diseño de circuitos lógicos. Backus fue matemático y diseñador del lenguaje de programación FORTRAN. Los estudios de álgebra booleana suelen formar parte del plan de estudios de matemáticas. Ni Backus ni Naur describieron los nombres incluidos como no terminales. La terminología de Chomsky no se utilizó originalmente para describir BNF. Más tarde, Naur las describió como clases de materiales del curso ALGOL. [2] En el informe ALGOL 60 se denominaron variables metalingüísticas. Cualquier cosa que no sean los metasímbolos , y los nombres de clase encerrados son símbolos del lenguaje que se define. El metasímbolo debe interpretarse como "se define como". Se utiliza para separar definiciones alternativas y se interpreta como "o". Los metasímbolos son delimitadores que encierran un nombre de clase. Peter Naur y Saul Rosen describen BNF como un metalenguaje para hablar sobre ALGOL . [2]< >::=|< >::=|< >
En 1947, Saul Rosen se involucró en las actividades de la incipiente Association for Computing Machinery , primero en el comité de idiomas que se convirtió en el grupo IAL y finalmente condujo a ALGOL. Fue el primer redactor jefe de Comunicaciones de la ACM. [ se necesita aclaración ] BNF se utilizó por primera vez como metalenguaje para hablar sobre el lenguaje ALGOL en el informe ALGOL 60. Así es como se explica en el material del curso de programación ALGOL desarrollado por Peter Naur en 1962. [2] Los primeros manuales de ALGOL de IBM, Honeywell, Burroughs y Digital Equipment Corporation siguieron el informe ALGOL 60 usándolo como metalenguaje. Saul Rosen en su libro [15] describe BNF como un metalenguaje para hablar de ALGOL. Un ejemplo de su uso como metalenguaje sería la definición de una expresión aritmética:
< expr > ::= < término > | < expr >< addop >< término >El primer símbolo de una alternativa puede ser la clase que se está definiendo, teniendo la repetición, como explica Naur, la función de especificar que la secuencia alternativa puede comenzar recursivamente con una alternativa anterior y puede repetirse cualquier número de veces. [2] Por ejemplo, lo anterior <expr>se define como <term>seguido de cualquier número de <addop> <term>.
En algunos metalenguajes posteriores, como META II de Schorre , la construcción de repetición recursiva BNF se reemplaza por un operador de secuencia y símbolos del lenguaje de destino definidos mediante cadenas entre comillas. Se quitaron los corchetes <y . Se agregaron >paréntesis para agrupación matemática. ()La <expr>regla aparecería en META II como
EXPR = TERM $ ( '+' TERM . OUT (' AGREGAR ') | '-' TERM . OUT (' SUB '));Estos cambios permitieron a META II y sus lenguajes de programación derivados definir y ampliar su propio metalenguaje, a costa de la capacidad de utilizar una descripción en lenguaje natural, una variable metalingüística y una descripción de construcción del lenguaje. Muchos metalenguajes derivados se inspiraron en BNF. [ cita requerida ] Ver META II , TREE-META y Metacompiler .
Una clase BNF describe la formación de una construcción del lenguaje, con la formación definida como un patrón o la acción de formar el patrón. El nombre de clase expr se describe en un lenguaje natural <term>seguido de una secuencia <addop> <term>. Una clase es una abstracción; podemos hablar de ello independientemente de su formación. Podemos hablar de término, independientemente de su definición, como suma o resta en expr. Podemos hablar de que un término es un tipo de datos específico y cómo se debe evaluar una expr teniendo combinaciones específicas de tipos de datos, o incluso reordenar una expresión para agrupar tipos de datos y resultados de evaluación de tipos mixtos. El suplemento de lenguaje natural proporcionó detalles específicos de la semántica de la clase de lenguaje que utilizará una implementación del compilador y un programador que escriba un programa ALGOL. La descripción en lenguaje natural también complementó aún más la sintaxis. La regla de los enteros es un buen ejemplo de lenguaje natural y metalenguaje utilizado para describir la sintaxis:
< entero > ::= < dígito > | < entero >< dígito >No hay detalles sobre los espacios en blanco en lo anterior. Como dice la regla, podríamos tener espacio entre los dígitos. En el lenguaje natural complementamos el metalenguaje BNF explicando que la secuencia de dígitos no puede tener espacios en blanco entre los dígitos. El inglés es sólo uno de los posibles idiomas naturales. Las traducciones de los informes ALGOL estaban disponibles en muchos idiomas naturales.
El origen de BNF no es tan importante como su impacto en el desarrollo del lenguaje de programación. [ cita necesaria ] Durante el período inmediatamente posterior a la publicación del informe ALGOL 60, BNF fue la base de muchos sistemas compiladores .
Algunos, como "Un compilador dirigido por sintaxis para ALGOL 60" desarrollado por Edgar T. Irons y "Un sistema de construcción de compiladores" desarrollado por Brooker y Morris, utilizaban directamente BNF. Otros, como los metacompiladores Schorre, lo convirtieron en un lenguaje de programación con sólo unos pocos cambios. <class name>se convirtieron en identificadores de símbolos, eliminando el encerramiento <y >usando cadenas entre comillas para los símbolos del idioma de destino. La agrupación de tipo aritmético proporcionó una simplificación que eliminó el uso de clases donde la agrupación era su único valor. La regla de expresión aritmética META II muestra el uso de agrupación. Las expresiones de salida colocadas en una regla META II se utilizan para generar código y etiquetas en un lenguaje ensamblador. Las reglas en META II son equivalentes a las definiciones de clase en BNF. La utilidad Unix yacc está basada en BNF con una producción de código similar a META II. yacc se usa más comúnmente como generador de analizadores y sus raíces son obviamente BNF.
BNF es hoy uno de los lenguajes informáticos más antiguos que aún se utilizan. [ cita necesaria ]
La sintaxis de BNF en sí se puede representar con un BNF como el siguiente:
<sintaxis> :: = <regla> | < regla > < sintaxis > < regla > ::= < opt-espacio en blanco > "<" < nombre de regla > ">" < opt-espacio en blanco > " ::= " < opt-espacio en blanco > < expresión > < fin de línea > < opt-espacio en blanco > ::= " " < opt-espacio en blanco > | "" < expresión > ::= < lista > | < lista > < opt-espacio en blanco > "|" < opt-espacio en blanco > < expresión > < fin de línea > ::= < opt-espacio en blanco > < EOL > | < final de línea > < final de línea > < lista > ::= < término > | < término > < opt-espacio en blanco > < lista > < término > ::= < literal > | "<" < nombre-regla > ">" < literal > ::= '"' < texto1 > '"' | "'" < texto2 > "'" < texto1 > ::= "" | < carácter1 > < texto1 > < texto2 > ::= "" | < carácter2 > < texto2 > < carácter > ::= < letra > | < dígito > | < símbolo > < letra > ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "yo" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "un" | "b" | "c" | "d" | "mi" | "f" | "g" | "h" | "yo" | "j" | "k" | "yo" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "tú" | "v" | "w" | "x" | "y" | "z" < dígito > ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" < símbolo > ::= "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~" < carácter1 > ::= < carácter > | "'" < carácter2 > ::= < carácter > | '"' < nombre-regla > ::= < letra > | < nombre-regla > < carácter-regla > < carácter-regla > ::= < letra > | < dígito > | "-"Tenga en cuenta que "" es la cadena vacía .
El BNF original no utilizó comillas como se muestra en <literal>la regla. Esto supone que no se necesitan espacios en blanco para una interpretación adecuada de la regla.
<EOL>representa el especificador de final de línea apropiado (en ASCII , retorno de carro, avance de línea o ambos, según el sistema operativo ). <rule-name>y <text>deben sustituirse por el nombre/etiqueta de una regla declarada o por el texto literal, respectivamente.
En el ejemplo anterior de dirección postal de EE. UU., la cita en bloque completa es un archivo <syntax>. Cada línea o agrupación ininterrumpida de líneas es una regla; por ejemplo, una regla comienza con <name-part> ::=. La otra parte de esa regla (aparte del final de línea) es una expresión, que consta de dos listas separadas por una barra vertical |. Estas dos listas constan de algunos términos (tres términos y dos términos, respectivamente). Cada término de esta regla en particular es un nombre de regla.
Existen muchas variantes y extensiones de BNF, generalmente ya sea por simplicidad y concisión, o para adaptarlo a una aplicación específica. Una característica común de muchas variantes es el uso de operadores de repetición de expresiones regulares como *y +. La forma extendida Backus-Naur (EBNF) es común.
Otra extensión común es el uso de corchetes alrededor de elementos opcionales. Aunque no está presente en el informe ALGOL 60 original (en cambio, se introdujo unos años más tarde en la definición PL/I de IBM ), la notación ahora es universalmente reconocida.
La forma Augmented Backus-Naur (ABNF) y la forma Routing Backus-Naur (RBNF) [16] son extensiones comúnmente utilizadas para describir los protocolos del Internet Engineering Task Force (IETF) .
Las gramáticas de expresión de análisis se basan en BNF y las notaciones de expresiones regulares para formar una clase alternativa de gramática formal , que es esencialmente de carácter analítico más que generativo .
Muchas especificaciones BNF que se encuentran en línea hoy en día están destinadas a ser legibles por humanos y no son formales. A menudo incluyen muchas de las siguientes reglas y extensiones de sintaxis:
[<item-x>].*), como <word> ::= <letter> {<letter>}o <word> ::= <letter> <letter>*respectivamente.+como por ejemplo <word> ::= <letter>+.< >, como <ab>, denotan clases cuyos miembros son secuencias de símbolos básicos. Las designaciones de clase de este tipo se encuentran en cualquier descripción de una lengua. Para describir lenguajes naturales ordinarios se utilizan designaciones como palabra, verbo, sustantivo. . [8] : 5, Nota 1