Лекция 16 Формальные методы описания перевода

Схемы компиляции

… Формирование ОМ ОМ Последовательная схема Семантический анализ Лексический анализ Синтаксический анализ

ИМ Лексический анализ Синтаксический анализ Семантический анализ Формирование ОМ ОМ Интегрированная схема Генерация кода ……

Синтаксически управляемые схемы СУ - схемы

СУ-схема Т =(V T, V N,, R, S) R: A,, где V*, (V N ) * V N * *, (A, ) R СУ- перевод (T)={(, y) | (S, S) *(, y), V T *, y * } Входная грамматика СУ-схемы G вх =(V T,V N,Р,S), где P={A |(A, ) R} Выходная грамматика СУ-схемы G вых =(,V N,Р´,S), где P´={A |(A, ) R}

Пример 1 Правила инфиксной формы: S E E E+T E T T T*F T F F (E) F имя Правила ПОЛИЗа: S E E ET+ E T T TF* T F F E F имя T 1 =(V T, V N,, R, S), где V T ={+, *, имя, (, )}; ={+, *, имя}; V N ={S, E, 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 имя, имя Вывод (S, S) *(a+b*c, abc*+): (S, S) Пара (a+b*c, abc*+) (T 1 ) (E, E) (E+T, ET+) (E+T*F, ETF*+) (T+T*F, TTF*+) (F+F*F, FFF*+) (a+b*c, abc*+) (T+F*F, TFF*+) Правила перевода:

МП-преобразователи МП-преобразователь P=(Q, T, N,, F, q 0, N 0, Z) Магазинная функция F: (Q (T { }) N) P(Q N * * )

a 1 a 2 … a n Управляющее устройство b 1 b 2 … b m Z1Z2…Z1Z2… Стек Входная строка Выходная строка Читающая головка Пишущая головка Схема преобразователя

Конфигурация МП-преобразователя: (q,,, y) (Q T* N * * ) Начальная конфигурация: (q 0,, N 0, ) Конечная конфигурация: (q,,, y), q Z Если F(q, t, n)=(q,, r), то (q, t, n, y) |- (q,,, yr), ( T*, N *, y * ) Основные определения

Переводом МП-преобразователя Р (Р)={(, y) | (q 0,, N 0, ) |-* (q,,, y), q Z, N * } Расширенный МП-преобразователь F: (Q (T { }) N * ) P(Q N * * ) Строка у – выход для, если (q 0,, N 0, ) |-* (q,,, y), q Z, N * Основные определения

Пример 2 2 : x {a, b} * переводит в y = (ab) n Например, 2 (aababb ) = ababab. ДМП P = ({q 0, q z }, {a, b, }, {Z, a, b}, {a, b}, F, q 0, Z, {q z }) Функция переходов вида: F(q 0, X, Z) = {(q 0, XZ, )}, X {a, b}; F(q 0,, Z) = {(q z, Z, )}; F(q 0, X, X) = {(q 0, XX, )}, X {a, b}; F(q 0, X, Y)={(q 0,, ab)}, X {a, b}, Y {a, b}, X Y.

Перевод цепочки aababb Q Стек Вход Выход q0q0 Z aababb q0q0 Za ababb q0q0 Zaa babb q0q0 Za abb ab q0q0 Zaa bb ab q0q0 Za b abab q0q0 Z ababab qzqz Z ababab