Környezetfüggetlen nyelvtan

A Wikipédiából, a szabad lexikonból.

A nyelvészetben és az informatikában a környezet független nyelvtan, angol kifejezéssel és rövidítéssel context-free grammar (CFG) egy formális nyelvtan amelyben minden produkciós szabály a következő formájú

V → w

ahol V egy nem-terminális szimbólum és w egy jelsorozat, amely terminális és/vagy nem-terminális szimbólumokat tartalmaz.

A "környezet független" kifejezés abból a tényből ered, hogy a nem-terminális V minden esetben helyettesíthető w-vel, függetlenül attól, hogy milyen környezetben fordul V elő. Egy formális nyelv akkor környezet független ha környezet független nyelvtan generálja.

A környezet független nyelvtanok kellően hatékonyak és erősek a legtöbb programozási nyelv szintaxisának leírásához; valójában a legtöbb programozási nyelv szintaxisának meghatározására környezet független nyelvtanokat használnak. A környezet független nyelvtanok egyszerűen elegendőek egy hatékony elemző algoritmus konstruálásához, amely egy adott jelsorozatról eldönti, hogy létrehozható-e az adott nyelvtan alapján.

A BNF (Backus-Naur Forma) a legismertebb jelölési rendszer a környezet független nyelvtan kifejezéseinek leírására.

Nem minden formális nyelv környezet független — a jól ismert az \{ a^n b^n c^n : n \ge 0 \} nyelv. Ez a sajátos nyelv egy parsing expression nyelvtannal generálható, ami viszonylag új formalizmus ami különösen jól illeszkedik a programozási nyelvekhez.