Kontextus mentes nyelvtan

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 3-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A kontextusmentes grammatika ( CS-grammar , context-free grammar ) a formális nyelvtan speciális esete (a Chomsky-hierarchia szerint 2-es típus ), amelyben az összes produkció bal oldali részei egyetlen nem terminálok (a nyelv bármely lényegét jelölő objektumok). a nyelv (például: képlet, aritmetikai kifejezés, parancs), és nincs konkrét szimbolikus jelentése). A "kontextusmentes" kifejezés jelentése az, hogy lehetséges a produkció alkalmazása nem terminálra, ráadásul ennek a nem terminálnak a kontextusától függetlenül (szemben a korlátlan Chomsky-nyelvtan általános esetével).

A CFG-vel megadható nyelvet környezetfüggetlen nyelvnek vagy CFL-nek nevezzük.

Valójában a KS-nyelvtan a BNF egy másik formája .

Alkalmazás

A COP-nyelvtanokat sokat használnak a számítástechnikában . Beállítják a legtöbb programozási nyelv nyelvtani szerkezetét , strukturált adatokat stb. (lásd a nyelvtani elemzést )

A COP-nyelvtan elemzéséhez elég egy lenyomó automata , a nem COP-nyelvtanok elemzéséhez pedig egy teljes Turing-gépre lehet szükség .

A CS nyelvtan típusai

LL nyelvtan
LALR nyelvtan (lásd: LALR(1) )
LR nyelvtan
SLR nyelvtan (lásd: SLR(1) )

Felismerők

A CF-nyelvek felismerőinek (felismerési automatáinak) két különböző osztálya van. A nevük a kimeneti fa felépítésének sorrendjéhez kapcsolódik. Általános szabály, hogy minden felismerő balról jobbra olvassa be a bemeneti karakterláncot, mivel a programok forráskódjának megírásakor ilyen jelölés szükséges.

Downstream feloldók

Felülről lefelé irányuló feloldók, amelyek bal oldali kimeneti láncokat generálnak, és felülről lefelé építik fel a kimeneti fát.

Az algoritmus módosításait alkalmazzák az alternatívák kiválasztásával. Létrehozásuk során olyan módszert alkalmaznak, amely lehetővé teszi, hogy az MP-automata minden lépésénél egyedileg válasszon egy és csak egy alternatívát (a „kidobás” lépés ebben az automatában mindig egyedileg történik).

Növekvő felismerők

Alulról felfelé mutató feloldók, amelyek jobb oldali kimeneti láncokat generálnak, és alulról felfelé építik fel a kimeneti fát.

Az upstream felismerők a shift-fold (vagy shift-fold, amely ugyanaz) algoritmus módosításait használják. Létrehozásuk során olyan módszereket használnak, amelyek lehetővé teszik, hogy a kiterjesztett MP-automata minden egyes lépésénél egyértelműen válasszon „eltolás” („transzfer”) vagy „konvolúció” között, a konvolúció végrehajtásakor pedig egyértelműen kiválaszthatja a szabályt. amellyel a konvolúció végrehajtásra kerül. Algoritmus "eltolás-konvolúció".

Példák

Példák SF-nyelvtanokra és a hozzájuk tartozó SF-nyelvekre:

Flip szó

Képlet alapján megadva $L=\{w\in \Sigma ^{*}|w=w^{R}\}$

Terminálok: az ábécé betűi ; $\Sigma$
Nem terminális: ; $S$
Termékek: $S\jobbra nyíl \alpha S\alpha \,|\,\alpha \,|\,\varepsilon ,\alpha \in \Sigma$
A kezdeti nem terminál a . $S$

Beágyazott zárójelek

Terminálok: és ; $($ $)$
nem terminál: ; $S$
termékek: ; $S\jobbra nyíl (S)\közép \varepszilon$
kezdeti nem terminális - . $S$

Ez a nyelvtan határozza meg a beágyazott zárójelek nyelvét . $\{\left(^{n}\right)^{n}\mid n\geq 0\}$

Dick nyelve

Aritmetikai kifejezés

Terminálok: '+', '-', '*', '/', '(', ')', 'x'
nemterminálisok: <kifejezés>, <kifejezés>, <szorzó>
Termékek:

<kifejezés> → <kifejezés> + <kifejezés>, <kifejezés> → <kifejezés> - <kifejezés>, <kifejezés> → <kifejezés>, <kifejezés> → <kifejezés> * <szorzó>, <kifejezés> → <kifejezés> / <szorzó>, <kifejezés> → <szorzó>, <szorzó> → ( <kifejezés> ), <szorzó> → x,

kezdeti nem terminális: <kifejezés>.

Ez a nyelvtan egy számtani kifejezést határoz meg, amely az x változó legegyszerűbb számtani műveleteit tartalmazza. Ha az 'x' terminált a nem terminális <szám>-ra cseréljük, akkor egy olyan nyelvtant kapunk, amely egy olyan aritmetikai kifejezést ad meg, amely egész számok összeadási, kivonási, szorzási és osztási műveleteiből áll.

A COP-nyelvtanok korlátai

Nem minden nyelv definiálható CF-nyelvtanokkal. Ezt a legegyszerűbben a következőképpen lehet bizonyítani: a COP-nyelvtanok megszámlálható halmazt alkotnak, míg az összes nyelv halmazának számossága egy kontinuum . Ugyanennek a ténynek konstruktív bizonyítása nyerhető például azon az alapon, hogy a nyelv { a n b n c n | n ≥1} nem környezetfüggetlen; úgy tűnik azonban, hogy ez utóbbi állításnak nincs rövid bizonyítéka: a publikált bizonyítások a kontextusmentes nyelvekre vonatkozó növekedési tételre támaszkodnak.

Általánosítások

A fa összeadás nyelvtana általánosítja a környezetfüggetlen nyelvtant, mivel a következtetési szabályokban az elemi egység a fák, nem pedig az egyes karakterek.

Lásd még

Irodalom

John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Bevezetés az automataelméletbe, a nyelvekbe és a számításba. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Belousov A. I., Tkachev S. B. Diszkrét matematika. — M .: MGTU , 2006. — 743 p. — ISBN 5-7038-2886-4 .

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus