Keresés

Részletes keresés

nadamhu Creative Commons License 2011-01-16 21:44:33 55

Igen ez igaz: csak a rekurzív nyelvek eldönthetők algoritmussal.

Ez tulajdonképpen egy jó hír lenne, hiszen a rekurzív nyelvek nagyon széles kategória: ugye ennek valódi részhalmaza a környezetfüggő nyelvek, annak is a valódi részhalmaza a környezetfüggetlen nyelvek és még annak a részhalmaza a reguláris nyelvek.

 

Valójában ahogy írtam azonban az eldöntő algoritmus csak akkor hasznos a gyakorlatban, ha elég gyors. És sajnos itt már csak a reguláris nyelvek azok a fenti osztályok közül, amelyek triviálisan nagyon gyorsan eldönthetőek (véges automatákkal), és már a környezetfüggetlen nyelvek között is vannak olyan nyelvek, amelyek ilyen szempontból borsot törnek az orrunk alá.

Emiatt a környezetfüggetlen nyelveken belül is megkülönböztetnek al nyelvosztályokat aszerint, hogy bizonyos típusú elemző algoritmusok tudják-e gyorsan eldönteni a nyelvet.

Pl. Az LL(1), LL(2), LL(n) stb... nyelveket az LL típusú elemzők elég gyorsan tudják elemezni; minél kisebb 'n' annál gyorsabban.

Vannak ennél bővebb nyelvosztályok, amik még gyorsan elmezhetők, és itt már egész új eredmények is vannak. Pl. az ANTLR LL(*) elemzőt használ, tehát az LL(*) nyelveket gyorsan tudja elemezni.

A gyakorlatban klaszzikus formális nyelvtant max környezetfüggetlent használnak, környezetfüggő nyelvtant már úgy adnak meg, hogy a környezetfüggetlen nyelvtant augmentálják kis a nyelvtanba be pluginolt szubrutinokkal, kódrészletekkel.

Továbbá érdekességként megjegyzem, hogy kényelmi okokból nyelvtanmegadásra nem is a klasszikus chomsky féle jelölést használják, hanem a gykorlatban intuitívabb jelölést, amelyet kifejezetten környezetfüggetlen nyelvekre tenyésztettek; a legimsertebb az  EBNF:

 

http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form

 

A hozzászólás:
Nautilus_ Creative Commons License 2011-01-16 16:21:53 54

"Elvileg egy mestreséges nyelvet, pl egy programozási nyelvet lehetne definiálni tisztán a Chomsky féle formalizmussal megadott nyelvtanával. Elvileg készíthető olyan általános program, amely fog egy mondatot meg egy nyelvtant és eldönti, hogy az adott mondat a nyelv része-e."

 

 

Általános esetben ez nem igaz, hiszen egy nyelv lehet csak felsorolható, de nem rekurzív.

De akkor is van grammatikája, amely őt generálja.

 

Pl. a Chomsky-féle reguláris nyelvek rekurzívak, azokra igaz az állításod.

 

Előzmény:
nadamhu Creative Commons License 2011-01-16 15:50:37 53

"Már csak az nem világos, hogy miért kell imperatív kód a gyakorlati használathoz, és micsoda egyáltalán."

 

Erre a kérdésedre nem válaszoltam.

Igazából ez nem biztos, hogy érdekes szerintem számodra, hiszen ez elsősorban programozóknak érdekes.

A következőről van szó:

Elvileg egy mestreséges nyelvet, pl egy programozási nyelvet lehetne definiálni tisztán a Chomsky féle formalizmussal megadott nyelvtanával. Elvileg készíthető olyan általános program, amely fog egy mondatot meg egy nyelvtant és eldönti, hogy az adott mondat a nyelv része-e.

Így pl. egyszerűen el lehetne dönteni, hogy egy program szintaktikailag helyes-e.

Az általam leírt okokból (ezeket mélyen sok programozási tapasztalattal lehet érteni) a dolog komplikáltabb. A gyakorlatban olyan nyelvtanmegadásokat használunk, amelyek első ránézésre Chomsky féle nyelvtanok, de meg vannak bolondítva kis részletekkel, amelyek kicsi programtöredékek, algoritmusok, amelyekre néha ráfut az elemző. Ha téged a filozófia érdekel, akkor ez neked érdektelen technikai részlet és egyébként ha nem programozol, nem nem is ilyesmivel kell kezdeni, hanem alapvetőbb dolgokkal.

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!