Formális nyelvek és nyelvtanok - studopediya
Annak szükségességét, hogy a formális nyelvek kapcsolatos bizonyos hiányosságokat a természetes nyelv kialakult használata az elméleti algoritmusok. Vegyünk néhány közülük:
1. A függőség a módját építésének mondat (szintaxis) a saját jelentésük (szemantika). Például, akkor kell használni a mondat „Az orvos megvizsgálta a beteg,” vagy „Az orvos megvizsgálta a beteg,” szerint egy orvos tartozó megfelelő padlón;
2. A szemantikai kétértelműség a javaslatokat. Például a mondat: „Tartsd meg a pénzt a bank”, lehet, hogy pénzt tárolni a pénzügyi intézmény vagy valamilyen minőségben;
3. szemantikai pontatlanság javaslatokat. Például a javaslatára „Tegnap meleg volt az időjárás,” lehetetlen meghatározni a levegő hőmérséklete, mert különböző időpontokban az év meleg felelhet meg különböző hőmérsékleteken;
4. A jelen paradoxonok tárgyalt az előző bekezdésben.
Formális nyelv, kényelmes a algoritmusok elmélete, nem lehet ezeket a hátrányokat. Ebben az esetben, hogy leírja a hivatalos nyelv (a nyelv - egy tárgy) fogja használni egy másik nyelv (meta-nyelv), például egy természetes orosz nyelvet.
Szabályai építése szavakat a betűk a szavak és mondatok egy formális nyelv lesz az úgynevezett formális nyelvtan. A leírás, a szintaxis formális használt nyelv által javasolt amerikai nyelvész és matematikus Chomsky szabványos formában fejezhető ki:
ahol X - ábécé terminális szimbólumok egy formális nyelv;
Y - kiegészítő ábécé a nemterminális szimbólumok;
R - egy véges halmaza szintaktikai szabályok;
S - kezdeti másodlagos szimbólum egy sor nem-terminális szimbólumok (terminális szimbólum - a legkevésbé lényeges eleme egy formális nyelv).
Mind a szintaktikai szabály R jelentése a helyettesítési A → B, ahol A és B - néhány szót származó szimbólumok X és Y. ábécé javaslatok formális nyelv ismét megkapják, ha alkalmazható, hogy a nemterminális S szimbólumot egy permutációja R. Ilyen szubsztitúció, balra része, amely megfelel a nemterminális szimbólum a S, legyen az R. Ha az eredmény tartalmazza csak a terminális szimbólumok, az azt jelenti, hogy a nyelv a javaslat nem érkezett. Ha jelen van a kapott láncban nemterminális szimbólumok, akkor kezdje újra alkalmazni a lánc egyik szubsztituens R, ahol ezek közül bármelyik. Ha az így kapott szöveget többszörös események egy, akkor a megfelelő szubsztitúciós lehetővé teszi cseréjét bármely ilyen események egy B.
Tekintsük a példa a formális nyelvtani, ahol X =, Y =, és helyettesítések a rendszer formájában:
Ez a nyelvtan generál egy hivatalos nyelv, amely tartalmazza a bináris számokat, amelyeket olvasni balról jobbra, illetve jobbról balra. Például, alkalmazása permutációk 3, 4, 1 vezetne a gyártási szám 01010; permutációk 4, 3, 3, 2 - követelés száma 1.001.001, stb
Normál Backus-Naur forma.
Normál Backus-Naur Form (BNF) - egy másik módja, hogy leírja a hivatalos nyelv.
A leírás, a hivatalos nyelv segítségével a BPF fogja használni szintaktikai szabályok (termelés), amely az alábbi szimbólumok:
1. = - a karakter, hogy elválasztja a bal oldalon a termék, amely egy nem-terminális szimbólum a jobb oldali, ami nem üres, véges lánc terminális és nem-terminális szimbólumokat. Symbol. = Olvasás definíció szerint, vagy állhat;
2. | - egy szeparátor között helyezkedik el a különböző formái ugyanazon nemterminális fogalmakat. Symbol vagy olvas;
3. <> - Kacsacsőr megkülönböztetésére nemterminális, azaz olyan dolog, ami nem található meg a javaslatokat ismerteti a nyelvet, és arra használják, hogy leírják ezeket a javaslatokat.
Tekintsük példák leírják a tizedes számjegye egész típusú és konstansok a BPF.
Az a tény, hogy a 1 egy szám, kifejezve a BNF az alábbiak szerint:
Ebben az esetben relációjelet <> azonosítására alkalmazott nem-terminális szimbólum, ami nem fordul elő a mondatban írja le a hivatalos nyelv, és céljuk, hogy bemutassák a szintaktikai szabályokat. Symbol 1 előfordulhatnak mondatban írja le a hivatalos nyelv, és egy terminál szimbólum.
Annak érdekében, hogy azt mutatják, hogy a nem terminális szimbólum <цифра> 0 vagy 1, akkor a következő szintaktikai szabályokat:
Így tudjuk levelet szabály, hogy leírja a decimális számok:
<цифра>:: = 0 | 1 | 2. | 3. | 4 | 5 | 6. | 7 | 8 | 9.
Konstansok egész típusú lehet meghatározni rekurzívan a következő:
- <константа>:: =<цифра>;
- <константа>:: =<константа> <цифра>;
- <цифра>:: = 0 | 1 | 2. | 3. | 4 | 5 | 6. | 7 | 8 | 9.
Az első szabály így szól: <константа> Állhat <цифры>. A második szabály így szól: <константа> Állhat más <константы>, majd <цифра>.
Ezek a szintaktikai szabályok alkotják a nyelvtan a nyelv <констант>. Javaslatok e nyelv olyan szekvenciák terminális szimbólumokat lehet származó nemterminális <константа>. Tekintsük a példát, hogy megszerezze a konstans 673 használatával szintaktikai szabályok írni a BNF:
- Mi csak a második szabály: nemterminális <константа> helyébe egy lánc <константа> <цифра>;
- Mi használjuk a harmadik szabály: nemterminális <цифра> helyébe egy terminál szimbólum 3;
- Mi használjuk a második szabály újra és kap <константа> <цифра>3;
- Az általunk használt harmadik szabály, és megkapjuk <константа> 73;
- Használjuk az első szabály: nemterminális <константа> helyébe a nemterminális <цифра>, Az eredmény egy lánc <цифра> 73;
- Mi használjuk a harmadik szabály, és kap egy 673.
BNF és annak módosításai jelenleg a szokásos módszere leíró szintaxis programozási nyelvek.