Forma Backus – Naur - Backus–Naur form

Não deve ser confundido com a forma normal de Boyce-Codd .

Em informática , forma-Backus Naur ( / ˌ b Æ k ə s n aʊər / ) ou forma normal Backus ( BNF ) é um metasyntax notação para gramáticas livres de contexto , muitas vezes usado para descrever a sintaxe de idiomas usado na computação, como linguagens de programação de computador , formatos de documentos , conjuntos de instruções e protocolos de comunicação . Eles são aplicados sempre que descrições exatas de linguagens são necessárias: por exemplo, em especificações oficiais de linguagem, em manuais e em livros didáticos sobre teoria de linguagem de programação.

Muitas extensões e variantes da notação Backus – Naur original são usadas; alguns são exatamente definidos, incluindo a forma Backus-Naur estendida (EBNF) e a forma Backus-Naur aumentada (ABNF).

História

A ideia de descrever a estrutura da linguagem usando regras de reescrita remonta pelo menos ao trabalho de Pāṇini , um antigo gramático sânscrito indiano e um estudioso reverenciado do hinduísmo que viveu entre os séculos 6 e 4 aC . Sua notação para descrever a estrutura da palavra sânscrita é equivalente em poder à de Backus e tem muitas propriedades semelhantes.

Na sociedade ocidental, a gramática foi por muito tempo considerada um assunto de ensino, ao invés de estudo científico; as descrições eram informais e voltadas para o uso prático. Na primeira metade do século 20, linguistas como Leonard Bloomfield e Zellig Harris começaram a tentar formalizar a descrição da linguagem, incluindo a estrutura das frases.

Enquanto isso, regras de reescrita de strings como sistemas lógicos formais foram introduzidas e estudadas por matemáticos como Axel Thue (em 1914), Emil Post (1920s –40s) e Alan Turing (1936). Noam Chomsky , ensinando lingüística para estudantes de teoria da informação no MIT , combinou lingüística e matemática tomando o que é essencialmente o formalismo de Thue como base para a descrição da sintaxe da linguagem natural . Ele também introduziu uma distinção clara entre regras gerativas (aquelas de gramáticas livres de contexto ) e regras de transformação (1956).

John Backus , um designer de linguagem de programação da IBM , propôs uma metalinguagem de "fórmulas metalinguísticas" para descrever a sintaxe da nova linguagem de programação IAL, conhecida hoje como ALGOL 58 (1959). Sua notação foi usada pela primeira vez no relatório ALGOL 60.

BNF é uma notação para gramáticas livres de contexto de Chomsky. Backus estava familiarizado com o trabalho de Chomsky.

Conforme proposto por Backus, a fórmula definia "classes" cujos nomes são colocados entre colchetes angulares. Por exemplo <ab>,. Cada um desses nomes denota uma classe de símbolos básicos.

O desenvolvimento adicional do ALGOL levou ao ALGOL 60 . No relatório do comitê de 1963, Peter Naur chamou a notação de Backus de forma normal . Donald Knuth argumentou que BNF deveria ser lido como forma Backus-Naur , já que "não é uma forma normal no sentido convencional", ao contrário, por exemplo, da forma normal de Chomsky . O nome Pāṇini Backus form também foi sugerido uma vez em vista do fato de que a forma normal de expansão Backus pode não ser precisa, e que Pāṇini havia desenvolvido independentemente uma notação semelhante anteriormente.

O BNF é descrito por Peter Naur no relatório ALGOL 60 como fórmula metalinguística :

As sequências de caracteres entre colchetes <> representam variáveis ​​metalinguísticas cujos valores são sequências de símbolos. As marcas ":: =" e "|" (o último com o significado de "ou") são conectivos metalinguísticos. Qualquer marca em uma fórmula, que não seja uma variável ou um conectivo, denota a si mesma. A justaposição de marcas ou variáveis ​​em uma fórmula significa a justaposição da sequência denotada.

