1 Трансляция арифметических выражений Тройка E C = E L E R, где E C – результат, E L, E R – левый и правый операнды, – операция. Пример: d = a+b*c должна. - презентация

1 1 Трансляция арифметических выражений Тройка E C = E L E R, где E C – результат, E L, E R – левый и правый операнды, – операция. Пример: d = a+b*c должна быть построена последовательность троек: T1 = b*c, d = a+T1

2 2 Метод Рутисхаузера 0. Записать в полной скобочной форме: d = a+b*c d = a+(b*c) 1. Сопоставить индексы: N[0]:=0 J:=1 Цикл-пока S[J] _ Если S[J] = ( или S[J] = то N[J]:=N[J-1] +1 иначе N[J]:=N[J-1] -1 Все-если J:=J+1 Все-цикл N[J]:=0 2. Определить max индекса k(k-1)k и построить тройку. 3. Удалить обработанные символы из выражения, результату сопоставить индекс N=k-1

3 3 Пример использования метода Рутисхаузера Пример. (((a+b)*c)+d)/k a) S: ( ( ( a + b ) * c ) + d ) / k N: b) S: ( ( T1 * c ) + d ) / k N: c) S: ( T2 + d ) / k N: d) S: T3 / k N: => T1 = a+b => T2 = T1*c => T3 = T2+d => T4 = T3/k

4 4 Классификация компилирующих программ Транслятор – программа, которая переводит програм- му, написанную на одном языке, в эквивалентную ей программу, написанную на другом языке. Компилятор – транслятор с языка высокого уровня на машинный язык или язык ассемблера. Ассемблер – транслятор с языка Ассемблера на ма- шинный язык. Интерпретатор – программа, которая принимает ис- ходную программу и выполняет ее, не создавая про- граммы на другом языке. Макрогенератор (для компиляторов – препроцессор) – программа, которая обрабатывает исходную про- грамму, как текст, и выполняет в нем замены ука- занных символов на подстроки. Макрогенератор обрабатывает программу до трансляции.

5 5 Синтаксис и семантика Синтаксис – это совокупность правил, определяющих допустимые конструкции языка, т. е. его форму. Семантика – это совокупность правил, определяющих логическое соответствие между элементами и значением синтаксически корректных предложений, т. е. содержание языка.

6 6 Структура процесса компиляции Лексический анализ Синтаксический анализ Семантический анализ Распределение памяти Генерация и оптимизация объектного кода

7 7 Лексический анализ Пример. if Sum>5 then pr:= true; Лексемы Терминальные словаБазовые понятия ЛексемаТипЗначениеСсылка ifСлужебное словоКод «if»- SumИдентификаторАдрес в таблице идентиф. >Служебный символКод «>»- 5ЛитералАдрес в таблице литералов thenСлужебное словоКод «then»- prИдентификаторАдрес в таблице идентиф. :=Служебный символКод «:=»- trueЛитералАдрес в таблице литералов ;Служебный символКод «;»-

8 8 Синтаксический анализ ЛексемаТипЗначениеСсылка if СсКод if Sum ИдАдрес > СКод > 5 КцАдрес then СсКод then pr ИдАдрес := СКод := true КлАдрес ; Р Логическое выражение Оператор Условный оператор Таблица токенов

9 9 Формальный язык Алфавит – непустое конечное множество символов, используе- мых для записи предложений языка. Пример: A = {0,1,2,3,4,5,6,7,8,9,+,-} Строка – любая последовательность символов алфавита, распо- ложенных один за другим. A* - множество строк, включая пустую, составленных из А. A + - множество строк за исключением пустой, составленных из А. A* = A + e Формальным языком L в алфавите A называют произвольное подмножество множества A*. Язык можно задать перечислением и правилами продукции.

10 10 Формальная грамматика G = (V T, V N, P, S), где V T – алфавит языка или множество терминальных (незаменяемых) символов; V N – множество нетерминальных (заменяемых) симво- лов – вспомогательный алфавит, символы которого обозначают допустимые понятия языка, V T V N = ; V = V T V N – словарь грамматики; P – множество порождающих правил – каждое правило состоит из пары строк (α, β), где α V+ – левая часть правила, β V* – правая часть правила: α β, где строка α должна содержать хотя бы один нетерми- нал; S V N – начальный символ – аксиома грамматики.

11 11 Грамматика записи десятичных чисел G 0 V T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}; V N = {,,, }; P = {,, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - }; S =. Правосторонняя рекурсия

12 12 Форма Бэкуса-Наура (БНФ) Условные обозначения: – нетерминальный символ – конструкция; Имя – терминальный символ – символ алфавита; ::= – «можно заменить на»; | – «или» Пример: ::= | ::= 0|1|2|3|4|5|6|7|8|9 ::= +| -

13 13 Грамматический разбор Вывод представляет собой последовательность подстановок. Пример. Вывод строки «-45»: целое знакцбз цифрацбз цифра Грамматический разбор Восходящий разбор Нисходящий разбор

14 14 Левосторонний восходящий грамматический разбор Пример. Разобрать строку «-45» Правила грамматики: ::= |, ::= 0|1|2|3|4|5|6|7|8|9, ::= +| -. Последовательность получения сентенциальных форм данным методом: 45 5 Тупик!

15 15 Левосторонний нисходящий грамматический разбор Пример. Разобрать строку «-45» Правила грамматики: а) ::= | б) ::= |, в) ::= 0|1|2|3|4|5|6|7|8|9, г) ::= +| -.

16 16 Левосторонний нисходящий грамматический разбор РаспознаноТекущий символЦель или подцельПравилоИстина? 1 -ЦелоеA1 2 -ЗнакГ1Нет 3 Г2Да 4 -4Целое без знакаБ1 5 4ЦифраВ1-В4Нет 6 В5Да Целое без знакаБ1 8 5ЦифраВ1-В5Нет 9 В6Да _Целое без знакаБ1 11 _ЦифраВ1-В10Нет 12 _Целое без знакаБ2Б2Нет 13_ЦифраВ1-В10Нет Целое без знакаБ2Б2 155ЦифраВ1-В5Нет 16В6Да Нет Да

17 17 Классификация грамматик Хомского Тип 0 – грамматики фразовой структуры или грамматики «без ограничений»: α β, где α V+, β V*– в таких грамматиках допустимо наличие любых правил вывода, что свойственно грамматикам естественных языков; Тип 1 – контекстно-зависимые (неукорачивающие) грамматики: α β, где α V +, β V*, | α | | β | – в этих грамматиках для правил вида α X β α x β возможность подстановки строки х вместо символа X определяется присутствием подстрок α и β, т. е. контекста, что также свойственно грамматикам естественных языков; Тип 2 – контекстно-свободные грамматики: A β, где A V N, β V* – поскольку в левой части правила стоит нетерминал, подстановки не зависят от контекста; Тип 3 – регулярная грамматика: A α, A αB, где A, В V N, α V T ;

18 18 Конечный автомат M = (Q,, δ, q 0, F), где Q – конечное множество состояний; – конечное множество входных символов; δ(q i, с k ) – функция переходов (q i – текущее состояние, с k – очередной символ); q 0 – начальное состояние; F = {q j } – подмножество допускающих состояний. Пример. Автомат «Чет-нечет»: Q = {Чет, Нечет}; = {0, 1}; δ(Чет, 0) = Чет, δ(Нечет, 0) = Нечет, δ(Чет, 1) = Нечет, δ(Нечет, 1) = Чет; q 0 = Чет; F = {Чет} 01 Чет Нечет Чет Таблица переходов ЧетНечет Граф переходов Синтаксическая диаграмма

19 19 Реализация конечного автомата Ind := 1 q := q0 Цикл-пока q «Ошибка» и q «Конец» q = Table [q, S[Ind]] Ind := Ind +1 Все-цикл Если q = «Конец» то «Строка принята» иначе «Строка отвергнута» Все-если 01Символы заверш. Другие символы Чет НечетКонецОшибка Нечет ЧетОшибка

20 20 Лексические анализаторы Пример. Распознаватель целых чисел. Состо- яние ЗнакЦиф- ра Разде- литель Другие 12, А13, А2E, D1E, D4 2Е, D23, А2E, D3E, D4 3K, A33, А2K, A3E, D4 A0: Инициализация: Целое := 0; Знак_числа := «+». А1: Знак_числа := Знак А2: Целое := Целое*10 + Цифра А3: Если Знак_числа = «-» то Целое := -Целое Все-если

21 21 Распознаватель целых чисел Д1: «Строка не является десятичным числом»; Д2: «Два знака рядом»; Д3: «В строке отсутствуют цифры», Д4: «В строке встречаются недопустимые символы» Ind := 1 q := 1 Выполнить А0 Цикл-пока q «Е» и q «К» Если S[Ind] = «+» или S[Ind] = «-», то j := 1 иначе Если S[Ind] «0» и S[Ind] «9», то j := 2, иначе j := 3 Все-если Выполнить Ai := Table [q, j]. A() q := Table [q, j] Ind := Ind +1 Все-цикл Если q = «К» то Выполнить А3 Вывести «Это число» иначе Вывести сообщение Di Все-если

22 22 Синтаксические анализаторы Пример. Синтаксический анализатор списка описания целых скаляров, массивов и функций, например: int xaf, y22[5], zrr[2][4], re[N], fun(), *g; int V,V[N],V[N][N],V[N],V(),*V V N * ( ) [ ], ; Другие 1 3 E 2 E E E E E E E 2 3 E E E E E E E E E 3 E E E 4 E 6 E 1 К E 4 E E E E 5 E E E E E 5 E E E E E E E 1 К E 6 E 7 E E E E E E E E 7 E E E E E E 8 E E E 8 E E E E E 6 E 1 К E Обозначения: V – идентификатор; N – целочисленная константа; служебные символы: «[ ] ( ), ; *».

