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



Дата06.02.2017
Размер290.82 Kb.
1: Транслатор – преводач. Програма (апаратура), която извършва превод на входен текст в изходен текст.

Класификация на базата на нивото на входния и обектния език:

Компилаторът е транслатор който превежда текст на език от високо ниво в текст на асемблерен или машинен език. От машинен език не се превежда в машинен => използва се средство {} за това изпълнение. Използва се за извършване на симулация/емулация при вземане на програма от 1 процесор и нейното изпълнение върху друг процесор.

Macro емулатор- macro генератор/асемблер- извършва се превод от машинен език в друг машинен език. – за голяма последователност от машинни инструкции. Преобразуването на няколко последнователности от текст в други последователности с различна големина.

За останалите няма транслатори т.к. този превод е нееднозначен.

High Level language Machine – машина, която разпознава език от високо ниво (не и трябва транслатор)

Интерпретация – когато директно нашата програма се изпълнява без превод (за първи път – езика Basic)

Предимство на интерпретаторите



  • програмата директно се интерпретира => всички съобщения за грешки могат да са в термините на съответния език

  • изменения в програмата при компилация могат да се прекомпилират (не се налага да се изчаква някакъв етап)

Недостатък – по бавен е; изпълнението на програмата става много бавно => това е основната причина за тяхното рядко ползуване

Входна програма частичен компилатор  р-код интерпретация

При компилатора реално имаме 3 езика – Т- образна диаграма:

Тогава когато обектния и инструменталния езици са еднакви => компилатора е резидентен, а когато са различни е кроскомпилатор. Когато входния език и инструменталния са еднакви..............

Bootstrapping на компилатора – подход


  1. Лингвистичен подход – лексикален/лексичен анализ- да съответства на входния език. Правим анализ на изречението, че да съответства на правописа на дадения език и после му правим превод.

  2. Лексичен анализ (сленер) – занимава се с лексиката на езика (последователност от букви които трябва да се разпознаят). Идентифиактори, константи, оператори, ключови думи ако те са допустими във входния ни език.

  3. Синтаксис – проверява (определя правилата за използване на лексиката) изграждането на изреченията

  4. Семантика – правила за използване на синтаксиса. Може да има изречение, което да е вярно лексично и синтактично, но не и семантично. Например: променливите да са от различен тип а=(б+с)*д; т.к. в езика не са допустими операции за присвояване на char and read или други подобни. Правилност на блоковата структура и дали типовете данни са допустими -> прави се такава проверка.

В зависимост от броя на сканиране на входните изречения те са еднопасови и многопасови.

2Формално определяне на езиците за програмиране

  1. Азбука – всяко непразно множество от различни помежду си елементи (букви/символи). Биват крайни и безкрайни- обозначение А

  2. Изречение (редица) – крайна последователност от букви

A={an,bn,cn} изречения: abc; aabcc; aaabccc

A* - множество от всички възможни изречения изградени от азбука А плюс така нареченето празно изречение (Е)

А+ - множество от всички възможни изречения изградени от азбука А, но без празното изречение (Е)



  1. Език – дефинира се подмножество на А*, където: L е подмножество на А* (А се нарича азбука на езика L); L1 е подмножество на L2. За да бъде дефинирано в езика трябва да се дефинират всички изречения от азбука А

  2. Граматика – G=(Vt, Vn,P,S). Всяка формална граматика е подредена четворка, където Vt е множество на термини, символи...... За дефиниране на безкраен брой изречения се използва редукция.

A={0n 1n}….00..01..1..

Правила


  1. S->0S1- S опр. чрез S (само себе си) => рекурсия

  2. S->E

Изречение 000111 -> S=>0S1=>00S11=>000111

Vt- множество терминални символи – с тях завършва извода

Vn – нетерминални символи – присъстват в правилата, но в края на изречението ги няма

P – множество на правилата

S – стартов символ на граматиката

P->( ) подредена двойка

- ред на правилата, като може да е празно изречения

A={ambn|m,n>=0}

GL=({a,b},{S,A,B},P,S)


  1. S->AB;

  2. A->aA

  3. A->E

  4. B->bB

  5. B->E

Пример: aaabb – това изречение принадлежи към GL: S=>AB=> aAB=>aaAB=> aaaAB=>aaaB=>aaabB=>aaabbB=>aaabb

Изреченията на дадения език може да се извеждат от повече от една граматика. Такива граматики се наричат еквивалентни. Използват се често във формалната лингвистика.

GL2=({a,b},{S,Y},P,S)


  1. S->aS

  2. S->a

  3. S->b

  4. S->bY

  5. Y->b

  6. Y->bY

  7. Y->E

*присъствието на празно изречение не се смята за разлика и не е проблем за тяхната еквивалентност. Chomsky – класификация на граматиките



  • тип 3 (автоматични граматики/линейни/регулярни)

A->a A->a

A->Ba A->aB

Ляво линейни или дясно линейни


  • тип 2 (контексно свободни)

А->

  • тип 1 (контексно зависими) по малък брой символи

  • тип 0 (никакви ограничения на правилата)

тип 0 е основното а останалите са негови подмножества

I->б/бRако заменим: б- буква R->б/ц ц- цифра

R->бR/цR R- остатък

I- идентификатор

*идентификатор- последователност от букви и цифри, започваща с буква. Идентификатор е елемент на лексиката в 1 език. С граматиката от тип 3 може да се опише лексиката на 1 език за програмиране.

Скобкови структури- скобите – to, while, begin, end

Те не могат да се опишат от граматиката тип3 и не могат да се опознаят от крайния автомат. Те се разпознават от стек паметта

S->(S) правило за вложени скоби.... това съответства на тип 2 т.е. описание на този тип структури става чрез езиков тип 2.

*разпознаване на синтаксиса става чрез КА със стек

БНФ – BNF форма

Бекус Наурова / нормална форма

Премини -> ::=



нетерм. символ

А:={a}A->aA (a,n-пъти а, Е)

А->Е

3.Граматичен разбор и проблеми

Пример на граматика – контексно свободна (1,3,3) – определя се от тях



  1. Е->Е+Т x,y,*,+,(,) – терм. символи

  2. Е->Т Е,Т,F- нетерм. символи

  3. Т->Т*F

  4. T->F E- expression

  5. F->(E) T- term

  6. F->x F- factor

  7. F->y

Можем да опишем произволни изрази вклчително плюс умножение и скоби

Например: (x+y)*x

Когато имаме даден израз трябва да му направим граматичен разбор

Правила към най- десния терминал

Е=>Т Е=>Т

Т=>T*F =>Т*F

=>F*F =>T*x

=>(E)*F =>F*x

=> (E+T)*F =>(E)*x

=>(T+T)*F =>(E+T)*x

=>(F+T)*F =>(E+F)*x

=>(x+T)*F =>(E+y)*x

=>(x+F)*F =>(T+y)*x

=>(x+y)*F =>(F+y)*x

=>(x+y)*x =>(x+y)*x

If B1 then if B2 then S1 else S2

If B then S1 else S2

Разбор - Всяко правило представяме като елемент от домино

Рамената могат да се разтягат

Е- е стартов символ G=(VT,VN,P,S)

(x+y)*x – израз

Дърво:Произволен избор за започване на строеж на дървото. Ако е от анализа към изречението- низходящ, ако е от изречението към стартовия символ е възходящ.

Низходящ – заменяме левия терминал с десния т.е. правилата се прилагат от ляво на дясно. При възходящ е обратното. Според това как сканираме/четем изречения от дясно на ляво или от ляво на дясно.

4.Лексичен анализ (лексикален)

Крайният автомат трябва да е детерминиран – ако при определен входен сигнал аз мога да направя само 1 точно определен преход. Ако имаме избор на преходите имаме недерминиран КА. => се стремим да построим детерминиран КА



Лексичен анализатор

Bool notendofsourse = TRUE;

Do { //чети буква

//класифицирай

//изгради символ

// запиши междинен код

}while (notendofsource);



Общи неща:

  • два основни метода за изграждане на програма (top-down, bottom-up)

  • класификация чрез switch

  • пропускане на празните символи

  • форм на число – да сканираме последователно всички числа от автомата и да ги направи цели числа

  • последователни са кодоветена цифрите в ASCII символи

  • при форматирането на стойности да се направи алгоритъма, така че да не се препълни разрядната мрежа

  • представими диапазони на числата

  • нормализира число- ако след запетаята числото е 1 => мантиса <1

използва се за разширяване на разрядната мрежа на значещото число след запетаята

  • ненормализация- разширяване на диапазона на числата за сметка на точността

Идентификатори:

  • таблици за съхраняване на ID

........ малка схема

ID се разпознават само ако са в таблицата и по първите 32 символа. Броят на ID се определят от таблицата. При препълване на таблицата се извежда съобщение => разделно компилиране (разбиване на програмата на части)



5.Работа с таблици:

  • търсене на ID – проверка за стойността му

последователно търсене: алгоритъм за линейно търсене

i=-1


do {

i+=1;


}while((a[i]!=x)&&(i!=N-1));

If (i>N-1)

Всеки път делим на 2 и търсим, като всяка половина делим пак на 2 и т.н. Броят сравнения е логаритъм при основа 2 от броя на елементите в таблицата, но елементите в таблицата трябва да са сортирани. Сортирането е бавен процес => използваме хеширане. Хешираната функция трябва да е равномерна- но такива няма. Има колизии т.е. подаваме 1 ID няколко пъти и получаваме различни стойности. Броят на хешираните функции е равен на броя символи в 1 ID. Най често използваме хеширана функция => сумиране на ASCII кодовете на идентификатора. Достатъчно бърза е и равномерна, но пак може да доведе до колизии.

Най чести проблеми на лексичния анализ:

Недерминираност на анализа- среща на операции като < или <= от което следва да се върнем и да продължим в друга посока. Малко са тези случаи



6. Синтактичен анализ

Начините на формирането на езика касаят синтактичния анализ. Разпознаването става с автомат на стек

LL(1)- граматики

LL1 –граматика на основата на която може да се изгради детерминиран синтактичен анализ (по метода отгоре- надолу) по низходящ метод.

Ограничения правила – продукция

A::=L1|L2|….Ln

Function first(L)


  1. first (bbeta)={b}- ако първият символ на аргумента е терм.

  2. B::=beta1|beta2|…beta(n)

First(B2)=first(beta1)обединено с first(beta2)…….first(betan)

Пример:


S->A/B

A->xA/y


B->xB/z

Началните символи на всяко отделно правило не трябва да съвпадат.

Можем да преобразуваме граматиката в еквивалент, на който ще се описва вече други правила, които спазват първото ограничение

S->C/xS


C->y/z

Недерминиран анализ позволява връщане назад

S->Ax


A->x/E

Второ ограничение



Функция follow ако,

X::=rAn

Follow(A)=first(n)



Ako

n->E


тогава folow(x)<=follow(A)

  1. A->B/AB – рекурсия – повтаряща се конструкция- B,BB,BBB

  2. A->E/AB

  3. A->E/BA- включва ограничения 1 и 2

Разликата е , че в 1 и 2 рекурсивния символ е в лявата част а при 3 е в дясната. Ако върху правилата на първата контекстна граматика наложим тези ограничения то получаваме G LL(1) , която описва език върху ограниченията, на който може да се приложи низходящ рекурсивен анализ G1=>G2(LL(1))

7. Преобразуване на граматиките

Метод на факторизацията

S->aSb

S->aSc


S->E

  • преобразуване G =>

S->aSХ

S->E


Х->b

Х->c


премахването на лявата рекурсия става по същия начин: чрез въвеждане на допълнителен нетерминал или въвеждане на дясна рекурсия.

Построяване на низходящ синтактичен анализатор (рекусивен)

  • построяване на графи от правилата на граматиката : A::=Alfa1|L2…|Ln

  1. терм. Символ

  2. нетерм. Символ

  3. A::=L1/L2…/Ln scheme

  4. A::=L1L2…Ln scheme

  5. A::={L} цикъл do while scheme

Транслация на синтактичната графика в програмата

3.Цикъл: while(ch INS) {P(S);}



Анализираме синтактичния анализатор

  • преобразуваме графа в програма извършваща синтактичен анализ нетем. Символи A, B, C => реализира 3 функции

void B(){

A();


C();}

Void C(){

While (ch==’+’)

{

Ch=getchar();



A();}

}

Void A(){



If(ch==’x’) ch=getchar();

Else if(ch==’(’) {

Ch=getchar();

B();


IF(ch==’)’) ch=getchar();

Else error();

}else error();}

Void main(){

Ch=getchar();

A();}


Всяка рекурсия се реализира чрез стек. Изпълнителната система на езика ни реализира стека (а чрез него се реализира рекурсията от нея)

8.Табличен управляем синтактичен анализ

Пример:


A::=x/(B)

B::=AC


C::={+A}
Низходящ рекурсивен анализ- предимства

  1. по време на анализа не се изисква връщане назад. Метода не е детерминиран, имаме еднозначен преход при постъпване на даден символ на входа-> постъпващия символ е лексема

  2. времето на разбор на изречението е пропорционално на дължината на програмата

  3. има добри възможности за диагностика ; евентуалните грешки се разпознават при първия приет символ. Можем да дадем информация за грешките

  4. таблиците се получават много по малки от други методи

10.Възходящ синтактичен анализ

  1. ->real

  2. ->,

  3. ->

  4. ->a/b/c/d

Методи за анализиране:

  • универсален метод – названието идва от името на граматиката която анализира LR(k). основава се на възходящ анализ. Притежава всички конфликти от типа: преместване- превеждане, превеждане- превеждане. Те могат да се разрешат на основа на вече прочетения контекст и фиксиран брой допълнително прочетени символи.

К=0 или 1 при G->LR(k). За да може да се реализира този анализ използваме LR таблица на граматичния разбор.



  1. ->real

  2. ->,

  3. ->

  4. ->a/b/c/d




съст.

S

IDLIST

ID

Real

,

a/b/c/d

_)_

1

stop







S2










2




S5

S4







S3




3













R4




R4

4













R3




R3

5







S7




S6




R1

6
















S3




7













R2




R2

В таблицата на разбора се съдържа по един сълб на всеки терм. Или нетерм. Символ. Редовете съответстват на състоянието на анализатора. Всяко състояние съответства на позицията от/в правило на граматиката, което е достигнала анализатора. Таблицата включва елементи от 4 типа:

1. Sx – елементи на преместване

2. елемент на превеждане Ry- да се изпълни превеждане по правило у. Ако в дясната част на правило у има н символа, то да се махнат тези символи от върха на стека. Автоматът преминава в състояние което се намира на върха на стека.

3. елемент на грешка- всички празни квадратчета се смятат за синтактична грешка

4. елемент на завършване stop- само един елемент за успешно завършване на разбора

Израза е програма, която при реализацията се слага във файл, затова края се задава с eof. 12.Построяване на таблица за RL разбора



  1. ->real

  2. ->,

  3. ->

  4. ->a/b/c/d

Конфигурация (1,0) . тя се използва, за да се представи предвижването по правилата по време на разбор. Състоянията в таблицата съответстват на конфикурацията на граматиката с малка разлика: конфигурациите които са неразличими от G съответно на 1 състояние. От дадено състояние несъществуващо за края на правило може да премине в друго състояние въвеждайки терм или нетерм символ. Това състояние се нарича приемник. Новата конфигурация която се получава при операция образ на приемник се нарича базова. Процедура: започваме от конфигурация (1,0) и последователно изпълняваме операциите образ на приемник и обединение докато всички конфигурации не се окажат включени в дадено състояние.

състояние

база

Обединение

1

1,0

{(1,0)}

2

1,1

{(1,1) (2,0) (3,0) (4,0)}

3

4,1

{(4,1)}

4

3,1

{(3,1)}

5

2,1-1,2

{(2,1) (1,2)}

6

2,2

{(2,2) (4,0)}

7

2,3

{(2,3)}

Обяснение на правило 1

Ако след базова конфигурация следва нетерм то всички конфигурации съответстват на точките най-ляво в правилата за този терминал, образуват обединения за тази базова конфигурация

Обяснение на правило 2

Ако след конфигурация с еднакво състояние следва еднакъв терм или нетерм символ то следвашите състояние са неразличими за автомата



съст.

S

IDLIST

ID

Real

,

a/b/c/d

_)_

1

stop







S2










2




S5

S4







S3




3













R4




R4

4













R3




R3

5







S7




S6




R1

6
















S3




7













R2




R2

Действията на анализатора – преместване са аналог на операцията образуване на приемник => действието преместване се формира според операцията образ на приемник.

13. Изход на синтактичен анализ

Най-често срещаните форми:

а(+)b-инфиксен израз, т.к. операцията е м/у операндите [(а+b)*(с+d)]

+аb – прeфиксен метод на запис -операцията предхожда операндите [*+ab+cd]

аb+ - постфиксен метод – или „обратен полски запис”- ОПЗ [ab+cd+*], най-често се използва.

Този метод не използва скоби, изчислението може да бъде направено директно чрез стекова машина.

→ab+cd+* стек 2(операнда)push + (операнд) execute

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



Преобразуването от инфиксен в ОПЗ става чрез стек.

Пример: -a ≡ 0-a

-0a; Унарен „-” ≡ @; -а->а @; (а+b)*(c+d)

Двоично дърво ≡ ОПЗ

Транслиращи граматики - това е контексно своб. граматика, множеството термални символи, на която е разбито на входни и изходни символи.

; Нетерм {E,T,P}; Стартов символ { E }



Транслираща граматика: описва аритм. изрази, произволни изречения

  1. E -> E+T{}

  2. E-> T

  3. T->T*P{}

  4. T->P

  5. P->(E)

  6. P->a{ }|b{ }|c{ } - в правилата където има скоби няма да има изх. символ;

=>(a+b)*c отговор (без изх. символи контексно свободна граматика)

E=>T=>T*P=>P*P=>(E)*P=>…..(a+b)*c



При ТГ

Е=>Т=>Т*P{*}=>P*P{}=>(E)*P{}=>(E+T{})*P{} ……=>(a{}+b{}{})*c{}{}

(a+b )*c ≡ (a+b)*c и ab+c* ≡ab+c* ОПЗ

Генериране на ОПЗ след анализиране на граматиката



14. Организация на паметта по време на изпълнение на програмата

Класификация - областите от данни се делят на: статични и динамични

Статичните (статична памет) - се отделят за цялото време на изпълнение на програмата. Динамичните – не винаги присъстват в паметта от нач. на изпълн. на програмата, а се появяват и изчезват (като губят всички ст-ти, които са се съхранявали в тях) в паметта динамично.

Динамични променливи в „С”- вс променливи в рамките на някакъв динамичен блок



Отделяне на памет за елементарни типове данни

int

long int

real

pointer

Изброим тип данни – enum color=(red(0),blue(1),yellow(2)); Чрез int се представя, като се присвояват ст-ти /1,2,3/

Или char - 255 ст-ти могат да се присвоят

Пакетирани ст-ти = 2-ия ел-нт се добавя плътно към предходния елемент.



Памет за масиви

1.Масивите могат да се представят чрез вектори (но само едномерните масиви). Индекса ще изменяме от 1 до 10 за универсалност А[1],A[2],…,A[10]

В масива индекса запазва от ‘0’ т.к самият масив е реално указател.


  • С нарастване на индекса  увелич. адреса на ОП

  • С намаляване на индекса  намалчва адреса на паметта

1 Метод: Матрици – Двумерен масив – представя се чрез таблица с редове и колони. Има значение как разполаг. последователните адреси дали по редове или по колони.

FORTRAN по колони разпол. последователните адреси; в ‘ С ‘ – по редове ....

[1….M,1…N]

A[1,1] A[1,2]…A[1,N]

A[2,1]…………A[2,N]

……………………….

A[M,1]………..A[M,N]

Намирането на клетка с адрес А[i,j]

Address(A[1,1])+(i-1)*N+(j-1)

1ви ел-нт ел-нт ред



(Addr(A[1,1])-N-1)+(i*N+j)

(Addr(A[1,1])-N-1) – CONST може да се изчислява преди началото

(i*N+j) – VAR изчислява се по време на работа на програмата

2 Метод Вектор



Такава организация се изпол. само когато имаме ограничена памет и не можем да съберем целия масив в паметта.

3. Метод Хеширанепри матрици които са разделени, гол.част от ел-нтите им имат еднакви ст-ти напр нула.

Многомерни масиви

A[L1….U1][L2…..U2]……[Ln……Un] //L горно, U-долно

А[i, *,*…..*]

A[L1,*….*], A[L1+1 ,* ….*]

A……….., A[U1, *……..*]

A[I, L2, ….]…..



Възможно е да се дефинира масиви при компилациите на които не се знае мах бр. ел-нти. Това става известно време при изпълн. на прогр. Това са динамични масиви т.е. с неизвестен бр ел-нти по време на компилация, а получаване на тази инф. по вр. на изпълнение на прогр в зависимост от данните, които постъпват се опр. броя им.






15.Информационен вектор - по време на изпълн. на прогр се допълват празните места.

В ’С’ стринг низ:



Памет за ≠ структури – заделя се място за елементи като вс. от тях е с ≠ дълж

В тях може да имаме обединение Union т.е. няколко типа данни. Заделяме няк. място според най-гол. тип данни. Една и съща област от данни 1 път я разглеждаме като int, др. път като char и т.н.

Параметри на процедури и ф-ии

Int func1(ina a, char b, ….) // a и b формални парам.{ Дефиниция на функцията – парам се наричат фактически парам

а= b= }

При реализ. на предав на парам. вътре във ф-ията става по няколко начина:



- По ст-ст (by value)- създ. копие първо и предаваме това копие, т.е ф-ията не може да промени оригинала. Масив неможе да предава по ст-ст.

  • По адрес ( by reference) – предаваме адреса на фактическите парам и вътре във ф-ията можем да променим факт. парам.

- по име (by name) –няма значение позицията на аргумента, а той се предава само по име

func1(…. Arg1=10,…..) В макро езиците се използва



Организация на паметта при извикване на процедури и ф-ии

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

1)global vars - с глобални променливи; 2)return address; 3)evaluation stack – викаме func1(…) – работен стек за изчисления; 4) локални пром (в раб стек са); 5) return address (да върне в stack); 6) static pointer – сочи обхващащия блок; 7)dynamic pointer – къде се намира стека – сочи точка на връщане; 8) evaluation stack за func1(..) тук викаме : local vars и func2

16. Семантичен анализ Основна задача - проверка за правилност на използване на всички конструкции, идентификатори (променливи, функции) и константи изхождайки от: правилата за видимост в/у езика ( блокова структура основно правило); ограниченията в реализацията се проверяват от семантичния анализ; разликата е в допълнителни възниквания към реализация на самия език

Пример:

program block;

var a,b,c,d,..

procedure p1;

var e,f,..

begin L1:..end;

procedure p2;

var g,a,h,..

procedure p3;

var a,..

begin .. end;

begin .. L2 .. end

begin..


1 a,b,c,d

2 e,f


L1 етикет

3 g,a,h


L2

4 a


Не можем да виждаме идентификатора в други блокове. Всеки следващ номер на блок вижда идентификатора в преходния му блок.

Последователноста на претърсване на блоковете с цел намиране:



  1. Претърсване на текущия блок за даден идентификатор

а) ако е намерен преход към т.3

b) ако не е намерен преход към т.2

2. Точка 2 на алгоритъма- претърсване на обхващащия блок

a) ако е намерен преход към т.3

b) ако не е намерен „последен ли е блока?” т.е. най-външен→ ако да преход в т.4; → ако не преход в т.2

3.Действия свързани с проверката на семантиката (правилност на използване на типовете)

4.Грешка- недефиниран идентификатор

Идентификатора по време на анализа се съхранява в таблици. За всяко ниво има отделна таблица, която се нарича display по време на компилацията се нарича display по/за времето на компилация.

Run time display/frame

i -номер на блока; s-block – номер на обхващащия блок; N_entry – брой идентификатори дефинирани в съответния блок; pointer – указател към началото на списъка на ident за даден блок



::= beginend

::={}

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

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

S[1..N]=stack

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







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



17.Вътрешни форми на програмата

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

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

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

+,a,b,t1

+,c,d,t2


*,t1,t2,t3

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

-,а

-,а, ,t


-,0,a,t

@,a, ,t


@-унарен минус

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

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

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

a*(b+c)

(1) +,b,c



(2) *,a,(1)->номер на триадата

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

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+* (в ОПЗ)



Стек S

Тек сим.

Остатък от низа

№ на правило

№ на сем. процедура

ОПЗ масив

P[ ]




A

*(B+C) ┴

-

-

-

┴А

*

(B+C) ┴

9

9

A

┴F

*

(B+C) ┴

6

6

A

┴T

*

(B+C) ┴

-

-

A

┴T*

(

B+C) ┴

-

-

A

┴T*(

B

+C) ┴

-

-

A

┴T*(B

+

C) ┴

9

9

AB

┴T*(F

+

C) ┴

9

9

AB





































┴z

1




stop




ABC+*

18.Преход от инфиксен запис в тетради

A*(B+C)


първа тетрада +,B,C,T1

втора тетрада *,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();

} }


void T() {

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

scan(); F();

} }


void 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);


op=SYM;

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);{



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

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

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

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

}else T(y);

op= SYM;


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

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

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

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

x=y; }

void Z(){



char *x; scan(); E(x); }

19.Генерация на код

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



Форми на обектния език

  • Абсолютен код – код, който е свързан с абсолютни адреси, зрежда се точно на определен адрес и започва да се изпълн.

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

  • Авитокод – езика асемблер, компилатора генерира код на езика от асемблер;

  • Пикод – P code – когато компилатора енерира код на виртуална машина трябва да има интерпретатор които да чете кода.

Цели:

Но тези изисквания са взаимнопротиворечиви.

Пример: Имаме машина, която има само един акумулатор – нарича се суматор.

Машина:


LD M: M->ACC

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)



} tetrage;

Tetrage PMG[…];


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница