5.3. Egyszerű szintaxis gráfok

A szintaxis gráfokat pl. programnyelvek egységeinek szintaktikai leírására használhatjuk. Ez a megadási mód a Pascal nyelvvel terjedt el igazán, a grafikus kép miatt iskolások és felnőttek is könnyedén sajátították el segítségével a programozás alapjait. Több elnevezése is ismert, pl. a vasúthálózat diagram név a diagramok alakja alapján találó. A terminálisokat körökkel jelöljük, beírva őket a körbe.

Használható műveletek:

5.13. példa - Azonosítók nyelvének megadása szintaxis gráffal


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. Ha az út során összeolvassuk a terminálisokat, akkor egy szót kapunk. Az összes olyan szó, amelyet megkaphatunk az indulóéltől az érkezőélig valamely úton végighaladva adja a gráf által leírt nyelvet.

A rövidebb és áttekinthetőbb leírás kedvvért bevezethetjük a nemterminálisokat, amik egyszerű szintaxisgráf részeket rövidítenek. Azt is megengedhetjük, hogy ezekben a nemterminális rövidítésekben szerepljenek már korábban definiált nemterminálsiok.

5.14. példa - Tizes számrendszerbeli egész számok nyelvének megadása szintaxis gráffal


Az előző példa alapján a -000 szó is egész szám (eleme a nyelvnek), hiszen egy számítógépes programnyelv általában ezt is ugyanúgy érti, mint a 0 szót. Az iskolában tanultaknak megfelelően viszont egy ember számára a -000 szám hibásnak tűnik.

5.15. példa - Egész számok köznapi értelemben vett leírása - Gyakorló feladat

Adjuk meg azt a szintaxis gráfot, amely az emberek számára hétköznapi értelemben vett egész számok leírását adja! ★


Az itt ismertetett szintaxis gráfokkal pontosan a reguláris nyelveket tudjuk leírni, 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. Ekkor ugyanis a szereplő nemterminálisok helyettesíthetőek a definíciójukban megadott leírással, ami ha tartalmaz nem terminálist, akkor az ott szereplő nemterminálisok is helyettesíthetőek stb., amíg végül visszakaphatjuk az eredeti nemterminális mentes definíciót.