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 Pāṇini, 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.

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 (en inglés)
• Grammatica Parser (en inglés)
• Spirit Parser (en inglés)