EBNF Genişletilmiş Backus-Naur formu

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Bilgisayar biliminde, Genişletilmiş Backus–Naur formu (EBNF) bağlamdan bağımsız dilbilgisini (context-free grammar) ifade etmek için kullanılan bir notasyondur. Başka bir ifadeyle, bilgisayar programlama dillerini ve biçimsel dilleri (formal languages) tanımlamanın bir yoludur. Backus–Naur formu (BNF) notasyonunu temel alır.

Niklaus Wirth tarafından geliştirilmiştir. En yaygın kullanılan türevleri standartlaştırılmıştır. ISO 14977

Konu başlıkları

[değiştir] Temel Bilgiler

Kod, örneğin bir bilgisayar programının kaynak kodu, terminal sembol olarak adlandırılan sembollerden oluşur. Bu semboller, karakterler, sayılar, noktalama işaretleri, boşluk işaretleri vb. olabilir.

EBNF, bu terminal sembol dizilerinin ilgili terminal olmayan (nonterminal) sembollere atanmasıyla oluşan üretim kuralını (production rule) tanımlar.


Örnek:

sifir haric sayi ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
sayi                 ::= "0" | sifir haric sayi ;

Bu üretim kuralı sol tarafta sayi adında terminal olmayan bir atama yapar. Dik çubuklar | alternatifleri gösterir (başka bir ifadeyle veya şeklinde de tanımlanabilir), kuralı oluşturan terminal semboller çift tırnak arasında verilmiş ve noktalı virgül ifadeyi sonlandırmıştır. sayi, 0 veya sifir haric sayi olarak ifadelendirildiğinden, bu kurala göre 0 ila 9 arasında değer alabilir.

Bir üretim kuralı virgül kullanarak terminal veya terminal olmayan semboller dizisi şeklinde de yazılabilir:


oniki                ::= "1" , "2" ;
ikiyuzbir            ::= "2" , "0" , "1" ;
ucyuzoniki           ::= "3" , oniki ;
onikibinikiyuzbir    ::= oniki , ikiyuzbir ;

Atlanabilir veya tekrarlanabilir ifadeler süslü parantez ile verilebilir { ... }:

dogal sayi ::= sifir haric sayi , { sayi } ;

Bu durumda, 1, 2, ...,10,...,12345,... sözceleri doğru ifadelerdir. Süslü parantez içinde verilene uygun ifade hiç kullanılmasa da, defalarca kullanılsa da doğrudur.

Köşeli parantez opsiyonlu kullanımı ifade eder [ ... ]:

tam sayi ::= "0" | [ "-" ] , dogal sayi ;

Bu kurala göre tam sayı sıfır veya işareti - olan veya olmayan bir doğal sayı olabilir.

EBNF ile yapılabilecek diğer şeyler arasında sembol tekrarına sınır koyabilme, üretim kuralında belli yerlere erişim engelleme veya açıklama kısımları ekleme gibi özellikleri sayabiliriz.


[değiştir] ISO standardına göre genişlemeler

ISO 14977 standardına göre EBNF genişletilebilirdir ve iki durumdan bahsedilir. Birincisi soru işareti arasında isteğe bağlı karakter katarı tanımlayabilmedir. Örneğin, boşluk karakteri aşağıdaki kuralla tanımlanabilir:

bosluk ::= ? US-ASCII character 32 ?;

İkinci durum şöyledir. Normalde etiket ifadeler parantez ile yazılamaz. Yani aşağıdaki şekil EBNF de geçersizdir:

something ::= foo ( bar );

Ancak EBNF nin bir uzantısı bu notasyonu kullanabilir. Örneğin, Lisp dilbilgisinde, bir fonksiyon aşağıdaki kuralla tanımlanabilir.

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

[değiştir] BNF yi genişletmek

The BNF had the problem that options and repetitions could not be directly expressed. Instead, they needed the use of an intermediate rule or alternative production defined to be either nothing or the optional production for option, or either the repeated production or itself, recursively, for repetition. The same constructs can still be used in EBNF.

