Transleerimine on lähteteksti (transleeritava programmi teksti, s.t. märgijada) teisendamine objekttekstiks - mingis teises programmeerimiskeeles kirjutatud tekstiks, s.t. teistsuguseks märgijadaks. Selliseid märgijadade hulki (näiteks kõikvõimalike korrektsete programmide hulka mingis programmeerimiskeeles) nimetatakse märgikeeleks (character language).
Märgikeele kirjeldamine algab keeles lubatud sümbolite, s.t. keele tähtestiku
defineerimisega.
Tähestik on lõplik hulk üksteisest eristatavaid sümboleid. Tähestiku esitamisel
vajatakse ka metasümboleid (abisümboleid, tähestikku mitte kuuluvaid sümboleid),
näiteks {0,1} on binaarsümbolitest 0,1 koosnev
kaheelemendiline tähestik, mille esitamisel on kasutatud metasümboleid ''{', ' }', ' ,'
(loogelised sulud ja koma). Metasümbolitel on alati mingi
interpretatsioon, näiteks loogelised sulud piiravad hulga
elementide loetelu, koma on eraldajaks hulge elementide vahel jne ja
nad ei kuulu tähestikku. Ka tähestikku kuuluvates
sümbolitel võib mõnikord olla interpretatsioon
(semantika), näiteks \n
tähendab paljudes programmeerimiskeeltes uuele reale siirdumist
jne, kuid see pole märgikeelte käsitlemisel tavaliselt
oluline (see on väga oluline nende keelte kasutamisel arvutis).
Kui keelde kuuluvate märkide (tähtede) esitamisel
(näiteks arvutis tekstina) on oht, et neid interpreteeritakse
(näiteks operatsioonisüsteemi poolt), esitatakse nad kas
apostroofide ' ' (märgi esitamisviis paljudes programmeerimiskeeltes) või jutummärkide
" " (stringi esitamisviis programmeerimiskeeltes) vahel. Mingi lihtsa
programmeerimiskeele
tähestik võiks näiteks olla
T = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,X,Y,Z,
a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,,u,v,x,y,z,
*, +, -,'/', ',', '.',';',' '}
Sõna (antud tähestikus) on igasugune selle tähestiku tähtedest moodustatud jada, näiteks a, aasd, a9Fa-q on sõnad tähestikus T; ka tühi sõna on sõna. T* on kõigi sõnade hulk tähestikus T, T+ = T* \ , st. T+ on kõigi mittetühjade sõnade hulk. T2 = TT , st. T2 on kõigi kahetäheliste sõnade hulk. Sõna w pikkust tähistatakse l(w) , näiteks l(vwc) = 3; la(w) on tähe a esinemiste arv sõnas w , näiteks lt(mitte) = 2.
Teoreem : T* = T U T 2 U T 3 U ...
Keel on mingi kõigi sõnade hulga T * alamhulk (seega keel on sõnade hulk). Formaalsete keelte teooria tegeleb (lõpmatute) keelte genereerimismehhanismide (formaalsete grammatikate ) ja tunnistamismehhanismide (abstraktsete automaatide ) uurimisega.
Genereerimismehhanism (grammatika) on algoritm, mis suudab genereerida (moodustada) kõik keelde kuuluvad sõnad (ja ainult need); eespool oli näitena eesti keele lihtlause genereerimismehhanism ja lihtsa programmeerimiskeele programmide genereerimismehhanism.
Tunnistamismehhanism on algoritm, mis mingi sõna w ja keele L jaoks (mõlemad samas tähestikus) suudab vastata küsimusele: w L ? Näiteks programmeerimiskeele translaator on tunnistamismehhanism, mis tunneb ära korrektsed (süntaksivigadeta) programmid; translaatori poolt tunnistatav keel koosneb kõigist selles programmeerimiskeeles kirjutatud korrektsetest (süntaksivigadeta) programmidest; iga selline programm on sõna selles keeles.