En informática , la forma extendida 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 diferente) de la notación de sintaxis de Wirth . Sin embargo, se utilizan muchas variantes de EBNF. La Organización Internacional de Normalización adoptó un estándar EBNF ( ISO / IEC 14977 ) en 1996. Sin embargo, según Zaytsev, este estándar "solo terminó agregando otros tres dialectos al caos" y, después de señalar su falta de éxito, también señala que el ISO EBNF ni siquiera se utiliza en todas las normas ISO. Wheeler se opone al uso del estándar ISO cuando se usa un EBNF y recomienda considerar notaciones EBNF alternativas como la del W3C Extensible Markup Language (XML) 1.0 (Quinta edición).
Este artículo utiliza EBNF como lo especifica la ISO para ejemplos que se aplican a todos los EBNF. Otras variantes de EBNF utilizan convenciones sintácticas algo diferentes.
Lo esencial
EBNF es un código que expresa la sintaxis de un lenguaje formal. [1] Un EBNF consta de símbolos terminales y reglas de producción no terminales que son las restricciones que gobiernan cómo se pueden combinar los símbolos terminales en una secuencia legal. Los ejemplos de símbolos de terminal incluyen caracteres alfanuméricos , signos de puntuación y espacios en blanco .
El EBNF define reglas de producción donde las secuencias de símbolos se asignan respectivamente a un no terminal :
dígito excluido cero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; dígito = "0" | dígito excluyendo el cero ;
Esta regla de producción define el dígito no terminal que está 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 o 2 o 3 y así sucesivamente 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 establece entre las llaves se puede repetir arbitrariamente a menudo, incluso no en absoluto.
Una opción se puede representar mediante corchetes [...]. Es decir, todo lo que se establece 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 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), excluir alguna parte de una producción e insertar comentarios en una gramática EBNF.
Tabla de simbolos
Lo siguiente representa una norma ISO / IEC 14977 propuesta, por RS Scowen, página 7, tabla 1.
Uso | Notación |
---|---|
definición | = |
concatenación | , |
terminación | ; |
alternancia | | |
Opcional | [...] |
repetición | {...} |
agrupamiento | (...) |
cadena terminal | "..." |
cadena terminal | '...' |
comentario | (* ... *) |
secuencia especial | ? ...? |
excepción | - |
Ejemplos de
Diagrama de sintaxis
Incluso EBNF se puede describir utilizando EBNF. Considere la gramática bosquejada a continuación:
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" | "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" ; dígito = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; símbolo = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | " = " | " | " | ". " | ", " | "; " ; carácter = letra | dígito | símbolo | " _ " ; identificador = letra , { letra | dígito | "_" } ; terminal = "'" , carácter , { carácter } , "'" | '"' , carácter , { carácter } , '"' ; lhs = identificador ; rhs = identificador | terminal | "[" , dcha. , "]" | "{" , rhs , "}" | "(" , dcha. , ")" | rhs , "|" , dcha | rhs , "," , rhs ;rule = lhs , "=" , rhs , ";" ; gramática = { regla } ;
Un lenguaje de programación similar a Pascal que permite solo asignaciones se puede definir en EBNF de la siguiente manera:
(* una sintaxis de programa simple en EBNF - Wikipedia *) program = 'PROGRAM' , white_space , identifier , white_space , 'BEGIN' , white_space , { asignación , ";" , espacio_blanco }, 'FIN'. ; identifier = alphabetic_character , { alphabetic_character | dígito } ; número = [ "-" ], dígito , { dígito } ; cadena = '"' , { todos_caracteres - '"' }, '"' ; asignación = identificador , ": = " , ( número | identificador | cadena ) ; alphabetic_character = " 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" ; white_space = ?? white_space caracteres ; all_characters = ?? todos los caracteres visibles ;
Por ejemplo, un programa sintácticamente correcto podría ser:
PROGRAMA DEMO1 COMENZAR A : = 3 ; B : = 45 ; H : = - 100023 ; C : = A ; D123 : = B34A ; BABOON : = JIRAFA ; TEXT : = " ¡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.
Ventajas sobre BNF
Cualquier gramática definida en EBNF también se puede representar en BNF, aunque las representaciones en este último son generalmente más extensas. Por ejemplo, las opciones y 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 opción, o la producción repetida de sí misma, recursivamente, para repetición. Las mismas construcciones todavía se pueden usar en EBNF.
El BNF utiliza los símbolos ( <
, >
, |
, ::=
) por sí mismo, pero no incluye las comillas alrededor de 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 '
... '
). Los corchetes angulares (" <
… >
") para 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.
Convenciones
- Se utilizan las siguientes convenciones:
- Cada meta-identificador de Extended BNF se escribe como una o más palabras unidas por guiones .
- Un meta-identificador que termina con -symbol es el nombre de un símbolo de terminal de Extended BNF.
- El carácter normal que representa a cada operador de BNF extendido y su precedencia implícita es (la precedencia más alta en la parte superior):
* Repetición símbolo - excepto-símbolo , concatenar-símbolo | símbolo-separador- definición = símbolo-definitorio ; símbolo-terminador . símbolo-terminador
- Los siguientes pares de corchetes anulan la precedencia normal: El primer símbolo de comillas es el apóstrofo definido por ISO / IEC 646: 1991, es decir, Unicode U + 0027 (
(* símbolo-comentario-inicio símbolo-comentario-final *) ' primer símbolo-comilla-primer-símbolo-cita ' ( símbolo -grupo-inicio-símbolo-grupo-final ) [ símbolo -opción-inicio-símbolo-opción-final ] { inicio-repetición-símbolo final-repetición-símbolo } ? símbolo-secuencia-especial símbolo-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, la norma ISO Extended BNF invoca ISO / IEC 646: 1991, "Conjunto de caracteres codificados ISO de 7 bits para el intercambio de información", como referencia normativa y no menciona ningún otro conjunto 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 la 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" ;
Las cadenas de terminales definidas por estas reglas son las siguientes:
aa: Abb: AAABcc: C AC AAC AAACdd: D AD AAD AAAD AAAAD etc.ee: AE AAE AAAE AAAAE AAAAAE etc.ff: AAAF AAAAF AAAAAF AAAAAAFgg: G AAAG AAAAAAG etc.
Extensibilidad
Según la norma ISO 14977, EBNF está destinado a ser extensible y se mencionan dos instalaciones. La primera es parte de la gramática EBNF, la secuencia especial, que es un texto arbitrario encerrado con 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 facilidad para la 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). El 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 usar esa notación. Por ejemplo, en una gramática Lisp , la aplicación de funciones podría definirse mediante la siguiente regla:
función aplicación = lista ( símbolo , { expresión } );
Trabajo relacionado
- El W3C utilizó un EBNF diferente para especificar la sintaxis XML .
- La British Standards Institution publicó un estándar para un EBNF: BS 6154 en 1981.
- El IETF utiliza BNF aumentado (ABNF), especificado en RFC 5234.
Ver también
- Meta-II : una de las primeras herramientas de escritura y notación del compilador
- Reglas de estructura de frases : el equivalente directo de EBNF en lenguajes naturales.
- Expresión regular
- Marco de Spirit Parser
Referencias
- ^ Pattis, Richard E. "EBNF: una notación para describir la sintaxis" (PDF) . ICS.UCI.edu . Universidad de California, Irvine . pag. 1 . Consultado el 26 de febrero de 2021 .
- Roger S. Scowen: BNF extendido: un estándar básico genérico. Simposio de Normas de Ingeniería de Software 1993.
- David A. Wheeler, No utilice el formulario extendido Backus-Naur (EBNF) de ISO / IEC 14977 , 2019.
- Vadim Zaytsev, " BNF ESTABA AQUÍ: ¿Qué hemos hecho acerca de la diversidad innecesaria de notación para las definiciones sintácticas? ", Actas del 27º Simposio Anual de Computación Aplicada de la ACM (SAC '12), páginas 1910-1915, Trento, Italia - marzo 26-30 de 2012.
- El estándar internacional ( ISO 14977 ), que es uno de los muchos formatos para EBNF, ahora está disponible gratuitamente como archivo PDF comprimido en Zip .
- Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.
enlaces externos
- ISO / IEC 14977: 1996 (E)
- RFC 4234 - BNF aumentado para especificaciones de sintaxis: ABNF (obsoleto por RFC 5234)
- Variantes BNF / EBNF : una tabla de Pete Jinks que compara varias sintaxis
- Analizador y renderizador en PHP5
- Representación del diagrama de sintaxis de SRFB por función de base + generación de EBNF (javascript)