Краткие ответы по теории (1115075), страница 3
Текст из файла (страница 3)
Всегда сначала надо избавиться от левой рекурсии ( A -> Aa | Ab )=>S -> fASd | εΑ -> dBA’ | fA’A’ -> aA’ | bA’ | εB -> bcB | ε2. После первого преобразования видно, что надо избавляться от ε-правил.а) FIRST (S) = {f}; FOLLOW (S) = {d}; пересечение - пустое множество => первоеε-правило не мешаетб) FIRST (A’) = {a,b}; FOLLOW (A’) = {f,d}; пересечение пустов) FIRST (B) = {b}; FOLLOW (B) = {a,b,f,d}; в пересечении получается {b} =>МРС не применим => надо преобразовывать3.=>S -> fASd | εΑ -> dB’ | fA’B’ -> bcB’ | A’A’ -> aA’ | bA’ | ε4.Β’ -> bcB’ | A’ - не подходит к МРС, т.к.
альтернатива начинаетсянетерминальным символом.=>S -> fASd | εΑ -> dB’ | fA’B’ -> bcB’ | aA’ | bA’ | εA’ -> aA’ | bA’ | ε=>S -> fASd | εΑ -> dB’ | fA’B’ -> bC | aA’ | εC -> cB’ | A’ - необходимо переписатьA’ -> aA’ | bA’ | ε=>S -> fASd | εΑ -> dB’ | fA’B’ -> bC | aA’ | εC -> cB’ | aA’ | bA’ | εA’ -> aA’ | bA’ | εS~SПосле всех преобразований надо опять проверить.FIRST (S) = {f}; FOLLOW (S) = {d}; Λ = 0FIRST (B’) = {a,b}; FOLLOW (B’) = {f,d} ; Λ = 0FIRST (A’) = {a,b}; FOLLOW (A’) = {f,d}; Λ = 0FIRST (C) = {a,b,c}; FOLLOW (C) = {f,d}; Λ = 0- грамматика преобразована к виду, к которому применим метод рекурсивного спуска.25.
Задачи семантического анализа. Грамматики с действиями.Проверка контекстных условий – семантический анализ:· Каждый используемый а программе идентификатор должен быть описан, но неболее одного раза в одной зоне описания·При вызове функций число фактических параметров и их типы должнысоответствовать числу и типам формальных параметров· Обычно в языке накладываются ограничения на типы операндов любой операции,определенной в этом языке, на типы левой и правой части в присваивании, на типпараметра цикла, на тип условия в операторе цикла и условном операторе, и т пНеобходимо расширить грамматику и вставить необходимые действия.Семантический анализ реализуется МРС, и им же вводятся дополнительные действия.26. Объектная модель синтаксического анализатора.*****27.
Использование исключений С++ при обработке синтаксических ошибок инарушении контекстных условий.Для обработки синтаксических ошибок и нарушений контекстных условий очень удобнопользоваться механизмом исключений С++. Для этого необходимо:i. Вместо вызовов функции ERROR() во время рекурсивного спуска писать throwс параметром, идентифицирующим тип ошибки (например, номер ошибки приусловии существования пронумерованного списка ошибок),ii.
Запуск РС-метода поместить в try-блок,iii. В соответствующий ему catch-блок поместить обработку этих ошибок.Выгода использования исключений заключается в простоте реализации, т.е. в том, чтонет необходимости реализовывать выход из рекурсии при возникновении ошибки.28. Свойства языка внутреннего представления программы, примеры таких языков.a. Он позволяет фиксировать синтаксическую структуру исходной программыb.
Текст на нем можно автоматически генерировать во время синтаксическогоанализаc. Его конструкции должны просто транслироваться в объектный код, либодостаточно эффективно интерпретироватьсяНекоторые общепринятые способы внутреннего представления программ:· Постфиксная запись· Префиксная запись· Многоадресный код с явно именуемыми результатами· Многоадресный код с неявно именуемыми результатами· Связные списочные структуры, представляющие синтаксическое дерево29. Синтаксически управляемый перевод: идея, принципы организации, примеры.В основе – грамматика с действиями.
Параллельно с анализом исходной цепочки лексемвыполняются действия по генерации внутреннего представления программы. Для этогограмматика дополняется соответствующими процедурами генерации.E -> T { + T }E -> T { + T <putchar(‘+’)> }T -> F { * F }T -> F { * F >putchar (‘*’)> }F -> a | b | (E)F -> a <putchar(‘a’)>|b<putchar(‘b’)| (E)30. ПОЛИЗ выражений.ПОЛИЗ выражений задаётся следующими правилами:· Если Е является простым (единственным) операндом, то его ПОЛИЗ - это и естьэтот операнд Е,· ПОЛИЗом выражения Е1 * Е2, где * - любая бинарная операция, а Е1 и Е2 - еёоперанды, является запись Е1' E2' *, где Е1' и Е2' - ПОЛИЗ запись выражений Е1 иЕ2 соответственно,··ПОЛИЗом выражения * Е, где * - любая унарная операция, а Е - её операнд,является запись Е' *, где Е' - ПОЛИЗ запись выражения Е,ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е31.
ПОЛИЗ операторов языков программирования.Для определения ПОЛИЗа операторов ЯП, необходимо ввести дополнительныеобозначения. Пусть:· I – означает, что операндом является адрес переменной I, а не её значение,· Для реализации ПОЛИЗа уловных операторов введём операции условного ибезусловного перехода:o Пусть ПОЛИЗ оператор, помеченный меткой L находится на позиции p(будем считать, что все элементы ПОЛИЗ-записи пронумерованы).
Тогдаоператор безусловного перехода goto L в ПОЛИЗ будет записываться так:p! – где ! – это оператор ПОЛИЗo Для реализации условного перехода введём переход по лжи: if(not B) gotoL. Также пусть оператор, помеченный L, стоит на позиции p. Тогда записьэтого условного перехода будет выглядеть так: B’ p !F, где !F – операторПОЛИЗ, а B’ – это ПОЛИЗ-запись выражения В· Операторы ввода/вывода в ПОЛИЗ обозначаются одноместными операциями.Пусть R – обозначение операции ввода, а W – обозначение операции вывода.Используя введённые операции ПОЛИЗ, приведём некоторые примеры ПОЛИЗаоператоров М-языка программирования:· Оператор присваиванияI := E ó I, E, :=· Условный операторif E then S1 else S2 ó P(E), L1, !F, P(S1), L2, !, [L1] P(S2) [L2]· Оператор цикла while-dowhile E do S ó [L2] P(E), L1, !F, P(S), L2, ! [L1]· Оператор цикла do-whiledo S while E ó [L2] P(S), P(E), L1, !F, L2, ! [L1]· Оператор цикла forfor(A; B; C) do S ó P(A), [L3] P(B), L1, !F, L2, !, [L4] P(C), L3, !, [L2] P(S), L4, ! [L1]· Оператор ввода read(I) ó I R· Оператор вывода write(E) ó P(E) W32.
Генерация ПОЛИЗа выражений и операторов.Каждый элемент в ПОЛИЗе – это лексема, то есть пара вида (номер_класса,номер_в_классе). Для этого расширим набор лексем:· Будем считать, что операции !, !F, R, W относятся к ограничителям языка, нарядус остальными операциями· Для описания ссылок на элемент ПОЛИЗа введём тип 0, то есть элемент вида (0, p)обозначает ссылку на элемент под номером p· Для операндов-адресов введём тип 5. То есть операнды-значения(идентификаторов) имеют тип 4, а их адреса – тип 5.Генерация ПОЛИЗа происходит во время синтаксического анализа параллельно сконтролем контекстных условий, поэтому для генерации можно использоватьинформацию, «собранную» синтаксическим и семантическим анализаторами.
Например,при генерации ПОЛИЗа выражений можно воспользоваться стеком для проверки типоввыражений или добавить операции генерации ПОЛИЗа в функцию для этой проверки.33. Интерпретация ПОЛИЗа.ПОЛИЗ просматривается слева направо, если встречаем операнд, то записываем его встек, если встретили знак операции, то извлекаем из стека нужное количество операндови выполняем операцию, результат (если он есть) записываем в стек.34. Использование исключений С++ при обработке ошибок периода выполнения.******35.
Основные стратегии распределения памяти.Явное выделение блоков фиксированного размера, которые связываются в список, надкоторым достаточно легко выполнять операции выделения и освобождения. Плюсы –если программа полностью использует блок памяти, то никаких дополнительныхрасходов не нужно. С каждым блоком связан указатель на его начало, и надо хранитьтолько информацию о том, занят блок или нет. Свободные блоки можно «подшивать»между собой, используя часть блока для хранения указателей, с помощью которыхосуществляется объединение свободной памяти в список.
Когда очередной блоксвободной памяти выделяется программе, он удаляется из списка, а начальный указательпринимает значение указателя на следующий свободный блок памяти. Когда какой-тоблок памяти освобождается, он добавляется в список свободной памяти.Достоинства: простота.Недостатки: какая-то часть памяти используется неэффективно в случае, если поразмеру требуется меньше, чем размер блока.Явное выделение блоков переменного размера. Один из методов выделения блоковпеременного размера – метод первого подходящего. При выделении блока размера sнаходится первый блок размера f >= s. Затем этот блок разбивается на два – с размерами sи f-s. Но мы можем и не найти такой фрагмент.
Тогда необходимо приостанавливатьвыполнение программы и искать все использованные фрагменты и перемещать их на днокучиДостоинства: эффективное использование памяти, место не тратится попусту.Недостатки: дольше работает программа.Неявное выделение/освобождение памяти. Неявно выделяемые блоки памяти такжемогут быть фиксированного или переменного размера. При неявном динамическомвыделении и освобождении блоков памяти, выделяемые блоки обычно имеютследующую структуру: - размер блока (для блоков переменного размера)- счетчик ссылок, пометка (обычно есть либо одно, либо другое)- указатели на блоки- то, что досталось пользователю, заказавшему этот блокСчетчик ссылок подсчитывает количество указателей в программе, которыессылаются на этот блок, если счетчик равен 0, то блок не используется и егоможно освободить.
Существует проблема циклических ссылок, когда счетчиквсегда >= 0.Пометка фиксирует задействован ли блок или нет, то есть имеется ли у программыхотя бы 1 указатель, ссылающийся на этот блок. В некоторый момент начинаетработать сборщик мусора. Он помечает все блоки как недостижимые, а потомначинает анализ текущих указателей программы. Блоки, на которые ничего неуказывает, считаются свободными и их можно перегруппировать.36.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
