Chomsky-hierarchia

A Chomsky-hierarchia a formális nyelvek és formális nyelvtanok osztályozása , amely szerint feltételes összetettségük szerint 4 típusra oszthatók. A MIT professzora , Noam Chomsky nyelvész javasolta .

Nyelvtanok osztályozása

Chomsky szerint a formális nyelvtanok négy típusra oszthatók. Egy nyelvtan egy adott típushoz való hozzárendeléséhez szükséges, hogy minden szabálya (produkciója) megfeleljen bizonyos sémáknak.

0. típus - Korlátlan

A G kifejezésszerkezetű nyelvtan egy algebrai szerkezet , egy rendezett négyes (V T , V N , P, S), ahol [1] :

$V_{T}$ — terminálszimbólumok ábécéje (készlete) — terminálok ,
$V_{N}$ — nem terminális szimbólumok ábécéje (készlete) — nem terminálok ,
$V=V_{T}\pohár V_{N}$ - szótár , ráadásul $G$ $V_{T}\cap V_{N}=\varnothing$
$P$ a nyelvtan produkcióinak (szabályainak) véges halmaza , $P\subseteq V^{+}\times V^{*}$
$S$ - kezdő karakter ( forrás ).

Itt látható az összes karakterlánc készlete az ábécé felett , és az ábécé feletti nem üres karakterláncok halmaza . $V^*$ $V$ $V^{+}$ $V$

A 0-s típus a Chomsky-féle besorolás szerint magában foglalja a korlátlan nyelvtanokat - a kifejezésszerkezetű nyelvtanokat , vagyis kivétel nélkül az összes formális nyelvtant. A szabályok a következőképpen írhatók fel:

\alpha \rightarrow \beta

ahol bármely nem üres karakterlánc, amely legalább egy nem terminális [2] szimbólumot tartalmaz, és az ábécé bármely szimbólumsora. ${\displaystyle \alpha \in V^{+))$ $\beta \in V^{*}$

Bonyolultságuk miatt az ilyen nyelvtanoknak nincs gyakorlati alkalmazása.

1. típus – környezetérzékeny

Ebbe a típusba tartoznak a kontextusfüggő (KZ) nyelvtanok és a nem rövidítő nyelvtanok. A nyelvtan esetében minden szabály [3] : $G(V_{T},V_{N},P,S),V=V_{T}\pohár V_{N}$

$\alpha A\beta \rightarrow \alpha \gamma \beta$ , hol . Az ilyen nyelvtanokat környezetérzékenynek nevezik. $\alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}$
$\alpha \rightarrow \beta$ , hol . Az ilyen nyelvtanok nem rövidítésnek minősülnek. $\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$

Ezek a nyelvtani osztályok egyenértékűek. Használhatók természetes nyelvű szövegek elemzésénél, de fordítóprogramok felépítésében bonyolultságuk miatt gyakorlatilag nem. Kontextusfüggő nyelvtanoknál az állítás bizonyítást nyer: valamilyen algoritmussal véges számú lépésben meg lehet határozni, hogy terminális szimbólumok lánca egy adott nyelvhez tartozik-e vagy sem.

2. típus – környezetfüggetlen

Ez a típus magában foglalja a környezetfüggetlen (CS) nyelvtanokat . A nyelvtan esetében az összes szabály a következő: $G(V_{T},V_{N},P,S),V=V_{T}\pohár V_{N}$

$A\jobbra nyíl\béta$ , ahol (nem rövidítő CF-nyelvtanoknál) vagy (rövidítőeknél), . Vagyis a nyelvtan csak egy nem terminális szimbólumot enged meg a szabály bal oldalán . $\beta \in V^{+}$ $\beta \in V^{*}$ $A\in V_{N}$

A COP nyelvtanokat széles körben használják a számítógépes nyelvek szintaxisának leírására (lásd az elemzést ).

3. típus - normál

A harmadik típusba a szabályos (automatikus) nyelvtanok tartoznak – a formális nyelvtanok közül a legegyszerűbb. Kontextusmentesek, de korlátozott funkcionalitással.

Minden reguláris nyelvtan két egyenértékű osztályra osztható, amelyek a III. típusú nyelvtan esetében a következő formájú szabályokkal rendelkeznek:

$A\jobbra nyíl B\gamma$ vagy , ahol (bal lineáris nyelvtanokhoz). $A\jobbra nyíl\gamma$ $\gamma \in V_{T}^{*},A,B\in V_{N}$
$A\jobbra nyíl\gamma B$ ; vagy , ahol (jobb-lineáris nyelvtanokhoz). $A\jobbra nyíl\gamma$ $\gamma \in V_{T}^{*},A,B\in V_{N}$

A reguláris nyelvtanokat a legegyszerűbb konstrukciók leírására használják: azonosítók , karakterláncok , konstansok , valamint assembly nyelvek , parancsfeldolgozók stb.

Nyelvek osztályozása

A formális nyelveket az őket meghatározó nyelvtan típusok szerint osztályozzák. Ugyanazt a nyelvet azonban különböző típusokhoz tartozó különböző nyelvtanok határozhatják meg. Ebben az esetben úgy tekintjük, hogy a nyelv a legegyszerűbbek közé tartozik. Tehát egy olyan nyelv, amelyet egy kifejezésszerkezettel, környezetérzékeny és kontextusmentes nyelvtannal ír le, kontextusmentes lesz.

A nyelvtanokhoz hasonlóan a nyelv összetettségét a típusa határozza meg. A legbonyolultabbak a kifejezésszerkezettel rendelkező nyelvek (ez magában foglalja a természetes nyelveket), majd a KZ-nyelvek, a KS-nyelvek és a legegyszerűbbek a reguláris nyelvek.

Jegyzetek

↑ Cook, Baze, 1990 , p. 258.264.
↑ Szerebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. A programozási nyelvek elmélete és megvalósítása. - M. : MZ-Press, 2006. - S. 21. - ISBN 5-94073-094-9 .
↑ Cook, Baze, 1990 , p. 268.

Irodalom

Molchanov A. Yu. Rendszerszoftver. Szentpétervár: Péter, 2006.
John Hopcroft , Rajiv Motwani , Jeffrey Ullman . 5. FEJEZET Környezetmentes nyelvtanok és nyelvek // Bevezetés az automataelméletbe, nyelvekbe és számításba. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Szerebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Programozási nyelvek elmélete és megvalósítása - M.: MZ-Press, 2006, 2. kiadás. — ISBN 5-94073-094-9
Robin Hunter . Alapvető fordítói fogalmak = A fordítók lényege. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
Cook D., Baze G. 8. fejezet Nyelvek és nyelvtan // Computer Mathematics = Computer Mathematics. - M . : Tudomány. Fizmatlit, 1990. - 384 p. — ISBN 5-02-014216-6 .

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