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 de programació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 Augmented Backus-Naur form (ABNF) y la Extended Backus–Naur Form (EBNF), tienen su propia documentación.

Historia

La idea de transcribir la estructura del lenguaje con reglas de reescritura se remontan cuando menos al trabajo del gramático indio Panini (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, un diseñ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-GAMM Conference".

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 conjunto es 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>

Esto se traduce a español como:

• Una dirección postal consiste en un nombre, seguido por una dirección, seguida por un apartado postal.
• Una parte "personal" consiste en un nombre o una inicial seguido(a) por un punto.
• Un nombre consiste de: una parte personal seguida por un apellido seguido opcionalmente por una jerarquía o el trato que se la da a la persona (Jr., Sr., o número dinástico) y un salto de línea (end-of-line), o bien una parte personal seguida por un nombre (esta regla ilustra el uso de la repetición en BNFs, cubriendo el caso de la gente que utiliza múltiples nombres y los nombres medios o las iniciales).
• Una dirección consiste de una especificación opcional del departamento, seguido de un número de casa, seguido por el nombre de la calle, seguido por un salto de línea (end-of-line).
• Un apartado postal consiste de una ciudad, seguida por una coma, seguida por un código del estado (recuerde que es un ejemplo que ocurre en EE.UU.), seguido por un código postal y este seguido por un salto de línea (end-of-line).

Observe que muchas cosas (tales como el formato de una parte personal, de una especificación del apartamento, o código postal) están dejadas sin especificar aquí. Si es necesario, pueden ser descritas usando reglas adicionales de BNF, o dejadas como abstracción si es inaplicable para el propósito actual.

Otros ejemplos

Bastante interesante, la sintaxis de BNF se puede representar en BNF como sigue:

 <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>]

Esto asume que no hay Whitespace necesario para la interpretación apropiada de la regla. El <QUOTE> se presume para ser el carácter ", y el <EOL> para ser el fin de línea apropiado especificado (en ASCII, retorno de carro o línea nueva, dependiendo del sistema operativo). El <rule-name> y el <text> deben ser substituidos con nombre/etiqueta o el texto literal de una regla declarada, respectivamente.

Variantes

Hay muchas variantes y extensiones de BNF, posiblemente conteniendo algunos o todos los comodines de expresiones regulares como un "*" o "+". El Extended Backus-Naur form (EBNF) es una variante común. De hecho el ejemplo anterior no es la forma pura inventada para el informe del ALGOL 60. La notación de los corchetes "[ ]" fue introducida algunos años más tarde en la definición de PL/I de la IBM pero ahora se reconoce universal. La ABNF es otra extensión usada comúnmente para describir protocolos del IETF.

Las expresiones gramaticales de analizadores sintácticos construidas en BNF y las notaciones de expresión regular para formar una clase alternativa de la gramática formal, que es esencialmente analítica más que generativa en carácter.

Muchas especificaciones de BNF disponibles en línea tienen como propósito ser legibles a simple vista y no son especificaciones formales. Estas incluyen con frecuencia algunas de estas reglas sintácticas y extensiones:

• Elementos opcionales son presentados entre paréntesis cuadrados. Por ejemplo [<elemento-x>]
• Los elementos que se repiten 0 o más veces son presentados entre paréntesis de llave o terminados con un asterisco. Por ejemplo <palabra> ::= <letra> {<letra>}
• Los elementos que se repiten 1 o más veces son terminados con un '+'
• Los terminales pueden aparecer en negrillas y los no-terminales en texto normal en lugar de utilizar itálicas o paréntesis de ángulo
• Alternativas opcionales son separadas por el símbolo '|'
• Cuando se requiere agrupar varios elementos, se hace con paréntesis simples

Véase también

• Astadhiai (gramática sánscrita con estructura matemática)
• GOLD BNF parser
• Yacc Parser Generator
• GNU bison GNU Version of Yacc

Referencias

1. ↑ Knuth, Donald E. (1964). «Backus Normal Form vs. Backus Naur Form». Communications of the ACM 7 (12):  pp. pp. 735-736.  (en inglés)

Enlaces externos

• [1] contains a posting on news:comp. compilers that explains some of the history of the two names (Backus-Naur form vs. Backus normal form).
• Article BNF and EBNF: What are they and how do they work? by Lars Marius Garshol.
• RFC 4234 Augmented BNF for Syntax Specifications: ABNF
• Grammatica Parser
• Spirit Parser