En informática , la forma extendida de Backus-Naur ( EBNF ) es una familia de notaciones de metasintaxis , cualquiera de las cuales puede usarse para expresar una gramática libre de contexto . EBNF se utiliza para hacer una descripción formal de un lenguaje formal como un lenguaje de programación de computadoras . Son extensiones de la notación de metasintaxis básica de la forma Backus-Naur (BNF).
El primer EBNF fue desarrollado por Niklaus Wirth , incorporando 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ó una norma EBNF , ISO/IEC 14977, en 1996. [1] [2] Sin embargo, según Zaytsev, esta norma "sólo acabó añadiendo otros tres dialectos al caos" y, tras señalar su falta de éxito, señala también que ISO EBNF ni siquiera se utiliza en todas las normas ISO. [3] Wheeler se opone al uso del estándar ISO cuando se utiliza un EBNF y recomienda considerar notaciones EBNF alternativas como la del lenguaje de marcado extensible (XML) 1.0 (quinta edición) del W3C. [4]
Este artículo utiliza EBNF según lo especificado por ISO para ejemplos que se aplican a todos los EBNF. Otras variantes de EBNF utilizan convenciones sintácticas algo diferentes.
EBNF es un código que expresa la sintaxis de un lenguaje formal. [5] Una 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. Ejemplos de símbolos de terminal incluyen caracteres alfanuméricos , signos de puntuación y espacios en blanco .
La EBNF define reglas de producción donde 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 están entre comillas seguidas de un punto y coma como carácter final. Por lo tanto, un dígito es un 0 o un dígito excluyendo el cero que puede ser 1 , 2 o 3 y así sucesivamente hasta 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 está entre llaves se puede repetir con una frecuencia arbitraria, incluso nada.
Una opción se puede representar mediante corchetes [...]. Es decir, todo lo que está entre 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 ir 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), excluir alguna parte de una producción e insertar comentarios en una gramática EBNF.
Lo siguiente representa una propuesta de estándar ISO/IEC 14977, por RS Scowen, página 7, tablas 1 y 2.
Incluso EBNF se puede describir utilizando EBNF. Considere la siguiente gramática (usando 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" | "yo" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "un" | "b" | "c" | "d" | "e" | "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 = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" | "-" | "+" | "*" | "?" | "\n" | "\t" | "\r" | "\f" | "\b" ;carácter = letra | dígito | símbolo | "_" | " " ; identificador = letra , { letra | dígito | "_" } ;S = { " " | "\n" | "\t" | "\r" | "\f" | "\b" } ;terminal = "'" , carácter - "'" , { carácter - "'" } , "'" | '"' , carácter - '"' , { carácter - '"' } , '"' ;terminador = ";" | "." ;término = "(" , S , rhs , S , ")" | "[" , S , derecha , S , "]" | "{" , S , rhs , S , "}" | terminales | identificador ;factor = término , S , "?" | término , S , "*" | término , S , "+" | término , S , "-" , S , término | términos ; 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 , 'COMIENZO' , espacio en blanco , { asignación , ";" , espacio en blanco }, 'FIN.' ; 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 = ? todo visible caracteres ? ;Por ejemplo, un programa sintácticamente correcto podría ser:
PROGRAMA DEMO1 COMIENZA 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. Luego se desarrollaría un lenguaje de programación pequeño y utilizable.
Cualquier gramática definida en EBNF también se puede representar en BNF, aunque las representaciones en este último son generalmente más largas. Por ejemplo, las opciones y las repeticiones no pueden expresarse directamente en BNF y requieren el uso de una regla intermedia o producción alternativa definida como nada o la producción opcional para la opción, o bien la producción repetida de sí misma, recursivamente, para la repetición. Las mismas construcciones todavía se pueden utilizar en EBNF.
El BNF utiliza los símbolos ( ,,, <) para sí mismo, 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, los terminales están estrictamente entre comillas ( ... o ... ). Se pueden omitir los corchetes angulares (" ... ") para no terminales .>|::=""''<>
La sintaxis de BNF solo puede representar una regla en una línea, mientras que en EBNF es un carácter de terminación, el punto y coma " ;" marca el final de una regla.
Además, EBNF incluye mecanismos de mejora, definiendo el número de repeticiones, excluyendo alternativas, comentarios, etc.
* símbolo-repetición - símbolo-excepto , símbolo-concatenado | definición-separador-símbolo = definición-símbolo ; símbolo-terminador . símbolo-terminador (* símbolo-comentario-inicial símbolo-comentario-final *) ' primer-símbolo-comilla-símbolo-primera-comilla ' ( símbolo-inicio-grupo-símbolo-final-grupo ) [ símbolo-opción-inicial-símbolo-opción-final ] { símbolo-repetición-inicio símbolo-repetición-final } ? símbolo-de-secuencia-especial símbolo-de-secuencia-especial ? " segundo símbolo de comillas segundo símbolo de comillas "'); la fuente utilizada en ISO/IEC 14977:1996(E) la hace muy parecida a la aguda Unicode U+00B4 ( ´), por lo que a veces surge confusión. Sin embargo, el estándar ISO Extended BNF invoca ISO/IEC 646:1991, "Juego de caracteres codificados ISO de 7 bits para intercambio de información", como referencia normativa y no menciona ningún otro juego de caracteres, por lo que formalmente no hay confusión con Caracteres Unicode fuera del rango ASCII de 7 bits.Como ejemplos, 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 de terminales definidas por estas reglas son las siguientes:
aa: unbb: AAABcc: C CA AAC AAACdd: D AD AAD AAAD AAAAD etc.ee: AE AAE AAAE AAAAE AAAAAE etc.ff: AAAF AAAAF AAAAAF AAAAAAFgg: G AAAG AAAAAAG etc.hh: AH AAABH CH ACH AACH AAACH
Según la norma ISO 14977, EBNF debe ser extensible y se mencionan dos funciones. La primera es 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 está más allá del alcance del estándar EBNF. Por ejemplo, el carácter de espacio podría definirse mediante la siguiente regla:
espacio = ? ¿Carácter ASCII 32? ;La segunda posibilidad de extensión es utilizar 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 , ( barra );Lo siguiente no es EBNF válido:
algo = foo ( barra );Por lo tanto, una extensión de EBNF podría utilizar esa notación. Por ejemplo, en una gramática Lisp , la aplicación de la función podría definirse mediante la siguiente regla:
aplicación de función = lista ( símbolo , { expresión } );