Backus-Naur Form

O Backus-Naur form (BNF) (tamén coñecida como Backus-Naur formalism, Backus normal form ou Panini-Backus Form) é unha metasintaxe usada para expresar gramáticas libres de contexto: é dicir, un xeito formal de describir linguaxes formais.

O BNF utilízase cumpridamente como notación para as gramáticas das linguaxes de programación da computadora, dos sistemas de comando e dos protocolos de comunicación, así como unha notación para representar partes das gramáticas da lingua natural (por exemplo, o metro na poesía de Venpa). A maioría dos libros de textos para a teoría e/ou a semántica da linguaxe de programación documentan a linguaxe de programación en BNF. Algunhas variantes, tales como a augmented Backus-Naur form (ABNF), teñen a súa propia documentación.

 Historia 
John Backus creou a notación co propósito de expresar a gramática de ALGOL. No primeiro Congreso de Computación Mundial (World Computer Congress), Backus presentou o artigo "The syntax and semantics of the proposed international algebraic language of the Zúric ACM-GAMM Conference", o cal contén a descrición formal da linguaxe que sería coñecido posteriormente como ALGOL 58.
Peter Naur identificou a notación de Backus como a Forma Normal de Backus (Backus Normal Form), e simplificouna para usar un conxunto de símbolos menor e, a suxestión de Donald Knuth, o seu apelido foi engadido en recoñecemento á súa contribución, substituíndo a palabra "Normal" por Naur, resultado en Forma de Backus Naur (Backus Naur Form) . A Backus-Naur Form ou as gramáticas de BNF ten semellanzas significativas ás regras da gramática de , e ás veces tamén se coñece como Panini-Backus Form. O BNF foi creado como parte de crear as regras para ALGOL 60.

 Introdución 
Unha especificación de BNF é un sistema de regras da derivación, escrito como

<simbolo> ::= <expresión con símbolos>

onde <símbolo> é un nonterminal, e a expresión consiste en secuencias de símbolos e/ou secuencias separadas pola barra vertical, '|', indicando unha opción, o conxunto é unha posible substitución para o símbolo á esquerda. Os símbolos que nunca aparecen nun lado esquerdo son terminalé.

 Exemplo 
Como exemplo, considere este BNF para unha dirección postal dos EEUU

<dirección postal> ::= <nomee> <dirección> <código postal>
<persoal> ::= <primeiro nome> | <inicial> "."
<nome> ::= <persoal> <apelido> [<trato>] <EOL>
             | <persoal> <nome>
<dirección> ::= [<dpto>] <número da casa> <nomee da rúa> <EOL>
<apartado postal> ::= <cidade> "," <código postal> <código postal> <EOL>

Isto tradúcese a galego como:
 Unha dirección postal consiste dun nome, seguido por unha dirección, seguida por un código postal.
 Unha parte "persoal" consiste nun nome ou unha inicial seguido(a) por un punto.
 Un nome consiste de: unha parte persoal seguida por un apelido seguido opcionalmente por unha xerarquía ou o trato que lla dá á persoa (Jr., Sr., ou número dinástico) e un salto de liña (end-of-line), ou ben unha parte persoal seguida por un nome (esta regra ilustra o uso da repetición en BNFs, cubrindo o caso da xente que utiliza múltiples nomes e os nomes medios e/ou as iniciais).
 Unha dirección consiste dunha especificación opcional do departamento, seguido dun número de casa, seguido polo nome da rúa, seguido por un salto de liña (end-of-line).
 Un apartado posta consiste dunha cidade, seguida por unha coma, seguida por un código do estado (recorden que é un exemplo que ocorre en EU), seguido por un código postal e este seguido por un salto de liña (end-of-line).

Observe que moitas cousas (tales como o formato dunha parte persoal, dunha especificación do apartamento, ou código postal) están deixadas sen especificar aquí. Se é necesario, poden ser descritas usando regras adicionais de BNF, ou deixadas como abstracción se é inaplicable para o propósito actual.

 Outros exemplos 
Bastante interesante, a sintaxe de BNF pódese representar en BNF como segue:

 <syntax> ::= <rule> [<syntax>]
 <rule> ::= <whitespace> "<" <rule-name> ">" <whitespace> "::="  
    <expression> <whitespace> <line-end>
 <expression> ::= <whitespace> <or-expression>
 <or-expression> ::= <whitespace> <list-expression> [ "|"
    <or-expression> ]
 <list-expression> ::= <whitespace> ("<" <rule-name> ">"
    | <QUOTE> <text> <QUOTE> | "(" <expression> ")" | "[" <expression> 
    "]") [<list-expression>]
 <whitespace> ::= [" " <whitespace>]
 <line-end> ::= [<whitespace>] <EOL> [<line-end>]

Isto asume que non hai Whitespace necesario para a interpretación apropiada da regra. O <QUOTE> presúmese para ser o carácter ", e o <EOL> para ser o fin de liña apropiado especificado (en ASCII, retorno de carro e/ou liña nova, dependendo do sistema operativo). O <rule-name> e o <text> deben ser substituídos con nome/etiqueta ou o texto literal dunha regra declarada, respectivamente.

 Variantes 
Hai moitas variantes e extensións de BNF, posiblemente contendo algúns ou todos os comodines de expresións regulares como "*" un ou "+". O Estendede Backus-Naur form (EBNF) é unha variante común. De feito o exemplo anterior non é a forma pura inventada para o informe do ALGOL 60. A notación dos corchetes "[ ]" foi introducida algúns anos máis tarde na definición de PL/I da IBM pero agora recoñécese universal. A ABNF é outra extensión usada comunmente para describir protocolos do IETF.

As expresións gramaticales de analizadores sintácticos construídas en BNF e as notaciones de expresión regular para formar unha clase alternativa da gramática formal, que é esencialmente analítica máis que generativa en carácter.

 Notas 

 Véxase tamén 
 Outros artigos 
 GOLD BNF parser
 Yacc Parser Generator
 GNU bison GNU Version of Yacc

 Ligazóns externas 
 RFC 4234 Augmented BNF for Syntax Specifications: ABNF 
 Grammatica Parser 
 Spirit Parser 

Categoría:Programación