6.4. После считывания знака операции и перед его передачей синтаксическому анализатору должен проверяться его приоритет.

6.5. 1. Алгебраические выражения. 2. Списки имен и адресов.

6.6. 1. Конечная ширина бумаги позволяет делать отступы (абзацы) только определенной глубины вложения.

2. Разные программисты прибегают к разным условным обозначениям отступов (абзацев).

6.7. С помощью следующей грамматики:

I-> +U

-> - U<M>

U->d<A>

d<A>U

где действиями являются

<M>

sum := -sum

<A>

sum := 10 * sum + d

Здесь sum первоначально нулевая, a d - значение последней считанной цифры.

6.8. Нет необходимости иметь таблицы d в виде блочной структуры, рассмотренной в данной главе. Можно использовать массивы

6.9. 1.Более естественный стиль программирования, позволяющий описывать идентификатор, когда это требуется.

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

6.10. Каждому вызову действия соответствует дополнительный элемент в таблице разбора.

Глава 7

7.1. 1. Для обеспечения естественного метода, разрешающего применение взаимно рекурсивных процедур и т. п.

2. Чтобы позволить перегружать определенные символы.

7.2. 1. Для уменьшения размеров компилятора.

2. С целью оптимизации объектного кода.

3. Для обеспечения хорошей диагностики во время компиляции.

7.3. Аргумент «за» - все еще доступен оригинальный исходный код. Аргумент «против» -многопроходный компилятор может способствовать выдаче сообщений о синтаксических ошибках на более раннем этапе исходной программы.

7.4. 1. Распознавание заголовков процедур в Алголе 68. 2. Обращение с объявлениями в Паскале.

7.5 Аргумент «за» - помогает в отладке компилятора. Аргумент «против» чтение и запись между проходами могут быть неэффективными.

7.6. Помогает объяснить последующие сообщения об ошибках.

7.7. Синтаксический анализатор может потерять время за счет неправильного допущения в более раннем проходе.

7.8. 1. Компилятор может воспользоваться таким преимуществом машины, как аппаратурный стек.

2. Возможности машины обусловливают виды оптимизации, выполняемые компилятором.

3. Конструкция генератора кода может зависеть от числа имеющихся регистров.

7.9. 1. Нет зависимости от машины на «переднем крае".

2. Применение абстрактной машины, которая легко реализуется на большинстве

ЭВМ.

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

2. Фазы компиляции можно логически разделить.

Глава 8

8.1. а) Преимущество: простая таблица идентификатором и простые функции хеширования для таблицы символов.

б) Недостаток: нельзя пользоваться мнемоническими идентификаторами.

8.2. Нет, так как могут быть переписаны стандартные типы, принятые по умолчанию.

8.3. Идентификаторы можно было бы заменить последовательными целыми числами, используемыми как индексы к таблице.

8.4. а) Могут быть помещены в таблицу хеширования перед идентификаторами, определяемыми пользователем, на фиксированные позиции, которые не надо было бы рассчитывать для каждой программы заново.

б) Будут помещаться в самый внешний специальный блок.

8.5. Аргумент «за» - исключается агрегирование в самой таблице символов и в таблице может содержаться произвольное число идентификаторов. Аргумент «против» - объем памяти, занимаемый указателями.

8.6. Найдите середину массива и сделайте этот элемент корнем дерева. Левое и правое поддеревья образуются из этих двух половинок массива и т. д.

8.7. Возможность описания взаимно рекурсивнхх процедур и т. п.

8.8. Аргумент «за» - экономит место в таблице видов. Аргумент «против» - для каждого встреченного нового вида необходимо производить проверку, чтобы убедиться в том, что его еще нет в таблице.

8.9. а) Недопустимое; real, ref real слишком тесно связаны.

б) Допустимое; эквивалентно union (real, char).

в) Недопустимое; потребует бесконечный объем памяти.

8.10. Нет. Вид нельзя определить как некоторое число, состоящее из ref и/или ргос, за которыми следует он сам.

Глава 9

9.1. Описывая переменные по возможности локально.

9.2. Процесс выборки значения из стека с помощью DISPLAY требует сложения смещения с начальным адресом DISPLAY по указателю и прибавления другого смещения. Частично этого можно избежать, если отвести для статических значений отдельный стек в том случае, когда процедуры не нужно реализовывать.

9.3. Преимущество: нет необходимости в дополнительном проходе компилятора, чтобы сделать смещения рабочего стека относительными началу рамки. Недостаток: сложность из-за того, что требуется множество стеков в рабочее время.

9.4. Глобальный объем выделяется на время выполнения программы, а локальный отдается для совместного пользования процедурам. Общий требуемый объем памяти определяется как глобальный объем + локальный объем, нужный каждой процедуре

9.5. При компиляции блока весь объем памяти для статических идентификаторов может выделяться перед любым статическим рабочим участком памяти. Таким образом, смещения рабочего стека относительно начала рамки будут известны при выделении рабочей памяти. Преимуществом является также возможность контроля динамической рабочей памяти во время прогона.

9.6. Допустим, у - формальный параметр процедуры, вызываемой посредством ссылки или по значению и результату, а х - соответствующий фактический параметр. Присвойте новое значение х внутри процедуры и напечатайте у. Если у

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

9.7. Вариантам не требуется память для фактического вида/типа.

9.8. Сборка мусора в условиях реального времени не представляется удовлетворительным решением, так как она может вызывать останов программы на неопределенный период. Лучшее решение - использовать счетчик ссылок даже несмотря на то, что в результате выполнение программы несколько замедлится.

9.9. Как отмечалось в этой главе, чем больше обратных указателей, тем больше времени занимает выполнение алгоритма. Предварительный просмотр можно использовать для того, чтобы определить, с какого конца «кучи» алгоритм должен начинать работу.

9.10. Исключается необходимость применения рекурсии или стека.

Глава 10

10.1. а) а + b б) а + b=1

1 + с 1 + с=2

d + e d + e=3

3 + f 3 + f=4

2X4 2X4=5

10.2. Чтобы тройки можно было перегруппировать (например, во время оптимизации), не изменяя их самих.

10.3. Во избежание неоднозначности унарный знак операции в полученной обратной польской записи должен отличаться от соответствующего бинарного знака операции.

10.4. Преимущество - устраняет приоритет знаков операций, позволяя тем самым выполнять трансляцию с помощью простого алгоритма. Недостаток - подход неоптимальный в отношении времени компиляции.

10.5. При компиляции нет необходимости в стеке значений, если нельзя использовать скобки для спецификации приоритетов.

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

10.7. Может несколько сократить объем поиска в таблице, но значительно удлинит исходный текст. :

10.8. Код, генерированный для оператора case в Алголе 68, может иметь вид

GOTO LO SETLABEL L I first element GOTOLE SETLABEL L2 second element GOTOLE

SETLABEL LO SWITCH address (I) GOTO LI GOTO L2

SETLABEL LE

Команда SWITCH осуществит переход к соответствующему GOTO, следующему за ней.