Програма (апаратура), която извършва превод на входен текст в изходен текст

като всеки елемент от този масив има 3 елемента

Текущ блок – current_bl: last_bl номера на най големия присвоен блок; top_el указател към върха на стека; last_el индекс на последователен елемент в стека; За стек използваме масив s

S[1..N]=stack

B[1..M]- списък на блоковете, като всеки елемен има 3 полета

- Ако символа е променлива => в описателите съхраняваме тип, точност, проста променлива / масив => вида. Ако е масив е необходимо да се знае колко мерен е, ако е структура е необходимо да се знаят компонентите й, ако е формален параметър на функция – нейния тип, как се предава адрес на променливата. Ако ident е функция: външна ли е функцията дефинирана в дадена програма; връща ли тя стойност; ако е функция и връща стойност е необходимо да се знае типа на тази стойност; броя на формалните параметри и типа им.

1)Обратен полски запис (ОПЗ) - a+b=>ab+; преобразуване чрез стек

2)Тетради - последователност от 4 елемента  a+b=>+,a,b,t

пример: (a+b)*(c+d)

+,a,b,t1

+,c,d,t2

Безкобов запис. Тетрадите се разполагат в реда в който трябва да се изпълняват.

-,а

-,а, ,t

@,a, ,t

Основен недостатък-големия брой временни променливи които се добавят.

(<оператор>,<опер.1>,<опер.2>,<операнд 3>)

3)Триади- последователност от 3 елемента. Нямат проблема с временните променливи. Няма поле за резултат. Ако операнд в последствие се окаже резултат то трябва да се представи в триадата.

a*(b+c)

(1) +,b,c

Нужни са толкова триади, колкото и триади. Разликата при тетрадите е че има множество временни променливи. От където следва междинния код при триадите заема по малко място. При тетрадите ако разглеждаме временни променливи в регистри (програмно достъпните бързи регистри на процеса) проблема няма да е толкова голям.

4)Дървета

а+b

При откриване на грешка пропуска се някакъв минимален брой символи и продължава анализа нататък.

-пропускаме до символа в контекста,който е допустим.

Да се открие максималния брой грешки при едно преминаване през програмата.

На всяко правило на граматиката се съпоставя по една семантична подпрограма или още се нарича процедура.

Z→E; E→T|E+T|E-T|-T; T→F|F*F|T/F; F→id|(E)

Преход от инфиксен в ОПЗ

За всяко правило съществува подпрограма която се извиква всеки път с правилото U→X тя обработва не само в запис X. В масива P[ ] записваме обратния полски запис (ОПЗ). Семантичните процедури ще имат достъп до стека. За правилото E+T в инфиксен запис в процедурата ОПЗ ще се запише: E+T; P[k]=”+”; k=k+1; За F→id => P[k]=s[i]; k=k+1; където к е тек.указател а i е върха на стека.

(1) Z::=E =>empty(т.к нямаме терминални символи)

(2) Е::=Т =>empty (символ)

(3) E::=E+T =>P[k]=”+”; ++k;

(4) E::=E-T =>P[k]=”-”; ++k;

(5) E::=-T =>P[k]=”c”; ++k; (с- специален символ)

(6) T::=F =>empty;

(7) T::=F*F =>P[k]=”*”; ++k;

(8) T::=T/F =>P[k]=”/”; ++k;

(9) F::=id =>P[k]=s[i]; ++k;

(10) F::=(E) =>empty (скобите са терм. символи но в ОПЗ нямаме скоби )

Правила 3,4,7,8 са общи и могат да изглеждат по следния начин:

P[k]=s[i-1]; k=k+1;

A*(B+C)→ABC+* (в ОПЗ)

A*(B+C)

втора тетрада *,A,T1,T2

Анализ на изречението: E::=E+T

A*(B+C); F*(B+C); T*(B+C); T*(F+C); T*(T+C); T*(E+C); T*(E+F); T*(E+T); T*(E)

Тъй като при преобразуването ние получихме нетерминални символи (E,T) за да се генерира първата тетрада са ни необходими B и C, които сме загубили при анализа.Необходимо е:

E,B

T,A T,B T,C

| | |

F,A F,B F,C

A *(B + C )

При представянето на всеки нетерм символ трябва да имаме по една структура U с поле sem, в което я идентифицираме

U struct {… identifier sem; } U;

1)Z→E=>Z.sem=E.sem;

2)E→T=>E.sem=T.sem;

3)E1→E2+T=>i=i+1; E1.sem=Ti; GEN(“+”,E2.sem,T1.sem,E1.sem);

4)E1→E2-T=>i=i+1; E1.sem=Ti; GEN(“-”,E2.sem,T1.sem,E1.sem);

....10)

Семантична обработка при низходящ анализ

Z::=E; E::=[-]T{“+|-“T}; T::=F{“*|/”F} F::=id|(E)

char *SYM; //текущия символ

extern void sem ();

void Z(){ scan(); E(); }

void E() {

if(SYM= = “-”) scan(); T();

while((SYM= = “+”)||(SYM= = “-”)) {

scan(); T();

} }

F(); while((SYM= = “*”)||(SYM= = “/”)) {

scan(); F();

} }

if(SYM= =”id”) scan();

else if(SYM!=”(”) error();

else { scan(); E();

if(SYM!=”)”) error();

else scan(); } }

Семантиката на всеки от нетерминалните символи на граматиката е името на времената променлива от програматаT(i).В променливата SYM се занася съкращението id, а в sem се занася самия идентификатор.

char *SYM;

exterm void scan(); /* SYM = “id”; , sem=”identifier name”; */

void F(char *x){

if(SYM = =”id”) {

x=sem; scan(); }

else if(SYM!=”(”) error();

else { scan(); E(x);

if(SYM!=”)”) error();

else scan(); }}

void T(char *x) {

char *y,*z,*op,*t;

F(y);

while((SYM= = “*”)||(SYM= = “/”)) {

scan(); F(z);

i=i+1; t=NEW_NAME(i); /* генериране на нова променлива */

GEN(op,y,z,t);

y=t; op=SYM;

} }

void E(char *x);{

if(SYM = =”-”) { scan();

T(); i=i+1; t=NEW_NAME(i);

GEN(“-”,0,z,t); y=t;

}else T(y);

op= SYM;

scan(); T(z); i=i+1;

t=NEW_NAME(i); /* генериране на нова променлива */

GEN(op,y,z,t); y=t; op=SYM; }

x=y; }

void Z(){

Генератора на код е тази част от програмата, която е свързана с конкретния текст.

• 
  Абсолютен код – код, който е свързан с абсолютни адреси, зрежда се точно на определен адрес и започва да се изпълн.
  
• 
  Преместваем код – код, който трябва да се настрои за конкретни адреси и после да се използва; използва се при разделна компилация (прогр. Се представя на отделни части, компилират се и после се свързват.)
  
• 
  Авитокод – езика асемблер, компилатора генерира код на езика от асемблер;
  
• 
  Пикод – P code – когато компилатора енерира код на виртуална машина трябва да има интерпретатор които да чете кода.
  

• 
  Простота на компилатора;
  
• 
  Бързина на компилация;
  
• 
  Възможност за разделна компилация;
  
• 
  Размер на кода(да е малък);
  

Машина:

ST M: ACC->M

ADD M: ACC=ACC+M

SUB M: ACC=ACC-M

MUL M: ACC=ACC*M

DIV M: ACC=ACC/M

NEG ACC=-ACC

BR E GOTO E

BRN E if ACC<0 goto E

BRP E if ACC<0 goto E

BRZ E if ACC<0 goto E

Тип:

Typedef char *string;

Extern void GEN(string, string);

GEN(”ADD”,”VAR1”)=> ADD VAR1

String ACC;

Генерация на код след тетради: във всеки момент в АСС имс стойност. Ако тя е нужа в следващите изчисления, то ние няма смисъл да я зареждаме, но ако не е ние я изхвърляме и зареждаме тази пром., която ще ни трябва.

За да се излючат излишните LD и ST инструкции, по време на изпълнението трябва да се следи съдърж. На АСС. За целта ще изпползваме String ACC. Значението на АСС (съдърж.) По време на копилация, ще съответства на значението на акумулатора по време на изшълнение на прогр.

If(strlen(ACC)==0){/*акумулатора на CPU е свободна*/

За да се генерира команда за генерариране на Х и Y в ACC, ние ще използваме GET_IN_ACC(X,Y), които:

GET_IN_ACC(X, “ ”)=>LD X

При разработването на GET_IN_ACC трябва да се има в предвид, че някои операции не са комутативни(операцията „-” и др.)

Typedef struct{

String eop;

String op1; тетрадата е от

String op2; следния вид

String op3; (+,A,B,T)