Formalismo de Backus-Naur

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A forma de Backus-Naur (também conhecido como BNF, formalismo de Backus-Naur, forma normal de 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.

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

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 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[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 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[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:

  1. 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:

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

é equivalente à:

  1. conjregra = alt1 / alt2
  2. conjregra =/ alt3
  3. 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:

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

É equivalente a:

  1. 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:

  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[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:

  1. [fubar snafu]
  2. *1(fubar snafu)
  3. 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:

  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[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 opcinal 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

Referências

  1. Ela está documentada em RFC 4234
  2. Linguagens de Programação 2006/07. Ficha 5. Gramáticas. 5.2.2 Notação BNF e EBNF (Extended BNF)
  3. KNUTH, Donald E.. 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, 2003. 95-97 p. ISBN 1-57586-382-0

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)

Ligações externas[editar | editar código-fonte]