Outro exemplo do relatório ALGOL 60 ilustra uma grande diferença entre a metalinguagem BNF e uma gramática livre de contexto de Chomsky. As variáveis ​​metalingüísticas não requerem uma regra que defina sua formação. Sua formação pode ser simplesmente descrita em linguagem natural entre <> colchetes. A seguinte especificação de comentários da seção 2.3 do relatório do ALGOL 60 exemplifica como isso funciona:

Com o propósito de incluir texto entre os símbolos de um programa, as seguintes convenções de "comentários" são válidas:

A sequência de símbolos básicos: é equivalente a
; comentário <qualquer sequência que não contenha ';'>; ;
começar o comentário <qualquer sequência que não contenha ';'>; começar
end <qualquer sequência que não contenha 'end' ou ';' ou 'else'> fim

Equivalência aqui significa que qualquer uma das três estruturas mostradas na coluna da esquerda pode ser substituída, em qualquer ocorrência fora das strings, pelo símbolo mostrado na mesma linha na coluna da direita sem qualquer efeito na ação do programa.

Naur mudou dois dos símbolos de Backus para caracteres comumente disponíveis. O ::=símbolo era originalmente um :≡. O |símbolo era originalmente a palavra " ou " (com uma barra sobre ele). Trabalhando para a IBM, Backus teria um acordo de não divulgação e não poderia ter falado sobre sua fonte se ela viesse de um projeto proprietário da IBM.

O BNF é muito semelhante às equações da álgebra booleana na forma canônica que são, e eram na época, usadas no projeto de circuitos lógicos. Backus era um matemático e o designer da linguagem de programação FORTRAN. Os estudos de álgebra booleana costumam fazer parte de um currículo de matemática. O que sabemos é que nem Backus nem Naur descreveram os nomes incluídos como não terminais. A terminologia de Chomsky não foi originalmente usada para descrever a BNF. Naur mais tarde as descreveu como aulas nos materiais do curso ALGOL. No relatório ALGOL 60, elas foram chamadas de variáveis ​​metalinguísticas. Qualquer coisa diferente dos meta-símbolos , e nomes de classes incluídos são símbolos da linguagem que está sendo definida. Os metassímbolos devem ser interpretados como "é definido como". O é usado para separar definições alternativas e é interpretado como "ou". Os meta-símbolos são delimitadores que encerram um nome de classe. BNF é descrito como uma metalinguagem para falar sobre ALGOL por Peter Naur e Saul Rosen . < >::=|< >::=|< >

Em 1947, Saul Rosen envolveu-se nas atividades da incipiente Association for Computing Machinery , primeiro no comitê de línguas que se tornou o grupo IAL e acabou levando ao ALGOL. Ele foi o primeiro editor-chefe das Comunicações da ACM. O que sabemos é que o BNF foi usado pela primeira vez como uma metalinguagem para falar sobre a linguagem ALGOL no relatório ALGOL 60. É assim que é explicado no material do curso de programação do ALGOL desenvolvido por Peter Naur em 1962. Os primeiros manuais do ALGOL da IBM, Honeywell, Burroughs e Digital Equipment Corporation seguiram o relatório do ALGOL 60 usando-o como uma metalinguagem. Saul Rosen em seu livro descreve o BNF como uma metalinguagem para falar sobre o ALGOL. Um exemplo de seu uso como metalinguagem seria na definição de uma expressão aritmética: 

<expr> ::= <term>|<expr><addop><term>

O primeiro símbolo de uma alternativa pode ser a classe que está sendo definida, a repetição, conforme explicado por Naur, que tem a função de especificar que a sequência alternativa pode começar recursivamente com uma alternativa anterior e pode ser repetida qualquer número de vezes. Por exemplo, acima <expr>é definido como um <term>seguido por qualquer número de <addop> <term>.

Em algumas metalinguagens posteriores, como o META II de Schorre , a construção de repetição recursiva BNF é substituída por um operador de sequência e símbolos de linguagem alvo definidos usando strings entre aspas. Os colchetes <e >foram removidos. Parênteses ()para agrupamento matemático foram adicionados. A <expr>regra apareceria no META II como 

EXPR = TERM $('+' TERM .OUT('ADD') | '-' TERM .OUT('SUB'));

Essas mudanças permitiram que META II e suas linguagens de programação derivadas definissem e estendessem sua própria metalinguagem, ao custo da habilidade de usar uma descrição em linguagem natural, variável metalinguística, descrição de construção de linguagem. Muitas metalinguagens spin-off foram inspiradas na BNF. Consulte META II , TREE-META e Metacompiler .

Uma classe BNF descreve a formação de uma construção de linguagem, com formação definida como um padrão ou a ação de formar o padrão. O nome da classe expr é descrito em uma linguagem natural como um <term>seguido por uma sequência <addop> <term>. Uma classe é uma abstração; podemos falar sobre ele independentemente de sua formação. Podemos falar sobre o termo, independentemente de sua definição, como sendo adicionado ou subtraído em expr. Podemos falar sobre um termo ser um tipo de dados específico e como uma expr deve ser avaliada tendo combinações específicas de tipos de dados. Ou até mesmo reordenar uma expressão para agrupar tipos de dados e resultados de avaliação de tipos mistos. O suplemento de linguagem natural forneceu detalhes específicos da semântica da classe de linguagem a ser usada por uma implementação de compilador e um programador escrevendo um programa ALGOL. A descrição em linguagem natural também complementou a sintaxe. A regra do inteiro é um bom exemplo de linguagem natural e metalinguagem usada para descrever a sintaxe: 

<integer> ::= <digit>|<integer><digit>

Não há especificações sobre o espaço em branco acima. De acordo com a regra, podemos ter espaço entre os dígitos. Na linguagem natural, complementamos a metalinguagem BNF explicando que a sequência de dígitos não pode ter nenhum espaço em branco entre os dígitos. O inglês é apenas uma das línguas naturais possíveis. As traduções dos relatórios ALGOL estavam disponíveis em muitas línguas naturais.

A origem do BNF não é tão importante quanto seu impacto no desenvolvimento da linguagem de programação. Durante o período imediatamente após a publicação do relatório ALGOL 60, o BNF foi a base de muitos sistemas compilador-compilador .

Alguns, como "A Syntax Directed Compiler for ALGOL 60" desenvolvido por Edgar T. Irons e "A Compiler Building System" desenvolvido por Brooker e Morris, usavam diretamente o BNF. Outros, como os Metacompiladores Schorre , tornaram-se uma linguagem de programação com apenas algumas alterações. <class name>tornaram-se identificadores de símbolo, eliminando o <,> e usando cadeias de caracteres entre aspas para símbolos do idioma de destino. O agrupamento semelhante à aritmética forneceu uma simplificação que removeu o uso de classes em que o agrupamento era seu único valor. A regra de expressão aritmética META II mostra o uso de agrupamento. Expressões de saída colocadas em uma regra META II são usadas para produzir código e rótulos em uma linguagem assembly. As regras no META II são equivalentes às definições de classe no BNF. O utilitário Unix yacc é baseado no BNF com produção de código semelhante ao META II. O yacc é mais comumente usado como um gerador de analisador , e suas raízes são obviamente BNF.

BNF hoje é uma das linguagens de informática mais antigas ainda em uso.

Introdução

Uma especificação BNF é um conjunto de regras de derivação, escrito como 

 <symbol> ::= __expression__

onde < símbolo > é um não terminal e a __expressão__ consiste em uma ou mais sequências de símbolos; mais sequências são separadas pela barra vertical "|", indicando uma escolha , sendo o todo uma possível substituição para o símbolo à esquerda. Os símbolos que nunca aparecem no lado esquerdo são terminais . Por outro lado, os símbolos que aparecem no lado esquerdo não são terminais e estão sempre entre o par <>.

O ":: =" significa que o símbolo à esquerda deve ser substituído pela expressão à direita.

Exemplo

Como exemplo, considere este possível BNF para um endereço postal dos EUA : 

 <postal-address> ::= <name-part> <street-address> <zip-part>

      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> | <personal-part> <name-part>

  <personal-part> ::= <initial> "." | <first-name>

 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>

       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>

