„Formális nyelvtan” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
|||
22. sor:
: 2. <math>S \longrightarrow ba</math>
Kezdő szimbólumunk a „<math>S</math>”, de ezután kiválaszthatjuk, hogy melyik szabályt alkalmazzuk a jelsorozat következő elemének előállításához. Ha az 1-es szabályt választjuk, akkor annak alapján az '<math>S</math>' szimbólumot a '<math>aSb</math>'-al helyettesítjük, eredményül tehát a „<math>aSb</math>” jelsorozatot kapjuk. Ha most ismételten az 1-es szabály alkalmazását választjuk, akkor helyettesítjük az '<math>S</math>' szimbólumot a '<math>aSb</math>'-
Az adott szimbólumokat használva a fentieket sokkal egyszerűbb formában is leírhatjuk: <math>S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow aababb</math>.
A nyelvtan által meghatározott nyelv nem lesz más, mint az összes olyan jelsorozat halmaza, amelyeket ezzel az eljárással elő tudunk állítani: <math>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.
34. sor:
* <math>\Sigma</math> a ''terminális szimbólumok'' véges halmaza, aminek nincs közös része <math>N</math>-nel;
* <math>P</math> a ''produkciós szabályok'' véges halmaza, ahol a szabályok a következő formában adottak
:: <math>(\Sigma \cup N)^{*}</math> beli jelsorozat <math>
:(ahol <math>{}^{*}</math> a [[Kleene star]] és <math>\cup</math> az [[unió (halmazelmélet)|unió]] művelet) azzal a megkötéssel, hogy a szabály bal oldalának (bal oldali rész a <math>\longrightarrow</math> előtt) legalább egy nem-terminális szimbólumot tartalmaznia kell.
* Az <math>N</math> halmazhoz tartozó <math>S</math> szimbólum, ami a ''kezdő szimbólumot'' jelöli.
Gyakran a <math>G</math> formális nyelvtan jelölésé a <math>(N, \Sigma, P, S)</math> négyessel történik.
46. sor:
''A következő példáknál a formális nyelvet a [[halmaz-felépítő jelölés]] használatával határozzuk meg.''
Például, tételezzük fel a <math>G</math> nyelvtanról, hogy a következőkből áll:
<math>N = \left \{S, B\right \}</math>, <math>\Sigma = \left \{a, b, c\right \}</math>, <math>P</math> pedig a következő produkciós szabályokat tartalmazza:
57. sor:
és az <math>S</math> nem-terminális szimbólum a kezdő szimbólum.
Néhány példa arra, hogyan származtathatók a jelsorozatok a <math>\boldsymbol{L}(G)</math> nyelvben:
* <math>\boldsymbol{S} \longrightarrow (2) abc</math>
146. sor:
== Analitikus nyelvtanok ==
Habár a rendelkezésre álló [[elemző]] [[algoritmus]]okkal foglalkozó irodalom igen terjedelmes, ezek közül az algoritmusok közül a legtöbb azt feltételezi, hogy az elemzendő nyelv ''leírása'' egy ''generatív'' formális nyelvtant jelent, és az a cél, hogy átalakítsa ezt a generatív nyelvtant egy működő elemzővé. Egy másik lehetséges megközelítés a nyelvet elsődlegesen egy '''analitikus nyelvtannal''' formalizálja, amely sokkal közvetlenebb kapcsolatot biztosít az [[elemző]] és az elemzendő nyelv struktúrája között. Az analitikus nyelvtanokkal történő
* [http://languagemachine.sourceforge.net The Language Machine] közvetlenül valósít meg korlátozások nélküli analitikus nyelvtanokat. A helyettesítési szabályok alkalmazásával vezérelhető a bemenetek és kimenetek közötti kapcsolat, illetve a rendszer viselkedése. A rendszer előállít úgynevezett [[lm-diagram]]ot is, amely megmutatja, mi történik a korlátozások
* [[Top-down elemző nyelv|fentről-lefelé elemző nyelv]] (TDPL, az angol Top-Down Parser Language rövidítése): a nagyon minimalista analitikus nyelvtan kifejlesztése az [[1970]]-es években történt, amikor a [[top-down elemző]]k viselkedést tanulmányozták.
* [[Parsing expression nyelvtan]]ok (PEGs): a TDPL egy újkeletű általánosításával tervezett gyakorlati megvalósítás a [[compiler]] írók számára.
| |||