Kétértelmű 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 2014. november 30-án áttekintett verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

Az informatikában a kétértelmű nyelvtan olyan formális nyelvtan , amely egy adott karakterláncot többféleképpen is generálhat (vagyis egy karakterlánchoz egynél több elemzőfa tartozik ) . Egy nyelvről azt mondjuk , hogy alapvetően kétértelmű , ha csak kétértelmű nyelvtanok generálhatják.

Egyes programozási nyelvek nyelvtana nem egyértelmű. Az ilyen nyelvek elemzésekor szemantikai információkat kell figyelembe venni a megfelelő változat kiválasztásához. Például C nyelvben a következő bejegyzés:

x*y;

a következőképpen értelmezhető :

pointer típusú azonosító deklarálása -to- , vagyyx
egy kifejezés , amelyben xa rendszer megszorozza yaz eredményt, és figyelmen kívül hagyja az eredményt.

Az értelmezések közötti választáshoz a fordítónak meg kell néznie a szimbólumtáblázatát, hogy megtudja, a deklaráció xtypedef név volt-e egy adott hatókörben.

Példa

Kontextus mentes nyelvtan

A → A + A | A − A | a

kétértelmű, mivel az a + a + a karakterláncnak két bal oldali kimenete van:

A	→A+A	A	→A+A
	→ a+A		→A+A+A
	→ a+A+A		→ a+A+A
	→ a+a+A		→ a+a+A
	→ a + a + a		→ a + a + a

Ezenkívül a nyelvtan kétértelmű, mert az a + a − a karakterlánchoz két elemzőfa tartozik:

Az általa generált nyelv azonban alapvetően nem kétértelmű, mivel a következő egyértelmű nyelvtan ugyanazt a nyelvet generálja:

A → A + a | A − a | a

Kétértelmű nyelvtan felismerése

Az általános probléma annak meghatározására, hogy egy nyelvtan kétértelmű-e, algoritmikusan eldönthetetlen . Nem létezik olyan algoritmus, amely meghatározza egy nyelvtan kétértelműségét, mivel Post megoldhatatlan megfelelési problémája kétértelműségi problémává redukálódik.

Nyilvánvaló nehézséget okoz egy kétértelmű nyelvtan determinisztikus értelmezővel történő elemzése, de a nem determinisztikus elemzés jelentős hatékonyságcsökkenést eredményez. A legtöbb elemzést igénylő konstrukció egyértelműen felismerhető a nyelvtanokkal. Egyes kétértelmű nyelvtanokat át lehet alakítani egyértelmű nyelvtanokká, de erre az átalakításra nincs általános eljárás, mint ahogy a nyelvtan kétértelműségének meghatározására sem létezik algoritmus. A fordítógenerátorok , mint például a YACC , képesek bizonyos típusok egyértelművé tételére, például elsőbbségi és asszociativitási megszorítások használatával .

Jelentősen kétértelmű nyelvek

Míg egyes nyelvek (egy nyelvtan által generált karakterlánc-készletek) egyértelmű és kétértelmű nyelvtanokkal is rendelkeznek, vannak nyelvek, amelyekre nincs egyértelmű nyelvtan. A lényegében kétértelmű nyelvre példa a és unió . Ez egy kontextusmentes nyelv, mint a kontextusmentes nyelvek ötvözete, de a Bevezetés az automataelméletbe… bizonyítékot tartalmaz arra , hogy nem lehetséges a karakterláncok egyedi elemzése abban a (nem kontextusmentes) részhalmazban , amely a kettő metszéspontja. nyelvek. ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\))$ ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\))$ ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\))$

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