A programozási nyelv kifejezőképessége a nyelv minősége, amely jelzi, hogy az adott nyelven megvalósítható ötletek mennyire változatosak és mennyire könnyen olvashatóak [1] .
Például a webes ontológia nyelvből (OWL2 EL) hiányzik az OWL2 RL-ben található számos szolgáltatás. Így az OWL2 EL kevésbé kifejező, mint az OWL2 RL. Ezek a korlátozások hatékonyabb ( polinomiális idejű ) megvalósítást tesznek lehetővé az OWL2 EL-ben, mint az OWL2 RL-ben. [2]
A „kifejezőség” kifejezés többféle értelemben is használható. Ez jelentheti az ezen a nyelven megvalósított ötletek szélességét [1] :
Az elméleti expresszivitás egy olyan mérőszám, amely azt méri, hogy hány gondolat fejezhető ki egy nyelvben, függetlenül attól, hogy a nyelvi konstrukció mennyire bonyolulttá válik [3] . A gyakorlati kifejezőkészség egy olyan mérőszám, amely megmutatja, mennyire olvashatók az adott nyelven megfogalmazott gondolatok [4] .
Az első értelmet gyakrabban használják a matematika és a logika különböző területein, amelyek a nyelvek formális leírásával és jelentésükkel foglalkoznak, például a formális nyelvek elméletében , a matematikai logikában és a folyamatszámításban [5] .
Az informális megbeszélések során a kifejezés gyakrabban utal a második értelemre, például a programozási nyelvek tárgyalásakor [6] Kísérletek történtek a kifejezés ezen informális használatának formalizálására. [7] .
Az expresszivitás fogalma mindig egy adott programozási nyelvben megvalósított ötletre vonatkozik, és ezt a kifejezést gyakran használják olyan nyelvek összehasonlításakor, amelyek ugyanazon paradigmákon osztoznak .
A formális nyelvelmélet főként a karakterláncok leírására szolgáló formalizmusokat tanulmányozza , például kontextusmentes nyelvtanokat és reguláris kifejezéseket . A formalizmus minden egyes előfordulása, például minden nyelvtan és minden reguláris kifejezés egy adott karakterlánc-készletet ír le. Ebben az összefüggésben a formalizmus kifejezőképessége a példányait leíró karakterláncok halmaza, a kifejezőerő összehasonlítása pedig ezeknek a halmazoknak az összehasonlítása.
A formalizmusok relatív expresszivitásának leírásának fontos kritériuma ezen a területen a Chomsky-hierarchia . Ebben például a reguláris kifejezések, a nem determinisztikus véges automaták és a reguláris nyelvtanok azonos kifejezőerővel bírnak, míg a kontextusmentes nyelvtanok több. Ez azt jelenti, hogy az első három formalizmusban leírt karakterlánchalmazok egyenlőek, és a szövegkörnyezet nélküli nyelvtanok megfelelő részhalmazát írják le a karakterlánchalmazoknak.
Ezen a területen az expresszivitás mértéke a kutatás központi témája.
A kifejezőbb formalizmusoknál ez a probléma nehéz vagy akár megoldhatatlan is lehet. Egy Turing-teljes formalizmus esetében, mint például az önkényes formális nyelvtanok esetében, nemcsak ez a probléma, hanem az általuk leírt karakterláncok összes nem triviális tulajdonsága is eldönthetetlen. Ez az állítás Rice-tételként ismert .
A rövidségre vonatkozóan is van néhány eredmény; például a nem determinisztikus automaták és a reguláris nyelvtanok tömörebbek, mint a reguláris kifejezések, abban az értelemben, hogy az utóbbiak méretnövekedés nélkül lefordíthatók az előbbire, míg fordítva nem lehetséges.
Hasonló megfontolások vonatkoznak azokra a formalizmusokra is, amelyek nem karakterláncok halmazát írják le, hanem fák halmazát (például az XML jelölőnyelv ), gráfokat vagy egyéb adatstruktúrákat.