Formalismo de Backus-Naur

 Nota: "FNB" redireciona para este artigo. Para o movimento político, veja Frente Negra Brasileira.

O Formalismo de Backus-Naur (BNF, do inglês Backus-Naur Form ou Backus Normal Form) é uma metassintaxe usada para expressar gramáticas livres de contexto, isto é, um modo formal de descrever linguagens formais.

O 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.

Há também variantes como a forma aumentada de Backus-Naur (FABN) baseada na BNF, mas que consiste em uma sintaxe e regras de derivações próprias. O princípio norteador desta metalinguagem é descrever um sistema formal de uma linguagem que é um protocolo (especificação bidirecional).

Formalismo de Backus-Naur

Visão geral

A notação BNF (Backus Naur Form ou Backus Normal Form) foi originalmente criada por John Backus e Peter Naur, no final dos anos 1950, para descrever a linguagem ALGOL (como parte da criação das regras para o ALGOL 60). Desde então a sua utilização generalizou-se para a especificação de linguagens de programação.

Originalmente foi nomeada em homenagem a Backus e, por sugestão de Donald Knuth, também a Peter Naur, 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 sânscrita de Pānini (cerca do século V a.C.), e é chamada às vezes de forma de Panini-Backus.

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 ditos terminais.

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-imóvel> <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 tratamento (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.

Mais exemplos

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

<sintaxe> ::= <regra> | <regra> <sintaxe>
<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> "'" <!-- Atualmente, a FNB original não usa citações -->

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. Outro exemplo de BNF:

Transformar a expressa 32 + 16 / 45 * 3 em Linguagem BNF

<expressao> ::= <valor> <operador><expressao>
<numero> <operador><expressao>
<sem sinal><sem sinal> <operador><expressao>
<digito><digito><operador><expressao>
32+<valor><operador><expressao>
32+<numero><operador><expressao>
32+<sem sinal><sem sinal><operador><expressao>
32+<digito><digito><operador><expressao>
32+16/<expressao>
32+16/ <valor><operador><expressao>
32+16/ <numero><operador><express>
32+16/ <sem sinal><sem sinal><op><ex>
32+16/<digito><digito><op><exp>
32+16/45*<expressao>
32+16/45*<valor>
32+16/45*<numero>
32+16/45*<sem sinal>
32+16/45*<digito>
32+16/45*3

Forma Aumentada de Backus-Naur

Introdução

Uma especificação da FABN é um conjunto de regras de derivação escrito na forma:

regra = definição ; comentário CR LF

onde regra é um não-terminal com caixa sensível (letras em maiúscula ou minúsculas), a definição consiste numa seqüência de símbolos que definem a regra, o comentário serve para documentação e terminando com o caractere de carriage return (retornar para a posição mais à esquerda) e um line feed (indica quebra de linha).

Nomes de regras não são caixa-sensíveis, logo <regranome>, <Regranome>, <REGRANOME>, e <rEgRaNoMe> se referem à mesma regra. Tais nomes consistem de uma letra seguida de letras, números ou hífens.

Os sinais “<” e “>” não são requeridos em torno do nome da regra (como são em BNF), no entanto, podem ser usados para delimitar um nome de regra a fim de discerni-lo mesmo fora de contexto.

A FABN é codificada em ASCII 7-bit, em que o 8º bit mais significativo é posto em 0.

Valores terminais

Terminais são especificados por um ou mais caracteres numéricos. Caracteres numéricos podem ser especificados com o sinal de porcentagem “%” seguido pela referência à base (b = binário, d = decimal, e x = hexadecimal) seguido pelo valor ou concatenação de valores (indicado por “.” ). Por exemplo um carriage return é especificado por %d13 em decimal ou %x0D em hexadecimal. Um carriage return seguido por um line feed pode ser especificado por %d13.10.

Textos literais são especificados pelo uso de uma string entre aspas duplas ("), tais strings são caixa-insensíveis e o conjunto de caracteres usado é o US-ASCII. Portanto a string “abc” casa com “abc”, “Abc”, “aBc”, “abC”, “ABc”, “AbC”, “aBC”, e “ABC”. Para um casamento com sensibilidade de caixa, os caracteres deverão ser definido de forma explícita; no caso de “aBc” a definição será %d97% d66% d99.

Operadores

Espaço em branco

Um espaço em branco é usando para separar elementos em uma definição. Para o espaço ser reconhecido como um delimitador, ele deve ser incluído explicitamente.

Concatenação

Regra1 Regra2

Uma regra pode ser definida listando-se uma sucessão de nomes de regras, ou seja, como uma concatenação de outras regras pré-existentes.

Para casar a string “aba” as seguintes regras podem ser usadas:

1. fu = %x61 ; a
2. bar = %x62 ; b
3. mumble = fu bar fu

Alternação

Regra1 / Regra2

Uma regra pode ser definida por uma lista de regras separadas pelo caractere “/”.

Ainda utilizando as regras <fu> e a regra <bar> a seguinte regra poderia ser construída:

1. fubar = fu / bar

Alternação com incremento

Regra1 =/ Regra2

Podem ser acrescentadas alternativas adicionais a uma regra pelo uso do ‘=/’ entre o nome da regra e a definição.

Desta forma, a regra:

1. conjregra = alt1 / alt2 / alt3 / alt4 / alt5

é equivalente à:

1. conjregra = alt1 / alt2
2. conjregra =/ alt3
3. conjregra =/ alt4 / alt5

Série de valores

%c##-##

Uma série de valores podem ser especificados pelo uso do hífen ("-").

Logo, a regra:

1. OCTAL = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7"

É equivalente a:

1. OCTAL = %x30-37

Agrupamento de Sequências

(Regra1 Regra2)

Pode-se colocar elementos entre parênteses a fim de agrupar regras em uma definição.

Para casar “elem fubar snafu” ou “elem tarfu snafu” usamos a seguinte regra:

1. grupo = elem (fubar / tarfu) snafu

Para casar “elem fubar” ou “tarfu snafu” podemos construir a seguinte regra:

1. grupo = elem fubar / tarfu snafu
2. grupo = (elem fubar) / (tarfu snafu)

Repetição de variáveis

n*nRegra

Para indicar a repetição de um elemento a forma <a>*<b>elemento é usada. O campo opcional <a> se refere ao número mínimo de elementos a ser incluído tendo por padrão 0 (zero). O segundo campo opcional <b> se refere ao número máximo de elementos a serem incluídos tendo infinito como padrão.

Logo, usamos *elemento para zero ou mais elementos, 1*elemento para um ou mais e 4*5elementos para quatro ou cinco elementos.

Repetição especifica

nRegra

Usa-se a forma <a>elemento para indicar um número explícito de elementos, tal forma é equivalente a <a>*<a>elemento.

Usa-se 2DIGIT para adquirir dois dígitos numéricos e 3DIGIT para adquirir três dígitos numéricos. (Veja a definição de DIGIT em ‘Regras essenciais’ e também no exemplo código postal.)

Sequências opcionais

[Regra]

Para indicar um elemento opcional as seguintes formas são equivalentes:

1. [fubar snafu]
2. *1(fubar snafu)
3. 0*1(fubar snafu)

Comentário

; comentário

Usa-se ponto e virgula (";") para iniciar um comentário que perdura o resto da linha.

Precedência de operadores

Segue uma lista com a precedência dos operadores descritos acima da maior para a menor precedência:

1. String, Formação de nomes;
2. Comentários;
3. Série de valores;
4. Repetição;
5. Agrupamento, Opcional;
6. Concatenação;
7. Alternação.

O uso do operador de alternação e o operador de concatenação podem ser confundidos. e recomenda-se que agrupamentos sejam usados para fazer concatenações explícitas de grupos.

Regras essenciais

Segue abaixo regras essenciais definidas por padrão na FABN

Regra	Definição Formal	Significado
ALPHA	%x41-5A / %x61-7A	Letras ASCII em caixa alta e baixa (A-Z, a-z )
DIGIT	%x30-39	Dígitos decimais (0-9)
HEXDIG	DIGIT / "A" / "B" / "C" / "D" / "E" / "F"	Dígitos hexadecimais (0-9 A-F a-f )
DQUOTE	%x22	Aspas duplas
SP	%x20	Espaço
HTAB	%x09	Tabulação
WSP	SP / HTAB	Espaço e tabulação
LWSP	*(WSP / CRLF WSP)	Espaço de linha em brando (nova linha)
VCHAR	%x21-7E	Caractere visível (imprimível)
CHAR	%x01-7F	Qualquer caractere US_ASCII 7-bit
OCTET	%x00-FF	8 bits de dados
CTL	%x00-1F / %x7F	Controles
CR	%x0D	Carriage return
LF	%x0A	Linefeed
CRLF	CR LF	Nova linha no padrão da internet
BIT	"0" / "1"

Exemplo

A implementação de um código-postal em FABN seria:

endereço-postal      = parte-do-nome rua parte-do-CEP

parte-do-nome        = [parte-opc-jr] *(parte-pessoal SP) ultimo-nome [SP parte-opc-jr] ; a segunda parte opcional se refere ao "Jr." CRLF
parte-do-nome        =/ parte-pessoal CRLF

parte-pessoal        = primeiro-nome / (inicial ".")
primeiro-nome        = *ALPHA
inicial              = ALPHA "."
ultimo-nome          = *ALPHA
parte-opc-jr         = ( "Sr." / "Jr." / 1*("I" / "V" / "X"))

rua                  = rua-nome SP numero-casa [SP apt] CRLF
apt                  = 1*4DIGIT
numero-casa          = 1*8(DIGIT / ALPHA)
rua-nome             = 1*VCHAR

parte-do-CEP         = CEP 1*2SP cidade SP "-" SP estado CRLF
cidade               = 1*(ALPHA / SP)
estado               = 2ALPHA
CEP                  = 5DIGIT "-" 3DIGIT

Ver também

• Ashtadhyāyi, tratado de gramática sânscrita com estrutura matemática
• GOLD Analisador BNF
• GNU bison Versão GNU do Yacc
• Yacc, gerador de analisador usado com o pré-processador Lex
• Expressão Regular
• RFC 5234 Augmented BNF for Syntax Specifications: ABNF
• RFC 4234 Augmented BNF for Syntax Specifications: ABNF (Obsoleto por: RFC 5234)
• RFC 2234 Augmented BNF for Syntax Specifications: ABNF (Obsoleto)

Referências

Ligações externas

• Backus Normal Form vs. Backus Naur Form
• BNF and EBNF: What are they and how do they work?. Por Lars Marius Garshol.
• Augmented BNF for Syntax Specifications: ABNF. RFC 4234