Forma Backus-Naur

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo está escrito como un manual o guía .Por favor, ayude a reescribir este artículo y elimine consejos o instrucciones. ( Diciembre de 2023 ) Este artículo puede ser demasiado técnico para que la mayoría de los lectores lo entiendan .Por favor, ayude a mejorarlo para que sea comprensible para los no expertos , sin eliminar los detalles técnicos. ( Diciembre de 2023 )( Aprenda cómo y cuándo eliminar este mensaje ) Este artículo necesita citas adicionales para su verificación .Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Backus–Naur form» – noticias  · periódicos  · libros  · académico  · JSTOR ( Diciembre de 2023 )( Aprenda cómo y cuándo eliminar este mensaje ) ( Aprenda cómo y cuándo eliminar este mensaje )

En informática , la forma Backus–Naur (BNF; /ˌbækəsˈnaʊər/; forma normal de Backus ) es una notación utilizada para describir la sintaxis de 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:

• Inicialice la secuencia para que solo contenga un símbolo de inicio.
• Aplique reglas de derivación a este símbolo de inicio y a las secuencias de símbolos resultantes. ^[1]

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:

• Una dirección postal consta de una parte que corresponde al nombre, seguida de una parte que corresponde a la dirección de la calle , seguida de una parte que corresponde al código postal .
• Una parte de nombre consta de: una parte personal seguida de un apellido seguido de un sufijo opcional (Jr. Sr., o número dinástico) y fin de línea , o una parte personal seguida de una parte de nombre (esta regla ilustra el uso de recursión en BNF, cubriendo el caso de personas que usan múltiples nombres y segundos nombres e iniciales). ^[3]
• Una parte personal consiste en un nombre o una inicial seguida de un punto.
• Una dirección de calle consta de un número de casa, seguido de un nombre de calle, seguido de un especificador de apartamento opcional , seguido de un final de línea.
• Una parte postal consta de un nombre de ciudad , seguido de una coma, seguido de un código de estado , seguido de un código postal seguido de un final de línea.
• Una parte de sufijo opt-suffix consta de un sufijo, como "Sr.", "Jr." o un número romano , o una cadena vacía (es decir, nada).
• Un opt-apt-num consta de un prefijo "Apt" seguido de un número de apartamento o una cadena vacía (es decir, nada).

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 erudito reverenciado 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":

La secuencia de símbolos básicos:	es equivalente a
; comentario <cualquier secuencia que no contenga ';'>;	;
comenzar comentario <cualquier secuencia que no contenga ';'>;	comenzar
fin <cualquier secuencia que no contenga 'fin' o ';' o 'else'>	fin

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}

BNF es muy similar a las ecuaciones de álgebra de Boole 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 de Boole 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 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 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 original de ALGOL 60 (en su lugar, se introdujo unos años más tarde en la definición PL/I de IBM ), la notación ahora es reconocida universalmente.

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:

• Elementos opcionales entre corchetes: [<item-x>].
• Los elementos que existen 0 o más veces se encierran entre llaves o se les añade un asterisco ( *) como por ejemplo <word> ::= <letter> {<letter>}o <word> ::= <letter> <letter>*respectivamente.
• Los elementos que existen una o más veces tienen como sufijo un símbolo de adición (más), +como <word> ::= <letter>+.
• Los terminales pueden aparecer en negrita en lugar de cursiva, y los no terminales en texto simple en lugar de entre corchetes angulares.
• Cuando los elementos están agrupados, se encierran entre paréntesis simples.

• ANTLR , un generador de analizadores sintácticos escrito en Java
• Coco/R , generador de compiladores que acepta una gramática atribuida en EBNF
• Kit de herramientas de reingeniería de software DMS , sistema de análisis y transformación de programas para lenguajes arbitrarios
• GOLD , un generador de analizador BNF
• Analizador BNF de RPA. ^[17] Análisis de demostración en línea (PHP): JavaScript, XML
• Sistema XACT X4MR, ^[18] un sistema experto basado en reglas para la traducción de lenguajes de programación
• Analizador XPL , una herramienta que acepta BNF simplificado para un lenguaje y produce un analizador para ese lenguaje en XPL; puede integrarse en el programa SKELETON suministrado, con el que se puede depurar el lenguaje ^[19] (un programa contribuido por SHARE , que fue precedido por A Compiler Generator ^[20] )
• bnfparser ² , ^[21] una utilidad de verificación de sintaxis universal
• bnf2xml, ^[22] Entrada de marcado con etiquetas XML mediante coincidencia BNF avanzada
• JavaCC , ^[23] Compilador Java Compiler tm (JavaCC tm): el generador de analizadores de Java

• GNU bison , versión GNU de yacc
• Yacc , generador de analizador (más comúnmente utilizado con el preprocesador Lex )
• Herramientas de análisis de Racket, análisis al estilo lex y yacc (edición Beautiful Racket)
• Qlik Sense, una herramienta de BI, utiliza una variante de BNF para la creación de scripts ^[24]
• Convertidor BNF (BNFC ^[25] ), que opera en una variante llamada "forma Backus–Naur etiquetada" (LBNF). En esta variante, a cada producción para un no terminal dado se le asigna una etiqueta, que puede usarse como constructor de un tipo de datos algebraicos que representa ese no terminal. El convertidor es capaz de producir tipos y analizadores para sintaxis abstracta en varios lenguajes, incluidos Haskell y Java.

• Forma aumentada de Backus-Naur (ABNF)
• Lenguaje de descripción del compilador (CDL)
• Gramática de cláusulas definidas : una alternativa más expresiva a la BNF utilizada en Prolog
• Forma extendida de Backus-Naur (EBNF)
• Meta-II : una de las primeras herramientas de escritura y notación de compiladores
• Diagrama de sintaxis – diagrama de ferrocarril
• Forma de traducción Backus-Naur (TBNF)
• Gramática de Van Wijngaarden : utilizada con preferencia a BNF para definir Algol68
• Notación sintáctica de Wirth : una alternativa a BNF desde 1977

• Garshol, Lars Marius, BNF y EBNF: ¿Qué son y cómo funcionan?, NO : Priv.
• RFC  5234 — BNF aumentada para especificaciones de sintaxis: ABNF.
• RFC  5511 — Enrutamiento BNF: una sintaxis utilizada en varias especificaciones de protocolo.
• ISO/IEC 14977:1996(E) Tecnología de la información – Metalenguaje sintáctico – BNF extendido , disponible en “Publicly available”, Normas, ISOo de Kuhn, Marcus, Iso 14977 (PDF) , Reino Unido : CAM (A este último le falta la portada, pero por lo demás está mucho más limpio)

• Bernhard, Algol-60 BNF, DE : LRZ Múnich, el BNF original.
• "Gramáticas BNF para SQL-92, SQL-99 y SQL-2003", Savage, AU : Net, gramáticas BNF disponibles gratuitamente para SQL .
• "BNF Web Club", DB research, CH : Unige, archivado desde el original el 24 de enero de 2007 , consultado el 25 de enero de 2007, gramáticas BNF disponibles gratuitamente para SQL, Ada , Java .
• "Gramáticas de lenguajes de programación libres para la construcción de compiladores", Código fuente, El país libre, gramáticas BNF/ EBNF disponibles gratuitamente para C/C++, Pascal , COBOL , Ada 95 , PL/I .
• "Archivos BNF relacionados con el estándar STEP", Exp Engine ( SVN ), Source Forge, archivado desde el original el 25 de diciembre de 2012. Incluye las partes 11, 14 y 21 de la norma ISO 10303 (STEP).