Image Image Image Image Image
Scroll to Top

Topo

ebnf

08

nov
2011

Sem Comentários

Em Blog

Por Allison

O que é BNF e por que os desenvolvedores devem ser importar?

Em 08, nov 2011 | Sem Comentários | Em Blog | Por Allison

Backus-Naur Form (BNF) é uma sintaxe para descrever uma sintaxe. É usado para escrever uma representação formal de uma gramática livre de contexto. Se ele não soar abstrato o suficiente para você, uma gramática não tem que ser uma linguagem de programação, ou até uma linguagem humana – ela pode ser qualquer sintaxe que você queira descrever.

Eu descobri o BNF pela primeira vez ao trabalhar no padrão ANSI de 1992 para DBOL, que continha uma especificação sintática BNF completa para aquela linguagem (eram 11 páginas). O exercício para definir a linguagem em BNF ajudou o comitê a rigorosamente definir os detalhes da sua sintaxe. Um dos implentadores da linguagem também alimentou este BNF para outro Yet Another Compiler Compiler (yacc) para ajudar a construir seu compilador para sua próxima versão, para que eles pudessem garantir que ele fosse compilado sintaticamente com a especificação. É aí que o BNF se destaca: uma vez que você tem uma definição sintática bastante sólida em BNF, você pode usar ferramentas para analisar rigorosamente a sintaxe que ele descreve, sem ter que inventar o código que implementa a especificação, ou se apoiar em expressões regulares.

O BNF usa uma sintaxe declarativa que permite que você defina seus temos via “regras de produção’. Cada regra contém termos em que cada um deles tem mais regras concretas, até que você chegue nos “terminais”, que são termos em que você somente pode descrever como caracteres específicos (valores literais). Assim, por exemplos, se quiséssemos descrever a sintaxe para chamar uma shell de comandos chamada “fred”, que precisa de um valor numérico não negativo como seu argumento, poderíamos expressá-lo assim:

<call-fred> ::= fred <whitespace> <number> <eol>

<whitespace> ::= <space-char> | <space-char> <whitespace>

<space-char> ::= \s | \t

<number> ::= <digit> | <digit> <number>

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<eol> ::= \n | <whitespace> \n

Cada um dos identificadores em um ângulo entre parênteses é o nome de um termo. Uma linha começando com o nome de um termo, seguido por um “::=” e os componentes que formam o termo compõe a regra de produção do mesmo. Os terminais no exemplo acima são valores literais que não estão inclusos nos ângulos entre parênteses. O operador “|” fornece um “or” lógico. Como nas linguagens de programação funcionais, usamos a recursão para descrever as listas de comprimento variável como <number> e <whitespace>.

Muitas variantes para a sintaxe acima emergiram. O Extended Backus-Naur Form (EBNF) fornece várias melhorias e simplificações. Ao pedir aspas em volta de valores literais, podemos dispensar muitas outras pontuações. Podemos então, expressar o exemplo acima de uma forma mais simples e familiar para os programadores:

Backus-Naur Form (BNF) é uma sintaxe para descrever uma sintaxe. É usado para escrever uma representação formal de uma gramática livre de contexto. Se ele não soar abstrato o suficiente para você, uma gramática não tem que ser uma linguagem de programação, ou até uma linguagem humana – ela pode ser qualquer sintaxe que você queira descrever.

Eu descobri o BNF pela primeira vez ao trabalhar no padrão ANSI de 1992 para DBOL, que continha uma especificação sintática BNF completa para aquela linguagem (eram 11 páginas). O exercício para definir a linguagem em BNF ajudou o comitê a rigorosamente definir os detalhes da sua sintaxe. Um dos implentadores da linguagem também alimentou este BNF para outro Yet Another Compiler Compiler (yacc) para ajudar a construir seu compilador para sua próxima versão, para que eles pudessem garantir que ele fosse compilado sintaticamente com a especificação. É aí que o BNF se destaca: uma vez que você tem uma definição sintática bastante sólida em BNF, você pode usar ferramentas para analisar rigorosamente a sintaxe que ele descreve, sem ter que inventar o código que implementa a especificação, ou se apoiar em expressões regulares.

O BNF usa uma sintaxe declarativa que permite que você defina seus temos via “regras de produção’. Cada regra contém termos em que cada um deles tem mais regras concretas, até que você chegue nos “terminais”, que são termos em que você somente pode descrever como caracteres específicos (valores literais). Assim, por exemplos, se quiséssemos descrever a sintaxe para chamar uma shell de comandos chamada “fred”, que precisa de um valor numérico não negativo como seu argumento, poderíamos expressá-lo assim:

<call-fred> ::= fred <whitespace> <number> <eol>

<whitespace> ::= <space-char> | <space-char> <whitespace>

<space-char> ::= \s | \t

<number> ::= <digit> | <digit> <number>

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<eol> ::= \n | <whitespace> \n

Cada um dos identificadores em um ângulo entre parênteses é o nome de um termo. Uma linha começando com o nome de um termo, seguido por um “::=” e os componentes que formam o termo compõe a regra de produção do mesmo. Os terminais no exemplo acima são valores literais que não estão inclusos nos ângulos entre parênteses. O operador “|” fornece um “or” lógico. Como nas linguagens de programação funcionais, usamos a recursão para descrever as listas de comprimento variável como <number> e <whitespace>.

Muitas variantes para a sintaxe acima emergiram. O Extended Backus-Naur Form (EBNF) fornece várias melhorias e simplificações. Ao pedir aspas em volta de valores literais, podemos dispensar muitas outras pontuações. Podemos então, expressar o exemplo acima de uma forma mais simples e familiar para os programadores:

call-fred = “fred”, whitespace, number, eol

whitespace = space-char, { space-char }

space-char = ” ” | “\t”

number = digit, { digit }

digit = “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”

eol = [ whitespace ], “\n”

Note o uso de “{ }” para indicar “zero, ou mais”, e “[ ]” para itens opcionais. Algumas variantes também usam o asterisco para indicar zero, ou mais, assim como o “+” para indicar um, ou mais.

Para mais exemplos úteis, vamos descrever a sintaxe de valores separados por vírgulas (CSVs, em inglês).

csv-file = { row }

row = field-list, eol

field-list = field, [ “,”, field-list ]

field = [ whitespace ], field-value, [ whitespace ]

field-value = quoted-string | bare-string

quoted-string = ‘”‘, quoted-content, ‘”‘

quoted-content = { quoted-char }

quoted-char = (any char except ‘”‘ or eol)

bare-string = { bare-char }

bare-char = (any char except ‘,’ or eol)

whitespace = space-char, { space-char }

space-char = ” ” | “\t”

eol = “\n”

Na primeira regra, definimos o arquivo CSV como uma série de zero, ou mais linhas. Uma linha é uma lista de campos, seguida por um caractere de fim de linha. A lista de campos tem pelo um campo (mesmo que esse campo tenha comprimento zero). Uma vírgula e outra lista de campos podem, opcionalmente, seguir (note a recursão). Um campo individual pode ter um espaço em branco em algum fim, e o valor do campo por ser uma string com aspas, ou sem nada. Uma string com aspas pode não conter aspas, e uma string sem nada pode não conter uma vírgula.

Em um artigo futuro iremos ver como transformar essa definição em um código que analisa um arquivo CSV.

Artigo original disponível em http://www.techrepublic.com/blog/programming-and-development/what-is-bnf-and-why-should-developers-care/4346

Fonte: IMasters

Tags | , , ,