Backus – Naur forma - Backus–Naur form

Nem tévesztendő össze a Boyce – Codd normál formával .

A számítástechnika , Backus-Naur formájában ( / ˌ b æ k ə s n aʊər / ) vagy Backus normál forma ( BNF ) egy metasyntax írásmód környezetfüggetlen nyelvtanok , gyakran használják, hogy leírja a szintaxis a nyelvek kiszámítása során alkalmazott, mint például a számítógépes programozási nyelvek , dokumentumformátumok , utasításkészletek és kommunikációs protokollok . Ezeket mindenhol alkalmazzák, ahol a nyelvek pontos leírására van szükség: például a hivatalos nyelvi specifikációkban, a kézikönyvekben és a programozási nyelvelméleti tankönyvekben.

Az eredeti Backus – Naur jelölés számos kiterjesztését és változatát használják; néhány pontosan meghatározott, beleértve a kiterjesztett Backus – Naur formát (EBNF) és a kiterjesztett Backus – Naur formát (ABNF).

Történelem

Az a gondolat, hogy a nyelv szerkezetét az átírási szabályok segítségével írják le , legalábbis Pāṇini munkájára vezethető vissza, aki egy ősi indiai szanszkrit nyelvtan és a hinduizmus egyik tisztelt tudósa, aki valamikor az i . E. 6. és 4. század között élt . A szanszkrit szószerkezet leírására vonatkozó jelölése hatalommal egyenértékű Backuséval, és sok hasonló tulajdonsággal rendelkezik.

A nyugati társadalomban a nyelvtant sokáig tanítás tárgyának tekintették, nem pedig tudományos tanulmányozásnak; a leírások informálisak és a gyakorlati felhasználást célozták. A 20. század első felében olyan nyelvészek , mint Leonard Bloomfield és Zellig Harris, kísérleteket tettek a nyelv leírásának, beleértve a kifejezésszerkezetet, formalizálására.

Eközben a karakterlánc -átírási szabályokat, mint formális logikai rendszereket olyan matematikusok vezették be és tanulmányozták, mint Axel Thue (1914 -ben), Emil Post (1920–40 -es évek) és Alan Turing (1936). Noam Chomsky , aki nyelvtant tanított az MIT információelméleti hallgatóinak , egyesítette a nyelvészetet és a matematikát úgy, hogy lényegében Thue formalizmusát vette alapul a természetes nyelv szintaxisának leírásához . Világos különbséget vezetett be a generatív szabályok (a kontextusmentes nyelvtanok szabályai) és az átalakítási szabályok (1956) között is.

John Backus , az IBM programozási nyelvtervezője "metanyelvi képletek" metanyelvét javasolta az új programozási nyelv IAL szintaxisának leírására, amelyet ma ALGOL 58 (1959) néven ismerünk . Jelölését először az ALGOL 60 jelentésben használták.

A BNF Chomsky kontextusmentes nyelvtanának jelölése. Backus ismerte Chomsky munkásságát.

A Backus javaslata szerint a képlet "osztályokat" határozott meg, amelyek neve szögletes zárójelben van. Például <ab>. E nevek mindegyike az alapvető szimbólumok osztályát jelöli.

Az ALGOL továbbfejlesztése az ALGOL 60 -hoz vezetett . A bizottság 1963 -as jelentésében Peter Naur Backus jelölését Backus normál formának nevezte . Donald Knuth azzal érvelt, hogy a BNF -et inkább Backus – Naur formaként kell értelmezni , mivel ez „nem normális forma a hagyományos értelemben”, ellentétben például Chomsky normál formájával . A Pāṇini Backus forma elnevezést is egyszer javasolták, tekintettel arra a tényre, hogy a Backus normál formája nem lehet pontos, és hogy Pāṇini korábban önállóan kifejlesztett egy hasonló jelölést.

A BNF -et Peter Naur írja le az ALGOL 60 jelentésében, mint metalingvisztikai képletet :

