Formális nyelv

A HupWiki-ből...

Számításelméletben használt, jelsorozatok és képzési szabályok kapcsán emlegetett konstrukció. Egy nagyon rövid és felületes áttekintés:

Képzési szabály (production rule): egy jelsorozatnak egy másik jelsorozattal helyettesítését előíró szabály. Pl.: aSb --> aAbc. A nagybetűs szimbólumokat "nemterminális"-nak, a kisbetűseket "terminális"-nak nevezik (a kettő közti különbség: a terminálist már nem lehet további helyettesítésben lecserélni).
Nyelvtan (grammar): képzési szabályok összessége.
Mondat (sentence): képzési szabályok alapján generált, csak terminálisokból álló jelsorozat.
Nyelv (language): az összes lehetséges mondat összessége.

Ezeket a képzési szabályokat a szerkezetük bonyolultsága szerint négyféle osztályba szokták sorolni (ezek az ún, Chomsky-féle nyelvosztályok, Noam Chomsky nyelvész 1956-ban publikálta őket):

• Chomsky 3-as osztály (reguláris): csak A --> Bc vagy A --> bC alakú szabályai lehetnek, az egész nyelvtanban egységesen.
• Chomsky 2-es osztály (környezetfüggetlen (Context Free, CF)): A --> sABcd... alakú szabályok. A bal oldalon még mindig csak egy nemterminális lehet, a jobb oldalon azonban már nincs megkötés: terminálisok és nemterminálisok tetszőleges kombinációja állhat.
• Chomsky 1-es osztály (környezetfüggő (Context Sensitive, CS)): sAcd --> sABcd... Az egyetlen megkötés, hogy a jobb oldalon a bal oldalinál hosszabb jelsorozatnak kell állnia.
• Chomsky 0-ás osztály: nincs megkötés, bármit bármire enged helyettesíteni.

Ilyen szabályokat két irányban használhatunk: egy kezdeti jelből (az ún. "mondatszimbólumból" -- "sentence symbol") képzési szabályokkal le akarunk vezetni egy adott jelsorozatot; illetve fordítva, egy adott jelsorozatból visszafelé végzett összevonásokkal akarunk eljutni a mondatszimbólumba.

Mire is jó ez az egész: a második irányt csinálják a fordítóprogramok. Egy adott programszövegből építik fel visszafelé azt a képzési sorozatot (az ún. "értelmezési fát" -- "parse tree"), ami a program forráskódját generálja. Ezen a fán (optimalizáció céljából) végzett összevonások és átalakítások után az eredményt egy gépi kódú utasítássorozatként írják ki, ez a lefordított program.

A programozási nyelvek tehát a Chomsky 2-es osztályba tartoznak.

Nyilván kell, hogy a nyelvtan egyértelmű legyen, vagyis minden programszöveget csak egyféle értelmezési fával lehessen generálni.