Реферат: Проектирование трансляторов
ASS := LE ':='E TYPE
LE := id | ^ LE
E1 := E1 MULOP T | T
E2 := E2 ADDOP E1 | E1
T :=id | const | (E2)
E3 :=E3 COMPOP E2 | id | const
E4 :=E4 BOOLOP E3 | E3
E := E2 | E4
MULOP := '*' | '/'
ADDOP := '+' |'-'
COMPOP := '<' ;'>';'<=';'>=';'='
BOOLOP := 'AND' ;'OR'
В заключение хотелось бы отметить различия в синтаксисе за-
писи правил КСграмматики и грамматики ван Вейнгардена. В первой
разделителями символов и метасимволов являются пробелы, раздели-
телями альтернатив являются знаки '|'. Терминальные символы за-
писываются малыми латинскими буквами, нетерминальные симво-
лы-большими. При записи грамматик ван Вейнгардена разделителями
символов являются запятые, разделителями альтернатив являются
точки с запятыми. Терминальные символы порождаемой грамматики
представляются цепочками терминалов метаграмматики, начинающими-
ся с терминала symbol.
ЛЕКЦИЯ 19
ПРИМЕР ГРАММАТИКИ ВАН ВЕЙНГААРДЕНА
Грамматикой ван Вейнгаардена описываются конструкции присваи-
вания вида ( например , преобразование типов в языке СИ) :
Пусть int i,j;
char c,ch;
т.е. описываем переменные i и j как целые,а c и ch как символь-
ные.Необходимо отметить , что для построения правильной конс-
трукции, выражающей присвоение переменной одного вида переменной
другого вида , в языке СИ необходимо в правой части перед соот-
ветствующим идентификатором нужно указать тип к которому должна
быть приведена переменная из правой части. Разумеется, этот тип
- тип переменной в левой части выражения . Если же имеет место
присвоение типа (2) ,т.е. типы переменных правой и левой частей
совпадают,то тип в правой части не указывается.
(1) c= (char) i;
(2) ch=c;
(3) ch= (char) j+c;
(4) i=(int) ch;
(5) c= (char) 20;
Для данных выражений типы правых частей не везде совпадают с
типами соответствующих им левых частей. Необходимо произвести
преобразование типа левой части к типу идентификатора в правой
части.
assign : е TYPE l,'=', e TYPE mod. /*Задание
конструкций присваивания*/
e TYPE l : id./*В левой части конструкции может быть
только идентификатор*/
/*Правая часть конструции может быть предс-
тавлена: */
e TYPE mod: e TYPE r ; /* выражением типа правой
части-(1)*/
TYPE nomber; /*числовым типом*/
'(',TYPE,')',e TYPE1 r;/*конструкцией вида
(тип)выражение_типа_отличного_от_типа_ле-
вой_части -(4)*/
'(',TYPE,')',TYPE1 nomber. /*конструкцией
вида ( тип) номер,имеющий тип,отличный от
типа левой части конструкции -(5) */
e TYPE r : e TYPE l,operation, e TYPE1 l;/* выражение
в правой части может быть представлен
типом, аналогичным типу левой части (2),
операцией - (3),выражением типа ,отличного
от типа левой части. */
TYPE : int symbol;/* в данном примере могут ис-
пользоваться данные цело-
численного или символьного
сhar symbol. типов */
Где :
е- expression -выражение,
TYPE- тип,
l- left -левый,
r- right - правый,
mod- modern -новый(англ.),тогда
e TYPE l -выражение, тип которого может встретиться в
левой части выражения,
e TYPE r -обозначает выражение , тип которого может
встретиться в правой части ( простое ) ,
e TYRE mod-обозначает выражение , тип которго может
встретиться в правой части ( составное или
простое, т.е., может быть состоять только
из выражения типа правой части или из приве-
денного к нему, или из суммы приведенной к
нужному типу и типа левой части переменных.
РАСПРЕДЕЛЕНИЕ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ
1. ДИСПЛЕЙ
1.1 Взаимодействие Дисплея и стека
После выяснения структуры (и значения) программы необходимо
выделить место в памяти для значений переменных и т.п. и помес-
тить соответствующие адреса, где это необходимо, в таблицу симво-
лов. Фаза распределения памяти почти не зависит от языка и маши-
ны и практически одинакова для подавляющего большинства языков,
имеющих блочную структуру и реализуемых на многих типичных ЭВМ.
Распределение памяти, по существу, заключается в отображении зна-
чений, появляющихся в программе, на запоминающем устройстве маши-
ны. Если допустить, что мы реализуем типичный язык с блочной
структурой, а машина имеет линейное запоминающее устройство, то
наиболее подходящим устройством, на котором мы будем базировать
распределение памяти, представляет стек или память магазинного
типа.
Ниже мы рассмотрим классическую структуру стека времени про-
гона для локального распределения памяти и покажем, как можно
произвести глобальное распределение памяти в отдельной области,
называемой "кучей".
В каждом компиляторе предусмотрена схема распределения памя-
ти, которая до некоторой степени зависит от компилируемого языка.
В Фортране память, выделенная для значений идентификаторов, ни-
когда не освобождается, так что здесь подходящей структурой для
нее является одномерный массив. Если считается, что массив имеет
левую и правую стороны, память можно выделять слево направо. При
этом применяется указатель, показывающий первый свободный эле-
мент в массиве. Например, в результате описания
INTEGER A,B,X,Y
выделяется память, как показано на рис. 20.1.
┌───┬───┬───┬───┬───────────────
│ A │ B │ X │ Y │
└───┴───┴───┴───┴───────────────
^
│
Рис. 20.1 Схема выделения памяти в Фортране
Такая схема не учитывает тот факт, что рабочая память (па-
мять для промежуточных результатов) используется неоднократно и
весьма неэффективна (в смысле использования объема памяти) для
языка с блочной структурой.
В языке, имеющем блочную структуру, память обычно высвобож-
дается при выходе из блока, которому она выделена. В этом случае
оптимальным решением было бы разрешить указателю в вышеприведен-
ном примере отодвигаться обратно влево при высвобождении памяти.
Такой механизм распределения эквивалентен стеку времени прогона
или памяти магазинного типа, хотя принято показывать стек запол-
няющимся снизу вверх.
│ │ │ │ │ │ (1) begin real x,y
│ │ │ │ │ │ .
│ │ ├───┤ ├───┤ .
│ │ │ d │ │ q │ .
│ │ ├───┤ ├───┤ (2) begin int c,d
│ │ │ c │ │ p │ .
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ end;
│ │ │ │ │ │ (3) begin int p,q
│ Y │ │ Y │ │ Y │
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ .
│ │ │ │ │ │ end;
│ X │ │ X │ │ X │ .
└───┘ └───┘ └───┘ .
end.
(1) (2) (3)
Рис. 20.2 Схема распределения памяти под переменные в раз-
личные моменты в программе на языке с блочной структурой
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
