СП - Краткие ответы на экзаменационные вопросы (1115082), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

VT – конечное множество допустимых входных символов

F – функция переходов: отображение множества KVT -> K

HК – конечное множество начальных состояний

SK – конечное множество заключительных состояний

1. Диаграмма состояний (ДС) конечного автомата .

Диаграмма состояний (ДС) НКА – это ориентированный помеченный граф такой, что:

1. Его вершины помечены символами состояний из K

2. Вершины А и В соединяются дугой от А к В, если  aVT: F(A,a)=B, при этом дуга помечется всеми такими а.

1. Леволинейные регулярные грамматики и конечные автоматы.

1. Определение детерминированного конечного автомата (ДКА).

Конечный автомат (КА) - это пятерка (K, VT, F, H, S), где:

K – конечное множество состояний

VT – конечное множество допустимых входных символов

F – функция переходов: отображение множества KVT -> K

HК – начальное состояние

SK – конечное множество заключительных состояний

Конечный автомат называют детерминированным конечным автоматом (ДКА), если в каждом из его состояний для любого входного символа функция перехода содержит не более одного состояния: для любого а из VT и A из K: либо F(A, a) = {R}, RK, либо F(A, a) = 

1. Алгоритм построения детерминированного конечного автомата по НКА.

М = (K, VT, F, H, S) – НКА; M’ = (K’, VT, F’, H’, S’) – ДКА, допускающий тот же язык, что и М.

1. Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать [A₁A₂…A_n], где A_iК

2. Отображение F’ определим как F’([A₁A₂…A_n], t) = [B₁B₂…B_m], где для каждого 1  j  m F(A_i, t) = B_j для каких-либо

1  i  n

1. Пусть H = {H₁, H₂, … H_k}, тогдa H' = [H₁, H₂, …, H_k]

2. Пусть S = {S₁, S₂, …, S_p}, тогда S’ – все состояния из K’, имеющие вид […S_i…], S_iS для какого-либо 1  i  p.

1. Задачи лексического анализа.

• Выделить в исходном тексте цепочку символов, представляющую лексему

• Удалить пробельные символы и комментарии

• Зафиксировать в специальных таблицах для хранения разных типов лексем факт появления соответствующих лексем в анализируемом тексте

• Преобразовать цепочку символов, представляющих лексему, в пару (тип лексемы, указатель на информацию о ней)

Лексический анализ важен для процесса компиляции по нескольким причинам:

• Замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы более удобным для дальнейшей обработки

• Лексический анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии

• Если будет изменена кодировка в исходном представлении программы, то это отразится только на лексическом анализаторе.

1. Лексический анализ на основе регулярных грамматик.

Лексемы можно описать с помощью регулярных грамматик.

Например, идентификатор (I): I ->a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9; целое без знака (N): N ->0 | 1 |...| 9 | N0 | N1 |...| N9 и т.д.

Для грамматик этого класса, как мы уже видели, существует простой и эффективный алгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он должен сам выделить в исходном тексте цепочку символов, представляющую лексему, а также преобразовать ее в пару (тип_лексемы, указатель_на_информацию_о_ней). Для того, чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммы состояний, введем на дугах дополнительный вид пометок - пометки-действия D_i.

Смысл прежний - если в состоянии A очередной анализируемый символ совпадает с t_i для какого-либо i = 1, 2 ,... n, то осуществляется переход в состояние B; при этом необходимо выполнить действия D₁, D₂, ... ,D_m.

1. Объектная модель лексического анализатора. Схема его работы.

*****

1. Задачи синтаксического анализа.

• Проверка правильности синтаксиса

• Фиксация распознанной синтаксической структуры программы.

Для описания языка программирования достаточно грамматики типа 2.

Существуют алгоритмы зависимости сложности вычислений cn³, cn².

Универсального алгоритма сложности cn нет. Есть только для формальной грамматики – метод рекурсивного спуска. Он лежит в основе многих методов, применяется к узкому подклассу КС грамматик.

1. Метод рекурсивного спуска (МРС): назначение, семантика процедур рекурсивного спуска.

Один из алгоритмов анализа входной цепочки, расходующий линейное время. Последовательность разбора эквивалентна построению дерева разбора методом «сверху вниз». Для каждого нетерминала грамматики создается своя процедура, носящая его имя, ее задача – начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор. Если цепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляет возврат в точку вызова. Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.

1. Достаточные условия применимости метода рекурсивного спуска.

• Либо A->, где а (VT  VN)^* и это единственное правило вывода для этого нетерминала

