Formulario extendido Backus – Naur - Extended Backus–Naur form

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. 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 :

digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit                = "0" | digit excluding zero ;

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:

twelve                          = "1", "2" ;
two hundred one                 = "2", "0", "1" ;
three hundred twelve            = "3", twelve ;
twelve thousand two hundred one = twelve, two hundred one ;

Las expresiones que pueden omitirse o repetirse se pueden representar mediante llaves {...}:

natural number = digit excluding zero, { digit } ;

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:

integer = "0" | [ "-" ], natural number ;

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.

Ejemplos de

Diagrama de sintaxis

Un posible diagrama de sintaxis EBNF

Incluso EBNF se puede describir utilizando EBNF. Considere la gramática bosquejada a continuación:

letter = "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" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | "_" ;
 
identifier = letter , { letter | digit | "_" } ;
terminal = "'" , character , { character } , "'" 
         | '"' , character , { character } , '"' ;
 
lhs = identifier ;
rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

Un lenguaje de programación similar a Pascal que permite solo asignaciones se puede definir en EBNF de la siguiente manera:

 (* a simple program syntax in EBNF − Wikipedia *)
 program = 'PROGRAM', white_space, identifier, white_space, 
            'BEGIN', white_space, 
            { assignment, ";", white_space }, 
            'END.' ;
 identifier = alphabetic_character, { alphabetic_character | digit } ;
 number = [ "-" ], digit, { digit } ;
 string = '"' , { all_characters - '"' }, '"' ;
 assignment = identifier , ":=" , ( number | identifier | string ) ;
 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" ;
 digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
 white_space = ? white_space characters ? ;
 all_characters = ? all visible characters ? ;

Por ejemplo, un programa sintácticamente correcto podría ser:

 PROGRAM DEMO1
 BEGIN
   A:=3;
   B:=45;
   H:=-100023;
   C:=A;
   D123:=B34A;
   BABOON:=GIRAFFE;
   TEXT:="Hello world!";
 END.

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

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: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD etc.
ee: AE AAE AAAE AAAAE AAAAAE etc.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: 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:

 space = ? ASCII character 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:

 something = foo, ( bar );

Lo siguiente no es EBNF válido:

 something = foo ( bar );

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:

 function application = list( symbol, { expression } );

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

enlaces externos

• ISO / IEC 14977: 1996 (E)
• 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)