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

ref proc ref int

в вид int.

Для сильной позиции (например, правая часть присваивания или параметр в вызове процедуры) правила таковы:

STRONG dereferance STRONG \ deprocedure STRONG unite \ unite ROW widen \ widen widen \

widen ROW \

widen widen ROW \

ROW row

row ROW

Чистка на этой стадии игнорируется.

Вид до выполнения приведений называется априорным, а после их выполнения -апостериорным. В случае сильных и раскрытых синтаксических позиций известны и априорный, апостериорный виды. Для других позиций известен лишь априорный вид и некоторая информация об апостериорном виде, например, о том, что он должен начинаться со struct или ref struct, как в выборе, или о том, что он не должен начинаться с proc, как в левой части присваивания. Компилятор, применяя соответствующую грамматику, генерирует последовательность приведений из априорного вида либо к известному, либо к подходящему апостериорному виду. Если нельзя найти никакой последовательности приведений, программа синтаксически неправильна. С другой стороны, если подходящая последовательность существует, компилятор применяет приведения по порядку, генерируя, очевидно, в ходе этого процесса код времени прогона.

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

x: = у;

Характер конструкции, которая дает очищенное значение, определяет, является ли эта чистка единственным выполняемым приведением или ей должны предшествовать другие приведения. Так, в случае присваивания

p: = q

значение p просто теряется, и никакие другие приведения не осуществляются независимо от того, какой вид p имеет. Однако в

где p есть прикладная реализация идентификаторов и вид p начинается с proc или ref proc и т.д., p нужно сначала распроцедурить или разыменовать и распроцедурить, а затем очистить. Обычно именно этого и следует ожидать, причем когда происходит

чистка, компилятор должен знать тип той конструкции, которая поставляет данное значение, а также вид этого значения. Более подробно чистка описывается в [43]. Еще одна сложность связана с выбирающими предложениями. В предложении

x + if b then 1 else 2.3 fi

во время компиляции необходимо знать вид правого операнда знака «+». Другими словами, все варианты выбирающего предложения должны приводиться к общему виду называемому объектным. Этот процесс известен как уравнивание, и его правила подразумевают, что последовательности сильных приведений можно применять во всех вариантах, кроме одного, в котором используются лишь последовательности приведений, уместные для синтаксической позиции выбирающего предложения. В вышеприведенном примере выбирающее предложение находится в крепкой синтаксической позиции, которая не допускает расширения. Однако внутри выбирающего предложения один вариант допускает сильное приведение, что может повлечь за собой расширение. В этом случае объектным видом окажется real, и первый вариант следует расширить, а второй (который, по сути, находится в крепкой позиции) нежелательно подвергнуть приведению. Алгоритм определения объектного вида в выбирающем предложении описывается в [38].

Действие компилятора при обращении с выбирающими предложениями заключается в том, что статические характеристики всех вариантов выбирающего предложения помещаются в нижний стек, а затем выводятся объектный вид и различные последовательности приведений для каждого варианта. Если какая-либо из этих последовательностей вызывает необходимость генерации кода во время прогона, ее можно выделить в отдельный поток, и между этими двумя потоками ввести указатели, чтобы во время последующего прохода код можно было соединить в нужном порядке.

10.5. ВРЕМЯ КОМПИЛЯЦИИ И ВРЕМЯ ПРОГОНА

Как было показано ранее на примерах, генератор кода во время компиляции выполняет некоторые действия (обращается к нижнему стеку и т. д.), а также генерирует код для других операций, которые будут выполняться во время прогона. Что именно должно быть сделано в процессе компиляции, а что - в процессе прогона, зависит в какой-то степени от компилирующего языка. Например, в РОР-2, где типы идентификаторов являются динамическими (т. е. могут динамически изменяться при прогоне), их проверку необходимо осуществлять во время прогона, и для выполнения такой проверки должен генерироваться код. В Алголе 68 все виды - статические (т. е. известны во время компиляции), и их проверку можно выполнять во время компиляции.

Тем не менее, хотя язык и влияет на решение вопроса о том, что осуществлять во время компиляции, а что - во время прогона, разработчик компилятора имеет некоторую свободу действий в этом плане. Например, в Алголе 68 не вполне ясно, повлечет ли разыменование за собой какое-либо действие при прогоне или нет. На первый взгляд может показаться, что нет, так как при этом просто происходит замена в памяти машины одного значения другим, и изменение адреса времени прогона в процессе компиляции должно быть возможным. Новым адресом будет тот, на который указывает первоначальный адрес, и несмотря на то, что значение указателя может быть неизвестным при компиляции, новый адрес можно обозначить, изменив тип первоначального адреса так, чтобы в нем указывался дополнительный косвенный

уровень. Но может ли значение разыменовываться во время компиляции произвольное число раз без генерации кода? Если может, то в наших типах адресов мы должны указывать произвольное число косвенных уровней, что практически едва ли вероятно. Следовательно, в некоторгх случаях для осуществления разыменования во время прогона требуется выполнить действие (переслать значение по новому адресу).

Для повышения эффективности выдаваемого кода при компиляции можно проделать дополнительную работу, которая обычно называют оптимизацией. В оптимизацию входит удаление кода из циклов там, где это не влияет на значение программы, исключение возможности вычисления идентичных выражений более чем один раз и т.д. Описание некоторых неизвестных методов оптимизации можно найти у Гриса [20]. Кроме, того в Алголе 68 например, если провести тщательный анализ во время компиляции, можно иногда избежать перезаписи сложных структур данных во время прогона [52].

Компиляторы, выполняющие обширную оптимизацию, компилируют программы дольше, чем те, которые ее не выполняют. Решение вопроса о включении оптимизации зависит от целей проектирования компиляторов. По обобщению Хорнинга [29], проведение некоторых локальных видов оптимизации (например, < узких» - см. разд. 11.3.) не требует больших затрат, так что их почти всегда имеет смысл включать. Большинство же глобальных методов оптимизации уместно лишь в тех случаях, когда требование эффективности во время прогона приобретает первостепенную важность.

Упражнения

10.1. Представьте следующее выражение

а) в тройках;

б) в четверках;

(a + b + c) X (d + e + f)

10.2. Почему употребляются косвенные тройки?

10.3. Какие проблемы при преобразовании выражений, в котортх используются унарные знаки операций, в обратную польскую запись?

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

a + b X c

заменялось на

(a + (b X c))

Каковы преимущества и недостатки этого метода?

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

a + b X c

вычисляется как

(a + b) X c

Прокомментируйте этот прием с точки зрения реализации.