Понятие синтаксически-управляемого перевода

Рассмотрим множество пар (a, b), где a - цепочка входного языка, а b - цепочка выходного языка. Если эти пары получаются с помощью некоторой грамматики, то перевод называют синтаксически управляемым.

Пусть дана последовательность актов, состоящая из входных символов и символов действий. Под входной цепочкой будем понимать последовательность входных символов, полученную из последовательности актов вычеркиванием всех символов действия. Под выходной цепочкой будем понимать последовательность входных символов, полученную из последовательности актов вычеркиванием всех входных символов. Будем говорить, что входная последовательность образует пару с последовательностью действий.

Замечание: Некоторые транслирующие грамматики обладают тем свойством, что одна и та же входная цепочка может встречаться более, чем в одной последовательности актов, или обрабатывать пары с более, чем одной последовательностью действий.

Пусть дана транслирующая грамматика. Грамматика, полученная вычеркиванием всех символов действий из правил этой грамматики, называется входной грамматикой для этой транслирующей грамматики. Язык, определяемый входной грамматикой, называется входным языком.

Пример: Для G_T входной грамматикой является G_I= ({a, b, c}, {A, B}, A, P_II).

P_I: A®aAB

A®e

B®Bc

B®b

Таким образом, входная грамматика определяет множество цепочек, для которых транслирующая грамматика определяет переводы. При разработке транслятора, вначале обрабатываемый язык описывается входной грамматикой, а затем в правила этой грамматики вставляются символы действия для описания требуемого процесса.

Выходную грамматику (или грамматику действий) можно получить вычеркиванием входных символов.

Пример: для G_T выходной грамматикой является G_O= ({x, y, z}, {A, B}, A, P_O).

P_O: A®AxB

A®z

B®B

B®y

))П)

Таким образом, транслирующую грамматику можно рассматривать как переводящую с одного КС-языка (входного) на другой КС-язык (выходной или действий). В случае грамматики цепочечного перевода, считаем последовательность действий синонимом соответствующей выходной цепочки.

Пример: Рассмотрим способ записи арифметических выражений, называемый постфиксной польской записью (разработана польским математиком Я. Лукасевичем). В постфиксной польской записи знак операции следует сразу за операндами:

<операнд> ® <операнд> <операнд> +

<операнд> ® <операнд> <операнд> *

<операнд> ® I, где I - любая переменная.

Цепочки: a b * (т.е. a*b), a b c * + (т.е. a+b*c)

Польская запись не содержит скобок: ((a+b)*c) ~ a b + c *.

Польская запись обеспечивает другой язык для записи математических формул. Некоторые компиляторы имеют синтаксический блок, который буквально переводит инфиксные выражения в польские. Многие другие выполняют перевод, аналогичный переводу в польскую запись.

Пример: Построим грамматику перевод инфиксных арифметических выражений в польскую запись.

1) Опишем грамматику инфиксных выражений (для удобства будем использовать три конкретных имени переменных).

P_i:

1. S ® S + T

2. S ® T

3. T ® T * P

4. T ® P

5. P ® (S)

6. P ® a

7. P ® b

8. P ® c

Будем обозначать действие ПЕЧАТЬ(СИМВОЛ) фигурными скобками {символ}. Например, чтобы напечатать а, после того как а прочитано, правило заменяется на P® a {a}.

Pt:

1. S ® S + T {+}

2. S ® T

3. T ® T * P {*}

4. T ® P

5. P ® (S)

6. P ® a {a}

7. P ® b {b}

8. P ® c {c}

Вход: (a+b)*c

Вывод:

Pi: S ® T ® T*P ® P*P ® (S)*P ® (S+T)*P ®* (a+b)*c

Pt: S ® T ® T*P{*} ® P*P{*} ® (S)*P{*}®(S+T{+})*P{*}®* (a{a}+b{b}{+})*c{c}{*}

Выход: a b + c *

Замечание: В рассмотренных грамматиках в понятие символа не включалось представление о том, что должен составлять из значения и класса. Грамматики, транслирующие цепочки, способны описывать перевод только той компоненты символа, которая указывает его класс. Таким образом, необходимо рассматривать понятие транслирующей грамматики.

Вопросы и упражнения

1. Что понимают под синтаксически управляемым переводом?

2.Что понимают под входной и выходной цепочками?

3. Что понимают под входной и выходной грамматиками?

4. Что понимают под входном и выходным языками?

5. Постройте транслирующую грамматику, переводящую польскую запись арифметического выражения в общепринятую (со скобками).