Реферат: Проектирование трансляторов
падать с числом пар граничащих массивов.
5. Количество и типы фактических параметров в операторах
процедур должны совпадать с количеством и типом форм. парамет-
ров, приведенных в описаниях процедур.
6. Фактический параметр, который соответствует формальному
параметру, вызываемому по наименованию и встреч. в левой части,
обязан быть переменной (а не выражением).
7. Идентификаторы,входящие в выражение для границ в описа-
ниях массивов, должны быть описаны в одном из объемлющих блоков.
ЛЕКЦИЯ 18
ГРАММАТИКИ ВАН ВЕЙНГААРДЕНА
ОПРЕДЕЛЕНИЕ: Грамматика ван Вейгаардена - это две связанные
грамматики, которые называются метаграмматикой или грамматикой
метаязыка и строгой грамматикой ( грамматикой ) языка:
Gv = < Gm, Gst >.
Gm = < Vs, Vm, Pm, M >
Vs - конечное множество малых синтаксических знаков ( в
русском издании "Пересмотренного сообщения об Алголе" множество
маленьких букв русского алфавита ).
Vl - конечное множество больших синтаксических знаков ( в
русском издании "Пересмотренного сообщения об Алголе" множество
больших букв русского алфавита ).
Vm - конечное множество метапонятий:
Vm с Vl+;
Vh - конечное множество гиперпонятий:
Vh с ( Vm U Vs )*;
Ah - конечное множество гиперальтернатив:
Ah с Vh ( {,} Vh )*
( гиперпонятия в гиперальтернативах отделяются запятыми ).
Ph - конечное множество гиперправил:
Ph с Vh {:} Ah ( {;} Ah )* {.}
( гиперальтернативы в гиперправилах отделяются точкой с
запятой, в конце гиперправила ставится точка ).
Правила в метаграмматике ( гиперправила ) также называются
формами или схемами.
Pm - конечное множество правил метапорождений:
Pm с Vm {::} Vh ( {;} Vh )* {.}
M - начальный символ грамматики ван Вейгаардена.
M с Vm
L ( Gm ) - ( в общем случае бесконечное ) множество терми-
нальных метапорождений метапонятия M: L ( Gm ) с Vs*
Пусть метапонятие MM имеет одно или более вхождений в ги-
перправило h. Согласованной заменой метапонятия MM в гиперправи-
ле h назовем замену всех его вхождений одним и тем же терминаль-
ным порождением Tm с L ( Gm ).
Правило порождения получается из гиперправила путем согласо-
ванной замены всех входящих в него метапонятий.
Понятием называется непустое ( протопонятие ), если для него
может быть получено правило порождения. Множество понятий как
раз является бесконечным множеством нетерминалов Vn грамматики.
Gst = < Vt, Vn, P, S >
Vt - конечное множество терминалов;
Vn - множество нетерминалов;
P - множество правил;
S - начальный символ грамматики
Множество правил порождения P определяется тем, что
P с Vn {:} A ( {;} A )* {.},
где Vn с Vs+ - множество понятий,
A с F ( {,} F )* - множество альтернатив,
F = 0 U Vt u Vn U B
0 - пустое множество;
B - множество тупиковых протопонятий.
Для тупикового протопонятия никакое правило порождения не
может быть выведено. Возможности тупиков используются в системе
предикатов для учета контекстных условий.
Предикат - это протопонятие имеющее одну из форм: where а (
если верно что а ) или unless а ( если неверно что а ).
Предикат выполняется ( используется правило под ним для по-
рождения ), если для него выводимо правило порождения, и в этом
случае его терминальное порождение всегда пусто, либо такой вы-
вод заводит в тупик, и в этом случае предикат не выполняется.
Таким образом, с правилом связывается контекст его примене-
ния.
Рассмотрим грамматику ван-Вейнгардена, описывающую синтаксис
оператора присваивания PASCAL-подобного языка и контролирующую
следующие контекстные условия (3-го рода по классификации Брат-
чикова)
1. Арифметическое выражение может состоять из выражений при-
надлежащих лишь арифметическим типам
2. Логическое выражение может состоять из выражений лишь ло-
гических типов
3. Не допускается смешивать в арифметических выражения раз-
личные типы
4. Переменной можно присваивать значение того же либо струк-
турно эквивалентного типа
Грамматика 1-го уровня
Нетерминальные символы метаграмматики
TYPE тип
ATYPE арифметический тип
PTYPE указательный тип ( указатель на нечто)
Правила метапорождения
TYPE ::= ATYPE | PTYPE | bool
PTYPE ::= pointer TYPE
ATYPE ::= int | float
Грамматика 2-го уровня
Реализация контексных условий основана на том что имена
терминальных и нетерминальных символов порождаемой граматики не-
сут в себе информацию о типе соответствующих объектов
Нетерминальные символы порождаемой грамматики
ass оператор присваивания
le TYPE левая часть оператора присваивания (выражение типа TYPE)
e TYPE правая часть оператора присваивания (lvalue типа TYPE)
e<n> TYPE выражения различных уровней приоритета
t TYPE терм (константа, переменная или выражение в скобках)
mulop операция *,/
addop +,-
compop <,>,>=,<=
boolop AND,OR
ass := le TYPE, ':=', e TYPE
le TYPE := id TYPE ; '^',le pointer TYPE
e1 ATYPE := e1 ATYPE, mulop, t ATYPE;t ATYPE
e2 ATYPE := e2 ATYPE, addop, e1 ATYPE; e1 ATYPE
t ATYPE := symbol id ATYPE; symbol const ATYPE; '(', e2 ATYPE, ')'
e3 bool := e3 ATYPE,compop ,e2 ATYPE ; symbol id bool ;symbol const bool
e4 bool := e4 bool ,boolop, e3; e3
e TYPE := e2 TYPE ; e4 TYPE
mulop := '*';'/'
addop := '+';'-'
compop := '<' ;'>';'<=';'>=';'='
boolop := 'AND' ;'OR'
Задача построения (конечной) контекстно-свободной грамма-
тики по грамматике ван-Вейнгардена решается путем разбиения бес-
конечных множеств терминальных и нетерминальных символов исход-
ной грамматики на конечное число классов, каждый из которых бу-
дет соответствовать терминалу либо нетеминалу строящейся грамма-
тики. Каждому классу соответствует цепочка символов метаграмма-
тики, из которой он выводится.
Нетерминалы КС-грамматики
ASS соответствует ass
LE ->le TYPE
E -> e
EN -> enTYPE
T -> t TYPE
MULOP ->mulop
ADDOP ->addop
COMPOP ->compop
BOOLOP ->boolop
Выполнив указанные выше замены в продукциях 2-го уровня (и
отбросив продукции грамматики 1-го уровня), получим
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 │ .
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
