Реферат: Проектирование трансляторов
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<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-го уровня), получим
Страницы: 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
