Formulário Backus – Naur estendido - Extended Backus–Naur form

Em ciência da computação , a forma Backus – Naur estendida ( EBNF ) é uma família de notações metassintaxe , qualquer uma das quais pode ser usada para expressar uma gramática livre de contexto . EBNF é usado para fazer uma descrição formal de uma linguagem formal , como uma linguagem de programação de computador . Eles são extensões da notação metassintaxe da forma Backus – Naur (BNF).

O EBNF mais antigo foi desenvolvido por Niklaus Wirth incorporando alguns dos conceitos (com uma sintaxe e notação diferentes) da notação de sintaxe de Wirth . No entanto, muitas variantes de EBNF estão em uso. A International Organization for Standardization adotou um padrão EBNF ( ISO / IEC 14977 ) em 1996. No entanto, de acordo com Zaytsev, esse padrão "só acabou adicionando mais três dialetos ao caos" e, após constatar seu insucesso, também observa que o ISO EBNF nem mesmo é usado em todos os padrões ISO. Wheeler argumenta contra o uso do padrão ISO ao usar um EBNF e recomenda considerar notações EBNF alternativas, como a do W3C Extensible Markup Language (XML) 1.0 (Quinta Edição).

Este artigo usa EBNF conforme especificado pela ISO para exemplos que se aplicam a todos os EBNFs. Outras variantes de EBNF usam convenções sintáticas um pouco diferentes.

Fundamentos

EBNF é um código que expressa a sintaxe de uma linguagem formal. Um EBNF consiste em símbolos terminais e regras de produção não terminais que são as restrições que governam como os símbolos terminais podem ser combinados em uma sequência legal. Exemplos de símbolos de terminal incluem caracteres alfanuméricos , sinais de pontuação e caracteres de espaço em branco .

O EBNF define regras de produção onde sequências de símbolos são respectivamente atribuídas a um não terminal :

digit excluding zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit                = "0" | digit excluding zero ;

Esta regra de produção define o dígito não terminal que está no lado esquerdo da atribuição. A barra vertical representa uma alternativa e os símbolos terminais são colocados entre aspas seguidas por um ponto e vírgula como caractere de terminação. Portanto, um dígito é um 0 ou um dígito excluindo zero que pode ser 1 ou 2 ou 3 e assim por diante até 9 .

Uma regra de produção também pode incluir uma sequência de terminais ou não terminais, cada um separado por uma vírgula:

twelve                          = "1", "2" ;
two hundred one                 = "2", "0", "1" ;
three hundred twelve            = "3", twelve ;
twelve thousand two hundred one = twelve, two hundred one ;

Expressões que podem ser omitidas ou repetidas podem ser representadas por chaves {...}:

natural number = digit excluding zero, { digit } ;

Neste caso, as strings 1 , 2 , ..., 10 , ..., 10000 , ... são expressões corretas. Para representar isso, tudo o que é definido entre as chaves pode ser repetido arbitrariamente com frequência, incluindo nada.

Uma opção pode ser representada por colchetes [...]. Ou seja, tudo o que está definido entre colchetes pode estar presente apenas uma vez ou não estar presente:

integer = "0" | [ "-" ], natural number ;

Portanto, um inteiro é um zero ( 0 ) ou um número natural que pode ser precedido por um sinal de menos opcional .

EBNF também fornece, entre outras coisas, a sintaxe para descrever repetições (de um determinado número de vezes), para excluir alguma parte de uma produção e para inserir comentários em uma gramática EBNF.

Tabela de símbolos

O seguinte representa uma proposta de padrão ISO / IEC 14977, por RS Scowen, página 7, tabela 1.

Exemplos

Diagrama de sintaxe

Um possível diagrama de sintaxe EBNF

Mesmo EBNF pode ser descrito usando EBNF. Considere o esboço de gramática abaixo:

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 = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">"
       | "'" | '"' | "=" | "|" | "." | "," | ";" ;
character = letter | digit | symbol | "_" ;
 
identifier = letter , { letter | digit | "_" } ;
terminal = "'" , character , { character } , "'" 
         | '"' , character , { character } , '"' ;
 
lhs = identifier ;
rhs = identifier
     | terminal
     | "[" , rhs , "]"
     | "{" , rhs , "}"
     | "(" , rhs , ")"
     | rhs , "|" , rhs
     | rhs , "," , rhs ;

rule = lhs , "=" , rhs , ";" ;
grammar = { rule } ;

