Перевод и семантика

Формализмы, используемые для определения перевода

Теория перевода

Перевод (или трансляция) — это некоторое отношение между цепочками, или, другими словами, это некоторое множество пар цепочек. Компилятор определяет перевод, образуемый парами вида (исходная программа, объектная программа). Если компилятор состоит из трех фаз – лексического анализа, синтаксического анализа и генерации кода, то каждая из них сама является переводом. Лексический анализ можно рассматривать как перевод, при котором цепочки, представляющие исходные программы, отображаются в цепочки лексем. Синтаксический анализатор отображает цепочки лексем в цепочки, представляющие деревья. Затем генератор кода переводит эти цепочки на машинный язык или язык ассемблера.

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

Сначала мы исследуем переводы с абстрактной точки зрения, а затем рассмотрим применимость моделей перевода к лексическому и синтаксическому анализу.

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

Здесь мы изложим два фундаментальных метода определения перевода. Один из них — «схема перевода», которая представляет собой грамматику, снабженную механизмом, обеспечивающим выход для каждой порождаемой цепочки. В другом методе основную роль играет «преобразователь», т. е. распознаватель с выходом, который на каждом такте может выдавать цепочку выходных символов ограниченной длины. Сначала мы рассмотрим схемы перевода, основанные на контекстно-свободных грамматиках, а потом займемся конечными преобразователями и преобразователями с магазинной памятью.

Исследуем механизмы, связывающие с каждым предложением (цепочкой) языка другую цепочку, которая должна быть выходом, или результатом перевода, этого предложения. Для обозначения этого отношения между предложениями и соответствующими выходными цепочками, определяющими их «смыслы», или «значения», иногда употребляют термин «семантика».

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

Если , то цепочка называется выходом для цепочки .

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

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

Определение: Запись обычных (инфиксных) арифметических выражений без использования скобок называют польской (бесскобочной)

формой записи инфиксных арифметических выражений.

Пусть множество - это множество знаков бинарных операций вида и - это множество операндов данного выражения. Дадим рекурсивное определение префиксной (постфиксной) формы польской записи арифметических выражений.

Определение: Рекурсивное определение префиксной (постфиксной) формы
польской записи арифметических выражений:

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

2. Пусть выражение - инфиксное выражение,

где

- знак бинарной операции;

- инфиксные выражения,

тогда

а) Префиксной формой записи данного выражения будет , где и - префиксные формы записи инфиксных выражений и соответственно;

б) Постфиксной формой записи данного выражения будет , где - постфиксные выражения для инфиксных выражений и соответственно.

3. Если выражение - инфиксное, тогда

а) Префиксной формой записи будет ;

б) Постфиксной формой записи будет .

Пример:

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

.

Решение:

1. Построим префиксную форму записи

, ;

;

;

;

Арифметическое выражение в префиксной форме записи будет иметь вид

;

2. Построим постфиксную форму записи

;

;

Арифметическое выражение в постфиксной форме записи будет иметь вид

.

Домашнее задание: Записать постфиксную и префиксную форму записи для выражения вида

.

Дата добавления: 2014-01-07