Környezetfüggetlen nyelvtan

A nyelvészetben és az informatikában a környezetfü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örnyezetfü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örnyezetfüggetlen ha környezetfüggetlen nyelvtan generálja.

A környezetfü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örnyezetfüggetlen nyelvtanokat használnak. A környezetfü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örnyezetfüggetlen nyelvtan kifejezéseinek leírására.

Nem minden formális nyelv környezetfüggetlen – a jól ismert az $\{a^{n}b^{n}c^{n}:n\geq 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.