• Либо A-> a₁₁ | a₂₂ |  | a_n_n, где a_iVT для всех i = 1, 2, …, n; a_i  a_j при i  j; _i(VT  VN)^*, т. е. если для нетерминала А правил вывода несколько, то они должны начинаться с терминалов, причем все эти терминалы должны быть различимыми.

1. Исследование применимости МРС в случае наличия ε-альтернативы и итерационных правил.

1. МРС заведомо не применяется, если в грамматике есть правила, заведомо рекурсивные, т.к. постоянно обращаются к А( ). Получается зацикливание. Например, A -> Aα | β

Преобразования:

A -> βΒ

Β -> αΒ | ε

При этом В должен быть новым терминальным символом в грамматике; ε обязательно, иначе преобразование не равносильно.

1. Две альтернативы начинаются с одинакового терминального символа:

A -> aα₁ | aα₂ | β

Тогда этот символ выносится и вводится новый нетерминальный символ.

Преобразования:

A -> aB | β

Β -> α₁ | α₂

1. Есть альтернативы, начинающиеся с нетерминальных символов.

Α -> Βα | β

Так как мы рассматриваем приведённые грамматики, то существует правило вида Β -> γ₁ | γ₂ , которое раскрывает В.

Преобразования:

Α -> γ₁α | γ₂α | β

см. пункт 2, если γ₁ и γ₂ начинаются с одного символа.

В результате избавились от нетерминальных символов в правой части.

1. Α -> Α | β | ε

Это УКС грамматика. Если есть правило с ε, метод применим не всегда.

Преобразования:

S -> A

A -> A | ε

void A( ) {

if (c==’’) { gc( ); A( ); }

}

Например, для цепочки  метод неприменим: в правиле S -> A при выходе из А( ) мы должны считать , но перед этим мы уже считали символ конца ввода, поэтому метод неприменим.

Пусть FIRST (A) – множество терминальных символов, с которых начинаются цепочки, выводимые из этого терминального символа; FOLLOW (A) – множество терминальных символов, с которых начинаются подцепочки, следующие за данным нетерминальным символом А.

Правило: Если FIRST(A)  FOLLOW(A)  , то метод не применим, если = , тогда данное правило не влияет на применимость метода (эти множества надо считать лишь для тех нетерминальных символов, из которых выводится ε).

Пример.

S -> fASd | ε

A -> Aa | Ab | dB | f

B -> bcB | ε

1. Всегда сначала надо избавиться от левой рекурсии ( A -> Aa | Ab )

=> S -> fASd | ε

Α -> dBA’ | fA’

A’ -> aA’ | bA’ | ε

B -> bcB | ε

1. После первого преобразования видно, что надо избавляться от ε-правил.

а) FIRST (S) = {f}; FOLLOW (S) = {d}; пересечение - пустое множество => первое ε-правило не мешает

б) FIRST (A’) = {a,b}; FOLLOW (A’) = {f,d}; пересечение пусто

в) FIRST (B) = {b}; FOLLOW (B) = {a,b,f,d}; в пересечении получается {b} => МРС не применим => надо преобразовывать

=> 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}; Λ = 0

FIRST (B’) = {a,b}; FOLLOW (B’) = {f,d} ; Λ = 0

FIRST (A’) = {a,b}; FOLLOW (A’) = {f,d}; Λ = 0

FIRST (C) = {a,b,c}; FOLLOW (C) = {f,d}; Λ = 0

- грамматика преобразована к виду, к которому применим метод рекурсивного спуска.

1. Задачи семантического анализа. Грамматики с действиями.

Проверка контекстных условий – семантический анализ:

• Каждый используемый а программе идентификатор должен быть описан, но не более одного раза в одной зоне описания

• При вызове функций число фактических параметров и их типы должны соответствовать числу и типам формальных параметров

• Обычно в языке накладываются ограничения на типы операндов любой операции, определенной в этом языке, на типы левой и правой части в присваивании, на тип параметра цикла, на тип условия в операторе цикла и условном операторе, и т п

Необходимо расширить грамматику и вставить необходимые действия.

Семантический анализ реализуется МРС, и им же вводятся дополнительные действия.

1. Объектная модель синтаксического анализатора.

*****

1. Использование исключений С++ при обработке синтаксических ошибок и нарушении контекстных условий.

Для обработки синтаксических ошибок и нарушений контекстных условий очень удобно пользоваться механизмом исключений С++. Для этого необходимо:

1. Вместо вызовов функции ERROR() во время рекурсивного спуска писать throw с параметром, идентифицирующим тип ошибки (например, номер ошибки при условии существования пронумерованного списка ошибок),

2. Запуск РС-метода поместить в try-блок,

3. В соответствующий ему catch-блок поместить обработку этих ошибок.

Выгода использования исключений заключается в простоте реализации, т.е. в том, что нет необходимости реализовывать выход из рекурсии при возникновении ошибки.

1. Свойства языка внутреннего представления программы, примеры таких языков.

   1. Он позволяет фиксировать синтаксическую структуру исходной программы

   2. Текст на нем можно автоматически генерировать во время синтаксического анализа

   3. Его конструкции должны просто транслироваться в объектный код, либо достаточно эффективно интерпретироваться

Некоторые общепринятые способы внутреннего представления программ:

• Постфиксная запись

• Префиксная запись

• Многоадресный код с явно именуемыми результатами

• Многоадресный код с неявно именуемыми результатами

• Связные списочные структуры, представляющие синтаксическое дерево

1. Синтаксически управляемый перевод: идея, принципы организации, примеры.

В основе – грамматика с действиями. Параллельно с анализом исходной цепочки лексем выполняются действия по генерации внутреннего представления программы. Для этого грамматика дополняется соответствующими процедурами генерации.

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)

1. ПОЛИЗ выражений.

ПОЛИЗ выражений задаётся следующими правилами:

• Если Е является простым (единственным) операндом, то его ПОЛИЗ - это и есть этот операнд Е,

• ПОЛИЗом выражения Е1 * Е2, где * - любая бинарная операция, а Е1 и Е2 - её операнды, является запись Е1' E2' *, где Е1' и Е2' - ПОЛИЗ запись выражений Е1 и Е2 соответственно,

• ПОЛИЗом выражения * Е, где * - любая унарная операция, а Е - её операнд, является запись Е' *, где Е' - ПОЛИЗ запись выражения Е,

• ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е

1. ПОЛИЗ операторов языков программирования.

Для определения ПОЛИЗа операторов ЯП, необходимо ввести дополнительные обозначения. Пусть:

• I – означает, что операндом является адрес переменной I, а не её значение,

• Для реализации ПОЛИЗа уловных операторов введём операции условного и безусловного перехода:

  • Пусть ПОЛИЗ оператор, помеченный меткой L находится на позиции p (будем считать, что все элементы ПОЛИЗ-записи пронумерованы). Тогда оператор безусловного перехода goto L в ПОЛИЗ будет записываться так: p! – где ! – это оператор ПОЛИЗ

  • Для реализации условного перехода введём переход по лжи: if(not B) goto L. Также пусть оператор, помеченный 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-do

while E do S  _[L2] P(E), L1, !F, P(S), L2, ! _[L1]

• Оператор цикла do-while

do S while E  _[L2] P(S), P(E), L1, !F, L2, ! _[L1]

• Оператор цикла for

for(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) W

1. Генерация ПОЛИЗа выражений и операторов.

Каждый элемент в ПОЛИЗе – это лексема, то есть пара вида (номер_класса, номер_в_классе). Для этого расширим набор лексем:

• Будем считать, что операции !, !F, R, W относятся к ограничителям языка, наряду с остальными операциями

• Для описания ссылок на элемент ПОЛИЗа введём тип 0, то есть элемент вида (0, p) обозначает ссылку на элемент под номером p

• Для операндов-адресов введём тип 5. То есть операнды-значения (идентификаторов) имеют тип 4, а их адреса – тип 5.

Генерация ПОЛИЗа происходит во время синтаксического анализа параллельно с контролем контекстных условий, поэтому для генерации можно использовать информацию, «собранную» синтаксическим и семантическим анализаторами. Например, при генерации ПОЛИЗа выражений можно воспользоваться стеком для проверки типов выражений или добавить операции генерации ПОЛИЗа в функцию для этой проверки.

1. Интерпретация ПОЛИЗа.

ПОЛИЗ просматривается слева направо, если встречаем операнд, то записываем его в стек, если встретили знак операции, то извлекаем из стека нужное количество операндов и выполняем операцию, результат (если он есть) записываем в стек.

1. Использование исключений С++ при обработке ошибок периода выполнения.

******

1. Основные стратегии распределения памяти.

Явное выделение блоков фиксированного размера, которые связываются в список, над которым достаточно легко выполнять операции выделения и освобождения. Плюсы – если программа полностью использует блок памяти, то никаких дополнительных расходов не нужно. С каждым блоком связан указатель на его начало, и надо хранить только информацию о том, занят блок или нет. Свободные блоки можно «подшивать» между собой, используя часть блока для хранения указателей, с помощью которых осуществляется объединение свободной памяти в список. Когда очередной блок свободной памяти выделяется программе, он удаляется из списка, а начальный указатель принимает значение указателя на следующий свободный блок памяти. Когда какой-то блок памяти освобождается, он добавляется в список свободной памяти.

Характеристики

Список файлов ответов (шпаргалок)