jueves, 18 de noviembre de 2010

Formato Backus-Naur (Lab)

 El formato Backus-Naur (BNF) es un sistema notacional para especificar tipos de datos o categorías sintácticas, también especifica la sintaxis de los lenguajes de programacion mediante reglas de producción o de re-escritura.






Una manera alternativa para establecer la producción de una gramática es usar esta forma, los símbolos no terminales suele comenzar con "<" y terminar con ">". La producción S->T se escribe S::=T


Las producciones de la forma
S::=T1, S::=T2, ..., S ::=Tn

se pueden combinar como
S::=T1|T2|...|Tn.

La barra "|" se lee como "o".


En esta entrada les pondré un ejemplo que encontré en el libro de matemáticas discretas en la pagina 519


una gramática para enteros.


Un entero se define como una cadena consistente en un signo opcional(+ o -) seguido de una cadena de dígito (0 al 9). La siguiente gramática genera todos los enteros.


< dígito > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< entero > ::= < enero con signo > | < enero sin signo >
< enero con signo > ::= + < enero sin signo > |- < enero sin signo >
< entero sin signo > ::= < dígito > | < digito > < enero sin signo >


El símbolo de inicio es < entero >.


Ejemplo la derivación del enero -901 es


< enero > -> < dígito con signo >
                       -> - < entero sin signo >
                       -> - < dígito > < entero sin signo >
                       -> - < dígito > < digito > < entero sin signo >
                       -> - < dígito > < digito > < digito >
                       -> - 9 < dígito > < digito >
                       -> - 90 < dígito >
                       -> - 901




Desglosando la gramática de estructura de frases, este lenguaje consiste en:



  1. El conjunto N = {< dígito > < entero > <enero con signo> <entero sin signo>} de símbolos no terminales
  2. El conjunto T = {0 1 2 3 4 5 6 7 8 9 + -}
  3. Las producciones
  4. < dígito > -> 0 .... < dígito > -> 9
    < entero > -> < entero con signo >
    < enero > -> < entero sin signo >
    < entero con signo > -> + < entero sin signo>
    < entero con signo > -> - < entero sin signo>
    < entero sin signo > -> < digito >
    < entero sin signo > -> < digito > < entero sin signo >
  5. El símbolo de inicio < entero >



Este ejemplo me demuestra claramente como funciona la forma regular de backus, encontré que es típico que los lenguajes de programacion como fortran, pascal y C++ utiliza esta gramática. podemos ver como se especifica en BNF una constante entera en un lenguaje de programación.


Espero que mi explicación les sirva, si tienen algún comentario acerca de esta entrada, espero me digan ya que estoy abierto a cualquier error.

3 comentarios: