Wikipédia

Formalismo de Backus-Naur

(Redirecionado de FNB)
 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).[1]

Formalismo de Backus-Naur

editar

Visão geral

editar

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

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

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

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

Introdução

editar

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

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

Espaço em branco

editar

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

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:

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

Alternação

editar

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

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

%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

(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

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

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

[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

; comentário

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

Precedência de operadores

editar

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

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

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
  • 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

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

Ligações externas

editar
Obtida de "https://pt.wiki.x.io/w/index.php?title=Formalismo_de_Backus-Naur&oldid=68475303"