СУ-схемы

Интегрированные схемы компиляции базируются на теории пере­вода языков, ключевыми понятиями которой являются схема синтаксически управляемого перевода (СУ-схема), синтакси­чески управляемый перевод (СУ-перевод), преобразователь с мага­зинной памятью (МП - преобразователь). Рассмотрим эти понятия.

Определение. СУ-схемой Т называется пятерка следующих объектов

T={V_T, V_N, ,R,S), где

V_T — конечный входной алфавит, терминалы;

V_N — конечное множество нетерминалов;

— конечный выходной алфавит;

R — конечное множество правил вида A-> , где V*,

(V_N )*;

S — аксиома (начальный символ) схемы.

Определение. СУ-схема называется простой, если в каждом правиле А-> одноименные нетерминалы встречаются в и в одном и том же порядке. СУ-схема называется постфиксной, если V_N ^* * в каждом правиле {А-> ) R.

Определение. СУ-переводом , определяемым (генерируемым) СУ-схемой T={V_T, V_N, ,R,S), называется множество пар

Грамматика G_BX = {V_T, V_N, P,S), где Р = {А -> | (А -> ) R}, называется входной грамматикой СУ-схемы. Грамматика G_ВЫХ ={ ,V_N, P^’,S), где P^’ = {А -> | (А -> ) R}, называется выходной грамматикой СУ-схемы.

ПримерРассмотрим СУ-схему Т₁ перевода арифметичес­ких выражений в обратную польскую запись. В основе этой схе­мы лежит соответствие правил записи арифметических выраже­ний в обычной (инфиксной) форме и в ПОЛИЗ. Для упрощенных выражений такое соответствие приводится ниже.

Правила инфиксной формы Правила ПОЛИЗ

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->имя

СУ-схема Т₁ представляется пятеркой Т₁ = {V_T, V_N, ,R,S), где S — аксиома, V_T= {+, *, имя, (,)}; = {+, *, имя}; V_N= {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 ->имя, имя

Входной грамматикой СУ-схемы Т₁ является G_ВХ = (Vt, Vn, Р, S), где множество правил Р представлено правилами инфиксной фор­мы. G_ВЫХ= ( , Vn, P^’ , S) — выходная грамматика СУ-схемы T₁, а ее правила Р^’ — это правила ОПЗ. Как показывает анализ пра­вил СУ-схемы, Т₁ — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода (а+b*с, abc*+) (T₁).