Formalismo de Backus-Naur
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
editarVisão geral
editarA 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
editarUma 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
editarNo 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
editarA 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
editarIntrodução
editarUma 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
editarTerminais 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
editarEspaço em branco
editarUm 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
editarRegra1 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
editarRegra1 / 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
editarRegra1 =/ 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%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(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
editarn*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
editarnRegra
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:
[fubar snafu]
*1(fubar snafu)
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
editarSegue 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
editarSegue 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
editarA 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
- ↑ 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