A zárójelben lévő karaktersorozatok <> olyan metalingvisztikai változókat képviselnek, amelyek értékei szimbólumok. A ":: =" és "|" jelölések (utóbbiak jelentése "vagy") metalingvisztikai összekötők. A képlet bármely jele, amely nem változó vagy összekötő, önmagát jelöli. A jelölések vagy változók egymás mellé helyezése a képletben a jelzett sorozat egymás mellé helyezését jelenti.

Az ALGOL 60 jelentés egy másik példája nagy különbséget mutat a BNF metanyelve és a Chomsky kontextusmentes nyelvtan között. A metalinguisztikus változók nem igényelnek szabályt, amely meghatározza a kialakulását. Kialakulásuk egyszerűen leírható természetes nyelven a <> zárójelek között. Az alábbi ALGOL 60 jelentés 2.3 szakasz megjegyzi a specifikációt, amely példázza ennek működését:

Annak érdekében, hogy a szöveget a program szimbólumai közé soroljuk, a következő megjegyzési konvenciók érvényesek:

Az alapvető szimbólumok sorrendje: egyenértékű
; comment <minden olyan sorozat, amely nem tartalmazza a ';'>>; ;
start comment <minden sorozat, amely nem tartalmazza a ';'>> -t; kezdődik
end <minden olyan sorozat, amely nem tartalmazza a 'end' vagy a ';' vagy "más"> vége

Az egyenértékűség itt azt jelenti, hogy a bal oldali oszlopban látható három szerkezet bármelyike ​​helyettesíthető a karakterláncokon kívül bármikor a jobb oldali oszlop azonos sorában látható szimbólummal, anélkül, hogy hatással lenne a program működésére.

Naur megváltoztatta Backus két szimbólumát a általánosan elérhető karakterekre. A ::=szimbólum eredetileg a :≡. A |szimbólum eredetileg a " vagy " szó volt (sáv fölött). Az IBM-nél dolgozó Backusnak titoktartási szerződése lett volna, és nem beszélhetett volna a forrásáról, ha az IBM tulajdonában álló projektből származik.

A BNF nagyon hasonlít a kanonikus alakú boole-algebra egyenletekhez, amelyeket akkor használtak a logikai áramkörök tervezésében. Backus matematikus volt és a FORTRAN programozási nyelv tervezője. A boolean algebra tanulmányai általában a matematika tantervének részét képezik. Annyit tudunk, hogy sem Backus, sem Naur nem írta le a < >terminálokba nem zárt neveket . Chomsky terminológiáját eredetileg nem használták a BNF leírására. Naur később úgy jellemezte őket, mint az ALGOL tananyagok osztályait. Az ALGOL 60 jelentésben metalingvisztikai változóknak nevezték őket. A metaszimbólumokon ::=, |és az osztályneveken kívül bármi más a < >definiált nyelv szimbóluma. A metaszimbólumokat ::=úgy kell értelmezni, hogy "definiálva van". Az |alternatív definíciók elválasztására szolgál, és "vagy" -ként értelmezik. A metaszimbólumok osztálynevet < >tartalmazó határolóelemek. A BNF -et Peter Naur és Saul Rosen metanyelvként írja le az ALGOL -ról .

1947 -ben Saul Rosen bekapcsolódott az újonnan induló Számítógép -gépek Szövetségének tevékenységébe , először a nyelvi bizottságba, amely az IAL -csoport lett, és végül az ALGOL -hoz vezetett. Ő volt az ACM kommunikációjának első ügyvezető szerkesztője. Annyit tudunk, hogy a BNF -et először metanyelvként használták az ALGOL nyelvről az ALGOL 60 jelentésben. Ezt magyarázza az ALGOL programozási tananyag, amelyet Peter Naur fejlesztett ki 1962 -ben. Az IBM, a Honeywell, a Burroughs és a Digital Equipment Corporation által készített ALGOL kézikönyvek az ALGOL 60 jelentését metanyelvként használták. Saul Rosen a könyvében leírja a BNF -et, mint egy metanyelvet az ALGOL -ról. A metanyelvként való felhasználásra példa lehet egy aritmetikai kifejezés meghatározása: 

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

