Notacja EBNF
Z Wikipedii
Rozszerzona Notacja Backusa-Naura (ang. Extended Backus-Naur Form) jest sposobem wyrażenia gramatyki bezkontekstowej czyli opisem języków formalnych. Jest rozszerzeniem Notacji BNF.
Początkowo rozwijana przez Niklausa Wirtha, jest określona przez Międzynarodową Organizację Normalizacyjną ISO-14977.
Spis treści |
[edytuj] Podstawy
Słowo opisywanego języka składa się z symboli terminalnych czyli widocznych znaków, w tym cyfr, znaków interpunkcyjnych czy spacji.
EBNF określa reguły produkcji gdzie do symboli nieterminalnych przypisane są sekwencje symboli:
digit excluding zero ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit ::= "0" | digit excluding zero ;
Ta reguła produkcji definiuje symbol nieterminalny digit, Znak "|" oddziela alternatywy, którymi są symbole terminalne w cudzysłowach a średnik kończy definicję.
Reguła może także zawierać sekwencję symboli terminalnych lub nieterminalnych, oddzielonych przecinkami:
twelve ::= "1" , "2" ; two hundred one ::= "2" , "0" , "1" ; three hundred twelve ::= "3" , twelve ; twelve thousand two hundred one ::= twelve , two hundred one ;
Wyrażenia które mogą być pomijane lub powtarzane można reprezentować biorąc je w nawiasy klamrowe { ... }:
natural number = digit excluding zero , { digit } ;
W tym wypadku ciągi 1, 2, ...,10,...,12345,... są poprawnymi wyrażeniami. Cokolwiek znajduje się w nawiasach klamrowych może być powtarzane dowolną liczbę razy, w tym ani razu.
Wyrażenie opcjonalne (występuje jeden raz, lub nie występuje) reprezentujemy przez wzięcie je w nawiasy kwadratowe [ ... ]:
integer = "0" | [ "-" ] , natural number ;
Stąd integer może być cyfrą zero lub ciągiem określonym przez natural number opcjonalnie poprzedzony znakiem minus.
[edytuj] Rozszerzenia zgodnie z normą ISO
Zgodnie z normą ISO 14977 standard EBNF ma być rozszerzalny. Wspomniano o dwóch udogodnieniach. Pierwsze jest częścią gramatyki EBNF, specjalną sekwencja, którą jest dowolny tekst ograniczony znakami zapytania, którego interpretacja jest poza zakresem standardu EBNF. Na przykład spacja może być zdefiniowana za pomocą następującej reguły:
space ::= ? US-ASCII character 32 ?;
Drugim jest wykorzystanie faktu, że nawiasy nie mogą występować za identyfikatorem. Następująca definicja nie ma poprawnej składni EBNF:
something ::= foo ( bar );
Więc ta notacja może być użyta do rozszerzenia EBNF. Na przykład w gramatyce Lispa funkcja application może być definiowana następująco:
function application ::= list( symbol , [ { expression } ] );
[edytuj] Motywycja rozszerzenia BNF
Problemem BNF jest to, że nie można wyrazić bezpośrednio powtórzeń i wystąpień opcjonalnych. Zamiast tego mamy pośrednie reguły i rekurencyjny sposób definiowania powtórzeń i opcji. Możliwość takiego sposobu definicji mamy również w EBNF.
Opcja:
signed number ::= [ sign , ] number ;
może być zdefiniowana w stylu BNF:
signed number ::= sign , number | number ;
lub
signed number ::= optional sign , number ; optional sign ::= ε | sign ; (* epsilon jest tu użyty do zaznaczenia pustej produkcji *)
Powtórzenia:
number ::= { digit } ;
mogą być zdefiniowane w stylu BNF:
number ::= digit | number digit;
[edytuj] Dodatki i modyfikacje
Notacja EBNF eliminuje kilka wad BNF:
- BNF używa symboli (<, >, |, ::=) dla siebie; gdy pojawią się one w języku który ma być definiowany, notacja BNF nie może być użyta bez modyfikacji i objaśnień.
- Składnia BNF może reprezentować wyłącznie jedną regułę w jednej linii.
EBNF rozwiązuje te problemy:
- Symbole terminalne są zamknięte pomiędzy znakami cudzysłowu ("..." lub '...'), a symbole w sekwencji rozdzielane przecinkami. Ostre nawiasy ("<...>") dla symboli nieterminalnych mogą zostać pominięte.
- Każdą regułę kończy znak ograniczający, zwykle średnik.
Ponadto istnieją mechanizmy ulepszenia definiujące ilość powtórzeń, wyłączanie (np. wszystkie znaki bez cudzysłowów), komentarze.
Pomimo wszystkich ulepszeń EBNF nie jest "silniejszy" w rozumieniu języka który może definiować. Gramatyka zdefiniowana w EBNF może być również reprezentowana w BNF.
[edytuj] Przykład
Prosty język programowania, który pozwala jedynie na przypisywanie, może być zdefiniowany w EBNF następująco:
(* a simple program 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 ? ;
Syntaktycznie poprawnym programem będzie:
PROGRAM DEMO1 BEGIN A0:=3; B:=45; H:=-100023; C:=A; D123:=B34A; BABOON:=GIRAFFE; TEXT:="Hello world!"; END.
