En informática , la forma Backus–Naur extendida ( EBNF ) es una familia de notaciones metasintaxis , cualquiera de las cuales puede utilizarse para expresar una gramática libre de contexto . La EBNF se utiliza para realizar una descripción formal de un lenguaje formal , como un lenguaje de programación informática . Son extensiones de la notación metasintaxis de la forma Backus–Naur básica (BNF).
El primer EBNF fue desarrollado por Niklaus Wirth , que incorporó algunos de los conceptos (con una sintaxis y notación diferentes) de la notación sintáctica de Wirth . Hoy en día, se utilizan muchas variantes de EBNF. La Organización Internacional de Normalización adoptó un estándar EBNF , ISO/IEC 14977, en 1996. [1] [2] Sin embargo, según Zaytsev, este estándar "solo terminó agregando otros tres dialectos al caos" y, después de notar su falta de éxito, también señala que el EBNF ISO ni siquiera se usa en todos los estándares ISO. [3] Wheeler argumenta en contra del uso del estándar ISO cuando se usa un EBNF y recomienda considerar notaciones EBNF alternativas como la del Lenguaje de marcado extensible (XML) 1.0 (Quinta edición) del W3C. [4]
En este artículo se utiliza el EBNF tal como lo especifica la ISO para los ejemplos que se aplican a todos los EBNF. Otras variantes del EBNF utilizan convenciones sintácticas ligeramente diferentes.
EBNF es un código que expresa la sintaxis de un lenguaje formal. [5] Un EBNF consta de símbolos terminales y reglas de producción no terminales que son las restricciones que rigen cómo se pueden combinar los símbolos terminales en una secuencia válida. Algunos ejemplos de símbolos terminales incluyen caracteres alfanuméricos , signos de puntuación y caracteres de espacio en blanco .
La EBNF define reglas de producción donde las secuencias de símbolos se asignan respectivamente a un no terminal :
dígito excluyendo cero = "1" | "2" | "3" | "4" | "5" | " 6" | "7" | "8" | "9" ; dígito = "0" | dígito excluyendo cero ;Esta regla de producción define el dígito no terminal que se encuentra en el lado izquierdo de la asignación. La barra vertical representa una alternativa y los símbolos terminales se encierran entre comillas seguidas de un punto y coma como carácter de terminación. Por lo tanto, un dígito es un 0 o un dígito que excluye el cero y que puede ser 1 , 2 , 3 , etc. hasta el 9 .
Una regla de producción también puede incluir una secuencia de terminales o no terminales, cada uno separado por una coma:
doce = "1" , "2" ; doscientos uno = "2" , "0" , "1" ; trescientos doce = "3" , doce ; doce mil doscientos uno = doce , doscientos uno ;Las expresiones que pueden omitirse o repetirse se pueden representar mediante llaves { ... }:
número natural = dígito excluyendo cero , { dígito } ;En este caso, las cadenas 1 , 2 , ..., 10 , ..., 10000 , ... son expresiones correctas. Para representar esto, todo lo que se encuentra dentro de las llaves se puede repetir con cualquier frecuencia, incluso nunca.
Una opción puede representarse mediante corchetes [...]. Es decir, todo lo que se encuentra dentro de los corchetes puede estar presente solo una vez o no estar presente en absoluto:
entero = "0" | [ "-" ], número natural ;Por lo tanto, un número entero es un cero ( 0 ) o un número natural que puede estar precedido por un signo menos opcional .
EBNF también proporciona, entre otras cosas, la sintaxis para describir repeticiones (de un número específico de veces), para excluir alguna parte de una producción y para insertar comentarios en una gramática EBNF.
A continuación se presenta una propuesta de norma ISO/IEC 14977, por RS Scowen, página 7, tablas 1 y 2.
Incluso la EBNF se puede describir utilizando EBNF. Considere la gramática a continuación (utilizando convenciones como "-" para indicar disyunción de conjuntos, "+" para indicar una o más coincidencias y "?" para opcionalidad):
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 = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" | "-" | "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;carácter = letra | dígito | símbolo | "_" | " " ; identificador = letra , { letra | dígito | "_" } ;S = { " " | "\n" | "\t " | "\r" | "\f" | "\b" } ;terminal = "'" , caracter - "'" , { caracter - "'" } , "'" | '"' , caracter - '"' , { caracter - '"' } , '"' ;terminador = ";" | "." ;término = "(" , S , rhs , S , ")" | "[" , S , rhs , S , "]" | "{" , S , rhs , S , "}" | terminal | identificador ;factor = término , S , "?" | término , S , "*" | término , S , "+" | término , S , "-" , S , término | término , S ;concatenación = ( S , factor , S , "," ? ) + ; alternancia = ( S , concatenación , S , "|" ? ) + ;rhs = alternancia ; lhs = identificador ;regla = lhs , S , "=" , S , rhs , S , terminador ;gramática = ( S , regla , S ) * ;Un lenguaje de programación similar a Pascal que solo permite asignaciones se puede definir en EBNF de la siguiente manera:
(* una sintaxis de programa simple en EBNF - Wikipedia *) programa = 'PROGRAMA' , espacio en blanco , identificador , espacio en blanco , 'BEGIN' , espacio en blanco , { asignación , ";" , espacio en blanco }, 'END.' ; identificador = carácter alfabético , { carácter alfabético | dígito } ; número = [ "-" ], dígito , { dígito } ; cadena = '"' , { todos los caracteres - '"' }, '"' ; asignación = identificador , ":=" , ( número | identificador | cadena ) ; carácter alfabético = "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" ; espacio en blanco = ? caracteres de espacio en blanco ? ; todos los caracteres = ? todos los caracteres visibles ? ; Por ejemplo, un programa sintácticamente correcto podría ser:
PROGRAMA DEMO1 COMIENZO A := 3 ; B := 45 ; H :=- 100023 ; C := A ; D123 := B34A ; BABUINO := JIRAFA ; TEXTO := " Hola mundo !" ; FIN . El lenguaje se puede ampliar fácilmente con flujos de control , expresiones aritméticas e instrucciones de entrada/salida. De esta forma se desarrollaría un lenguaje de programación pequeño y utilizable.
Cualquier gramática definida en EBNF también puede representarse en BNF, aunque las representaciones en esta última son generalmente más largas. Por ejemplo, las opciones y repeticiones no pueden expresarse directamente en BNF y requieren el uso de una regla intermedia o una producción alternativa definida como nada o la producción opcional para opción, o bien la producción repetida de sí misma, recursivamente, para repetición. Las mismas construcciones aún pueden usarse en EBNF.
La BNF utiliza los símbolos ( <, >, |, ::=) para sí misma, pero no incluye comillas alrededor de las cadenas terminales. Esto evita que estos caracteres se utilicen en los idiomas y requiere un símbolo especial para la cadena vacía. En EBNF, las terminales se encierran estrictamente entre comillas ( "... "o '... '). Los corchetes angulares (" <... >") para los no terminales se pueden omitir.
La sintaxis BNF solo puede representar una regla en una línea, mientras que en EBNF un carácter de terminación, el carácter de punto y coma “ ;”, marca el final de una regla.
Además, EBNF incluye mecanismos de mejora, definición del número de repeticiones, exclusión de alternativas, comentarios, etc.
* símbolo-de-repetición - símbolo-de-excepción , símbolo-de-concatenación | símbolo-separador-de-definición = símbolo-definitorio ; símbolo-terminador . símbolo-terminador (* símbolo-de-comentario-inicio símbolo-de-comentario-fin *) ' símbolo-de-comilla-primera símbolo-de-comilla-primera ' ( símbolo-de-grupo-inicio símbolo-de-grupo-fin ) [ símbolo-de-opción-inicio símbolo-de-opción-fin ] { símbolo -de-repetición-inicio símbolo-de-repetición-fin } ? símbolo-de-secuencia-especial símbolo-de-secuencia-especial ? " símbolo-de-comilla-segunda símbolo-de-comilla-segunda "'); la fuente utilizada en la norma ISO/IEC 14977:1996(E) lo reproduce de forma muy similar al apóstrofo, Unicode U+00B4 ( ´), por lo que a veces se produce confusión. Sin embargo, la norma ISO Extended BNF invoca la norma ISO/IEC 646:1991, "Conjunto de caracteres codificados ISO de 7 bits para el intercambio de información", como referencia normativa y no hace mención de ningún otro conjunto de caracteres, por lo que formalmente no hay confusión con los caracteres Unicode fuera del rango ASCII de 7 bits.A modo de ejemplo, las siguientes reglas de sintaxis ilustran las facilidades para expresar repetición:
aa = "A" ; bb = 3 * aa , "B" ; cc = 3 * [ aa ], "C" ; dd = { aa }, "D" ; ee = aa , { aa }, "E" ; ff = 3 * aa , 3 * [ aa ], "F" ; gg = { 3 * aa }, "G" ; hh = ( aa | bb | cc ), "H" ;Las cadenas terminales definidas por estas reglas son las siguientes:
aa: Unbb:aaaaacc: C A A A A A A A Add: D AD AAD AAAD AAAAD etc.ee: AE AAE AAAE AAAAE AAAAAE etc.ff: AAAAF AAAAF AAAAAF AAAAAAFgg: G AAAG AAAAAAG etc.hh: AH AAABH CH ACH AACH AAACH
Según la norma ISO 14977, el EBNF está pensado para ser extensible y se mencionan dos funciones. La primera forma parte de la gramática EBNF, la secuencia especial, que es un texto arbitrario encerrado entre signos de interrogación. La interpretación del texto dentro de una secuencia especial queda fuera del alcance de la norma EBNF. Por ejemplo, el carácter de espacio podría definirse mediante la siguiente regla:
espacio = ? carácter ASCII 32 ? ;La segunda función de extensión es aprovechar el hecho de que los paréntesis en EBNF no se pueden colocar junto a los identificadores (deben estar concatenados con ellos). Lo siguiente es EBNF válido:
algo = foo , ( bar );Lo siguiente no es un EBNF válido:
algo = foo ( bar );Por lo tanto, una extensión de EBNF podría utilizar esa notación. Por ejemplo, en una gramática de Lisp , la función application podría definirse mediante la siguiente regla:
función aplicación = lista ( símbolo , { expresión } );