Uma linguagem de programação semelhante a Pascal que permite apenas atribuições pode ser definida em EBNF da seguinte forma:

 (* a simple program syntax in EBNF − Wikipedia *)
 program = 'PROGRAM', white_space, identifier, white_space, 
            'BEGIN', white_space, 
            { assignment, ";", white_space }, 
            'END.' ;
 identifier = alphabetic_character, { alphabetic_character | digit } ;
 number = [ "-" ], digit, { digit } ;
 string = '"' , { all_characters - '"' }, '"' ;
 assignment = identifier , ":=" , ( number | identifier | string ) ;
 alphabetic_character = "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" ;
 white_space = ? white_space characters ? ;
 all_characters = ? all visible characters ? ;

Por exemplo, um programa sintaticamente correto poderia ser:

 PROGRAM DEMO1
 BEGIN
   A:=3;
   B:=45;
   H:=-100023;
   C:=A;
   D123:=B34A;
   BABOON:=GIRAFFE;
   TEXT:="Hello world!";
 END.

A linguagem pode ser facilmente estendida com fluxos de controle , expressões aritméticas e instruções de entrada / saída. Em seguida, uma linguagem de programação pequena e utilizável seria desenvolvida.

Vantagens sobre BNF

Qualquer gramática definida em EBNF também pode ser representada em BNF, embora as representações no último sejam geralmente mais longas. Por exemplo, opções e repetições não podem ser expressas diretamente em BNF e requerem o uso de uma regra intermediária ou produção alternativa definida como nada ou a produção opcional por opção, ou a produção repetida de si mesma, recursivamente, para repetição. As mesmas construções ainda podem ser usadas em EBNF.

A BNF usa os símbolos ( <, >, |, ::=) para si mesmo, mas não inclui aspas em torno de cordas terminais. Isso evita que esses caracteres sejam usados ​​nos idiomas e requer um símbolo especial para a string vazia. Na EBNF, os terminais são colocados estritamente entre aspas ( "... "ou '... '). Os colchetes angulares (" <… >") para não terminais podem ser omitidos.

A sintaxe BNF só pode representar uma regra em uma linha, enquanto em EBNF um caractere de terminação, o caractere ponto-e-vírgula “ ;” marca o fim de uma regra.

Além disso, EBNF inclui mecanismos de melhorias, definindo o número de repetições, excluindo alternativas, comentários, etc.

Convenções

Como exemplos, as seguintes regras de sintaxe ilustram os recursos para expressar a repetição:

aa = "A";
bb = 3 * aa, "B";
cc = 3 * [aa], "C";
dd = {aa}, "D";
ee = aa, {aa}, "E";
ff = 3 * aa, 3 * [aa], "F";
gg = {3 * aa}, "G";

As strings de terminal definidas por essas regras são as seguintes:

aa: A
bb: AAAB
cc: C AC AAC AAAC
dd: D AD AAD AAAD AAAAD etc.
ee: AE AAE AAAE AAAAE AAAAAE etc.
ff: AAAF AAAAF AAAAAF AAAAAAF
gg: G AAAG AAAAAAG etc.

Extensibilidade

De acordo com o padrão ISO 14977, o EBNF é extensível e duas facilidades são mencionadas. O primeiro é parte da gramática EBNF, a sequência especial, que é um texto arbitrário delimitado por pontos de interrogação. A interpretação do texto dentro de uma sequência especial está além do escopo do padrão EBNF. Por exemplo, o caractere de espaço pode ser definido pela seguinte regra:

 space = ? ASCII character 32 ?;

O segundo recurso para extensão é usar o fato de que parênteses em EBNF não podem ser colocados ao lado de identificadores (eles devem ser concatenados com eles). O seguinte é EBNF válido:

 something = foo, ( bar );

O seguinte não é EBNF válido:

 something = foo ( bar );

Portanto, uma extensão de EBNF poderia usar essa notação. Por exemplo, em uma gramática Lisp , a aplicação da função pode ser definida pela seguinte regra:

 function application = list( symbol, { expression } );

Trabalho relatado

• O W3C usou um EBNF diferente para especificar a sintaxe XML .
• A British Standards Institution publicou um padrão para uma EBNF: BS 6154 em 1981.
• O IETF usa BNF aumentado (ABNF), especificado no RFC  5234 .

Veja também

• Meta-II - Uma das primeiras ferramentas de escrita de compiladores e notação
• Regras de estrutura de frase - O equivalente direto de EBNF em linguagens naturais
• Expressão regular
• Estrutura do Spirit Parser

Referências

links externos

• ISO / IEC 14977: 1996 (E)
• Variantes BNF / EBNF - uma tabela de Pete Jinks comparando várias sintaxes
• Analisador e Renderizador em PHP5
• Representação do diagrama de sintaxe SRFB por base de função + geração EBNF (javascript)