Formalismo de Backus-Naur
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Disambig_grey.svg/20px-Disambig_grey.svg.png)
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).[1]
Formalismo de Backus-Naur
[editar | editar código-fonte]Visão geral
[editar | editar código-fonte]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[2] (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,[3] 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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]Introdução
[editar | editar código-fonte]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 sequê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
[editar | editar código-fonte]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
[editar | editar código-fonte]Espaço em branco
[editar | editar código-fonte]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
[editar | editar código-fonte]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 preexistentes.
Para casar a string “aba” as seguintes regras podem ser usadas:
fu = %x61 ; a
bar = %x62 ; b
mumble = fu bar fu
Alternação
[editar | editar código-fonte]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:
fubar = fu / bar
Alternação com incremento
[editar | editar código-fonte]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:
conjregra = alt1 / alt2 / alt3 / alt4 / alt5
é equivalente à:
conjregra = alt1 / alt2
conjregra =/ alt3
conjregra =/ alt4 / alt5
Série de valores
[editar | editar código-fonte]%c##-##
Uma série de valores podem ser especificados pelo uso do hífen ("-
").
Logo, a regra:
OCTAL = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7"
É equivalente a:
OCTAL = %x30-37
Agrupamento de Sequências
[editar | editar código-fonte](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:
grupo = elem (fubar / tarfu) snafu
Para casar “elem fubar” ou “tarfu snafu” podemos construir a seguinte regra:
grupo = elem fubar / tarfu snafu
grupo = (elem fubar) / (tarfu snafu)
Repetição de variáveis
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte][Regra]
Para indicar um elemento opcional as seguintes formas são equivalentes:
[fubar snafu]
*1(fubar snafu)
0*1(fubar snafu)
Comentário
[editar | editar código-fonte]; comentário
Usa-se ponto e virgula (";
") para iniciar um comentário que perdura o resto da linha.
Precedência de operadores
[editar | editar código-fonte]Segue uma lista com a precedência dos operadores descritos acima da maior para a menor precedência:
- String, Formação de nomes;
- Comentários;
- Série de valores;
- Repetição;
- Agrupamento, Opcional;
- Concatenação;
- 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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]- 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
- ↑ Ela está documentada em RFC 4234
- ↑ Linguagens de Programação 2006/07. Ficha 5. Gramáticas. 5.2.2 Notação BNF e EBNF (Extended BNF)
- ↑ KNUTH, Donald E. (2003). Selected Papers on Computer Languages. Backus Normal Form versus Backus Naur Form (em inglês). Ventura Hall, Stanford CA: CSLI-Center for Study of Language and Information. pp. 95–97. ISBN 1-57586-382-0