Programski prevodioci i formalni jezici: Teorija i implementacija

Vrste programskih prevodilaca

Postoji nekoliko osnovnih vrsta programskih prevodilaca:

• Asembleri
• Makroprocesori
• Prevodioci jezika višeg nivoa
• Hibridni prevodioci
• Multijezički prevodioci

Šta su asembleri?

Asembleri su programski prevodioci koji se koriste za prevođenje zapisa sa nivoa asemblerskog jezika na nivo mašinskog jezika.

Šta su makroprocesori i njihovi sastavni delovi?

Makroprocesori su programski prevodioci koji se koriste za prevođenje makroasemblerske naredbe u niz asemblerskih naredbi. Osnovni delovi su makroprocesor i asembler.

Razlika između kompilatora i interpretatora

Osnovna razlika između kompilatora i interpretatora je u strategiji izvršavanja:

• Kompilator: Najpre vrši analizu programa, a zatim generiše mašinski kod celog programa.
• Interpretatori: Prevode naredbu po naredbu programa i time formiraju celinu koja može odmah da se izvršava.

Hibridni prevodioci

Pored čistih kompilatora i interpretatora, danas se koriste i hibridni prevodioci. Oni predstavljaju mešavinu oba pristupa: vrše analizu koda kao kompilatori, generišu međukod programa, a nakon toga interpretiraju taj međukod.

Višejezički prevodioci

To su kompilatori koji imaju posebne delove za analizu koda za više različitih programskih jezika, pri čemu se kod svih ovih analizatora generiše isti međukod programa. Kasnije se taj međukod može prevoditi u mašinski jezik određenog računara, jednog ili više različitih procesora.

Osnovne faze u procesu prevođenja viših programskih jezika

Proces prevođenja se sastoji od sledećih faza:

1. Leksička analiza: Leksički analizator analizira znak po znak naredbe i nastoji da identifikuje leksičke celine (lekseme), pri čemu svaku leksemu zamenjuje odgovarajućim simbolom (tokenom).
2. Sintaksna analiza: Zadatak sintaksnog analizatora je da utvrdi da li je data naredba napisana u skladu sa formalnim opisom jezika. Koristi skup pravila kojima se opisuje taj jezik.
3. Semantička analiza: Proveravaju se dodatna semantička pravila kojima je dopunjen opis jezika.
4. Generisanje međukoda: Na osnovu apstraktnog sintaksnog stabla generiše se međukod programa.
5. Generisanje koda: Na osnovu međukoda generiše se ciljni kod programa (asemblerski ili direktno mašinski jezik).

Pojam formalne azbuke i reči

Formalna azbuka

Prilikom opisa jezika polazi se od azbuke. Neka je V konačan neprazan skup elemenata. Elementi skupa V su simboli ili slova, a sam skup je apstraktna azbuka.

Formalna definicija reči

Reč u kontekstu formalnih jezika definiše se kao konačan niz simbola azbuke V. Niz koji ne sadrži nijedan simbol naziva se prazna reč i označava se sa ε (epsilon).

Reči se formalno definišu sledećim pravilima:

• ε je reč nad azbukom V.
• Ako je x reč azbuke V i ako je a slovo azbuke V, tada je i xa reč azbuke V.
• Niz y je reč nad azbukom V ako i samo ako je dobijen primenom prethodna dva pravila.

Pojam formalnog jezika

Neka je data azbuka V. Skup svih reči nad azbukom V označava se sa V*. Skup V* je beskonačan. Formalni jezik nad azbukom V je bilo koji podskup skupa V*.

Osnovne operacije nad jezicima

• Reverzni jezik (Lᴿ): Skup svih transponovanih reči jezika L. Lᴿ = {xᵀ | x ∈ L}.
• Unija (L ∪ M): Obuhvata sve reči koje pripadaju jeziku L ili jeziku M.
• Proizvod (L ∘ M): Obuhvata sve reči koje nastaju nadovezivanjem reči jezika M na reči jezika L. Operacija nije komutativna.
• Potpuno zatvaranje (L*): Skup svih reči koje nastaju kao proizvod reči jezika L, uključujući i ε: .
• Pozitivno zatvaranje (L⁺): Definiše se kao: .

Formalna gramatika

Svaka formalna gramatika G se definiše kao torka G = {Vn, Vt, S, P}, gde je:

• Vn: Skup neterminalnih simbola.
• Vt: Skup terminalnih simbola.
• S: Startni simbol.
• P: Skup smena (pravila) oblika x -> y.

