7. fejezet - Környezetfüggetlen nyelvek

Ebben a fejezetben a Chomsky-féle 2-típusú nyelvek sajátosságait tárgyaljuk. E nyelvosztály ugyancsak sok területen jól alkalmazható és vannak rá hatékony algoritmusok, melyek közül néhányat részletesen is bemutatunk.

7.1. Programnyelvek szintaktikájának leírása

Különböző programnyelvek elemeinek (mint pl. számjegy, szám, változó név, utasítás, eljárás stb.) megadásához sokféle módszer ismert. Ilyenek pl. a BNF (Backus-Naur Form), a COBOL-szerű megadási mód, a szintaxis gráf és a hibrid módszer. A leírás terminális egységeket és nemterminális egységeket tartalmaz BNF-ben. A nemterminálisokat más egységekből a konkatenáció, az alternatíva, az iteráció és ezek egy speciális esetének, az opciónak a segítségével adhatjuk meg. Ugyanezek a lépések grafikusan a szintaxis-gráfban is megtalálhatóak. Ezeket a leírási módokat ismertetjük röviden a következőkben, kiterjesztve az egyszerű szintaxis gráfok korábban bemutatott (lásd Szintaxis gráf) alakját is.

A szintaktika leírásához, a különböző programnyelvek megadásánál, használt műveletek:

  • konkatenáció (összefűzés: több szövegelem egymás mellé/után írása),

  • alternatíva (választás: különböző lehetőségek közül egy kiválasztása),

  • opció (a szövegelem vagy megjelenik vagy nem),

  • iteráció (a szövegelem akárhányszor megjelenhet (általában a nullaszori megjelenést is beleértjük)).

Lássuk, akkor most hogyan is néznek ki a már említett leírási módok.

7.1.1. A BNF megadási mód

Ezt a megadási módot abban az időben találták ki, amikor az ALGOL60 nyelvet fejlesztették.

A konkatenációnak nincs külön jele, egyszerűen egymás után írjuk a megfelelő szövegelemeket. A nemterminális jeleket < > zárójelek közé tesszük, és ::= definiáló egyenlőségjel segítségével definiáljuk.

7.1. példa - A számok jelölésére használható karaktersorozatok

Az egész számok megadásához szükség van az opcióra (van előjel vagy nincs), ha van: alternatíva (plusz vagy mínusz), a számjegyek sorozatát pedig iterációval adjuk meg:


< számjegy > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

< előjel > ::= + | –

< egész szám > ::= [ < előjel > ] < számjegy > { < számjegy > } ★

7.1.2. A COBOL-szerű megadási mód

Ez a megadási mód a PL/1 nyelv idején volt leginkább használatban.

7.2. példa - A számok megadása COBOL-szerű módszerrel


7.1.3. A szintaxis gráf

Itt a korábban már a reguláris nyelvek esetén ismertetett Szintaxis gráf módszer teljes kifejezőerejű változatát mutatjuk be.

A korábbiakhoz képest a változás az, hogy egy nemterminális definíciójában felhasználhatunk még nem definiált nemterminálisokat is, akár a definiálandó nemterminálist saját magát is. Így megengedjük a rekurzió kialakulását, akár közvetlenül egy saját magát "meghívó" definícióval, vagy akár egymást hívó több nemterminális definíciójával.

Természetesen, így minden műveletnél, a konkatenációnál, alternatívánál nemcsak terminálisok, hanem nemterminálisok, illetve bármilyen, a módszerrel már összetett gráfok is előfordulhatnak. Az iteráció pedig akár úgy is előfordulhat, mint az opció, csak fordított nyíliránnyal az adott szövegelemnél (megengedve a nullaszoros ismétlést).

Egy szintaxis gráfban mindig van pont egy indulóél és egy érkezőél, ahonnan indulva és ahova érkezve kell egy utat bejárnunk a gráfban. Az út során összeolvassuk a terminálisokat, illetve ha egy nemterminálishoz érünk akkor az adott nemterminális definíciója alapján a neki megfelelő szintaxis gráfban megyünk végig egy úton, ha annak végére értünk akkor folytatjuk az utunkat az eredeti gráfban az adott nemterminális után. Egy nemterminális tehát egy rekurzív hívást jelent, az adott gráfban lefutott út után folytathatjuk csak utunkat. Az hogy megengedjük nem csak a már korábban definiált nemterminálisok használatát egy nemterminális definíciójában, azt jelenti, hogy a rekurziót nem korlátozzuk, annak mélysége bármennyi lehet. A reguláris nyelveknél (5.14. példa - Tizes számrendszerbeli egész számok nyelvének megadása szintaxis gráffal) megadott egész szám fogalmát felhasználva adhatjuk meg például a zárójeles kifejezés fogalmát:

7.1.4. A Hibrid megadási mód

A 90-es évek gyakori leíró nyelve. Tulajdonképpen az előző módszerek keveréke, illetve egyvelege. Az egész számok például a következő módon adhatók meg:

számjegy : { 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

egész szám : [ { + | – } ] számjegy ...

Az ismertetett leírási módoknak a kifejezőereje azonos. Mindegyikkel pontosan a reguláris halmazokat tudjuk definiálni, ha a nemterminálisokat nem használjuk. A kifejező erő ugyanennyi, ha a nemterminálisok definíciójában csak a már korábban ugyanígy megadott nemterminálisokat használhatjuk fel. Ezzel szemben, ha megengedjük a rekurziót, vagyis, hogy egy adott nemterminális definíciójában saját magát is felhasználjuk, vagy előtte még nem definiált nemterminálist, akkor a kifejezőerő megnő; így mindegyik ismertetett módszer segítségével pontosan a környezetfüggetlen nyelvek írhatók le. Ezeknek a megadási módoknak a kifejezőereje tehát azonos, velük a környezetfüggetlen nyelveket tudjuk definiálni.