Az alternatíva első szimbóluma lehet a definiált osztály, az ismétlés, amint azt Naur kifejtette, amelynek feladata annak meghatározása, hogy az alternatív szekvencia rekurzívan kezdődhet egy korábbi alternatívával, és tetszőleges számú alkalommal megismételhető. Például, a fenti <expr>definíció szerint egy <term>követ tetszőleges számú <addop> <term>.

Néhány későbbi metanyelvben, mint például Schorre META II -jében , a BNF rekurzív ismétlődő konstrukciót felváltja egy szekvencia operátor és az idézett karakterláncok segítségével meghatározott célnyelvi szimbólumok. A <és a >zárójeleket eltávolították. Zárójeleket ()adtunk hozzá a matematikai csoportosításhoz. A <expr>szabály a META II -ben így jelenik meg 

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

Ezek a változtatások lehetővé tették a META II -nek és a származékos programozási nyelveknek, hogy saját metanyelvüket határozzák meg és bővítsék ki, a természetes nyelvi leírás, a metalingvisztikai változó, a nyelvi konstrukció leírásának használatának árán. Sok spin-off metanyelvet a BNF inspirált. Lásd: META II , TREE-META és Metacompiler .

A BNF osztály egy nyelvi konstrukció képződményét írja le, a formációt mintázatként vagy a minta kialakításának műveleteként definiálva. Az osztálynév kifejezést természetes nyelven írják le, <term>amelyet egy sorozat követ <addop> <term>. Az osztály absztrakció; kialakulásától függetlenül beszélhetünk róla. Beszélhetünk a kifejezésről, függetlenül annak definíciójától, úgy, hogy hozzáadjuk vagy kivonjuk a kifejezést. Beszélhetünk arról, hogy egy kifejezés egy adott adattípus, és hogyan kell értékelni a kifejezést az adott típusú adattípusok kombinációjával. Vagy akár egy kifejezés átrendezése az adattípusok csoportosítására és a vegyes típusok értékelési eredményeire. A természetes nyelvű kiegészítés konkrét részleteket adott a nyelvórák szemantikájáról, amelyeket a fordító implementáció és az ALGOL programot író programozó használ. A természetes nyelvű leírás kiegészítette a szintaxist is. Az egész szám szabály jó példa a szintaxis leírására használt természetes és metanyelvre: 

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

A fentiekben nincsenek konkrétumok a fehér térről. Amennyire a szabály kimondja, a számjegyek között lehet szóköz. A természetes nyelvben kiegészítjük a BNF metanyelvét azzal, hogy elmagyarázzuk, hogy a számjegysor nem tartalmazhat szóközt a számjegyek között. Az angol csak az egyik lehetséges természetes nyelv. Az ALGOL jelentések fordításai számos természetes nyelven elérhetők voltak.

A BNF eredete nem olyan fontos, mint a programozási nyelv fejlesztésére gyakorolt ​​hatása. Az ALGOL 60 jelentés közzétételét közvetlenül követő időszakban a BNF számos fordító-fordító rendszer alapja volt .

Néhányan, például az Edgar T. Irons által kifejlesztett "A Syntax Directed Compiler for ALGOL 60" és a Brooker és Morris által kifejlesztett "A Compiler Building System" közvetlenül a BNF -et használták. Mások, például a Schorre Metacompilerek , csak néhány változtatással programozási nyelvvé tették. <class name>szimbólumazonosítók lettek, a mellékelt <,> elemet elhagyva, és a célnyelv szimbólumaihoz idézőjeles karakterláncokat használtak. Az aritmetikai jellegű csoportosítás egyszerűsítést biztosított, amely eltávolította azokat az osztályokat, ahol a csoportosítás volt az egyetlen érték. A META II számtani kifejezési szabály a csoportosítás használatát mutatja. A META II szabályba helyezett kimeneti kifejezéseket a kód és a címkék összeállítási nyelven történő kiadására használják. A META II szabályai egyenértékűek a BNF osztálydefinícióival. A yacc Unix segédprogram a BNF -en alapul, a META II -hez hasonló kódgyártással. yacc leggyakrabban használt, mint egy értelmező generátor , és a gyökerei nyilvánvalóan BNF.

A BNF ma az egyik legrégebben használt, számítógéppel kapcsolatos nyelv.

Bevezetés

A BNF specifikáció a származtatási szabályok halmaza, amelyet így írnak 

 <symbol> ::= __expression__

ahol a < szimbólum > nem terminális , és a __kifejezés__ egy vagy több szimbólum -sorozatból áll; több sorozatot elválaszt a függőleges "|" sáv , ami választást jelez , az egész a bal oldali szimbólum lehetséges helyettesítése. A bal oldalon soha nem megjelenő szimbólumok terminálok . Másrészt a bal oldalon megjelenő szimbólumok nem terminálok, és mindig a <> pár közé vannak zárva.

A ":: =" azt jelenti, hogy a bal oldali szimbólumot fel kell cserélni a jobb oldali kifejezésre.

Példa

Példaként tekintse meg ezt a lehetséges BNF -et egy amerikai postacím esetében : 

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

Ez angolra fordítva:

  • A postai cím a név-rész, majd egy street-address részét, majd egy zip-kód részét.
  • A névrész vagy a következőkből áll: egy személyes részből, amelyet egy vezetéknév követ egy választható utótag (ifj., Ifj. Vagy dinasztikus szám) és a sor vége , vagy egy személyes részből, amelyet egy névrész követ ( ez a szabály szemlélteti a rekurzió használatát a BNF -ekben, lefedve azoknak az esetét, akik több kereszt- és középnevet és kezdőbetűt használnak).
  • A személyes rész egy keresztnévből vagy egy kezdőbetűből áll , amelyet egy pont követ.
  • Az utca címe egy házszámból, egy utcanévből, egy opcionális lakás- specifikátorból, majd egy sorvégből áll.
  • A zip-rész egy város -name, majd egy vessző, majd egy állam kódját , majd egy ZIP-kódot, majd end-of-line.
  • Az opt-suffix rész utótagból áll, például "Sr.", "Jr." vagy római szám , vagy üres karakterlánc (azaz semmi).
  • Az opt-apt-num egy lakás számából vagy egy üres karakterláncból (azaz semmi) áll.

Ne feledje, hogy itt sok mindent (például a keresztnév formátumát, a lakásszámot, az irányítószámot és a római számot) itt nem kell megadni. Szükség esetén leírhatók további BNF szabályok használatával.

További példák

BNF szintaxis diagram
BNF szintaxis diagram

Maga a BNF szintaxisa BNF -el ábrázolható, az alábbiak szerint: 

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

Ne feledje, hogy a "" az üres karakterlánc .

Az eredeti BNF nem használt idézőjeleket, ahogy a <literal>szabály mutatja . Ez feltételezi, hogy a szabály helyes értelmezéséhez nincs szükség szóközre .

<EOL>a megfelelő sorvég- specifikátort képviseli ( ASCII-ben , kocsi-visszatérés, sor-előtolás vagy mindkettő az operációs rendszertől függően ). <rule-name>és <text>helyettesíteni kell egy deklarált szabály nevével/címkéjével vagy szó szerinti szövegével.

A fenti amerikai postacím-példában a teljes blokk-idézet szintaxis. Minden sor vagy sorok töretlen csoportosítása szabály; például egy szabály azzal kezdődik <name-part> ::=. E szabály másik része (a vonalvégén kívül) egy kifejezés, amely két, csővel elválasztott listából áll |. Ez a két lista néhány kifejezésből áll (három és két kifejezés). Ebben a szabályban minden kifejezés egy szabálynév.

Változatok

A BNF -nek számos változata és kiterjesztése létezik, általában vagy az egyszerűség és a tömörség kedvéért, vagy egy adott alkalmazáshoz való igazítás céljából. Sok változat egyik közös jellemzője a reguláris kifejezés ismétlődő operátorai, például az *és +. A kiterjesztett Backus – Naur forma (EBNF) gyakori.

Egy másik gyakori kiterjesztés a szögletes zárójel használata az opcionális elemek körül. Bár nincs jelen az eredeti ALGOL 60 jelentés (helyett bevezetett néhány évvel később az IBM „s PL / I meghatározás), a jelölés most általánosan elismert.

A kiterjesztett Backus – Naur űrlap (ABNF) és a Routing Backus – Naur űrlap (RBNF) az Internet Engineering Task Force (IETF) protokollok leírására általánosan használt kiterjesztések .

Az elemző kifejezési nyelvtanok a BNF -re és a reguláris kifejezések jelölésére épülnek, hogy a formális nyelvtan alternatív osztályát képezzék , amely lényegében analitikus, nem pedig generatív jellegű.

A BNF számos specifikációját ma az interneten találják, és ember által olvashatóak, és nem formálisak. Ezek gyakran az alábbi szintaktikai szabályok és bővítmények közül sokat tartalmaznak:

  • Választható tételek szögletes zárójelben : [<item-x>].
  • Tételek meglévő 0 vagy több alkalommal van zárójelbe tett vagy toldalékolt csillaggal ( *), például <word> ::= <letter> {<letter>}, vagy <word> ::= <letter> <letter>*rendre.
  • Az 1 vagy több alkalommal létező elemeket kiegészítés (plusz) szimbólummal toldják meg +, például <word> ::= <letter>+.
  • A terminálok félkövér betűkkel jelenhetnek meg, nem dőlt betűvel, a nem terminálok pedig egyszerű szöveggel, nem pedig zárójelben.
  • Ahol az elemek csoportosítva vannak, azokat egyszerű zárójelben kell elhelyezni.

BNF -et használó szoftver

  • ANTLR , egy másik Java -ban írt elemzőgenerátor
  • A Qlik Sense BI eszköz a BNF egyik változatát használja a szkripteléshez
  • BNF konverter (BNFC), amely a "címkézett Backus – Naur forma" (LBNF) nevű változaton működik. Ebben a változatban egy adott nem végberendezéshez tartozó minden produkció címkét kap, amely felhasználható az adott nemterminált képviselő algebrai adattípus konstruktoraként . Az átalakító több nyelven is képes típusokat és elemzőket előállítani az absztrakt szintaxishoz , beleértve a Haskell -t és a Java -t .
  • Coco/R , fordító generátor, amely az EBNF -ben hozzárendelt nyelvtant fogad el
  • DMS szoftver újratervezési eszközkészlet , programelemző és átalakító rendszer tetszőleges nyelvekhez
  • GOLD BNF elemző
  • GNU bölény , a yacc GNU változata
  • RPA BNF elemző. Online (PHP) demóelemzés: JavaScript, XML
  • XACT X4MR System, szabályalapú szakértői rendszer a programozási nyelv fordításához
  • XPL Analyzer, egy eszköz, amely elfogadja az egyszerűsített BNF -et egy nyelvhez, és előállít egy elemzőt az adott nyelvhez az XPL -ben; integrálható a mellékelt SKELETON programba, amellyel a nyelv hibakereshető (egy SHARE -közreműködő program, amelyet A Compiler Generator előzött meg )
  • Yacc , elemző generátor (leggyakrabban a Lex előfeldolgozónál használják)
  • bnfparser 2 , univerzális szintaxis -ellenőrző segédprogram
  • bnf2xml, Jelölő bemenet XML -címkékkel a fejlett BNF -egyezés használatával.
  • JavaCC, Java Compiler Compiler tm (JavaCC tm) - A Java Parser Generator.
  • Racket elemzőeszközei, lex és yacc stílusú elemzés (Beautiful Racket edition)
  • Belr , C ++ 11 nyelven írt elemzőgenerátor . ABNF -et használ .

Lásd még

Hivatkozások

Külső linkek

  • Garshol, Lars Marius, BNF és EBNF: Mik ezek és hogyan működnek? , NEM : Priv.
  • RFC  5234 - Kiterjesztett BNF a szintaxis specifikációihoz: ABNF.
  • RFC  5511 - Útválasztás BNF: A különböző protokoll specifikációkban használt szintaxis.
  • ISO / IEC 14977: 1996 (E) Információs technológia - szintaktikai metanyelv - Extended BNF , beszerezhető a "nyilvánosan elérhető" Standards , ISOvagy Kuhn, Marcus, Iso 14977 (PDF) , Egyesült Királyság : CAM (utóbbiról hiányzik a címlap, de egyébként sokkal tisztább)

Nyelvi nyelvtanok