<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""

Isso se traduz para o inglês como:

  • Um endereço postal consiste em uma parte do nome, seguida por uma parte do endereço da rua , seguida por uma parte do código postal .
  • Uma parte do nome consiste em: uma parte pessoal seguida por um sobrenome seguido por um sufixo opcional (Jr., Sr. ou número dinástico) e fim de linha , ou uma parte pessoal seguida por uma parte do nome ( esta regra ilustra o uso de recursão em BNFs, cobrindo o caso de pessoas que usam vários nomes do meio e iniciais).
  • Uma parte pessoal consiste em um primeiro nome ou uma inicial seguida por um ponto.
  • Um endereço de rua consiste em um número de casa, seguido por um nome de rua, seguido por um especificador de apartamento opcional , seguido por um fim de linha.
  • Uma parte do CEP consiste em um nome de cidade , seguido por uma vírgula, seguido por um código de estado , seguido por um código postal seguido por um fim de linha.
  • Um opt-sufixo-parte consiste em um sufixo, como "Sr.", "Jr." ou um numeral romano , ou uma string vazia (ou seja, nada).
  • Um opt-apt-num consiste em um número de apartamento ou uma string vazia (ou seja, nada).

Observe que muitas coisas (como o formato do primeiro nome, número do apartamento, CEP e algarismo romano) não foram especificadas aqui. Se necessário, eles podem ser descritos usando regras BNF adicionais.

Outros exemplos

Diagrama de sintaxe BNF
Diagrama de sintaxe BNF

A própria sintaxe do BNF pode ser representada por um BNF como o seguinte: 

 <syntax>         ::= <rule> | <rule> <syntax>
 <rule>           ::= <opt-whitespace> "<" <rule-name> ">" <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end>
 <opt-whitespace> ::= " " <opt-whitespace> | ""
 <expression>     ::= <list> | <list> <opt-whitespace> "|" <opt-whitespace> <expression>
 <line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
 <list>           ::= <term> | <term> <opt-whitespace> <list>
 <term>           ::= <literal> | "<" <rule-name> ">"
 <literal>        ::= '"' <text1> '"' | "'" <text2> "'"
 <text1>          ::= "" | <character1> <text1>
 <text2>          ::= '' | <character2> <text2>
 <character>      ::= <letter> | <digit> | <symbol>
 <letter>         ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
 <digit>          ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
 <symbol>         ::=  "|" | " " | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | ">" | "=" | "<" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "{" | "}" | "~"
 <character1>     ::= <character> | "'"
 <character2>     ::= <character> | '"'
 <rule-name>      ::= <letter> | <rule-name> <rule-char>
 <rule-char>      ::= <letter> | <digit> | "-"

Observe que "" é a string vazia .

O BNF original não usava aspas conforme mostrado na <literal>regra. Isso pressupõe que nenhum espaço em branco é necessário para a interpretação adequada da regra.

<EOL>representa o especificador de fim de linha apropriado (em ASCII , retorno de carro, alimentação de linha ou ambos, dependendo do sistema operacional ). <rule-name>e <text>devem ser substituídos pelo nome / rótulo de uma regra declarada ou texto literal, respectivamente.

No exemplo de endereço postal dos EUA acima, toda a aspas em bloco é uma sintaxe. Cada linha ou agrupamento ininterrupto de linhas é uma regra; por exemplo, uma regra começa com <name-part> ::=. A outra parte dessa regra (além do fim da linha) é uma expressão, que consiste em duas listas separadas por uma barra vertical |. Essas duas listas consistem em alguns termos (três termos e dois termos, respectivamente). Cada termo nesta regra particular é um nome de regra.

Variantes

Existem muitas variantes e extensões do BNF, geralmente por uma questão de simplicidade e sucinto, ou para adaptá-lo a uma aplicação específica. Um recurso comum de muitas variantes é o uso de operadores de repetição de expressão regular , como *e +. A forma estendida de Backus – Naur (EBNF) é comum.

Outra extensão comum é o uso de colchetes em torno de itens opcionais. Embora não presentes no original relatório ALGOL 60 (em vez introduzida alguns anos mais tarde na IBM 's I PL / definição), a notação é hoje universalmente reconhecida.

O formulário Backus-Naur aumentado (ABNF) e o formulário Backus-Naur Routing (RBNF) são extensões comumente usadas para descrever os protocolos da Força-Tarefa de Engenharia da Internet (IETF) .

A análise de gramáticas de expressão baseia-se no BNF e nas notações de expressão regular para formar uma classe alternativa de gramática formal , que é essencialmente analítica em vez de generativa em caráter.

Muitas especificações BNF encontradas online hoje são destinadas a serem legíveis por humanos e não são formais. Isso geralmente inclui muitas das seguintes regras de sintaxe e extensões:

  • Itens opcionais entre colchetes: [<item-x>].
  • Os itens existentes 0 ou mais vezes são colocados entre colchetes ou sufixados com um asterisco ( *) como <word> ::= <letter> {<letter>}ou <word> ::= <letter> <letter>*respectivamente.
  • Os itens que existem 1 ou mais vezes são sufixados com um símbolo de adição (mais) +, como <word> ::= <letter>+.
  • Os terminais podem aparecer em negrito em vez de itálico e não terminais em texto simples em vez de colchetes angulares.
  • Onde os itens são agrupados, eles são colocados entre parênteses simples.

Software usando BNF

  • ANTLR , outro gerador de analisador escrito em Java
  • Qlik Sense, uma ferramenta de BI, usa uma variante do BNF para scripts
  • Conversor BNF (BNFC), operando em uma variante chamada "forma rotulada de Backus – Naur" (LBNF). Nesta variante, cada produção para um determinado não terminal recebe um rótulo, que pode ser usado como um construtor de um tipo de dados algébrico que representa aquele não terminal. O conversor é capaz de produzir tipos e analisadores para sintaxe abstrata em várias linguagens, incluindo Haskell e Java.
  • Coco / R , gerador de compilador que aceita uma gramática atribuída em EBNF
  • DMS Software Reengineering Toolkit , análise de programa e sistema de transformação para linguagens arbitrárias
  • Analisador GOLD BNF
  • GNU bison , versão GNU do yacc
  • Analisador de RPA BNF. Análise de demonstração online (PHP): JavaScript, XML
  • Sistema XACT X4MR, um sistema especialista baseado em regras para tradução de linguagem de programação
  • XPL Analyzer, uma ferramenta que aceita BNF simplificado para uma linguagem e produz um analisador para essa linguagem em XPL; pode ser integrado ao programa SKELETON fornecido, com o qual a linguagem pode ser depurada (um programa contribuído por SHARE , que foi precedido por um gerador de compilador )
  • Yacc , gerador de analisador (mais comumente usado com o pré-processador Lex )
  • bnfparser 2 , um utilitário universal de verificação de sintaxe
  • bnf2xml, entrada de marcação com tags XML usando correspondência BNF avançada.
  • JavaCC, Java Compiler Compiler tm (JavaCC tm) - O Java Parser Generator.
  • Ferramentas de análise do Racket, análise no estilo lex e yacc (edição Beautiful Racket)
  • Belr , um gerador de analisador escrito em C ++ 11. Ele usa ABNF .

Veja também

Referências

links externos

  • Garshol, Lars Marius, BNF e EBNF: O que são e como funcionam? , NÃO : Priv.
  • RFC  5234 - BNF aumentado para especificações de sintaxe: ABNF.
  • RFC  5511 - Routing BNF: uma sintaxe usada em várias especificações de protocolo.
  • ISO / IEC 14977: 1996 (E) Tecnologia da informação - Metalinguagem sintática - BNF estendida , disponível em "Publicly available", Standards , ISOou de Kuhn, Marcus, Iso 14977 (PDF) , UK : CAM (o último não tem a página de rosto, mas por outro lado é muito mais limpo)

Gramáticas de linguagem