Backus–Naur-forma

A Wikipédiából, a szabad enciklopédiából
(Backus–Naur forma szócikkből átirányítva)
Ugrás a navigációhoz Ugrás a kereséshez

A Backus–Naur-forma (ismert még, mint BNF, vagy Backus–Naur-formalizmus, Backus–normálforma, Bacus–Naur-forma, vagy Pánini–Backus-forma) környezetfüggetlen nyelvtanok leírására használható metaszintaxis: végeredményben formális nyelvek is leírhatók vele.

A BNF széles körben használatos a számítógépek programozási nyelveinek nyelvtanának leírására, ideértve az utasítás készleteket és a kommunikációs protokollokat is, valamint egyes természetes nyelvek nyelvtanának (pl. meter a szanszkrit költészetben.) A legtöbb programozási nyelv elméleti leírása és/vagy szemantikai dokumentumai általában BNF-ban vannak leírva.

A BNF-nek több bővítése és változata létezik és van használatban.

Története[szerkesztés]

A jelölési rendszert John Backus hozta létre az ALGOL nyelvtanának leírására. Az első, 1959-ben, Párizsban megtartott "World Computer Congress"-on mutatta be Backus a rendszerét a "The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM Conference" – a zürichi ACM-GAMM konferencián javasolt a nemzetközi algebrai nyelv szintaxisa és szemantikája – előadásában. A nemzetközi algebrai nyelv leírása később ALGOL 58 néven vált ismertté. Az ismertetett formális nyelv Emil Post produkciós rendszerén alapul. A generatív nyelvtanokat már matematikai módszerekkel többen is tanulmányozták, közöttük Noam Chomsky, aki ezeket a formális leírásokat a természetes nyelvekre is alkalmazta.[1][2]

Peter Naur később egyszerűsítette Backus jelöléseit, minimalizálta a használt karakterek számát, ezért Donald Knuth javaslatára, a hozzájárulásáért a neve megjelent a jelölési mód elnevezésében.

A Backus–Naur Forma vagy BNF nyelvtanok nagyon hasonlóak a Pánini nyelvtani szabályaihoz, ezért erre a jelölésre gyakran Panini–Backus Forma néven is hivatkoznak.

Összefoglaló[szerkesztés]

Egy BNF leírás valójában leszármaztatási szabályok halmaza, amelyeket a következő formában írnak fel: 

<szimbólum> ::= <kifejezés a szimbólumra>

ahol <szimbólum> egy nemterminális elem, a ::= jelölés (olvasd: négypont egyenlő) választja el a szimbólumot a leszármaztatási szabálytól, ami egy kifejezés. Ez a kifejezés tartalmazza a szimbólumok sorozatát és/vagy egymástól a függőleges vonal, '|', karterrel elválasztott sorozatokat (a '|' jel a választást jelenti – olvasd: vagy). A szabály bal oldala valójában azt mutatja, mivel/mikkel helyettesíthető a jobb oldalon álló szimbólum. Az a szimbólum, amely soha sem bukkan fel szabály bal oldalán, az úgynevezett terminális.

1. példa[szerkesztés]

A fentiek illusztrálására nézzük meg egy (egyszerűsített) postai cím BNF leírását: 

<postai_cím> ::= <név_rész> "," <irányítószám_rész> " " <cím_rész>
<név_rész> ::= <személyi_rész> <keresztnév> | <név_rész> <keresztnév>
<személyi_rész> ::= <titulus> "."" "<vezetéknév>|<vezetéknév>" "
<cím_rész> ::= <kerület> <elnevezés> <közterület_tipus> <szám> <EOL>
<közterület_tipus> ::= "utca"|"tér"|"körút"|"lépcső"|"u."|"krt."
<irányítószám_rész> ::= <ország_kód>"-"<irányítószám_belső>| <irányítószám_belső>
<irányítószám_belső> ::= <irányítószám>" "<városnév> ","

magyarra fordítva:

  • ez a bizonyos postai cím tartalmaz egy név részt, amit egy <,> választ el az irányítószám résztől, amit egy szóköz követ, majd a cím a „tényleges” címrésszel zárul.
  • a név rész vagy : egy személyi részből áll, amit a keresztnév követ, vagy – és ez egyben a BNF rekurzív lehetőségeit mutatja – egy személyi rész, amit ismét a keresztnév követ. Ez a megoldás biztosítja, hogy például egy esetleges második keresztnév is megjeleníthető legyen.
  • a személyi rész vagy egy titulusból (Dr, id, özv, ifj stb.), amit egy pont követ és a vezetéknévből, vagy csak egy vezetéknévből állhat össze.
  • a cím részt kerület, elnevezés, közterület típus és szám alkotja, amit egy EOL (end_of_line) záró szimbólum követ. Az elnevezés lesz tulajdonképpen annak a bizonyos közterület típusnak a neve (gyakorlatilag az utca, tér stb. neve).
  • a közterület típus azonosítja, hogy „minek” a nevéről van szó, esetünkben ez vagy utca, vagy annak rövidítése, u. vagy tér, vagy körút, vagy ennek rövidítése krt., vagy lépcső.
  • az irányítószám rész vagy egy országkód, amit <-> követ és egy irányítószám és városnév, vagy csak egy irányítószám és városnév lehet.
  • az irányítószám és a városnév egymástól egy szóközzel van elválasztva, és egy <,> vessző a záró karaktere.

Meg kell jegyezni, hogy a fenti leírás korán sem teljes, hiszen nincsen pontosan definiálva, hogy mit is kell például ország_kód vagy akár irányítószám alatt érteni (annak ellenére, hogy tudjuk, mi is az irányítószám – esetünkben ez elég is). Egy programozási nyelv leírásakor viszont pontosan le kell írni mindent, ezért gyakran úgy kezdődnek a leírások, hogy megadják, mit kell betű alatt érteni, és mit kell szám alatt érteni, mik a fenntartott karakterek (ha vannak), szavak, stb., és csak ezután kezdődik a nyelv szintaxisának leírása.

2. példa[szerkesztés]

A BNF szintaxis leírható a BNF saját jelölési módjával, a következők szerint: 

<szintaxis> ::= <szabály> | <szabály> <szintaxis>
<szabály> ::= <opc-szóköz> "<" <szabály-név> ">" <opc-szóköz> "::="
           <opc-szóköz> <kifejezés> <sorvég>
<opc-szóköz> ::= " " <opc-szóköz> | ""  
<kifejezés> ::= <lista> | <lista> "|" <kifejezés>
<sorvég> ::= <opc-szóköz> <EOL> | <soremelés> <sorvég>
<lista> ::= <term> | <term> <opc-szóköz> <lista>
<term> ::= <literál> | "<" <szabály-név> ">"
<literál> ::= '"' <szöveg> '"' | "'" <szöveg> "'"

Feltételeztük, hogy a szabályok elemzéséhez nincsen szükség az opc_szóköz (whitespace) karakterre. Az <EOL> megfelel a használt sor vég jelző karakternek (az ASCII kódban ez a kocsi-vissza és/vagy soremelés, de a konkrét megvalósítás operációs rendszer függő). A <szabály-név> és a <szöveg> helyettesítendő az aktuális szabály nevével, címkéjével vagy leíró szövegével.

Változatok[szerkesztés]

A BNF-nek több változata és kiterjesztése létezik, amelyeket vagy leírással kapcsolatos speciális igények, vagy pedig a további egyszerűsítésekre illetve hatékonyságra való törekvések hoztak létre. Közös ezekben a változatokban a szabályos kifejezések ismétlési műveleteinek, mint a * and + a használata. Az Extended Backus-Naur form (EBNF) a legismertebb ezek közül. A fenti példa sem felel meg pontosan az "ALGOL 60 report" jelölésmódjának. A "[ ]" zárójelek használata néhány évvel később, az IBM PL/I-es nyelvének meghatározásánál kezdődött, de azóta általánosan elfogadottá vált. Az ABNF a másik bővítés, amelyet az IETF használt protokollok leírására.

Parsing expression nyelvtanok is felépíthetők a BNF használatával, és a szabályos kifejezések jelölései is formalizálhatók, mint egy lehetséges osztálya a formális nyelvtanoknak. A BNF használata kevésbé jellemző az analitikus, mint a generatív nyelvtanok leírásánál.

Ma már számos BNF specifikáció található online, amelyek jól olvashatók és nem annyira formálisak. Ezeknél gyakran a következő szintaktikai szabályokat használják, bővítésként:

  • Az opcionális elemeket szögletes zárójelek közé kell tenni, például [<elem-x>]
  • A 0-szor vagy többször ismétlődő elemeket kapcsos zárójelek közé kell tenni, például <szó> ::= <betű> { <betű> }
  • az 1-szer vagy többször ismétlődő elemeket '+' követi.
  • A terminális elemeket vastagon, míg a nemterminális elemeket pedig normál szöveggel szedik
  • Egy elem ismétlődését az elem utáni csillag ‘*’ karakterrel jelölik.
  • Az alternatív lehetőségeket a ‘|’ jelek választják el egymástól, például <A_alternatíva>|<B_alternatíva>
  • Ha az elemeket csoportba kell foglalni, akkor arra a normál zárójeleket használják.

Források[szerkesztés]

  1. ↑ Chomsky, Noam, "Three Models for the Description of Language," IRE Transactions on Information Theory, Vol. 2 No. 2, pp. 113-123, 1956.
  2. ↑ Chomsky, Noam, Syntactic Structures, Mouton, The Hague, 1957.

Kapcsolódó szócikkek[szerkesztés]

Egyéb külső, angol nyelvű referenciák, kapcsolatok[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Backus–Naur-forma&oldid=20171778”