Predavanje 13 - Prevodioci

1. Prevodioci

Prevodioc je program koji prevodi (korektan) program napisan u jednom jeziku u program napisan u drugom jeziku.

Primjeri:

2. Gramatika

Svaki programski jezik mora imati strogo specificiran u gramatiku koja definira onovni skup simbola (tokena) iz kojih se grade kroz strogo propisana pravila stringovi koji predstavljaju recenice u danom jeziku. Gramatiku programskog jezika C mozete vidjeti u A.13 u knjizi "The C programming language".

Mi cemo napisati prevodioc koji uzima nizove aritmetickih izraza ciji je kraj signaliziran sa ; iz prefiks oblika u postfiks oblik.
(a+((b*c)*(d+e)))*f abc*de+*+f* x+y*4+8 xy4*+8+ x div y; x y DIV (DIV oznacava cjelobrojno djeljenje) x mod y; x y MOD (MOD oznacava cjelobrojno djeljenje)

Prije nego sto krenemo na rjesavanje ovog problema moramo precizirati vise stvari. Moramo specificirati gramatiku u kojoj se nama prihvatljivi izrazi pisu. Krenimo redom.

2. Parsiranje

Parsiranje je proces odredjivana je li zadani string moze biti generiranoj u danoj gramatici. Ocigledno je parsiranje vrlo vazno u konstrukciji programa prevodioca. Iz gornjeg opisa gramatike dobijemo iduci rekurzivni nacin parsiranja.

start -->list eof(kraj unosa) list -->expr; list (izrazi odvojeni tocka zarezom) | prazna lista (ovdje i dalje karakter | oznacava ili) expr -->term moreterms moreterms -->+term (ispisujemo '+') moreterms |-term (ispisujemo '-') moreterms | prazna rijec term -->factor morefactors morefactors -->* factor (ispisujemo '*') morefactors |/ factor (ispisujemo '/') morefactors |div factor (ispisujemo 'DIV')morefactors |mod factor (ispisujemo 'MOD') morefactors |prazna rijec factor -->(expr) | id (ispisujemo vrijednost odgovarajuceg stringa) | num (ispisujemo brojku)

Ovo se direktno translatira u C -kod koji se nalazi u parser.c.

void parse(){ lookahead=lexan(); /*uzmi iduci token*/ while(lookahead!=DONE){ expr(); match(';'); /*svaki izraz mora zavrsiti sa ;*/ }/*end while*/ }/*kraj funkcije parse*/ void expr(){ int t; term(); while(1){ switch(lookahead){ case '+': case '-': t=lookahead; match(lookahead); term(); emit(t, NONE); continue; default: return; }/*end switch*/ }/*end while(1)*/ }/*kraj funkcije expr*/ void term(){ int t; factor(); while(1){ switch(lookahead){ case '*': case '/': case DIV: case MOD: t=lookahead; match(lookahead); factor(); emit(t, NONE); continue; default: return; }/*end switch*/ }/*end while(1)*/ }/*kraj funkcije term*/ void factor(){ switch(lookahead){ case '(': match('('); expr(); match(')'); break; case NUM: emit(NUM, tokenval); match(NUM); break; case ID: emit(ID, tokenval); match(ID); break; default: error("syntax error"); } } void match(int t){ if (lookahead==t) lookahead=lexan(); else error("syntax error"); }

3.Ostali moduli prevodioca

Program prevodioc dolazi u sedam izvornih datoteka: