1. B1. Nyelvek definiálása Backus–Naur-Formában (BNF)

Jelen könyvben definiáltunk néhány nyelvet, az ítéletlogika nyelvét (7.4. szakasz - Az ítéletkalkulus: egy nagyon egyszerű logika rész), az elsőrendű logika nyelvét (8.2.2. szakasz - Szimbólumok és interpretációk rész) és az angol nyelv részhalmazát (22.4. szakasz - Kiterjesztett nyelvtanok rész). Egy formális nyelvet mondathalmazként definiálunk, ahol egy-egy mondat a szimbólumok halmaza. A számunkra érdekes nyelvek mindegyike végtelen sok mondatból áll, következésképpen szükségünk van e halmaz tömör jellemzésére. A jellemzést egy nyelvtan (grammar) segítségével kíséreljük meg. Nyelvtanunkat Backus–Naur-forma (Backus– Naur form) vagy BNF-formalizmusban fejezzük ki. Egy BNF-nyelvtannak négy komponense van:

  • A zárószimbólumok vagy a terminálisok (terminal symbols) halmaza. Ezekből a szimbólumokból, másképpen szavakból, állnak össze a nyelv mondatai. Ezek lehetnek betűk (A, B, C, …) vagy szavak (a, aardvark, abacus, ...).

  • A nyelv részkifejezéseit kategorizáló nemzáró szimbólumok vagy nemterminálisok (nonterminal symbols) halmaza. Az angol nyelvben például a FőnéviKifejezés (NounPhrase) nemzáró szimbólum a „you” és a „the big slobbery dog” mondatokat is tartalmazó végtelen halmazt jelenti.

  • A kezdő szimbólum (start symbol) a nyelv teljes mondatait jelentő nemzáró szimbólum. Az angol nyelv esetén ez a Mondat (Sentence), az aritmetika esetén ilyen szimbólum lehet a Kifejezés (Expr).

  • A képzési szabályok (rewrite rules) halmaza, ahol egy-egy szabály LHS → RHS formájú. LHS egy nemzáró szimbólum, az RHS pedig 0 vagy több (záró vagy nemzáró) szimbólumból állhat.

A

Mondat → FőnéviKifejezés IgeiKifejezés

alakú képzési szabály azt jelenti, hogy ha bármikor is van két, egy FőnéviKifejezés-ként és egy IgeiKifejezés-ként kategorizált mondatunk, akkor azokat összekapcsolhatjuk, és az eredményt Mondat-ként kategorizálhatjuk. A | szimbólum az alternatív jobb oldali kifejezéseket választja szét. Nézzük most az egyszerű aritmetikai kifejezések BNF- nyelvtanát:

Kifejezés

→ Kifejezés Operátor Kifejezés | ( Kifejezés ) | Szám

Szám

→ Számjegy | Szám Számjegy

Számjegy

→ 0|1|2|3|4|5|6|7|8|9

Operátor

→ + | – | ÷ | ×

A nyelvekkel és a nyelvtanokkal bővebben a 22. fejezetben foglalkoztunk. Előfordul, hogy más forrásokban a BNF-re kissé módosított jelölést használnak. Nemzáró szimbólum esetén 〈Számjegy〉-gyel találkozhatunk a Számjegy helyett, a zárószimbólum esetén ’szó’-val a szó helyett, illetve szabályokban a : : = jelöléssel a → helyett.

fel