Смекни!
smekni.com

Проектирование трансляторов (стр. 26 из 31)

няется и для меток).

2. По каждому использующему вхождению идентификатора или

целого, представляющего метку, в данном или объемлющем блоках

должно быть описание этого идентификатора.

3. Все переменные в левых частях при присваивании должны

быть одного типа.

4. Количество индексов у переменных с индексами должно сов-

падать с числом пар граничащих массивов.

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 Взаимодействие Дисплея и стека

После выяснения структуры (и значения) программы необходимо