Проектирование трансляторов

ЛЕКЦИЯ 16


КОНТЕКСТНЫЕ УСЛОВИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ


КОНТЕКСТНЫЕ УСЛОВИЯ 1-ОГО И 2-ОГО ТИПА


1. Условия, связанные с описанием правил идентификаторов


В каждом блоке без внутренних блоков идентификатор нельзя

описывать более одного раза.

Для процедур и функций ни один идентификатор не должен вхо-

дить более одного раза в список формальных параметров в совокуп-

ности спецификаций.


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

вхождениями идентификаторов.

.


Правила поиска часто называют алгоритмами идентификации.

Проверим одно контекстное условие:

1. Рассмотрим min блок.

2. Ищем определяющее вхождение идентификатора в рассмотрен-

ном блоке. Если оно найдено, то процедура идентификации законче-

на.

Иначе - шаг 3.

3. Ищем min блок, который мы рассмотрели в шаге 2. Если та-

кой блок найден, рассмотрим его и переходим к шагу 2. Иначе,

процедура закончена.

Это мы проверяем одно контекстное условие.

Однако, задача идентификации сложнее, т.к. обычно рассмат-

ривается группа контекстных условий.


1. Каждый идентификатор, входящий в совокупность специфика-

ций, должен также входить в список формальных параметров.

2. Каждый идентификатор, входящий в список значений, должен

входить в совокупность спецификаций.

3. Идентификаторы, входящие в тело процедуры, могут быть

описаны в блоке, вне этого блока или могут быть включены в

список формальных параметров.

Список спецификаций - заголовок (имя) функции, описание ти-

па функции.

Список значений - те параметры, кот. меняются при изменении

функции, т.е. результат.


КОНТЕКСТНЫЕ УСЛОВИЯ ТРЕТЬЕГО ТИПА


Они регламентируют:

1) Соответствие видов величин, входящих в синтаксические

конструкции программ.

2) Задание допустимых соотношений между формальными парамет-

рами в процессах и формальными описаниями соответствующих проце-

дур.

3) Сравнение индексов переменных в использующем и определяю-

щем вхождениях идентификаторов.

4) Сравнение размерности массива в используемом и определяю-

щем вхождении идентификатора.


КОНТЕКСТНЫЕ УСЛОВИЯ ЧЕТВЕРТОГО ТИПА


Некоторые логические ограничения, которые относятся к реа-

лизации той или иной версии транслятора.

Массив может быть с неограниченным размером.

ЛЕКЦИЯ 17


ПРОГРАММНЫЕ ГРАММАТИКИ


Правила вывода этих грамматик имеют тот же вид, что и у

классических, однако в отличии от последних на каждом шаге выво-

да правила, кот. могут быть применены, зависит не только от це-

почек вывода, но и от того, какие правила применялись на преды-

дущих шагах.


Gp = { Vт, Vn, P, I, S }

G - конечное множество целых положительных чисел

(множество меток)

** **

r) Ф -> psi │ W1 │ W2 │, W1, W2 - некоторое подмножество меток

│ * * *

метка,соотв. Ф,psi ( Vт U Vn )

выводу

* - соответствующий класс грамматическим правилам

** - обозначается некоторое подмножество

В терм. порожденной грамматике сформируем использование

данного грамматического файла.

w - промежуточная цепочка.

Если w содержит вхождения по цепочке Ф, то левое вхождение

Ф в цепочке заменяем на psi.

После чего к полученной цепочке вывода применяется правило,

помеченное метками из множества W1.

Если w не содержит вхождения строки Ф, то строка w не моди-

фицируется, и к ней применяется некоторое правило, полученное

меткой из множества W2.


Язык, порожденный этой грамматикой, содержит только терми-

нальные символы.

В зависимости от ограничений на классическую часть различа-

ют:

1) контекстно-свободные,

2) контекстно-зависимые,

3) укорачивающие грамматики.

Имеют место теории, которые доказывают, что программные кон-

текстно-свободной грамматики более мощные, чем просто контек-

стные-свободные грамматики, в то время как зависимые контек-

стно-свободные грамматики совпадают с программно контекстно-сво-

бодными грамматиками.

Когда применяются программные грамматики процесс трансляций

выполняется в 2 этапа:

1) Порождается промежуточная форма программы.

Имеет место некоторый промежуточный язык, в котором некото-

рые синтаксические конструкции отсутствуют (например, внутр.

блоки), а те, которые представлены - состоят из терминальных

символов-двойников, соответствующим терминальным символам прог-

раммы.

2) Промежуточная форма программы проверяется на предмет

соотношения контекстных условий и выполняется замена симво-

лов-двойников на терминальные символы программы.

Все терминальные символы в т.ч. и двойники должны использо-

ваться в различных модификациях.

После первого этапа выполняется проверка контекстных усло-

вий (2 этап).

Каждая проверка заключается в следующем:

- сначала выделяются конструкции, участвующие в проверке;

- выделение производится путем модификации символов, из ко-

торых эта конструкция состоит (присвоение индекса);

- далее производится сравнение выделенных конструкций;

способ зависит от конкретного контекстного условия (сравнение

может производиться на сравнение и не сравнение, т.д.)

Если результаты положительные, то производится вывод неко-

торых построенных конструкций.

На выходе все двойники заменяются на терминальные символы

(соответствующие).


КОНТЕКСТНЫЕ УСЛОВИЯ ДЛЯ ПРОГРАММНЫХ ГРАММАТИК


1. В каждом блоке без внутренних блоков каждый идентифика-

тор должен быть описан не более одного раза (это условие приме-

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

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 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;

Для данных выражений типы правых частей не везде совпадают с

типами соответствующих им левых частей. Необходимо произвести

преобразование типа

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: