Chomsky hierarki

Chomsky-hierarkiet er en klassifikation af formelle sprog og formelle grammatikker , hvorefter de er opdelt i 4 typer i henhold til deres betingede kompleksitet. Foreslået af MIT professor , lingvist Noam Chomsky .

Klassifikation af grammatikker

Ifølge Chomsky kan formelle grammatikker opdeles i fire typer. For at tilskrive en grammatik til en bestemt type er det nødvendigt, at alle dens regler (produktioner) svarer til visse skemaer.

Type 0 - Ubegrænset

En grammatik med en sætningsstruktur G er en algebraisk struktur , en ordnet firdobbelt (V T , V N , P, S), hvor [1] :

$V_{T}$ — alfabet (sæt) af terminalsymboler — terminaler ,
$V_{N}$ — alfabet (sæt) af ikke-terminale symboler — ikke -terminaler ,
$V=V_{T}\kop V_{N}$ - ordbog i øvrigt $G$ $V_{T}\cap V_{N}=\varnothing$
$P$ er et begrænset sæt produktioner (regler) af grammatikken, $P\subseteq V^{+}\ gange V^{*}$
$S$ - starttegn ( kilde ).

Her er sættet af alle strenge over alfabetet , og er sættet af ikke-tomme strenge over alfabetet . $V^*$ $V$ $V^{+}$ $V$

Type 0 ifølge Chomskys klassifikation omfatter ubegrænsede grammatikker - grammatikker med sætningsstruktur , det vil sige alle formelle grammatikker uden undtagelse. Reglerne kan skrives som:

\alpha \rightarrow \beta

hvor er enhver ikke-tom streng, der indeholder mindst et ikke-terminalt [2] symbol, og er enhver streng af symboler fra alfabetet. ${\displaystyle \alpha \in V^{+))$ $\beta \in V^{*}$

På grund af deres kompleksitet har sådanne grammatikker ingen praktisk anvendelse.

Type 1 - kontekstafhængig

Denne type inkluderer kontekstafhængige (KZ) grammatikker og ikke-forkortende grammatikker. For grammatik er alle regler [3] : $G(V_{T},V_{N},P,S),V=V_{T}\kop V_{N}$

$\alpha A\beta \højrepil \alpha \gamma \beta$ , hvor . Sådanne grammatikker omtales som kontekstfølsomme. $\alpha ,\beta \in V^{*},\gamma \in V^{+},A\in V_{N}$
$\alpha \rightarrow \beta$ , hvor . Sådanne grammatikker er klassificeret som ikke-afkortende. $\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$

Disse klasser af grammatikker er ækvivalente. De kan bruges til analyse af tekster på naturlige sprog, men de bruges praktisk talt ikke i konstruktionen af compilere på grund af deres kompleksitet. For kontekstafhængige grammatikker er udsagnet bevist: med en eller anden algoritme, i et begrænset antal trin, er det muligt at bestemme, om en kæde af terminalsymboler tilhører et givet sprog eller ej.

Type 2 - kontekstfri

Denne type inkluderer kontekstfri (CS) grammatikker . For grammatik er alle reglerne: $G(V_{T},V_{N},P,S),V=V_{T}\kop V_{N}$

$En\højrepil\beta$ , hvor (til ikke-afkortende CF-grammatikker) eller (til at afkorte), . Det vil sige, at grammatikken kun tillader, at et ikke-terminalt symbol vises i venstre side af reglen . $\beta \in V^{+}$ $\beta \in V^{*}$ $A\in V_{N}$

COP-grammatikker er meget brugt til at beskrive syntaksen for computersprog (se parsing ).

Type 3 - almindelig

Den tredje type omfatter almindelige grammatikker (automatisk) - den enkleste af de formelle grammatikker. De er kontekstfri, men med begrænset funktionalitet.

Alle almindelige grammatikker kan opdeles i to ækvivalente klasser, som for en grammatik af type III vil have regler af følgende form:

$A\højrepil B\gamma$ eller , hvor (for venstre-lineære grammatikker). $En\højrepil\gamma$ $\gamma \i V_{T}^{*},A,B\i V_{N}$
$A\højrepil\gamma B$ ; eller , hvor (for højre-lineære grammatikker). $En\højrepil\gamma$ $\gamma \i V_{T}^{*},A,B\i V_{N}$

Almindelige grammatikker bruges til at beskrive de enkleste konstruktioner: identifikatorer , strenge , konstanter , samt assemblersprog , kommandoprocessorer osv.

Klassificering af sprog

Formelle sprog er klassificeret efter de typer grammatik, der definerer dem. Det samme sprog kan dog defineres af forskellige grammatikker, der tilhører forskellige typer. I dette tilfælde anses det for, at sproget tilhører den enkleste af dem. Så et sprog beskrevet af en grammatik med en sætningsstruktur, kontekstfølsomme og kontekstfrie grammatikker vil være kontekstfri.

Som med grammatik er et sprogs kompleksitet bestemt af dets type. De mest komplekse er sprog med en sætningsstruktur (dette inkluderer naturlige sprog), derefter - KZ-sprog, KS-sprog og de enkleste - almindelige sprog.

Noter

↑ Cook, Baze, 1990 , s. 258,264.
↑ Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori og implementering af programmeringssprog. - M. : MZ-Press, 2006. - S. 21. - ISBN 5-94073-094-9 .
↑ Cook, Baze, 1990 , s. 268.

Litteratur

Molchanov A. Yu. Systemsoftware. St. Petersborg: Peter, 2006.
John Hopcroft , Rajiv Motwani , Jeffrey Ullman . KAPITEL 5. Kontekstfrie grammatikker og sprog // Introduktion til automatteori, sprog og beregninger. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teori og implementering af programmeringssprog - M.: MZ-Press, 2006, 2. udg. — ISBN 5-94073-094-9
Robin Hunter . Grundlæggende compilerkoncepter = Essensen af compilere. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
Cook D., Baze G. Kapitel 8. Sprog og grammatik // Computermatematik = Computermatematik. - M . : Videnskab. Fizmatlit, 1990. - 384 s. — ISBN 5-02-014216-6 .

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme