Backus–Naur formu - Backus–Naur form

Olarak bilgisayar biliminin , Backus Naur biçimi ( / ˌ b æ k ə s n aʊər / ) ya da Backus, normal bir şekilde ( BNF ) a, metasyntax için gösterim bağlam serbest gramerlerin genellikle tarif etmek için kullanılan, sözdizimi ve dil , hesaplamada kullanılan bilgisayar programlama dilleri , belge biçimleri , komut setleri ve iletişim protokolleri gibi. Dillerin tam tanımlarına ihtiyaç duyulan her yerde uygulanırlar: örneğin, resmi dil belirtimlerinde, kılavuzlarda ve programlama dili teorisi üzerine ders kitaplarında.

Orijinal Backus–Naur notasyonunun birçok uzantısı ve varyantı kullanılır; genişletilmiş Backus–Naur formu (EBNF) ve artırılmış Backus–Naur formu (ABNF) dahil, bazıları tam olarak tanımlanmıştır .

Tarih

Yeniden yazma kurallarını kullanarak dilin yapısını tanımlama fikri, en azından eski bir Hintli Sanskritçe gramer ve Hinduizm'de 6. ve 4. yüzyıllar arasında yaşamış saygı duyulan bir bilgin olan Pāṇini'nin çalışmasına kadar götürülebilir . Sanskritçe kelime yapısını tanımlama notasyonu , Backus'unkine eşdeğerdir ve birçok benzer özelliğe sahiptir.

Batı toplumunda dilbilgisi, uzun zamandır bilimsel bir çalışmadan ziyade bir öğretim konusu olarak görülüyordu; açıklamalar gayri resmiydi ve pratik kullanıma yönelikti. 20. yüzyılın ilk yarısında, Leonard Bloomfield ve Zellig Harris gibi dilbilimciler , cümle yapısı da dahil olmak üzere dilin tanımını resmileştirme girişimlerine başladılar.

Bu arada, biçimsel mantıksal sistemler olarak dizi yeniden yazma kuralları , Axel Thue (1914'te), Emil Post (1920'ler-40'lar) ve Alan Turing (1936) gibi matematikçiler tarafından tanıtıldı ve incelendi . Noam Chomsky , öğrencilerine dilbilim bilgi teorisi de MIT esasen sözdizimi açıklaması için temel olarak Thue en biçimciliği ne alarak, kombine dilbilim ve matematik doğal dil . Ayrıca üretici kurallar ( bağlamdan bağımsız dilbilgisi kuralları) ile dönüşüm kuralları (1956) arasında net bir ayrım yaptı .

John Backus , bir programlama dili tasarımcı IBM , önerilen bir üstdil olarak bugün bilinen yeni programlama dili IAL, sözdizimini tanımlamak için "üstdilsel formüller" nin ALGOL 58 (1959). Notasyonu ilk olarak ALGOL 60 raporunda kullanılmıştır.

BNF, Chomsky'nin bağlamdan bağımsız gramerleri için bir gösterimdir. Backus, Chomsky'nin çalışmalarına aşinaydı.

Backus tarafından önerildiği gibi, formül, adları köşeli parantezler içine alınmış "sınıfları" tanımladı. Örneğin, <ab>. Bu isimlerin her biri bir temel semboller sınıfını ifade eder.

ALGOL'un daha da geliştirilmesi ALGOL 60'a yol açtı . Komitenin 1963 tarihli raporunda, Peter Naur Backus'un notasyonunu Backus normal form olarak adlandırdı . Donald Knuth , örneğin Chomsky normal formunun aksine, BNF'nin "geleneksel anlamda normal bir form olmadığı" için Backus-Naur formu olarak okunması gerektiğini savundu . Pāṇini Backus formu adı da bir zamanlar Backus normal formunun genişlemesinin doğru olmayabileceği ve Pāṇini'nin daha önce bağımsız olarak benzer bir gösterim geliştirmiş olduğu gerçeği ışığında önerildi .

BNF, Peter Naur tarafından ALGOL 60 raporunda üst dilsel formül olarak tanımlanmaktadır :

Parantez <> içine alınmış karakter dizileri, değerleri sembol dizileri olan üst dil değişkenlerini temsil eder. "::=" ve "|" işaretleri (ikincisi "veya" anlamına gelir) üstdilsel bağlaçlardır. Bir formüldeki değişken veya bağlayıcı olmayan herhangi bir işaret kendini ifade eder. Bir formüldeki işaretlerin veya değişkenlerin yan yana gelmesi, belirtilen dizinin yan yana getirilmesi anlamına gelir.

ALGOL 60 raporundan bir başka örnek, BNF üst dili ile Chomsky bağlamından bağımsız dilbilgisi arasındaki büyük bir farkı göstermektedir. Üst dilsel değişkenler, oluşumlarını tanımlayan bir kural gerektirmez. Oluşumları, <> parantezleri içinde doğal dilde basitçe tanımlanabilir. Aşağıdaki ALGOL 60 rapor bölümü 2.3 yorum spesifikasyonu, bunun nasıl çalıştığını örneklemektedir:

Bir programın sembolleri arasına metin eklemek amacıyla aşağıdaki "yorum" kuralları geçerlidir:

Temel sembollerin sırası: eşdeğerdir
; yorum <';' içermeyen herhangi bir dizi>; ;
yoruma başla <';' içermeyen herhangi bir dizi>; başlamak
end <'end' veya ';' içermeyen herhangi bir dizi veya 'başka'> son

Buradaki eşdeğerlik, sol sütunda gösterilen üç yapıdan herhangi birinin, dizelerin dışında herhangi bir durumda, programın eylemi üzerinde herhangi bir etkisi olmaksızın, sağ sütunda aynı satırda gösterilen sembolle değiştirilebileceği anlamına gelir.

Naur, Backus'un iki sembolünü yaygın olarak bulunan karakterlerle değiştirdi. ::=Sembol aslında bir oldu :≡. |Sembol kelime "aslen veya (üzerinde bir bar ile)". IBM için çalışan Backus, bir ifşa etmeme anlaşmasına sahip olacaktı ve IBM'e ait bir projeden geliyorsa kaynağı hakkında konuşamazdı.

BNF, mantık devresi tasarımında kullanılan ve o sırada kullanılan kanonik biçimli boole cebir denklemlerine çok benzer . Backus bir matematikçiydi ve FORTRAN programlama dilinin tasarımcısıydı. Boole cebri çalışmaları genellikle matematik müfredatının bir parçasıdır. Bildiğimiz şey, ne Backus'un ne de Naur'un, içine alınan isimleri < >terminal olmayan olarak tanımlamadığıdır . Chomsky'nin terminolojisi başlangıçta BNF'yi tanımlarken kullanılmamıştı. Naur daha sonra bunları ALGOL ders materyallerinde sınıflar olarak tanımladı. ALGOL 60 raporunda bunlara üst dilsel değişkenler deniyordu. İçindeki metasemboller ::=, |ve sınıf adları dışındaki her şey , < >tanımlanan dilin simgeleridir. Metasemboller ::="olarak tanımlanır" olarak yorumlanmalıdır. |Alternatif tanımları ayırmak için kullanılır ve "ya da" olarak yorumlanır. Metasemboller < >, bir sınıf adını içeren sınırlayıcılardır. BNF, Peter Naur ve Saul Rosen tarafından ALGOL hakkında konuşmak için bir üst dil olarak tanımlanmaktadır .

1947'de Saul Rosen , ilk olarak IAL grubu haline gelen ve sonunda ALGOL'a yol açan diller komitesinde , yeni kurulan Bilgisayar Makineleri Derneği'nin faaliyetlerine dahil oldu. ACM Communications'ın ilk yönetici editörüydü. Bildiğimiz şey, BNF'nin ilk olarak ALGOL 60 raporunda ALGOL dili hakkında konuşmak için bir üst dil olarak kullanıldığıdır. 1962'de Peter Naur tarafından geliştirilen ALGOL programlama kursu materyalinde bu şekilde açıklanmıştır. IBM, Honeywell, Burroughs ve Digital Equipment Corporation'ın ilk ALGOL kılavuzları, onu bir üst dil olarak kullanan ALGOL 60 raporunu izlemiştir. Saul Rosen kitabında BNF'yi ALGOL hakkında konuşmak için bir üst dil olarak tanımlıyor. Bir üst dil olarak kullanımına bir örnek, aritmetik bir ifadenin tanımlanması olabilir:

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

Bir alternatifin ilk sembolü, tanımlanan sınıf olabilir, Naur tarafından açıklandığı gibi, alternatif dizinin yinelemeli olarak önceki bir alternatifle başlayabileceğini ve herhangi bir sayıda tekrarlanabileceğini belirtme işlevine sahip tekrar. Örneğin, yukarıda herhangi bir sayının ardından bir sayı <expr>olarak tanımlanır . <term><addop> <term>

Schorre'nin META II'si gibi daha sonraki bazı metadillerde , BNF özyinelemeli tekrar yapısı, bir dizi operatörü ve alıntılanmış dizeler kullanılarak tanımlanan hedef dil sembolleri ile değiştirilir. <Ve >parantez uzaklaştırılmıştır. ()Matematiksel gruplama için parantezler eklendi. <expr>Kural olarak META II'de görünür

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

Bu değişiklikler, META II ve türev programlama dillerinin, doğal bir dil tanımı, üst dilsel değişken, dil yapısı açıklaması kullanma yeteneği pahasına kendi üst dillerini tanımlamasını ve genişletmesini sağladı. Birçok spin-off meta dili BNF'den ilham almıştır. Bkz. META II , TREE-META ve Metacompiler .

Bir BNF sınıfı, bir kalıp veya kalıp oluşturma eylemi olarak tanımlanan oluşum ile bir dil yapısı oluşumunu tanımlar. Sınıf adı expr, doğal bir dilde, <term>ardından bir dizi olarak tanımlanır <addop> <term>. Bir sınıf bir soyutlamadır; oluşumundan bağımsız olarak ondan bahsedebiliriz. Terimden, tanımından bağımsız olarak, ifadede toplama veya çıkarma şeklinde bahsedebiliriz. Belirli bir veri türü olan bir terimden ve belirli veri türleri kombinasyonlarına sahip bir ifadenin nasıl değerlendirileceğinden bahsedebiliriz. Veya veri türlerini ve karma türlerin değerlendirme sonuçlarını gruplamak için bir ifadeyi yeniden sıralamak. Doğal dil eki, bir derleyici uygulaması ve bir ALGOL programı yazan bir programcı tarafından kullanılacak dil sınıfı semantiğinin belirli ayrıntılarını sağladı. Doğal dilde betimleme sözdizimini daha da destekledi. Tamsayı kuralı, söz dizimini tanımlamak için kullanılan doğal ve üst dilin iyi bir örneğidir:

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

Yukarıdaki beyaz boşlukla ilgili hiçbir özellik yoktur. Kuralın belirttiği kadarıyla, rakamlar arasında boşluk olabilir. Doğal dilde, BNF üst dilini, basamak dizisinin basamaklar arasında boşluk olamayacağını açıklayarak tamamlarız. İngilizce olası doğal dillerden sadece biridir. ALGOL raporlarının çevirileri birçok doğal dilde mevcuttu.

BNF'nin kökeni, programlama dili gelişimi üzerindeki etkisi kadar önemli değildir. ALGOL 60 raporunun yayınlanmasından hemen sonraki dönemde BNF, birçok derleyici-derleyici sisteminin temeliydi .

Edgar T. Irons tarafından geliştirilen "ALGOL 60 için Sözdizimi Yönlendirilmiş Derleyici" ve Brooker ve Morris tarafından geliştirilen "Bir Derleyici Oluşturma Sistemi" gibi bazıları doğrudan BNF'yi kullandı. Schorre Metacompilers gibi diğerleri, onu yalnızca birkaç değişiklikle bir programlama dili haline getirdi. <class name><,> ekini bırakarak ve hedef dilin sembolleri için tırnak içine alınmış dizeleri kullanarak sembol tanımlayıcıları haline geldi. Aritmetik benzeri gruplama, gruplandırmanın tek değeri olduğu sınıfları kullanmayı kaldıran bir basitleştirme sağladı. META II aritmetik ifade kuralı, gruplama kullanımını gösterir. Bir META II kuralına yerleştirilen çıktı ifadeleri, bir montaj dilinde kod ve etiketlerin çıktısını almak için kullanılır. META II'deki kurallar, BNF'deki sınıf tanımlarına eşdeğerdir. Unix yardımcı programı yacc , META II'ye benzer kod üretimiyle BNF'ye dayanmaktadır. yacc en yaygın olarak ayrıştırıcı üreteci olarak kullanılır ve kökleri açıkça BNF'dir.

BNF bugün hala kullanımda olan bilgisayarla ilgili en eski dillerden biridir.

Tanıtım

Bir BNF belirtimi, şu şekilde yazılmış bir dizi türetme kuralıdır:

 <symbol> ::= __expression__

< symbol > bir uçbirim dışıdır ve __ifade__ bir veya daha fazla sembol dizisinden oluşur; daha fazla dizi, bir seçimi belirten dikey çubuk "|" ile ayrılır , tümü soldaki sembolün olası bir ikamesidir. Asla sol tarafta görünmeyen semboller terminallerdir . Öte yandan, sol tarafta görünen semboller terminal değildir ve her zaman <> çifti arasına alınır.

"::=", soldaki sembolün sağdaki ifadeyle değiştirilmesi gerektiği anlamına gelir.

Örnek

Örnek olarak, bir ABD posta adresi için bu olası BNF'yi düşünün :

 <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> | ""

Bu, İngilizce'ye şu şekilde çevrilir:

  • Bir posta adresi, bir ad bölümünden, ardından bir sokak adresi bölümünden ve ardından bir posta kodu bölümünden oluşur.
  • Bir ad bölümü şunlardan oluşur: bir kişisel bölümün ardından bir soyadı ve ardından isteğe bağlı bir sonek (Jr., Sr. veya hanedan numarası) ve satır sonu veya kişisel bir bölüm ve ardından bir ad bölümü ( bu kural , BNF'lerde özyinelemenin kullanımını gösterir ve birden çok ad ve ikinci ad ve baş harf kullanan kişilerin durumunu kapsar).
  • Kişisel bölüm, ya bir ad ya da bir ilk ve ardından bir noktadan oluşur.
  • Bir sokak adresi, bir ev numarası, ardından bir sokak adı, ardından isteğe bağlı bir apartman belirteci ve ardından bir satır sonundan oluşur.
  • Bir posta bölümü, bir kasaba -adı, ardından bir virgül, ardından bir eyalet kodu , ardından bir posta kodu ve ardından bir satır sonundan oluşur.
  • Bir opt-soneki bölümü, "Sr.", "Jr." gibi bir son ekten oluşur. veya bir romen rakamı veya boş bir dize (yani hiçbir şey).
  • Opt-apt-num, bir daire numarasından veya boş bir dizeden (yani hiçbir şeyden) oluşur.

Burada birçok şeyin (bir ad biçimi, apartman numarası, posta kodu ve Romen rakamı gibi) belirtilmediğini unutmayın. Gerekirse, ek BNF kuralları kullanılarak tanımlanabilirler.

Diğer örnekler

BNF'nin sözdiziminin kendisi aşağıdaki gibi bir BNF ile temsil edilebilir:

 <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> | "-"

"" öğesinin boş dize olduğuna dikkat edin .

Orijinal BNF, <literal>kuralda gösterildiği gibi tırnak kullanmadı . Bu , kuralın uygun şekilde yorumlanması için boşluk gerekmediğini varsayar .

<EOL>uygun satır sonu belirtecini temsil eder ( işletim sistemine bağlı olarak ASCII , satır başı, satır besleme veya her ikisinde de ). ve sırasıyla beyan edilmiş bir kuralın adı/etiketi veya gerçek metni ile değiştirilecektir. <rule-name><text>

Yukarıdaki ABD posta adresi örneğinde, tüm blok alıntı bir sözdizimidir. Her satır veya satırların kesintisiz gruplandırılması bir kuraldır; örneğin bir kural ile başlar <name-part> ::=. Bu kuralın diğer kısmı (bir satır sonu dışında), bir boru ile ayrılmış iki listeden oluşan bir ifadedir |. Bu iki liste bazı terimlerden oluşur (sırasıyla üç terim ve iki terim). Bu özel kuraldaki her terim bir kural adıdır.

Varyantlar

BNF'nin genellikle basitlik ve özlülük adına veya belirli bir uygulamaya uyarlamak için birçok varyantı ve uzantısı vardır. Birçok varyantın ortak bir özelliği, ve gibi düzenli ifade tekrarlama operatörlerinin kullanılmasıdır . Backus-Naur formu (EBNF), ortak bir tanesidir. *+

Diğer bir yaygın uzantı, isteğe bağlı öğelerin etrafında köşeli parantez kullanılmasıdır. Orijinal ALGOL 60 raporunda mevcut olmamakla birlikte (yerine bir kaç yıl sonra tanıtıldı IBM'in 'ın PL / I , gösterim artık genel olarak kabul edilmektedir tanım).

Artırılmış Backus–Naur formu (ABNF) ve Yönlendirme Backus–Naur formu (RBNF), İnternet Mühendisliği Görev Gücü (IETF) protokollerini tanımlamak için yaygın olarak kullanılan uzantılardır .

Ayrıştırma ifadesi dilbilgisi , karakter olarak üretken olmaktan ziyade esasen analitik olan alternatif bir biçimsel dilbilgisi sınıfı oluşturmak için BNF ve düzenli ifade gösterimleri üzerine kuruludur .

Bugün çevrimiçi olarak bulunan birçok BNF spesifikasyonunun insan tarafından okunabilir olması amaçlanmıştır ve resmi değildir. Bunlar genellikle aşağıdaki sözdizimi kurallarının ve uzantılarının çoğunu içerir:

  • Köşeli parantez içine alınmış isteğe bağlı öğeler: [<item-x>].
  • 0 veya daha fazla kez mevcut olan öğeler, küme parantezleri içine alınır veya sırasıyla veya *gibi bir yıldız işareti ( ) ile eklenir .<word> ::= <letter> {<letter>}<word> ::= <letter> <letter>*
  • 1 ya da daha fazla kez mevcut ürünler, bir ilave (artı) sembolü ile ekli olan +gibi <word> ::= <letter>+.
  • Terminaller italik yerine kalın olarak ve terminal olmayanlar köşeli ayraçlar yerine düz metin olarak görünebilir.
  • Öğelerin gruplandırıldığı yerlerde basit parantez içine alınır.

BNF kullanan yazılım

  • ANTLR , Java ile yazılmış başka bir ayrıştırıcı üreteci
  • Bir BI aracı olan Qlik Sense, komut dosyası oluşturmak için BNF'nin bir türevini kullanır
  • BNF Dönüştürücü (BNFC), "etiketli Backus–Naur formu" (LBNF) adı verilen bir varyantta çalışır. Bu varyantta, belirli bir terminal olmayan için her üretime, o terminal olmayanı temsil eden bir cebirsel veri tipinin yapıcısı olarak kullanılabilen bir etiket verilir. Dönüştürücü, Haskell ve Java dahil olmak üzere birçok dilde soyut sözdizimi için türler ve ayrıştırıcılar üretebilir .
  • Coco/R , EBNF'de atfedilen bir dilbilgisini kabul eden derleyici oluşturucu
  • DMS Software Reengineering Toolkit , isteğe bağlı diller için program analizi ve dönüştürme sistemi
  • ALTIN BNF ayrıştırıcı
  • GNU bizonu , yacc'ın GNU versiyonu
  • RPA BNF ayrıştırıcısı. Çevrimiçi (PHP) demo ayrıştırma: JavaScript, XML
  • XACT X4MR Sistemi, programlama dili çevirisi için kural tabanlı bir uzman sistem
  • Bir dil için basitleştirilmiş BNF'yi kabul eden ve XPL'de o dil için bir ayrıştırıcı üreten bir araç olan XPL Analyzer; dilin hatalarının ayıklanabileceği sağlanan SKELETON programına entegre edilebilir ( öncesinde A Compiler Generator olan SHARE katkılı bir program )
  • Yacc , ayrıştırıcı üreteci (en yaygın olarak Lex önişlemcisi ile kullanılır )
  • bnfparser 2 , evrensel bir sözdizimi doğrulama aracı
  • bnf2xml, Gelişmiş BNF eşleştirmesini kullanarak XML etiketleriyle İşaretleme girişi.
  • JavaCC, Java Derleyici Derleyici tm (JavaCC tm) - Java Ayrıştırıcı Oluşturucu.
  • Racket'in ayrıştırıcı araçları , lex ve yacc tarzı Ayrıştırma (Beautiful Racket sürümü)
  • Belr , C++11 ile yazılmış bir ayrıştırıcı üreteci. ABNF'yi kullanır .

Ayrıca bakınız

Referanslar

Dış bağlantılar

  • Garshol, Lars Marius, BNF ve EBNF: Bunlar nedir ve nasıl çalışırlar? , HAYIR : Özel.
  • RFC  5234 — Sözdizimi Spesifikasyonları için Artırılmış BNF: ABNF.
  • RFC  5511 — Yönlendirme BNF: Çeşitli Protokol Spesifikasyonlarında Kullanılan Bir Sözdizimi.
  • ISO/IEC 14977:1996(E) Bilgi teknolojisi – Sözdizimsel metadil – Genişletilmiş BNF , "Genel kullanıma açık", Standartlar , ISOveya Kuhn, Marcus, Iso 14977 (PDF) , İngiltere'den : CAM (ikincisi kapak sayfası eksik, ancak bunun dışında çok daha temiz)

Dil gramerleri