Интегрированные схемы компиляции базируются на теории перевода языков, ключевыми понятиями которой являются схема синтаксически управляемого перевода (СУ-схема), синтаксически управляемый перевод (СУ-перевод), преобразователь с магазинной памятью (МП - преобразователь). Рассмотрим эти понятия.
Определение. СУ-схемой Т называется пятерка следующих объектов
T={VT, VN, ,R,S), где
VT — конечный входной алфавит, терминалы;
VN — конечное множество нетерминалов;
— конечный выходной алфавит;
R — конечное множество правил вида A-> , где V*,
(VN )*;
S — аксиома (начальный символ) схемы.
Определение. СУ-схема называется простой, если в каждом правиле А -> одноименные нетерминалы встречаются в и в одном и том же порядке. СУ-схема называется постфиксной, если VN * * в каждом правиле {А-> ) R.
Определение. СУ-переводом , определяемым (генерируемым) СУ-схемой T={VT, VN, ,R,S), называется множество пар
Грамматика GBX = {VT, VN, P,S), где Р = {А -> | (А -> ) R}, называется входной грамматикой СУ-схемы. Грамматика GВЫХ = { ,VN, P’,S), где P’ = {А -> | (А -> ) R}, называется выходной грамматикой СУ-схемы.
|
|
Пример Рассмотрим СУ-схему Т1 перевода арифметических выражений в обратную польскую запись. В основе этой схемы лежит соответствие правил записи арифметических выражений в обычной (инфиксной) форме и в ПОЛИЗ. Для упрощенных выражений такое соответствие приводится ниже.
Правила инфиксной формы Правила ПОЛИЗ
S->E S->E
E->E+T E->ET+
E->T E->T
T->T*F T->TF*
T->F T->F
F->(E) F->E
F-> имя F->имя
СУ-схема Т1 представляется пятеркой Т1 = {VT, VN, ,R,S), где S — аксиома, VT= {+, *, имя, (,)}; = {+, *, имя}; VN= {S, Е,T, F} и множество R содержит следующие правила:
1)S ->E,E 2)E->E+T,ET+ 3)E->T,T 4)T->T*F,TF* 5)T->F,F 6)F->(E),E 7)F ->имя, имя
Входной грамматикой СУ-схемы Т1 является GВХ = (Vt, Vn, Р, S), где множество правил Р представлено правилами инфиксной формы. GВЫХ= (, Vn, P’, S) — выходная грамматика СУ-схемы T1, а ее правила Р’ — это правила ОПЗ. Как показывает анализ правил СУ-схемы, Т1 — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода (а+b*с, abc*+) (T1).