En informática , la forma Backus–Naur ( / ˌbækəsˈnaʊər / ) ( BNF o forma normal de Backus ) es una notación utilizada para describir la sintaxis de los lenguajes de programación u otros lenguajes formales . Fue desarrollada por John Backus y Peter Naur . BNF puede describirse como una notación 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 oficiales de los lenguajes, en los manuales y en los libros de texto sobre la teoría de los 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; algunas están definidas con exactitud, incluida la forma Backus-Naur extendida (EBNF) y la forma Backus-Naur aumentada (ABNF).
Las BNF describen cómo combinar diferentes símbolos para producir una secuencia sintácticamente correcta. Las 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 denominadas "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 reemplazarse por la expresión de la derecha.__expression__consiste en una o más secuencias de símbolos terminales o no terminales, donde cada secuencia está separada por una barra vertical "|" que indica una elección , siendo el total 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 "eliminación", lo que pretende indicar que podemos eliminar los símbolos de nuestra secuencia y seguir teniendo una secuencia sintácticamente correcta. [1]
A modo de ejemplo, considere este posible BNF para una dirección postal de EE . UU.:
< dirección postal > ::= < parte del nombre > < dirección de la calle > < parte del código postal > < parte-nombre > ::= < parte-personal > < apellido > < parte-sufijo-opt > < EOL > | < parte-personal > < parte-nombre > < parte-personal > ::= < nombre > | < inicial > "." < dirección de la calle > ::= < número de casa > < nombre de la calle > < número de apto. opt. > < EOL > < zip-part > ::= < nombre-ciudad > "," < código-estado > < código-postal > < EOL >< opt-suffix-part > ::= "Sr." | "Jr." | < número romano > | "" < opt-apt-num > ::= "Apt" < apt-num > | ""Esto se traduce al español como:
Tenga en cuenta que aquí no se especifican muchos aspectos (como el formato del nombre, el número de apartamento, el código postal y los números romanos). Si es necesario, se pueden describir utilizando reglas BNF adicionales.
La idea de describir la estructura del lenguaje usando reglas de reescritura se remonta al menos al trabajo de Pāṇini , un antiguo gramático sánscrito indio y un reverenciado erudito en el hinduismo que vivió en algún momento entre el siglo VI y el 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 un estudio científico; las descripciones eran informales y estaban orientadas al uso práctico. En la primera mitad del siglo XX, lingüistas como Leonard Bloomfield y Zellig Harris comenzaron a intentar formalizar la descripción del lenguaje, incluida la estructura de las frases .
Mientras tanto, las reglas de reescritura de cadenas como sistemas lógicos formales fueron introducidas y estudiadas por matemáticos como Axel Thue (en 1914), Emil Post (década de 1920-1940) y Alan Turing (1936). Noam Chomsky , que enseñaba lingüística a estudiantes de teoría de la información en el MIT , combinó la lingüística y las matemáticas al tomar lo que es esencialmente el formalismo de Thue como base para la descripción de la sintaxis del lenguaje natural . También introdujo una distinción clara entre reglas generativas (las de las gramáticas libres de contexto ) y reglas de transformación (1956). [6] [7]
John Backus , diseñador de lenguajes de programación de 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 el trabajo de Chomsky. [11]
Según lo propuesto por Backus, la fórmula define "clases" cuyos nombres están encerrados entre corchetes angulares. Por ejemplo, <ab>. Cada uno de estos nombres denota una clase de símbolos básicos. [2]
El desarrollo posterior de ALGOL condujo 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 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 de Backus de Pāṇini" también se sugirió una vez en vista del hecho de que la forma normal de Backus de expansión puede no ser precisa, y que Pāṇini había desarrollado independientemente una notación similar con anterioridad. [13]
Peter Naur describe BNF en el informe ALGOL 60 como una fórmula metalingüística : [14]
Las secuencias de caracteres encerradas entre corchetes <> representan variables metalingüísticas cuyos valores son secuencias de símbolos. Los signos "::=" y "|" (este último con el significado de "o") son conectores metalingüísticos. Cualquier signo en una fórmula, que no sea una variable o un conector, se denota a sí mismo. La yuxtaposición de signos 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 dentro de los corchetes <>. La siguiente especificación de comentarios de la sección 2.3 del informe ALGOL 60 ejemplifica cómo funciona esto:
Para 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 ocurrencia fuera de cadenas, por el símbolo mostrado en la misma línea en la columna de la derecha sin ningún efecto en la acción del programa.
Naur cambió dos de los símbolos de Backus por caracteres comunes. El ::=símbolo original era un :≡. El |símbolo original era la palabra " o " (con una barra encima). [9] : 14
La BNF es muy similar a las ecuaciones de álgebra booleana en forma canónica que se utilizan, y se utilizaban en su momento, en el diseño de circuitos lógicos. Backus fue matemático y el diseñador del lenguaje de programación FORTRAN. Los estudios de álgebra booleana suelen formar parte de un plan de estudios de matemáticas. Ni Backus ni Naur describieron los nombres incluidos en como no terminales. La terminología de Chomsky no se utilizó originalmente para describir la BNF. Naur los describió más tarde como clases en los materiales del curso ALGOL. [2] En el informe ALGOL 60 se denominaron variables metalingüísticas. Todo lo que no sean los metasímbolos , , y los nombres de clase incluidos en son símbolos del lenguaje que se está definiendo. El metasímbolo debe interpretarse como "se define como". El 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 la 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 lenguajes que se convirtió en el grupo IAL y finalmente condujo a ALGOL. Fue el primer editor gerente de las Comunicaciones de la ACM. [ aclaración necesaria ] 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 ALGOL de IBM, Honeywell, Burroughs y Digital Equipment Corporation siguieron el informe ALGOL 60 utilizándolo como metalenguaje. Saul Rosen en su libro [15] describe BNF como un metalenguaje para hablar sobre 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 de alternativas puede comenzar recursivamente con una alternativa anterior y puede repetirse cualquier número de veces. [2] Por ejemplo, lo anterior <expr>se define como un <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 idioma de destino definidos utilizando cadenas entre comillas. Se eliminaron los corchetes <y . Se agregaron paréntesis para agrupamiento matemático. La regla aparecería en META II como>()<expr>
EXPR = TÉRMINO $ ( '+' TÉRMINO . SALIDA (' AGREGAR ') | '-' TÉRMINO . SALIDA (' SUBIR '));Estos cambios permitieron a META II y a 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 o una descripción de construcción del lenguaje. Muchos metalenguajes derivados se inspiraron en BNF. [ cita requerida ] Véase META II , TREE-META y Metacompiler .
Una clase BNF describe la formación de una construcción de lenguaje, donde la formación se define como un patrón o la acción de formar el patrón. El nombre de clase expr se describe en un lenguaje natural como un <term>seguido de una secuencia <addop> <term>. Una clase es una abstracción; podemos hablar de ella independientemente de su formación. Podemos hablar de un término, independientemente de su definición, como si se agregara o restara en expr. Podemos hablar de un término como un tipo de datos específico y de cómo se debe evaluar una expr teniendo combinaciones específicas de tipos de datos, o incluso reordenando 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 se utilizará en una implementación de compilador y en un programador que escriba un programa ALGOL. La descripción de lenguaje natural también complementó la sintaxis. La regla de los números enteros es un buen ejemplo de lenguaje natural y metalenguaje utilizado para describir la sintaxis:
< entero > ::= < dígito > | < entero >< dígito >En el caso anterior, no hay ninguna especificación sobre los espacios en blanco. En la medida en que la regla lo indica, podríamos tener espacios 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 solo uno de los idiomas naturales posibles. Las traducciones de los informes de 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 requerida ] Durante el período inmediatamente posterior a la publicación del informe ALGOL 60, BNF fue la base de muchos sistemas compilador-compilador .
Algunos, como "A Syntax Directed Compiler for ALGOL 60" desarrollado por Edgar T. Irons y "A Compiler Building System" desarrollado por Brooker y Morris, utilizaron directamente BNF. Otros, como los metacompiladores de Schorre, lo convirtieron en un lenguaje de programación con solo unos pocos cambios. <class name>se convirtieron en identificadores de símbolos, eliminando el envolvente <y >utilizando cadenas entre comillas para los símbolos del lenguaje 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 la 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 se basa en BNF con una producción de código similar a META II. yacc se usa más comúnmente como un generador de analizadores sintácticos y sus raíces son obviamente BNF.
BNF es hoy en día uno de los lenguajes informáticos más antiguos que aún se utiliza. [ cita requerida ]
La sintaxis de BNF puede representarse con un BNF como el siguiente:
< sintaxis > ::= < regla > | < regla > < sintaxis > < regla > ::= < opt-whitespace > "<" < nombre-regla > ">" < opt-whitespace > " ::= " < opt-whitespace > < expresión > < fin-línea > < opt-whitespace > ::= " " < opt-whitespace > | "" < expresión > ::= < lista > | < lista > < opt-whitespace > "|" < opt-whitespace > < expresión > < fin-línea > ::= < opt-whitespace > < EOL > | < fin-línea > < fin-línea > < lista > ::= < término > | < término > < opt-whitespace > < 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" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "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 utilizaba comillas como se muestra en <literal>la regla. Esto supone que no es necesario dejar 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 dependiendo del sistema operativo ) <rule-name>y <text>deben sustituirse con el nombre/etiqueta de una regla declarada o texto literal, respectivamente.
En el ejemplo de la dirección postal de EE. UU. anterior, todo el bloque de citas es un <syntax>. Cada línea o grupo ininterrumpido de líneas es una regla; por ejemplo, una regla comienza con <name-part> ::=. La otra parte de esa regla (aparte de un 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 en esta regla en particular es un nombre de regla.
Existen muchas variantes y extensiones de BNF, generalmente por razones de simplicidad y concisión o para adaptarla 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 una de las más comunes.
Otra extensión común es el uso de corchetes en torno a elementos opcionales. Aunque no estaba presente en el informe ALGOL 60 original (en su lugar, 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 Backus-Naur aumentada (ABNF) y la forma Backus-Naur de enrutamiento (RBNF) [16] son extensiones comúnmente utilizadas para describir los protocolos del Grupo de trabajo de ingeniería de Internet (IETF) .
Las gramáticas de expresiones de análisis se basan en las notaciones BNF y de expresiones regulares para formar una clase alternativa de gramática formal , que es esencialmente analítica en lugar de generativa en su carácter.
Muchas de las especificaciones BNF que se encuentran en línea hoy en día están pensadas para ser legibles por humanos y no son formales. A menudo, incluyen muchas de las siguientes reglas y extensiones de sintaxis:
[<item-x>].*) como por ejemplo <word> ::= <letter> {<letter>}o <word> ::= <letter> <letter>*respectivamente.+como <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 un lenguaje. Para describir lenguajes naturales ordinarios se utilizan designaciones como palabra, verbo, sustantivo. . [8] : 5, Nota 1