Formalismo de Backus-Naur

Origem: Wikipédia, a enciclopédia livre.

A forma de Backus-Naur (também conhecido como BNF, o formalismo de Backus-Naur, forma normal Backus, ou forma de Panini-Backus) é uma meta-sintaxe usada para expressar gramáticas livres de contexto: isto é, um modo formal de descrever linguagens formais.

A BNF é amplamente usada como uma notação para as gramáticas de linguagens de programação, conjuntos de instruções e protocolos de comunicação, e também como notação para representar partes de gramáticas de linguagens naturais. A maioria dos livros-texto para teoria de linguagem de programação e/ou semântica documenta a linguagem de programação em BNF. Algumas variantes, como a Forma Aumentada de Backus-Naur (FABN), têm sua própria documentação.

[editar] Visão Geral

BNF foi originalmente nomeada em homenagem a John Backus e também (por sugestão de Donald Knuth) a Peter Naur. Eles foram dois pioneiros da ciência da computação, especialmente na arte de design de compiladores. A forma de Backus-Naur ou gramáticas BNF é bastante similar às regras da gramática de Panini, e é chamada às vezes de forma de Panini-Backus. A BNF foi proposta como parte da criação das regra para o Algol 60.

[editar] Introdução

Uma especificação BNF é um conjunto de regras de derivação, escritas como

<símbolo> ::= <expressão com símbolos>

onde <símbolo> é um não-terminal, e a expressão consiste em sequências de símbolos e/ou sequências separadas pela barra vertical, '|', indicando uma escolha. Esta notação indica as possibilidades de substituição para símbolo da esquerda. Símbolos que nunca aparecem no lado esquerdo são dito terminais.

[editar] Exemplo

No exemplo, considere essa BNF possível para um endereço postal do Brasil:

 <endereço-postal> ::= <parte-do-nome> <endereço-da-rua> <parte-do-CEP>
   <parte-do-nome> ::= <parte-pessoal> <último-nome> <parte-opc-jr> <FDL> 
                  | <parte-pessoal> <parte-do-nome>
   <parte-pessoal> ::= <inicial> "." | <primeiro-nome>
 <endereço-da-rua> ::= <nome-da-rua> < número-do-ímovel> <num-apto-opc> <FDL>
    <parte-do-CEP> ::= <CEP> <nome-da-cidade> "-" <código-do-estado> <FDL>

Isto se traduz para o português como:

Um endereço postal consiste da parte-do-nome, seguido pela parte do endereço-da-rua, seguido pela parte do CEP.
A parte do nome consiste em: ou a parte-pessoal seguido pelo último nome seguido por um opcional "parte-jr" (Jr., Sr.) e o end-of-line (fim da linha), ou a parte pessoal seguido pela parte do nome (essa regra mostra o uso da recursão em FNBs, que inclui o caso das pessoas que usam o primeiro nome e o nome do meio e/ou as iniciais).
A parte-pessoal consiste de ou uma inicial seguida por um ponto ou o primeiro nome.
Um endereço da rua consiste do nome da rua, seguido pelo número do imóvel, seguido do especificador de apartamento opcional, seguido por um fim-da-linha.
A parte-do-CEP consiste do CEP, seguido pelo nome-da-cidade, por um hífen, pelo código do estado, e por um fim-da-linha.

Note que muitas coisas (tais como o formato de um primeiro nome, especificador de apartamento, ou do CEP) não são especificados aqui. Se necessário, elas podem se descritas usando regras BNF adicionais.

[editar] Mais exemplos

A sintaxe da FNB pode ser representado com uma FNB como no que se segue:

<sintaxe> ::= <rule> | <rule> <syntax>
<regra> ::= <espaço em branco-opc> "<" <nome da regra> ">" espaço em branco-opc> "::=" 
           <espaço em branco-opc> <expressão> <fim da linha>
<espaço em branco-opc> ::= " " <espaço em branco-opc> | ""  
<expressão> ::= <lista> | <lista> "|" <expressão>
<fim da linha> ::= <espaço em branco-opc> <FDL> | <fim da linha> <fim da linha>
<lista> ::= <termo> | <termo> <espaço em branco-opc> <lista>
<termo> ::= <literal> | "<" <nome da regra> ">"
<literal> ::= '"' <texto> '"' | "'" <texto> "'"

Isso assume que o espaço em branco não é necessário para a devida interpretação da regra. <FDL> é o especificador fim da linha apropriado. <nome da regra> e <texto> são substituídos com uma regra nome/rótulo ou um texto literal, respectivamente.