Notación BNF en el diseño del compilador

BNF significa notación Backus Naur Form . Es un método formal para describir la sintaxis del lenguaje de programación que se entiende como Backus Naur Formas introducido por John Bakus y Peter Naur en 1960. BNF y CFG (Gramática libre de contexto) eran casi idénticos. BNF puede ser un metalenguaje (un idioma que no puede describir otro idioma) para idiomas primarios. 

Para el consumo humano, una notación adecuada para codificar gramáticas destinadas y denominadas Backus Naur Form (BNF). Los diferentes idiomas tienen diferentes descripciones y reglas, pero la estructura general de BNF se proporciona a continuación: 

name ::= expansion

El símbolo ::= significa «puede expandirse en» y «puede ser reemplazado por». En algunos textos, una reputación también se denomina símbolo no terminal. 

• Cada nombre en forma Backus-Naur está entre corchetes angulares, < >, ya sea que aparezca en el lado izquierdo o derecho de la regla. 

   

• Una expansión es una expresión que contiene símbolos terminales y símbolos no terminales, unidos por secuenciación y selección. 

   

• Un símbolo de terminal puede ser un literal como («+» o «función») o una categoría de literales (como un número entero). 

   

• Simplemente yuxtaponer expresiones indica secuenciación. 

   

• Una barra vertical | indica elección. 

  Ejemplos:  

<expr> ::= <term> "+" <expr>
        |  <term>

<term> ::= <factor> "*" <term>
        |  <factor>

<factor> ::= "(" <expr> ")"
          |  <const>

<const> ::= integer

Reglas para hacer BNF: 
Naturalmente, definiremos una gramática para las reglas en BNF: 
 

rule → name ::= expansion
name → < identifier >
expansion → expansion expansion
expansion → expansion | expansion
expansion → name
expansion → terminal

• Podríamos definir identificadores usando la expresión regular [-A-Za-z_0-9]+. 

   

• Un terminal podría ser un literal entrecomillado (como “+”, “interruptor” o “<<=”) o el nombre de una categoría de literales (como un entero). 

   

• El nombre de una categoría de literales generalmente se define por otros medios, como una expresión diaria o quizás prosa. 

  Es común buscar operaciones similares a expresiones regulares dentro de las gramáticas. como ejemplo, la especificación léxica de Python los usa. En estas gramáticas: 
   

postfix * means "repeated 0 or more times"
postfix + means "repeated 1 or more times"
postfix ? means "0 or 1 times"

La definición de literales de punto flotante en Python puede ser un ejemplo de mezclar varias notaciones: 

floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+

No usa corchetes angulares alrededor de los nombres (como muchas notaciones EBNF y ABNF), pero sí usa ::= (como BNF). Combina operaciones regulares como + para repetición no vacía con convenciones EBNF como [ ] para opción. La gramática de todo el lenguaje Python usa una notación bastante diferente (pero aún regular).