Jezik definisan gramatikom: L(G) = {w | S -*-> w, w ∈ Vt*}.

Automati i hijerarhija gramatika

Konačni automati

Konačni automati su uređaji za prepoznavanje regularnih jezika. Nemaju radnu memoriju, već predistoriju pamte preko promene stanja.

• Deterministički (DKA): Pod dejstvom istog ulaznog simbola prelazi u tačno jedno stanje.
• Nedeterministički (NKA): Pod dejstvom istog ulaznog simbola može preći u više stanja.

Tipovi gramatika po Čomskom

0. Tip 0 (Gramatike bez ograničenja): Praktično su sinonimi za algoritam.
1. Tip 1 (Kontekstne gramatike): Pravila su oblika |x| <= |y|. Nisu dozvoljena pravila x -> ε.
2. Tip 2 (Beskontekstne gramatike): Na levoj strani pravila nalazi se jedan neterminal (A -> y). Koriste se za opis programskih jezika.
3. Tip 3 (Regularne gramatike): Smene su oblika A -> aB ili A -> a. Koriste se za opis leksičkih elemenata.

Tjuringova mašina i Magacinski automati

Tjuringova mašina (TM): Ima radnu memoriju u vidu beskonačne trake. Opisuje se torkom Tm = {Q, V, S, g, q0, b, F}.

Magacinski automati (MA): Koriste memoriju organizovanu u vidu magacina (stack). Koriste se za prepoznavanje beskontekstnih jezika.

Leksička analiza u detalje

Zadaci leksičkog analizatora: Izdvajanje reči, određivanje značenja, uklanjanje belih simbola i komentara.

• Leksema: Ulazni niz koji se prepoznaje.
• Token: Izlazni simbol koji se generiše.
• Šablon: Regularni izraz koji opisuje ulazne nizove.

Sintaksna analiza

Sintaksni analizator proverava da li niz simbola pripada jeziku opisanom gramatikom. Postoje dva tipa:

• Top-down (odozgo naniže): Kreće se od startnog simbola ka ulaznom nizu (npr. LL algoritmi).
• Bottom-up (odozdo naviše): Vrši se redukcija ulaznog niza ka startnom simbolu (npr. LR algoritmi).

Problem leve rekurzije

Top-down analiza ne može da radi sa levo rekurzivnim gramatikama (A -> Ar) jer ulazi u beskonačnu petlju. Takve gramatike se moraju transformisati u nerekurzivne.

LL(1) i LR(0) analize

LL(1): Look-left 1. Predikcija se vrši na osnovu jednog simbola. Koriste se First i Follow funkcije za popunjavanje sintaksne tabele.

LR(0) član: Pravilo gramatike sa tačkom koja označava dokle se stiglo u prepoznavanju (npr. A -> α•β).

Operatorske gramatike

To su beskontekstne gramatike kod kojih ne postoje pravila gde su dva neterminala jedan do drugog. Između terminala se definišu relacije prvenstva: ·= (isti prioritet), <· (niži) i >· (viši).

Alati: JFlex i CUP

JFlex (Leksički generator)

Koristi direktive za podešavanje klase, brojača linija i makroa. Pravila se sastoje od regularnih izraza i Java koda.

CUP (Sintaksni generator)

Definiše terminale, neterminale, prioritete operatora i gramatička pravila. Omogućava detekciju grešaka pomoću ključne reči error.

Primeri koda

JFlex Specifikacija (Lexer)

import java_cup.runtime.*;

%%

%class Lexer
%cup
%line
%column

%eofval{
 return new Symbol( sym.EOF );
%eofval}

slovo = [a-zA-Z]
cifra = [0-9]
okta  = [0-7]
heksa = [0-9A-F]

%%

[\t\r\n ]  { ; }
,    { return new Symbol( sym.ZAREZ ); } // terminali

({slovo}|_)({slovo}|_|{cifra})*  { return new Symbol( sym.ID, yytext() ); } 

\'[^']*\'  { return new Symbol( sym.STRING_CONST, yytext() ); }
{cifra}+  { return new Symbol( sym.INT_CONST, Integer.parseInt( yytext() ) ); }

{cifra}+(\.{cifra}+)?[eE][+-]?{cifra}+ // realni br u eksp zapisu

CUP Specifikacija (MPPARSER)

import java.cup.runtime.*;

terminal START, END, CONST;
non terminal Element, Content, ElementList;

start with Element;

// Gramatička pravila
Element     ::= START Content END ;

Content     ::= CONST 
              | ElementList 
              | /* epsilon */ ;

ElementList ::= Element 
              | ElementList Element ;