Option:

signed number ::= [ sign , ] number ;

can be defined in BNF-style as:

signed number ::= sign , number | number ;

or

signed number ::= optional sign , number ;
optional sign ::= ε | sign ; (* epsilon is used to denote more clearly an empty production *)

Repetition:

number ::= { digit } ;

can be defined in BNF-style as:

number ::= digit | number digit;

[değiştir] Diğer eklemeler ve değişiklikler

EBNF BNF' nin bazı hatalarını düzeltir:

  • The BNF uses the symbols (<, >, |, ::=) for itself. When these appear in the language that is to be defined, the BNF can not be used without modifications and explanation.
  • A BNF-syntax can only represent a rule in one line.

The EBNF solves these problems:

  • Terminals are strictly enclosed within quotation marks ("..." or '...'). The angle brackets ("<...>") for nonterminals can be omitted.
  • A terminating character, usually a semicolon marks the end of a rule.

Furthermore there are mechanisms for enhancements, defining the number of repetitions, excluding alternatives (e.g. all characters excluding quotation marks), comments etc. provided.

Despite all enhancements, the EBNF is not "more powerful" than the BNF in the sense of the language it can define. As a matter of principle any grammar defined in EBNF can also be represented in BNF. However this often leads to a considerably larger representation.

The EBNF has been standardized by the ISO under the code ISO/IEC 14977:1996(E).

Under some circumstances any extended BNF is referred to as EBNF. For example the W3C uses one EBNF to specify XML.

[değiştir] Diğer bir örnek

EBNF' ye göre tanımlanmış atamalara izin veren basit bir programlama dili:

(* 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 ? ;

Yukarıdaki kurala göre söz dizimi doğru olan bir program:

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

Bu dil kontrol akışları, matematiksel ifadeler ve G/Ç komutlarıyla kolayca genişletilebilir, küçük ve kullanılabilir bir programlama dili haline getirilebilir.

Standartta normal gösterim olarak önerilen şu işaretler kullanıldı:

Kullanım Notasyon
definition =
concatenation ,
termination  ;
separation |
option [ ... ]
repetition { ... }
grouping ( ... )
double quotation marks " ... "
single quotation marks ' ... '
comment (* ... *)
special sequence  ? ... ?
exception -

[değiştir] Kurallar

1. The following conventions are used:

  • Each meta-identifier of Extended BNF is written as one or more words joined together by hyphens;
  • A meta-identifier ending with “-symbol” is the name of a terminal symbol of Extended BNF.

2. The normal character representing each operator of Extended BNF and its implied precedence is (highest precedence at the top):

* repetition-symbol
- except-symbol
, concatenate-symbol
| definition-separator-symbol
= defining-symbol
; terminator-symbol

3. The normal precedence is over-ridden by the following bracket pairs:

´  first-quote-symbol            first-quote-symbol  ´
"  second-quote-symbol          second-quote-symbol  "
(* start-comment-symbol          end-comment-symbol *)
(  start-group-symbol              end-group-symbol  )
[  start-option-symbol            end-option-symbol  ]
{  start-repeat-symbol            end-repeat-symbol  }
?  special-sequence-symbol   special-sequence-symbol ?

As examples, the following syntax-rules illustrate the facilities for expressing repetition:

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}, "D";

Terminal-strings defined by these rules are as follows:

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: D AAAD AAAAAAD etc.


[değiştir] İlgili çalışmalar

[değiştir] Şunları da inceleyin

[değiştir] Referanslar

  • Roger S. Scowen: Extended BNF — A generic base standard. Software Engineering Standards Symposium 1993.

[değiştir] Dış bağlantılar

"http://tr.wikipedia.org/w/index.php?title=EBNF_Genişletilmiş_Backus-Naur_formu&oldid=12997593" adresinden alındı.