7.2. Levezetési fa

A környezetfüggetlen nyelvek (nyelvtanok) egy tulajdonsága (mely népszerűségükben is központi szerepet játszik), hogy a levezetések fa alakban ábrázolhatók.

Környezetfüggetlen nyelvtanban minden levezetés nagyon egyszerűen ábrázolható egy irányított gráf (fa) segítségével. Tekintsünk egy S* p levezetést, ahol p∈(NT)*. A gráf csúcsainak nemterminális, illetve terminális szimbólumokat feleltethetünk meg: a fa gyökeréhez S- t, leveleihez rendre terminális és nemterminális szimbólumokat, a közbülső csúcsaihoz pedig nemterminális jeleket rendelhetünk. Az egy csúcsból kiinduló élek annak a helyettesítési szabálynak az alkalmazását jelölik, amelynek bal oldalán az élek közös kiindulási pontjában található nemterminális jel áll, a jobb oldalán pedig az élek végpontjaiban található nemterminális, illetve terminális jelek sorozata (az egyes éleket balról jobbra véve sorra). Azt, hogy egyes szabályokat milyen sorrendben alkalmazunk, nem mindig tudjuk egyértelműen rekonstruálni. Egy levezetési gráf mélységén a benne az S gyökértől induló és levélelemhez tartó irányított utak hosszának maximumát értjük. Ha a fa minden levéleleme terminális címkéjű, akkor befejezett levezetésről és befejezett levezetési fáról beszélhetünk.

7.3. példa - Levezetési fa

Legyen G=({S, A, B}, {a, b, c}, S, H), ahol H={SA B c, A → a B, A → B c, Ba A c, Bb c}. Ebben a nyelvtanban megadható a következő levezetés: SA B cA a A c cB c a A c cB c a a B c cb c c a a B c cb c c a a b c c c.


Egy levezetési fa általában nem egy levezetést ábrázol (vagyis több olyan levezetés is lehetséges melynek ábrázolásával ugyanazt a fát kapjuk). Az egy fa által reprezentált levezetések viszont egy ekvivalencia osztályt alkotnak, hiszen mindegyikükben ugyanaz a mondatforma (vagy szó) van levezetve, illetve az ugyanott megjelenő ugynarra a nemterminálisra ugyanazt a szabályt alkalmazzuk. Egyedül a szabályalkalmazások sorrendje lehet különböző.

Legbaloldalibb levezetésnek hívunk egy levezetést, ha a levezetés során minden lépésben az aktuális mondatforma legelső (legbaloldalibb) nemterminálisára végzünk el egy helyettesítést valamely alkalmas levezetési szabály segítségével.

45. Tétel. Minden levezetési fához egyértelműen hozzárendelhető egy legbaloldalibb levezetés.

Az adott levezetési fához tartozó levezetések közül tehát egyértelműen kiválaszthatunk egyet, amivel az osztályt reprezentálhatjuk: a legbaloldalibbat.

A legbaloldalibb levezetés arra hasonlít, mintha a levezetési fát a mesterséges intelligenciában mélységi keresőként ismert algoritmus segítségével építenénk fel.

7.2.1. Többalakúság

Fontos szerepet játszik az egyértelműség kérdése a következő tekintetben. Adott nyelvtan esetén előfordulhat, hogy egy adott szóhoz több különböző levezetési fa létezik. A természetes nyelvekre nagyon jellemző ez a többalakúság. A "láttam Pétert egy távcsővel." mondat értelmezése lehet kétféle: vagy a tárgy rendelkezik egy részeshatározóval: Péter a kezében vitt egy távcsövet, amikor láttam, hogy megy kirándulni. A másik elemzés szerint az alany (én) rendelkezem egy távcsővel (eszközhatározós szerkezet) és ennek segítségével láttam Pétert, ahogy jön föl a hegyre. A természetes nyelvek esetén általában a szövegkörnyezet, vagy az adott szituáció segít kiválasztani a helyes elemzést...

Ezzel szemben, pl. a programnyelvek leírásakor törekednünk kell az egyértelműségre. Például a G=({S}, {2, +, *}, S, {SS+S, S  → S*S, S  → 2}) nyelvtanban SS+SS+S*S*2+2*2 valamint SS*SS+S*S*2+2*2 ugyanannak a szónak két különböző levezetése, a levezetési fákat a következő ábra mutatja.

Viszont a levezetés elemzése alapján az első értelmezés szerint 2+(2*2)=6 az eredmény, míg a második értelmezés (2+2)*2=8- at jelent. Ez pl. gondot okozhat egy számítógépes fordító részére. Ezért fontos, hogy lehetőleg kerüljük a többalakúságot egy programnyelv tervezése során, nem célszerű ilyen döntéseket a fordítóra hagyni.

7.4. példa - Csellengő "else" feladat

Ismert a csellengő "else" problémája, amikoris nem egyértelmű, hogy egy else-ág melyik feltételhez tartozik. Példaként tekintsük a következő kódot:


if a then if b then do else print

Adjunk példát olyan nyelvtanra, ahol ez a probléma fellép. ★

Ismert tény, hogy vannak olyan környezetfüggetlen nyelvek, amelyeket nem lehet olyan nyelvtannal generálni, hogy ne legyen olyan szó amelynél a többalakúság fellép. Ilyen nyelvre példa: L={anbmcmdn } ∪ {anbncmdm }.