23 23 Алгоритм распознавателя Ind := 1 q := 1 Цикл-пока q «Е» и q «К» q := Table [q, Pos(S[Ind], «VN*()[];»)] Ind := Ind +1 Все-цикл Если q = «К» то Выполнить А3 Вывести сообщение «Это число» иначе Вывести сообщение Дi Все-если

24 24 Автомат с магазинной памятью P M = (Q,, Г,, q 0, z 0, F), где Q – конечное множество состояний автомата; – конечный входной алфавит; Г – конечное множество магазинных символов; (q, ck, zj) – функция переходов; q 0 Q – начальное состояние автомата; z 0 Г – символ, находящийся в магазине в начальный момент, F Q – множество заключительных (допускающих) состояний. Пример. Синтаксический анализатор выражений. = {, +, –, *, /, (, ),, }.

25 25 Синтаксические диаграммы выражения A * (B + C) + (D + F) / (A + B) - C * D

26 26 Объединенная синтаксическая диаграмма

27 27 Таблица переходов автомата

28 28 Алгоритм распознавателя q:=1 Ind := 1 Mag := Цикл-пока q «E» и q «К» q := Table [q, String[Ind]].q Если q = то Mag Table [q, String[Ind]].S q := X иначе Если q = то Mag q иначе Ind := Ind +1 Все-если Если q = «К» то «Строка принята» иначе «Строка отвергнута» Все-если

29 29 LL(k)-грамматики Пример. Дана грамматика записи выражений: 1) ::= 2) ::= 3) ::= e | + | - 4) ::= 5) ::= e | * | / 6) ::= | ( )

30 30 Метод рекурсивного спуска Пример. Выражение

31 31 Алгоритм распознавателя Функция Выражение:Boolean: R:=Терм() Цикл-пока R=true и (NextSymbol =+ или NextSymbol =-) R:=Терм() Все-цикл Выражение:= R Все Функция Терм:Boolean: Множ() Цикл-пока R=true и (NextSymbol =* или NextSymbol =/) R:=Множ() Все-цикл Терм:= R Все

32 32 Алгоритм распознавателя (2) Функция Множ:Boolean: Если NextSymbol =( то R:=Выражение() Если NextSymbol ) то Ошибка Все-если иначе R:= Ид() Все-если Все Основная программа: R:=Выражение() Если NextSymbol то Ошибка () Все-если Конец

33 33 LR(k)-грамматики Если два символа α, β V расположены рядом в сентенциальной форме, то между ними возможны следующие отношения, названные отношениями предшествования: 1)α принадлежит основе, а β – нет, т. е. α – конец основы: α > β; 2)β принадлежит основе, а α – нет, т. е. β – начало основы: α < β ; 3)α и β принадлежит одной основе, т. е. α = β; 4)α и β не могут находиться рядом в сентенциальной форме (ошибка). Пример. Грамматика арифметических выражений (с левосторонней рекурсией): ::= | + | - ::= | * | / ::= ( ) |

34 34 Построение таблицы предшествования A+ A* (A A) A +A+ +A* +(A +A) +A *A+ *A* *(A *A ) *A (A+ (A* ((A (A) (A A)+ A)* A)( A)) A) < - начало основы; > - конец основы; = - одна основа; ? - ошибка

35 35 Пример разбора выражения d+c*(a+b)

36 36 Польская запись Польская запись представляет собой последовательность команд двух типов: К I, где I – идентификатор операнда – выбрать число по имени I и заслать его в стек операндов; K, где – операция – выбрать два верхних числа из стека операндов, произвести над ними операцию и занести результат в стек операндов. Пример: A+B*C K A K B K C K * K +

37 37 Алгоритм Бауэра-Замельзона Построение польской записи : а) если символ – операнд, то вырабатывается команда К I, б) если символ – операция, то выполняются действия согласно таблице: Операции: I – заслать в стек операций и читать следующий символ; II – генерировать K, заслать в стек операций и читать следующий символ; III – удалить верхний символ из стека операций и читать следующий символ; IV – генерировать K и повторить с тем же входным символом.

38 38 Пример. Построить тройки для выражения (a+b*c)/d. Построение польской записи: K a K b K c K * K + K d K / или abc*+d/

39 39 Пример (2) Выполнение операций:

40 40 Распределение памяти 1)статическое; 2)автоматическое; 3)управляемое; 4)базированное.

41 41 Генерация и оптимизация кодов Пример «заготовки»: Mov AX, Add AX, Mov AX, Машинно-независимая оптимизация включает: а) исключение повторных вычислений одних и тех же операндов; б) выполнение операций над константами во время трансляции; в) вынесение из циклов вычисления величин, не зависящих от параметров циклов; г) упрощение сложных логических выражений и т. п. Машинно-зависимая оптимизация включает: а) исключение лишних передач управления типа «память-регистр»; б) выбор более эффективных команд т. п.