46023 (665330), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

разом, чтобы можно было выполнить "внешние" поиски определяю-

щих реализаций идентификаторов и т.д.

2. Поместить в стек (idstack pointer). Поместить в стек

(wostack pointer). Поместить в стек (block number). Все эти

значения ссылаются на включающий блок и могут потребоваться

вновь после того, как будет покинуть блок, в который только

что осуществлен вход:

idstack pointer := 0

wostack pointer := 0

3. Генерировать код для исправления DISPLAY

BLOCK ENTRY block number

4. Увеличить номер уровня блока на 1. Увеличить наиболь-

ший использованный до сих пор номер блока на 1 и присвоить

это значение номеру блока.

5. Прочитать информацию о виде и добавить ее в таблицу

видов ( если в языке имеются такие "сложные" виды, как в Ал-

голе 68 ).

При выходе из блока требуется:

1. Обновить таблицу блоков, задав размер стека идентифи-

каторов и т.п. для покинутого блока.

2. Исключить информацию в виде таблицы символов для по-

кинутого блока.

3. Генерировать код для изменения дисплея

BLOCK EXIT block number

4. Удалить из стека (block number). Удалить из стека

(wostack pointer). Удалить из стека (idstack pointer). Умень-

шить номер уровня на 1.

5. Поместить результат (при необходимости) в рамку стека

вызывающего блока.

ЛЕКЦИЯ 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 =

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 - начальный символ грамматики

Множество правил порождения 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-го уровня

Реализация контексных условий основана на том что имена

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

сут в себе информацию о типе соответствующих объектов

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

Характеристики

Список файлов реферата