Компилятор

Сентябрь 2, 2022

Главная
Алгебра
Компилятор

Содержание

2. Компилятор – транслятор, осуществляющий перевод исходной программы в эквивалентную ей объектную программу на машинном языке Схема
3. Системное Программное Обеспечение Таблица идентификаторов – специальным образом организованные наборы данных, служащие для хранения информации об
4. Метод рехэширования с помощью произведения Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции
5. Блок-схема добавления элемента в ТИ по методу рехэширования с помощью произведения
6. Блок-схема алгоритма поиска элемента в ТИ, организованной по методу рехэширования с помощью произведения
7. Метод организации ТИ простым списком При использовании данного метода элементы таблицы располагаются в порядке поступления. Поиск
8. Блок-схема добавления элемента в ТИ по методу простого списка
9. Блок-схема алгоритма поиска элемента в ТИ, организованной с помощью метода простого списка
10. Системное Программное Обеспечение Результаты Метод рехэширования с помощью произведения: – всего сравнений: 8; – в среднем
11. Лексический анализатор Лексический анализ – часть компилятора, которая читает литеры программы на исходном языке и строит
12. Граф конечного детерминированного автомата
13. Пример обработки текстового файла prog repeat {начало цикла} begin if ((Cnt>-1)and(Result>0)) then begin Cnt--; Result:=5-Cnt; end
14. Результаты обработки текстового файла (фрагмент)
15. Синтаксический анализатор Синтаксический разбор – выделение синтаксических конструкций и проверка синтаксической правильности программы. Распознаватель – алгоритм,
16. Контекстно-свободная грамматика в форме Бэкуса-Наура: G({prog, end., if, then, else, begin, end, repeat, until, or, xor,
17. Множества крайних левых и крайних правых символов грамматики G . Результат
18. Множества крайних левых и крайних правых терминальных символов грамматики G. Результат
19. Остовная грамматика G’, полученная на основе исходной грамматики G’({prog, end., if, then, else, begin, end, repeat,
20. Результаты работы синтаксического анализатора (фрагмент)
22. Скачать презентацию

Слайд 2

Компилятор – транслятор, осуществляющий перевод исходной программы в эквивалентную ей объектную

программу на машинном языке

Схема трансляции:

Слайд 3

Системное Программное Обеспечение
Таблица идентификаторов – специальным образом организованные наборы данных, служащие

для хранения информации об элементах исходной программы.

Методы организации ТИ:
Простой список;
Упорядоченный список;
Простое рехэширование;
Рехэширование с использованием псевдослучайных чисел;
Рехэширование с помощью произведения;
Бинарное дерево;
Метод цепочек.

Слайд 4

Метод рехэширования с помощью произведения
Для организации таблицы идентификаторов по методу рехэширования

необходимо определить все хэш-функции h[i] для всех i. Чаще всего функции h[i] определяют как некоторые модификации хэш-функции h.
h[i](A) = (h(A)∙i) mod N,
где N – максимальное значение хэш-функции.

Слайд 5

Блок-схема добавления элемента в ТИ по методу рехэширования с помощью произведения

Слайд 6

Блок-схема алгоритма поиска элемента в ТИ, организованной по методу рехэширования с

помощью произведения

Слайд 7

Метод организации ТИ простым списком
При использовании данного метода элементы таблицы располагаются

в порядке поступления.
Поиск в этом случае требует сравнения с каждым элементом таблицы, пока не будет найден подходящий. Для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений.
Недостатком метода является то, что если N велико, то способ не является эффективным.

Слайд 8

Блок-схема добавления элемента в ТИ по методу простого списка

Слайд 9

Блок-схема алгоритма поиска элемента в ТИ, организованной с помощью метода простого

списка

Слайд 10

Системное Программное Обеспечение
Результаты
Метод рехэширования с помощью произведения:
– всего сравнений: 8;
– в

среднем сравнений: 0,8;
Метод простого списка:
– всего сравнений: 55;
– в среднем сравнений: 5,5.

Слайд 11

Лексический анализатор
Лексический анализ – часть компилятора, которая читает литеры программы на

исходном языке и строит из них слова – лексемы.
Граф переходов КА – направленный нагруженным однонаправленным граф, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а символы нагрузки (метки) дуг соответствуют функции перехода.

Слайд 12

Граф конечного детерминированного автомата

Слайд 13

Пример обработки текстового файла
prog
repeat {начало цикла}
begin
if ((Cnt>-1)and(Result>0)) then begin
Cnt--;
Result:=5-Cnt;
end
else
Cnt:=Result;
Var4:=-Cnt;
Sum:=Cnt+Result+Var4;
end
until((Sum=25)xor(Result>10)); {конец цикла}
end.

Слайд 14

Результаты обработки текстового файла (фрагмент)

Слайд 15

Синтаксический анализатор
Синтаксический разбор – выделение синтаксических конструкций и проверка синтаксической

правильности программы.
Распознаватель – алгоритм, позволяющий определить принадлежность цепочки символов к некоторому языку.
МП-автомат – недетерминированный конечный автомат со стековой (или магазинной) памятью. Переход из одного состояния в другое зависит не только от входного элемента, но и от одного или нескольких верхних символов магазина (стека).

Слайд 16

Контекстно-свободная грамматика в форме Бэкуса-Наура:
G({prog, end., if, then, else, begin, end,

repeat, until, or, xor, and, not, <, >, =, (, ), –, +, um, dec, a, c, ;, :=}, {S, L, O, R, B, C, D, E, I, T, F}, P, S)
правила P:
S → prog L end.
L → O | L ; O | L ;
O → if B then R else O | if B then O | begin L end | repeat O until B | a := E
R → if B then R else R | begin L end | repeat O until B | a := E
B → B or C | B xor C | C
C → C and D | D
D → E < E | E > E | E = E | ( B ) | not ( B )
E → E – I | E + T | T
I → ( um I ) | F
T → um T | F
F → ( E ) | a | c | a dec

Слайд 17

Множества крайних левых и крайних правых символов грамматики G .
Результат

Слайд 18

Множества крайних левых и крайних правых терминальных символов грамматики G.
Результат

Слайд 19

Остовная грамматика G’, полученная на основе исходной грамматики
G’({prog, end., if, then,

else, begin, end, repeat, until, or, xor, and, not, <, >, =, (, ), –, +, um, dec, a, c, ;, :=}, {E, B}, P’, E)
правила P’:
E → prog E end. – правило № 1
E → E | E ; E | E ; – правила № 2 – 4
E → if B then E else E | if B then E | begin E end | repeat E until B | a := E – правила № 5 – 9
E → if B then E else E | begin E end | repeat E until B | a := E
– правила № 10 – 13
B → B or B | B xor B | B – правила № 14 – 16
B → B and B | B – правила № 17 и 18
B → E < E | E > E | E = E | ( B ) | not ( B ) – правила № 19 – 23
E → E – I | E + E | E – правила № 24 – 26
E → ( um E ) | E – правила № 27 и 28
E → um E | E – правила № 29 и 30
E → ( E ) | a | c | a dec – правила № 31 – 34

Слайд 20

Компилятор

Содержание

Компилятор – транслятор, осуществляющий перевод исходной программы в эквивалентную ей объектную

Системное Программное ОбеспечениеТаблица идентификаторов – специальным образом организованные наборы данных, служащие

Метод рехэширования с помощью произведения Для организации таблицы идентификаторов по методу рехэширования

Блок-схема добавления элемента в ТИ по методу рехэширования с помощью произведения

Блок-схема алгоритма поиска элемента в ТИ, организованной по методу рехэширования с

Метод организации ТИ простым спискомПри использовании данного метода элементы таблицы располагаются

Блок-схема добавления элемента в ТИ по методу простого списка

Блок-схема алгоритма поиска элемента в ТИ, организованной с помощью метода простого

Системное Программное ОбеспечениеРезультатыМетод рехэширования с помощью произведения: – всего сравнений: 8; – в

Лексический анализаторЛексический анализ – часть компилятора, которая читает литеры программы на

Граф конечного детерминированного автомата

Пример обработки текстового файлаprog repeat {начало цикла} begin if ((Cnt>-1)and(Result>0)) then begin Cnt--; Result:=5-Cnt; end else Cnt:=Result; Var4:=-Cnt; Sum:=Cnt+Result+Var4; end until((Sum=25)xor(Result>10)); {конец цикла}end.

Результаты обработки текстового файла (фрагмент)

Синтаксический анализатор Синтаксический разбор – выделение синтаксических конструкций и проверка синтаксической

Контекстно-свободная грамматика в форме Бэкуса-Наура:G({prog, end., if, then, else, begin, end,

Множества крайних левых и крайних правых символов грамматики G . Результат

Множества крайних левых и крайних правых терминальных символов грамматики G. Результат

Остовная грамматика G’, полученная на основе исходной грамматикиG’({prog, end., if, then,

Результаты работы синтаксического анализатора (фрагмент)

Похожие презентации