Для перевода с одного языка на другой программам, как и людям, требуется переводчик или, говоря по-научному, транслятор.

Транслятор: основные понятия

Такая программа как транслятор представляет собой лингвистическое представление вычислений I ->P ->P (i). Интерпретатор представляет собой программу, на вход которой подается программа P с некоторыми входными данными X.Выполняет он P на X: I(P, x)=P(x).Существует единственный транслятор, который способен выполнять все возможные программы (которые можно представить в формальной системе). Это является очень значительным и глубоким открытием Тьюринга. Процессор представляет собой интерпретатор программ на машинном языке. Писать интерпретаторы для языков высокого уровня, как правило, слишком дорого, поэтому их транслируют в ту форму, которую легче интерпретировать. Некоторые виды трансляторов обладают очень странными именами. Программа транслирует программы на ассемблере в машинный язык. Компилятор позволяет транслировать с языка высокого уровня на язык более низкого уровня. Транслятор представляет собой программу, которая в качестве входных данных принимает программу на некотором языке S и после обработки выдает программу на языке T.Таким образом, они обе имеют ту же семантику: P->X->Q. Таким образом, для любого xP(x)=Q(x). Если транслировать всю программу в нечто интерпретируемое, то это называется компиляцией перед исполнением или компиляцией AOT. Компиляторы AOT могут использоваться последовательно. Последний из них очень часто является ассемблером. Так, рассмотрим пример: Исходный код ->Компилятор (транслятор) -> Ассемблерный код -> Ассемблер (транслятор) -> Машинный код -> ЦПУ (интерпретатор). Динамическая или оперативная компиляция осуществляется в том случае, если часть программы транслируется, когда исполняются другие скомпилированные ранее части. Трансляторы JIT запоминают то, что они уже выполнили ранее, чтобы снова и снова не повторять исходный код. Они даже способны выполнять адаптивную компиляцию и перекомпиляцию, которая основана на поведении среды выполнения программы. Многие языки дают возможность выполнять код во время трансляции, а также компилировать новый код во время выполнения программы.

Трансляция: этапы

Процесс трансляции состоит из этапов синтеза и анализа. Схематично этот процесс выглядит примерно следующим образом: Исходный код -> Анализатор -> Концептуальное представление -> Синтезатор (генератор) -> Целевой код. Обусловлено это следующими причинами:

— любой другой способ просто не подходит;

— перевод по словам просто не работает.

Можно использовать следующее инженерное решение: если необходимо написать трансляторы для M исходных языков и N целевых, потребуется написать только M+N простых программ (полукомпиляторов), а не MxN полных (комплексных) трансляторов. На практике, тем не менее, концептуальное представление довольно редко бывает выразительным и мощным, чтобы охватить все существующие целевые и исходные языки. Хотя некоторые пользователи смогли приблизиться к этому. Реальные компиляторы проходят через множество различных этапов. При создании собственного компилятора не нужно будет заново проводить всю тяжелую работу, которую программисты уже проделали при создании генераторов и представлений. Свой язык можно транслировать непосредственно в JavaScript или C и использовать для этой цели существующие компиляторы языка C и JavaScript движки для того, чтобы сделать все остальное. Можно также использовать существующие промежуточные представления и виртуальные машины.

Запись транслятора

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

1. Транслятор – это самокомпилятор, если исходный язык у него соответствует базисному.
2. Саморезидентным называется компилятор, у которого целевой язык равняется базисному.
3. Если целевой и базисный языки различные, то транслятор – это кросс-компилятор.

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

Масштабная технология

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

Проектирование компилятора. Возможные проблемы, возникающие при создании реального транслятора

Какие проблемы могут возникать с исходным языком? Легко ли его скомпилировать? Имеется ли для этого препроцессор? Каким образом обрабатываются типы? Какая группировка проходов компилятора используется – одно- или многоходовая? Также особого внимания заслуживает желаемая степень оптимизации. Быстрая и нечистая трансляция программы практически без оптимизации может быть нормальной. Чрезмерная оптимизация может тормозить компилятор, однако, во время выполнения лучший код может того стоить.

Степень обнаружения ошибок. Нужно ли, чтобы транслятор остановился уже на первой ошибке? Когда он должен остановиться? Стоит ли доверять компилятору процедуру исправления ошибок?

Необходимый набор инструментов

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

Что касается вида целевого кода для генерации, тут необходимо выбирать из чистого, дополненного или виртуального машинного кода. Можно также написать входную часть, которая создает популярные промежуточные представления, такие как LLVM, JVM, RTL. Можно также сделать трансляцию из исходного в исходный код на Java Script или C. Если говорить о формате целевого кода, тут здесь можно выбрать переносимый машинный код, машинный код образа памяти, язык ассемблера.

Перенацеливание

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

Компоненты компилятора

Перечислим главные функциональные компоненты транслятора, который генерирует машинный код, если выходной программой является программа, написанная на языке C или виртуальная машина:

— входная программа поступает в лексический анализатор, или по-другому сканер, который преобразует ее в поток токенов;

— синтаксический анализатор (парсер) строит из них абстрактное синтаксическое дерево;

— семантический анализатор раскладывает семантическую информацию и проверяет на предмет наличия ошибок узлы дерева;

— в результате строится семантический граф. Под этим термином понимают абстрактное синтаксическое дерево с установленными ссылками и дополнительными свойствами;

— генератор промежуточного кода строит граф потока (кортежи группируются в основные блоки);

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

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

— для распределения памяти между виртуальными регистрами и выполнения планирования команд используется машинозависимый оптимизатор-компоновщик. Он также осуществляет преобразование программы, написанной на ассемблере, в настоящий ассемблер с применением конвейерной обработки.

— используются подсистемы обнаружения ошибок и менеджер таблиц символов;

— сканирование и лексический анализ. Сканер используется для конвертации потока знаков исходного кода в поток токенов, убирая комментарии, пробелы и расширяя макросы. Довольно часто сканеры встречаются с такой проблемой, принимать ли во внимание отступы, регистр, вложенные комментарии.

Те ошибки, которые могут встретиться при сканировании, называются лексическими. Они включают в себя следующие:

— отсутствующие в алфавите символы;

— превышение количества знаков в строке или слове;

— не закрытый строковый литерал или знак;

— конец файла в комментарии.

Синтаксический анализ или парсинг применяется для преобразования последовательности токенов в абстрактное синтаксическое дерево. При этом каждый узел дерева сохраняется как объект с именованными полями. Многие из них сами являются узлами дерева. Циклы на этом этапе отсутствуют. При создании парсера нужно в первую очередь обращать внимание на уровень сложности грамматики (LRили LL) и выяснить, имеются ли какие-то правила снятия неоднозначности. Действительно некоторые языки требуют проведения семантического анализа. Ошибки, которые встречаются на данном этапе, называются синтаксическими.

Семантический анализ

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

— множественные объявления переменной в пределах области ее действия;

— нарушение правил доступности;

— наличие ссылок на необъявленное имя;

— чересчур большое или, наоборот, недостаточное число аргументов при вызове метода;

— несоответствие типов.

Генерация

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

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

Основные понятия

Программа представляет собой лингвистическое представление вычислений: i → P → P(i). Интерпретатор представляет собой программу, на вход которой подается программа Р и некоторые входные данные x. Он выполняет P на х: I(P, x) = P(x). Тот факт, что существует единственный транслятор, способный выполнять все возможные программы (которые можно представить в формальной системе), является очень глубоким и значительным открытием Тьюринга.

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

Некоторые виды трансляторов имеют очень странные имена:

• Ассемблер транслирует программы на ассемблере в машинный язык.
• Компилятор транслирует с языка высокого уровня на язык более низкого.

Транслятор - это программа, которая принимает в качестве входных данных программу на некотором языке S и выдает программу на языке T таким образом, что обе они имеют ту же семантику: P → X → Q. То есть, ∀x. P(х) = Q(х).

Если транслировать всю программу в нечто интерпретируемое, то это называется компиляцией перед исполнением, или АОТ-компиляцией. АОТ-компиляторы могут использоваться последовательно, последний из которых часто является ассемблером, например:

Исходный код → Компилятор (транслятор) → Ассемблерный код → Ассемблер (транслятор) → Машинный код → ЦПУ (интерпретатор).

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

Многие языки позволяют выполнять код во время трансляции и компилировать новый код во время выполнения программы.

Этапы трансляции

Трансляция состоит из этапов анализа и синтеза:

Исходный код → Анализатор → Концептуальное представление → Генератор (синтезатор) → Целевой код.

Это обусловлено такими причинами:

• Любой другой способ не подходит. Пословный перевод просто не работает.
• Хорошее инженерное решение: если нужно написать трансляторы для M исходных языков и N целевых, потребуется написать только M + N простых программ (полукомпиляторов), а не M × N комплексных (полных трансляторов).

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

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

Запись транслятора

Транслятор - это программа или техническое средство, в котором задействованы три языка: исходный, целевой и базисный. Их можно записать в Т-форме, расположив исходный слева, целевой справа и базисный ниже.

Существует три вида компиляторов:

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

Почему это важно?

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

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

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

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

Всеобъемлющая технология

Технология компилятора охватывает множество различных областей информатики:

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

Проектирование компилятора

Некоторые проблемы, возникающие при разработке реального транслятора:

• Проблемы с исходным языком. Легко ли его скомпилировать? Есть ли препроцессор? Как обрабатываются типы? Имеются ли библиотеки?
• Группировка проходов компилятора: одно- или многоходовая?
• Степень желательной оптимизации. Быстрая и нечистая трансляция программы практически без оптимизации может быть нормальной. Чрезмерная оптимизация будет тормозить компилятор, но лучший код во время выполнения может того стоить.
• Требуемая степень обнаружения ошибок. Может ли транслятор просто остановиться на первой ошибке? Когда он должен остановиться? Доверить ли компилятору исправление ошибок?
• Наличие инструментов. Если исходный язык не является очень маленьким, сканер и генератор анализаторов являются обязательными. Также существуют генераторы генераторов кода, но они не так распространены.
• Вид целевого кода для генерации. Следует выбирать из чистого, дополненного или виртуального машинного кода. Или просто написать входную часть, создающую популярные промежуточные представления, такие как LLVM, RTL или JVM. Или сделать трансляцию от исходного в исходный код на C или JavaScript.
• Формат целевого кода. Можно выбрать переносимый образа памяти.
• Перенацеливание. При множестве генераторов хорошо иметь общую входную часть. По этой же причине лучше иметь один генератор для многих входных частей.

Архитектура компилятора: компоненты

Это главные функциональные компоненты транслятора, генерирующего машинный код (если выходной программой является программа на С или виртуальная машина, то потребуется не так много этапов):

• Входная программа (поток знаков) поступает в сканер (лексический анализатор), который преобразует ее в поток токенов.
• Парсер (синтаксический анализатор) строит из них абстрактное синтаксическое дерево.
• Семантический анализатор раскладывает семантическую информацию и проверяет узлы дерева на ошибки. В результате строится семантический граф - абстрактное синтаксическое дерево с дополнительными свойствами и установленными ссылками.
• Генератор промежуточного кода строит граф потока (кортежи группируются в основные блоки).
• Машинонезависимый оптимизатор кода проводит как локальную (внутри базового блока), так и глобальную (по всем блокам) оптимизацию, в основном оставаясь в рамках подпрограмм. Сокращает избыточный код и упрощает вычисления. В результате получается модифицированный граф потока.
• Генератор целевого кода связывает базовые блоки в прямолинейный код с передачей управления, создавая объектный файл на ассемблере с виртуальными регистрами (возможно, неэффективными).
• Машинозависимый оптимизатор-компоновщик распределяет память между регистрами и производит планирование команд. Осуществляет преобразование программы на ассемблере в настоящий ассемблер с хорошим использованием конвейерной обработки.

Кроме того, используются подсистемы обнаружения ошибок и менеджер таблиц символов.

Лексический анализ (сканирование)

Сканер конвертирует поток знаков исходного кода в поток токенов, убирая пробелы, комментарии и расширяя макросы.

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

Ошибки, которые могут встретиться при сканировании, называются лексическими и включают:

• символы, отсутствующие в алфавите;
• превышение числа знаков в слове или строке;
• не закрытый знак или строковый литерал;
• конец файла в комментарии.

Синтаксический анализ (парсинг)

Парсер преобразует последовательность токенов в абстрактное синтаксическое дерево. Каждый узел дерева сохраняется как объект с именованными полями, многие из которых сами являются узлами дерева. На этом этапе циклы отсутствуют. При создании парсера необходимо обратить внимание на уровень сложности грамматики (LL или LR) и выяснить, есть ли какие-либо правила снятия неоднозначности. Некоторые языки действительно требуют проведения семантического анализа.

Ошибки, встречающиеся на этом этапе, называются синтаксическими. Например:

• k = 5 * (7 - y;
• j = /5;
• 56 = x * 4.

Семантический анализ

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

Очевидно, что набор правил допустимости у разных языков различный. Если компилируются Java-подобные языки, трансляторы могут найти:

• множественные объявления переменной в пределах области ее действия;
• ссылки на переменную до ее объявления;
• ссылки на необъявленное имя;
• нарушение правил доступности;
• слишком большое или недостаточное количество аргументов при вызове метода;
• несоответствие типов.

Генерация

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

Генерация кода производит реальный машинный код. В традиционных компиляторах для RISC-машин на первом этапе создается ассемблер с бесконечным числом виртуальных регистров. Для CISC-машин, вероятно, этого не произойдет.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

хорошую работу на сайт">

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

Размещено на http://www.allbest.ru

Введение

1.1 Разбор сверху-вниз

1.2 Разбор снизу-вверх

1.2.1 LR(k) - грамматики

1.2.1.1 LR(0) - грамматики

1.2.2 LALR(1) - грамматики

2. Разработка транслятора

2.1 Анализ требований

2.2 Проектирование

2.2.1 Проектирование лексического анализатора

2.2.4 Программная реализация синтаксического анализатора

2.3 Кодирование

2.4 Тестирование

Заключение

Список использованных источников

Приложение А. Листинг программного текста транслятора

Приложение Б. Результаты тестирования

Приложение В. Схема программы транслятора

Введение

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

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

Языки программирования являются инструментами для решения задач в разных предметных областях, что определяет специфику их организации и различия по назначению. В качестве примера можно привести такие языки как Фортран, ориентированный на научные расчеты, C, предназначенный для системного программирования, Пролог, эффективно описывающий задачи логического вывода, Лисп, используемый для рекурсивной обработки списков. Эти примеры можно продолжить. Каждая из предметных областей предъявляет свои требования к организации самого языка. Поэтому можно отметить разнообразие форм представления операторов и выражений, различие в наборе базовых операций, снижение эффективности программирования при решении задач, не связанных с предметной областью. Языковые различия отражаются и в структуре трансляторов. Лисп и Пролог чаще всего выполняются в режиме интерпретации из-за того, что используют динамическое формирование типов данных в ходе вычислений. Для трансляторов с языка Фортран характерна агрессивная оптимизация результирующего машинного кода, которая становится возможной благодаря относительно простой семантике конструкций языка - в частности, благодаря отсутствию механизмов альтернативного именования переменных через указатели или ссылки. Наличие же указателей в языке C предъявляет специфические требования к динамическому распределению памяти.

Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Язык программирования PL/1 допускает произвольное вложение процедур и функций, тогда как в C все функции должны находиться на внешнем уровне вложенности. Язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. Еще дальше в этом вопросе идет PL/1, который допускает описание переменной после ее использования. Или описание можно вообще опустить и руководствоваться правилами, принятыми по умолчанию. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.

Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

Наряду с традиционным процедурным программированием, называемым также императивным, существуют такие парадигмы как функциональное программирование, логическое программирование и объектно-ориентированное программирование. Структура понятий и объектов языков сильно зависит от избранной парадигмы, что также влияет на реализацию транслятора.

Даже один и тот же язык может быть реализован нескольким способами. Это связано с тем, что теория формальных грамматик допускает различные методы разбора одних и тех же предложений. В соответствии с этим трансляторы разными способами могут получать один и тот же результат (объектную программу) по первоначальному исходному тексту.

Вместе с тем, все языки программирования обладают рядом общих характеристик и параметров. Эта общность определяет и схожие для всех языков принципы организации трансляторов.

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

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

Для любого языка определяется:

- множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы,

- множество правильных программ (синтаксис),

- "смысл" каждой правильной программы (семантика).

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

Формально каждая правильная программа X - это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

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

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

Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic). Знание семантики языка позволяет отделить ее от его синтаксиса и использовать для преобразования в другой язык (осуществить генерацию кода).

Целью данной курсовой работы является разработка учебного транслятора с заданного упрощенного текстового языка высокого уровня.

1. Методы грамматического разбора

Рассмотрим основные методы грамматического разбора.

1.1 Разбор сверху-вниз

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

1.1.1 LL(k) - языки и грамматики

Рассмотрим дерево вывода в процессе получения левого вывода цепочки. Промежуточная цепочка в процессе вывода состоит из цепочки из терминалов w, самого левого нетерминала A, недовыведенной части x:

-S--

/ \

/ -А-x-\

/ | \

-w---u----

Pисунок 1

Для продолжения разбора требуется заменить нетерминал A по одному из правил вида A:y. Если требуется, чтобы разбор был детерминированным (без возвратов), это правило требуется выбирать специальным способом. Говорят, что грамматика имеет свойство LL(k), если для выбора правила оказывается достаточно рассмотреть только wAx и первые k символов непросмотренной цепочки u. Первая буква L (Left, левый) относится к просмотру входной цепочки слева направо, вторая - к используемому левому выводу.

Определим два множества цепочек:

а) FIRST(x) - множество терминальных цепочек, выводимых из x, укороченных до k символов.

б) FOLLOW(A)- множество укороченных до k символов терминальных цепочек, которые могут следовать непосредственно за A в выводимых цепочках.

Грамматика имеет свойство LL(k), если из существования двух цепочек левых выводов:

S:: wAx: wzx:: wu

S:: wAx: wtx:: wv

из условия FIRST(u)=FIRST(v) следует z=t.

В случае k=1 для выбора правила для А, достаточно знать только нетерминал A и а - первый символ цепочки u:

- следует выбрать правило A:x, если а входит в FIRST(x),

- следует выбрать правило A:е, если а входит в FOLLOW(A).

LL(к)-свойство накладывает довольно сильные ограничения на грамматику. Например, LL(2) грамматика S: aS | a не обладает свойством LL(1), т.к. FIRST(aS)=FIRST(a)=a. В данном случае можно понизить величину k с помощью "факторизации" (вынесения множителя за скобку):

S: aA

A: S | e

Любая LL(k)-грамматика однозначна. Леворекурсивная грамматика не принадлежит классу LL(k) ни для какого k. Иногда удается преобразовать не LL(1)-грамматику в эквивалентную ей LL(1)-грамматику с помощью устранения левой рекурсии и факторизации. Однако проблема существования эквивалентной LL(k)-грамматики для произвольной не LL(k)-грамматики неразрешима.

1.1.2 Метод рекурсивного спуска

Метод рекурсивного спуска ориентирован на те случаи, когда компилятор программируется на одном из языков высокого уровня, когда допускается использование рекурсивных процедур.

Основная идея рекурсивного спуска состоит в том, что каждому нетерминалу грамматики соотвествует процедура, которая распознает любую цепочку, порождаемую этим нетерминалом. Эти процедуры вызывают друг друга, когда это требуется.

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

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

Применение рекурсивного спуска на языке высокого уровня облегчает программирование и от отладку.

1.2 Разбор снизу-вверх

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

-S--

/ \

/-x- \

/ | \

--w--b--u-

Рисунок 2

Промежуточный вывод имеет вид xbu, где x - цепочка терминалов и нетерминалов, из которой выводится просмотренная часть терминальной цепочки w, bu - непросмотренная часть терминальной цепочки, b - очередной символ. Чтобы продолжить разбор, можно либо добавить символ b к просмотренной части цепочки (выполнить так называемый "сдвиг"), либо выделить в конце x такую цепочку z (x=yz), что к z можно применить одно из правил грамматики B:z и заменить x на цепочку yB (выполнить так называемую "свертку"):

-S-- -S--

/ \ / \

/-x-b- \ /yB- \

/ | \ / | \

--w--b--u- --w--b--u-

Рисунок 3 - После сдвига Рисунок 4 - После свертки

Если свертку применять только к последним символам x, то мы будем получать правые выводы цепочки. Такой разбор получил название LR, где символ L (Left,левый) относится к просмотру цепочки слева направо, а R (Right, правый) относится к получаемым выводам.

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

1.2.1 LR(k) - грамматики

Если в процессе LR-разбора принять детерминированное решение о сдвиге/свертке удается, рассматривая только цепочку x и первые k символов непросмотренной части входной цепочки u (эти k символов называют аванцепочкой), говорят, что грамматика обладает LR(k)-свойством.

-S--

/ \

/-x- \

--w----u--

Рисунок 5

Различие между LL(k)- и LR(k)-грамматиками в терминах дерева вывода:

-S-

/ | \

/ A \

/ / \ \

-w---v---u-

Рисунок 6

В случае LL(k)-грамматик однозначно определить правило, примененное к A, можно по w и первым k символам vu, а в случае LR(k)-грамматик - по w,v и первым k символам u. Это нестрогое рассуждение показывает, что LL(k)-языки < LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - грамматики

Рассмотрим вначале наиболее простые грамматики этого класса - LR(0). При разборе строки LR(0)-языка можно вообще не использовать аванцепочку - выбор между сдвигом и сверткой делается на основании цепочки x. Так как в процессе разбора она изменяется только с правого конца, ее называют стеком. Будем считать, что в грамматике нет бесполезных символов и начальный символ не встречается в правых частях правил - тогда свертка к начальному символу сигнализирует об успешном завершении разбора. Попробуем описать множество цепочек из терминалов и нетерминалов, появляющихся в стеке в процессе всех LR-разборов (другими словами - всех правых выводов из грамматики).

Определим следующие множества:

L(A:v) - левый контекст правила A:v - множество состояний стека, непосредственно перед сверткой v в A в ходе всех успешных LR-разборов. Очевидно, каждая цепочка из L(A:v) кончается на v. Если у всех таких цепочек отрезать хвост v, то получится множество цепочек, встречающихся слева от A в процессе всех успешных правых выводов. Обозначим это множество L(A) - левый контекст нетерминала A.

Построим грамматику для множества L(A). Терминалами новой грамматики будут терминалы и нетерминалы исходной грамматики, нетерминалы новой грамматики обозначим ,... - их значениями будут левые контексты нетерминалов исходной грамматики. Если S - начальный символ исходной грамматики, то грамматика левых контекстов будет содержать правило : e - левый контекст S содержит пустую цепочку Для каждого правила исходной грамматики, например, A: B C d E

и добавим в новую грамматику правила:

: - L(B) включает L(A)

: B - L(C) включает L(A) B

: B C d - L(E) включает L(A) B C d

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

- регулярны. Из этого следует, что принадлежность цепочки левому контексту какого-либо нетерминала можно вычислять индуктивно с помощью конечного автомата, просматривая цепочку слева направо. Опишем этот процесс конструктивно.

Назовем LR(0)-ситуацией правило грамматики с одной отмеченной позицией между символами правой части правила. Например, для грамматики S:A; A:aAA; A:b существуют следующие LR(0)-ситуации: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (позиция обозначена символом подчеркивания).

Будем говорить, что цепочка x согласована с ситуацией А:b_c, если x=ab и a принадлежит L(A). (Другими словами, LR-вывод может быть продолжен x_... = ab_...:: abc_...:: aA_...:: S_.) В этих терминах L(A:b) - множество цепочек, согласованных с ситуацией A:b_, L(A)

- цепочки, согласованные с ситуацией A:_b, для любого правила A:b.

Пусть V(u) - множество ситуаций, согласованных с u. Покажем, что функция V - индуктивна.

Если в множество V(u) входит ситуация A:b_cd, то ситуация A:bc_d принадлежит V(uc). (c - терминал или нетерминал; b, d - последовательности (может быть пустые) терминалов и нетерминалов). Других ситуаций вида A:b_d, с непустым b в V(uc) нет. Осталось добавить в V(uc) ситуации вида C:_..., для каждого нетерминала C, левый контекст которого содержит uc. Если ситуация A:..._C... (C-нетерминал) принадлежит множеству V(uc), то uc принадлежит L(C) и V(uc) включает в себя ситуации вида C:_... для всех C-правил грамматики.

V(e) содержит ситуации S:_... (S-начальный символ), а также ситуации A:_..., если нетерминал A встречается непосредственно после _ в ситуациях, уже включенных в V(e).

Наконец, мы готовы дать определение LR(0)-грамматики. Пусть u - содержимое стека в процессе LR-разбора, V(u)-множество LR(0) ситуаций, согласованных с u. Если V(u) содержит ситуацию вида А:x_ (x-последовательность терминалов и нетерминалов), то u принадлежит L(A:x) и допустима свертка x в A. Если V(u) содержит ситуацию A:..._a... (а-терминал), то допустим сдвиг. Говорят о конфликте сдвиг-свертка, если для одной цепочки u допустимы и сдвиг, и свертка. Говорят о конфликте свертка-свертка, если допустимы свертки по различным правилам.

Грамматика называется LR(0), если для всех состояний стека в процессе LR-вывода нет конфликтов сдвиг-свертка или свертка-свертка.

1.2.1.2 LR(k) - грамматики

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

Будем включать в левый контекст правила также аванцепочку. Если в правом выводе применяется вывод wAu: wvu, то пара wv,FIRSTk(u) принадлежит Lk(A:v), а пара w,FIRSTk(u) - Lk(A). Множество левых контекстов, как и в случае LR(0), можно вычислять с помощью индукции по левой цепочке. Назовем LR(k)-ситуацией пару: правило грамматики с отмеченной позицией и аванцепочку длины не более k. Отделять правило от аванцепочки будем вертикальной чертой.

Будем говорить, что цепочка x согласована с ситуацией А:b_c|t если существует LR-вывод: x_yz = ab_yz:: abc_z:: aA_z:: S_, и FIRSTk(z)=t. Правила индуктивного вычисления множества состояний Vk следующие:

Vk(e) содержит ситуации S:_a|e для всех правил S:a, где S-начальный символ. Для каждой ситуации А:_Ba|u из Vk(e), каждого правила B:b и цепочки x, принадлежащей FIRSTk(au), надо добавить в Vk(e) ситуацию B:_b|x.

Если в Vк(w) входит ситуация A:b_cd|u, то ситуация A:bc_d|u будет принадлежать Vk(wc). Для каждой ситуации А:b_Cd|u из Vk(wc), каждого правила C:f и цепочки x, принадлежащей FIRSTk(du) надо добавить в Vk(wc) ситуацию C:_f|x.

Используем построенные множества LR(k)-состояний для разрешения вопроса сдвиг-свертка. Пусть u - содержимое стека, а x - аванцепочка. Очевидно, что свертка по правилу A:b может быть проведена, если Vk(u) содержит ситуацию A:b_|x. Решение вопроса о допустимости сдвига требует аккуратности, если в грамматике имеются e-правила. В ситуации A:b_c|t (c не пусто) сдвиг возможен, если c начинается с терминала и x принадлежит FIRSTk(ct). Неформально говоря, можно занести в стек самый левый символ правой части правила, подготавливая последующую свертку. Если c начинается с нетерминала (ситуация имеет вид A:b_Cd|t), то занести в стек символ, подготавливая свертку в C, можно только в случае, если C не порождает пустую цепочку. Например, в состоянии V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a нет допустимых сдвигов, т.к. при выводе из A терминальных цепочек на некотором шаге требуется применить правило A:e к нетерминалу A, находящемуся на левом конце цепочки.

Определим множество EFFk(x), состоящее из всех элементов множества FIRSTk(x), при выводе которых нетерминал на левом конце x (если он есть) не заменяется на пустую цепочку. В этих терминах сдвиг допустим, если в множестве Vk(u) есть ситуация А:b_c|t, c не пусто и x принадлежит EFFk(ct).

Грамматика называется LR(k)-грамматикой, если ни одно LR(k) состояние не содержит двух ситуаций A:b_|u и B:c_d|v, таких что u принадлежит EFFk(dv). Такая пара соответствует конфликту свертка-свертка, если d пусто, и конфликту сдвиг-свертка, если d не пусто.

На практике LR(k)-грамматики при k>1 не применяются. На это имеются две причины. Первая: очень большое число LR(k) состояний. Вторая: для любого языка, определяемого LR(k)-грамматикой, существует LR(1)-грамматика; более того, для любого детерминированного КС-языка существует LR(1)-грамматика.

Число LR(1)-состояний для практически интересных грамматик также весьма велико. LR(0) свойством такие грамматики обладают редко. На практике чаще используется промежуточный между LR(0) и LR(1) метод, известный под названиями и LALR(1).

1.2.2 LALR(1) - грамматики

В основе этих двух методов лежит одна и та же идея. Построим множество канонических LR(0)-состояний грамматики. Если это множество не содержит конфликтов, то можно применить LR(0)-парсер. Иначе попытаемся разрешить возникшие конфликты, рассматривая односимвольную аванцепочку. Другими словами, попробуем построить LR(1) парсер с множеством LR(0)-состояний.

LALR(1)-метод (Look Ahead - заглядывание вперед) заключается в следующем. Введем на множестве LR(1)-ситуаций отношение эквивалентности: будем считать две ситуации эквивалентными, если они различаются только аванцепочками. Например, ситуации A:Aa_Ab|e и A:Aa_Ab|a эквивалентны. Построим каноническое множество LR(1)-состояний и объединим состояния, состоящие из множества эквивалентных ситуаций.

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

2. Разработка транслятора

2.1 Анализ требований

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

Проектирование лексического анализатора;

Проектирование магазинного автомата;

Программная реализация синтаксического анализатора;

Разработка модуля интерпретации.

Разработка будет проведена с использованием операционной системы Windows XP на персональном компьютере IBM PC с процессором Intel Pentium IV.

Исходя из тенденций развития программного обеспечения для реализации учебного транслятора выбран язык программирования С# в среде Visual Studio 2010.

2.2 Проектирование

2.1.1 Проектирование лексического анализатора

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

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

Лексема может описываться двумя основными признаками. Одним из них является принадлежность лексемы определенному классу (переменные, константы, операции и т. д.) Второй признак определяет конкретный элемент данного класса.

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

Просмотр таблицы идентификаторов выполняет две основные функции:

а) запись нового имени в таблицу при обработке описания переменных;

б) поиск имени, ранее записанного в таблицу.

Это позволяет выявлять такие ошибочные ситуации, как множественное описание переменной и наличие неописанной переменной.

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

Запуская лексический анализатор, мы разбиваем нашу программу на лексемы, после чего каждая лексемы проходит проверку длины (лексема не может быть больше 11 символов). Пройдя успешно этот этап, мы проверяем правильность расположения лексем (ключевых слов var, begin, end, for, to, do, end_for). Затем анализируем лексемы переменные - они не должны содержать цифр в своем описании и повторяться. На последнем этапе проверяем правильность написания лексем (ключевые слова, неизвестные идентификаторы). Если хотя бы одна из проверок выдает ошибку, лексический анализатор выводит ошибку.

Схема программы работы лексического анализатора приведена в приложении B на рисунке В.1.

2.2.2 Проектирование магазинного автомата

Зададим следующую грамматику:

Г: {Vt, Va, I, R},

где Vt - это множесто терминальных символов, Va - множество нетерминальных символов, I - начальное состояние грамматики, R - множество правил грамматики.

Для данной граматики зададим множества терминальных и нетерминальных символов:

Составим правила для нашей грамматики Г и приведем их в таблице 1.

Таблица 1 - Правила грамматики

№ правила	Левая часть правила	Правая часть правила
		f ID = EX t EX d LE n;
Продолжение таблицы 1.
№ правила	Левая часть правила	Правая часть правила

Обозначения лексем, перевод лексем в коды и список обозначений грамматики приведем в таблицах 2, 3, 4 соответственно.

Таблица 2 - Обозначения лексем

	Обозначение лексемы
	ключевое слово «begin» (начало описания действий)
	ключевое слово «end» (окончание описания действий)
	ключевое слово «var» (описание переменных)
	ключевое слово «read» (оператор ввода данных)
	ключевое слово «write» (оператор вывода данных)
	ключевое слово «for» (оператор цикла)
	ключевое слово «to»
	ключевое слово «do»
	ключевое слово «end_case» (окончание оператора цикла)
	тип переменных «целый»
	оперция сложение
	операция вычитания
	операция умножения
	разделительный символ «:»
	разделительный символ «;»
	разделительный символ «(»
	разделительный символ «)»
	разделительный символ «,»
	Обозначение лексемы
	разделительный символ «=»

Таблица 3 - Перевод лексем в коды

<цифра>
<буква>

Таблица 4 - Список обозначений грамматики

Обозначение	Пояснение
	Программа
	Описание вычислений
	Описание переменных
	Список переменных
	Оператор
	Присваивание
	Выражение
	Подвыражение
	Бинарные операции
	Унарные операции
	Список присваиваний
	Идентификатор
	Константа

Построим детерменированный восходящий распознаватель.

Рассмотрим следующие отношения, для того чтобы построить детерминированный восходящий распознаватель:

а)Если имеется символ группы В такой, что в некоторое правило грамматики входит цепочка АВ и существует символ хПЕРВ"(В), то будем считать, что между символами х и А определяются отношения х ПОСЛЕ А

б)Если в заданной грамматике имеетя правило В->бАб А,ВV a , б то между А и х определяется отношение А СВЕРТ х.

Вся наша грамматика остается прежней, то есть:

Г: {Vt, Va, I, R},

а правила грамматики Г приведены в таблице 5.

Таблица 5 - Правила грамматики

№ правила	Левая часть правила	Правая часть правила
		f ID = EX t EX d LE n;?
Продолжение таблицы 5.
№ правила	Левая часть правила	Правая часть правила

Где? - маркер конца цепочки.

Определим некоторые случаи:

а)Идентификатор ID состоит из множества букв латинского алфавита, то есть будем считать, что u = { a, b, c, d, e, f,g, h, i,j,k, l,m, n, o, p,q,r,s, t, u, v, w, x, y, z}

б) Константа СО состоит из цифр, то есть будем считать, что k = {0,1,2,3,4,5,6,7,8,9}

Для того, чтобы наша грамматика является смешанной стратегией предшествования, необходимо, чтобы выполнялись следующие условия:

а) Отсутствие е - правил

б) Имеются правила при которых, х ПОСЛЕ А? А СВЕРТ х = ?

в) А -> бYг

и необходимо, чтобы В ПОСЛЕ х? В СВЕРТ х = ?

т.е в грамматике будут выполняться В ПОСЛЕ х либо А ПОСЛЕ х, где х - символ -предикат цепочки б.

а) ПЕРВ"(PG)={PG?}

ПЕРВ"(RG) = ПЕРВ(DE) = {RG, v,:, i,;}

ПЕРВ" (AL) = ПЕРВ (b LE e)= {AL, b, e}

ПЕРВ" (DE) = ПЕРВ (v LV: i;) = {DE, v,:, i,;}

ПЕРВ" (LV) = ПЕРВ (ID, LV) = { LV, ID }

ПЕРВ" (OP) ={OP, ID, CO}

ПЕРВ" (EQ) = ПЕРВ(ID = EX;) = {EQ, =,;}

ПЕРВ" (EX) = {EX, SB, -}

ПЕРВ" (BO) ={B0, +,*,-}

ПЕРВ" (SB) =ПЕРВ((EX)SB) ? ПЕРВ(OP) ? ПЕРВ (ВО)={SB, (,), OP, BO};

ПЕРВ" (LE) = ПЕРВ(EQ) = {LE, (,), =,;, f, t, d, n, w, r}

ПЕРВ" (UO) = {UO,-}

ПЕРВ" (ID)= ПЕРВ" (u) = {u}

ПЕРВ" (CO) = ПЕРВ" (k) = {k}ПЕРВ" (e) ={ e}

ПЕРВ" (b) ={ b}

ПЕРВ" (e) ={ e}

ПЕРВ" (v) ={ v}

ПЕРВ" (w) ={ w}

ПЕРВ" (r) ={ r}

ПЕРВ" (i) ={ i}

ПЕРВ" (f) ={ f}

ПЕРВ" (d) ={d}

ПЕРВ" (n) ={ n}

ПЕРВ" (c) ={ c}

ПЕРВ" (+) ={ +}

ПЕРВ" (*) ={ *}

ПЕРВ" (-) ={ -}

ПЕРВ" (,) ={,}

ПЕРВ" (;) ={;}

ПЕРВ" (:) ={:}

ПЕРВ" (=) = { = }

ПЕРВ" (() ={ (}

ПЕРВ" ()) ={) }

ПЕРВ" (u) ={u}

ПЕРВ" (k) ={k}

б) СЛЕД `(AL) = {?}?СЛЕД"(PG)={?,b,e}

СЛЕД ` (DE) = {?}?ПЕРВ"(AL)= {?, b, e }

СЛЕД ` (LV) = {?}?ПЕРВ"(:)= {?,:}

СЛЕД ` (OP) = {?}?ПЕРВ"(SB)= {?,;,), d, t, +, -, *}

СЛЕД ` (EQ) = {?}?ПЕРВ"(LE)={?, (,),;, f, =, t, d, n,w,r }

СЛЕД ` (EX) = {?}?ПЕРВ"(t)?ПЕРВ"(d)?ПЕРВ"(;)?ПЕРВ"())={?, t,d,;,)}

СЛЕД ` (BO) = {?}?ПЕРВ"(SB)= {?, (,), OP, BO}

СЛЕД ` (UO) = {?}?ПЕРВ"(SB)= {?, (,), OP, BO}

СЛЕД ` (SB) = {?}?СЛЕД"(EX)= {?, t,d,;,), +, *, -}

СЛЕД ` (LE) = {?} ?ПЕРВ"(e) ?ПЕРВ"(n) = {?, e, n}

СЛЕД `(ID)= {?}? СЛЕД" (OP) ? ПЕРВ" (=) ={?,;,), d, t, +, -, *, =}

СЛЕД `(CO) = {?}? СЛЕД" (OP)= {?,;,), d, t, +, -, *, =}

СЛЕД ` (b) ={?}?ПЕРВ"(LE)= {?, u, =,;}

СЛЕД ` (e) ={?}?СЛЕД"(AL)= {?, b}

СЛЕД ` (v) ={?}?ПЕРВ"(LV)= {?, u }

СЛЕД ` (w) ={?}?ПЕРВ"(()= {?, (}

СЛЕД ` (r) ={?}?ПЕРВ"(() = {?, (}

СЛЕД ` (i) ={?}?ПЕРВ"(;)= {?,; }

СЛЕД ` (f) ={?}?ПЕРВ"(ID) = {?, u}

СЛЕД ` (d) ={?}?ПЕРВ"(LE)= {?, u, =,;}

СЛЕД ` (n) ={?}?ПЕРВ"(i) = {?, i }

СЛЕД ` (+) ={?}?СЛЕД"(ВО) = {?, +,*,-}

СЛЕД ` (-) ={?}?СЛЕД"(ВО) = {?, +,*,-}

СЛЕД ` (*) ={?}?СЛЕД"(ВО) = {?, +,*,-}

СЛЕД ` (;) ={?}?СЛЕД" (DE)?СЛЕД `(LE1)?СЛЕД" (EQ) = {?, b, e, l, u }

СЛЕД ` (:) ={?}?ПЕРВ"(i)= {?, i }

СЛЕД ` (=) = {?}?ПЕРВ"(EX) = {? (,), u, k, +, -, *}

СЛЕД ` (() ={?}?ПЕРВ"(DE)= {?, v,:, i,;}

СЛЕД ` ()) ={?}? ПЕРВ"(;) = {?,; }

СЛЕД ` (,) ={?}? ПЕРВ"(LV) = {?, u }

СЛЕД `(u) ={?}? ПЕРВ" (ID)= { u, ?}

СЛЕД `(k) ={?}? ПЕРВ (CO)= {?, k}

в) PG ->DE AL

AL ПОСЛЕ DE = {b,e} ПОСЛЕ DE = {(b DE), (e DE) }

e ПОСЛЕ LE = {(e LE)}

LE ПОСЛЕ b = {(,), =,;, f, t, d, n, w, r} ПОСЛЕ b = {((b), ()b), (=b), (;b), (f b), (t b), (d b), (n b), (w b), (r b)}

;ПОСЛЕ i = {(; i)}

i ПОСЛЕ: = { (i:) }

: ПОСЛЕ LV = { (: LV) }

LV ПОСЛЕ v = { (ID, v) }

LV ПОСЛЕ, = {(ID,)}

ПОСЛЕ ID = {(,u)}

LE ПОСЛЕ EQ = {(,), =,;, f, t, d, n, w, r } ПОСЛЕ EQ = {((EQ), () EQ), (= EQ), (; EQ), (f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ)}

LE -> r (DE);

; ПОСЛЕ) = {(;))}

) ПОСЛЕ DE = {((DE)}

DE ПОСЛЕ (= (= {(v)), (:)), (i)), (;)), (e))}

(ПОСЛЕ r = {((r)}

LE -> w (DE);

; ПОСЛЕ) = {(;))}

) ПОСЛ DE = {((DE)}

DE ПОСЛЕ (= {(v)), (:)), (i)), (;)), (e))}

(ПОСЛЕ w = {((w)}

LE -> f ID = EX t EX d LE n;

; ПОСЛЕ n = {(;n)}

n ПОСЛЕ LE = { (n, LE)}

LE ПОСЛЕ d = { ((,), =,;, f, t, d, n, w, r)} ? ПОСЛЕ d = {((d), ()d), (;d), (f d), (t d), (d d), (n d), (w d), (r d)}

d ПОСЛЕ EX = {(d, EX)}

EX ПОСЛЕ t = (BO, -) ? ПОСЛЕ t = {(BO t), (- t)}

t ПОСЛЕ EX = { t EX}

EX ПОСЛЕ = = {(BO, -) ? ПОСЛЕ = = {(BO =), (- =)}

ПОСЛЕ ID = {(= ID)}

ID ПОСЛЕ f = {(ID f)}

EQ -> ID = EX;

; ПОСЛЕ EX = {(; EX }

EX ПОСЛЕ = = (BO, -) ? ПОСЛЕ = = {(BO =), (- =)}

ПОСЛЕ u = { (=u)}

SB ПОСЛЕ UO = { (,), OP, BO } ПОСЛЕ UO = {((UO), (OP UO), (BO UO) }

) ПОСЛЕ EX = { ()EX) }

EX ПОСЛЕ (= (BO, -) ? ПОСЛЕ (= {(BO (), (- ()}

SB-> SB BO SB

SB ПОСЛЕ BO = ((,), OP, BO) ПОСЛЕ BO = {((BO), ()BO), (OP BO), (BO BO)}

BO ПОСЛЕ SB = {+,*,-} ПОСЛЕ SB = {(+SB), (*SB), (-SB)}

ID ПОСЛЕ u = {(u, u)}

г) PG ->DE AL

AL СВЕРТ PG = AL СВЕРТ СЛЕД" (PG) = {(AL ?)}

e СВЕРТ AL = e СВЕРТ СЛЕД"(AL)= {(eb), (e?)}

=; СВЕРТ СЛЕД"(DE) = {(;b), (;?)}

LV СВЕРТ LV = LV СВЕРТ СЛЕД" (LV) = {(LV:), (LV?)}

ID СВЕРТ LV = ID СВЕРТ СЛЕД" (LV) = {(ID:), (ID ?)}

; СВЕРТ LE =; СВЕРТ СЛЕД" (LE) = {(; e), (;?), (;n)}

LE -> f ID = EX t EX d LE n;

; СВЕРТ LE =; СВЕРТ СЛЕД" (LE) = {(; e), (;?), (;n)}

EQ СВЕРТ LE = EQ СВЕРТ СЛЕД" (LE) = {(EQ e), (EQ?), (EQ n)}

EQ -> ID = EX;

; СВЕРТ EQ =; СВЕРТ СЛЕД" (EQ) = {(; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (;n), (;w), (;r)}

SB СВЕРТ EX = SB СВЕРТ СЛЕД" (EX) = {(SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf), (SBn), (SBw), (SBr) }

) СВЕРТ SB = SB СВЕРТ СЛЕД" (SB) = {() t), ()?), () d), ())), ();)}

OP СВЕРТ SB = OP СВЕРТ СЛЕД" (SB) = {(OP t), (OP ?), (OP d), (OP)), (OP;)}

SB-> SB BO SB

SB СВЕРТ SB = SB СВЕРТ СЛЕД" (SB) = {(SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB?) }

СВЕРТ UO = - СВЕРТ СЛЕД" (UO) = { (-?), (--)}

СВЕРТ BO = + СВЕРТ СЛЕД" (BO) = {(++), (+?), (+*), (+-)}

* СВЕРТ BO = * СВЕРТ СЛЕД" (BO) = {(*+), (*?), (**), (*-)}

СВЕРТ BO = - СВЕРТ СЛЕД" (BO) = {(-+), (-?), (-*), (--)}

ID СВЕРТ OP = ID СВЕРТ СЛЕД" (OP) = {(ID+), (ID?), (ID*), (ID-)}

CO СВЕРТ OP = CO СВЕРТ СЛЕД" (OP) = {(CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO))}

ID СВЕРТ ID = ID СВЕРТ СЛЕД" (ID) = {(ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt), (IDd))}

u СВЕРТ ID = l СВЕРТ СЛЕД" (ID) = {(u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud))}

CO СВЕРТ CO = CO СВЕРТ СЛЕД" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO))}

k СВЕРТ CO = k СВЕРТ СЛЕД" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k))}

Обнаружена одна конфликтная ситуация при сворачивании правил

OP ->ID и ID -> u ID

Вводим ID1 -> ID, следовательно переписываем правило ID1 -> u ID

Следовательно, проведем операции свертка.

ID1 СВЕРТ ID = ID1 СВЕРТ СЛЕД" (ID) = {(ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t), (ID1d))}

Для каждой пары (х, А)? х ПОСЛЕ А строим функцию перехода, определяющее действие перенос??(S 0 , x, A) = (S 0 , A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (S0, b;)

? (S0, (, b) = (S0, b()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, bn)

? (S0, w, b) = (S0, bw)

? (S0, r, b) = (S0, br)

? (S0,;, i) = (S0, i;)

? (S0, i,:) = (S0, i:)

? (S0,: LV) = (S0, LV:)

? (S0, ID, v) = (S0, vID)

? (S0, ID,) = (S0,ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ)= (S0, EQ()

? (S0,), EQ)= (S0, EQ))

? (S0, =, EQ)= (S0, EQ=)

? (S0,;, EQ)= (S0, EQ;)

? (S0, f, EQ)= (S0, EQf)

? (S0, t, EQ)= (S0, EQt)

? (S0, d, EQ)= (S0, EQd)

? (S0, n, EQ)= (S0, EQn)

? (S0, w, EQ)= (S0, EQw)

? (S0, r, EQ)= (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE()

? (S0, v,)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0, i,)) = (S0,)i)

? (S0,:,)) = (S0,):)

? (S0, e,)) = (S0,)e)

? (S0, (, r) = (S0, r()

? (S0, (, w) = (S0, w()

? (S0,;, n) = (S0, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d()

? (S0,), d) = (S0, d))

? (S0,;, d) = (S0, d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, =BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u=)

? (S0, (, UO) = (S0, UO()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO)

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO()

? (S0,), BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB*)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Для каждой пары (х,А)? А СВЕРТ х строим функцию перехода, определяющее действие свертка?? * (S 0 , x, бA) = (S 0 , В), где В->бA

? * (S 0 , AL, ?) = (S 0 , PG)

? * (S 0 , e, b) = (S 0 , AL)

? * (S 0 , n, ?) = (S 0 , AL)

? * (S 0 ,;, b) = (S 0 , DE)

? * (S 0 ,;, ?) = (S 0 , DE)

? * (S 0 ,;, e) = (S 0 , DE)

? * (S 0 , LV,:) = (S 0 , LV)

? * (S 0 , LV, ?) = (S 0 , LV)

? * (S 0 , ID, ?) = (S 0 , LV)

? * (S 0 , ID, e) = (S 0 , LV)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, n) = (S 0 , LE)

? * (S 0 , EQ, n) = (S 0 , LE)

? * (S 0 , EQ, e) = (S 0 , LE)

? * (S 0 , EQ, ?) = (S 0 , LE)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, () = (S 0 , EQ)

? * (S 0 ,;,)) = (S 0 , EQ)

? * (S 0 ,;, f) = (S 0 , EQ)

? * (S 0 ,;, =) = (S 0 , EQ)

? * (S 0 ,;, t) = (S 0 , EQ)

? * (S 0 ,;, d) = (S 0 , EQ)

? * (S 0 ,;, n) = (S 0 , EQ)

? * (S 0 ,;, w) = (S 0 , EQ)

? * (S 0 ,;, r) = (S 0 , EQ)

? * (S 0 , SB, ?) = (S 0 , EX)

? * (S 0 , SB, d) = (S 0 , EX)

? * (S 0 , SB,)) = (S 0 , EX)

? * (S 0 , SB,;) = (S 0 , EX)

? * (S 0 , SB, w) = (S 0 , EX)

? * (S 0 , SB, r) = (S 0 , EX)

? * (S 0 , SB, f) = (S 0 , EX)

? * (S 0 , SB, =) = (S 0 , EX)

? * (S 0 , SB, t) = (S 0 , EX)

? * (S 0 , SB, ?) = (S 0 , SB)

? * (S 0 , SB, () = (S 0 , SB)

? * (S 0 , SB,)) = (S 0 , SB)

? * (S 0 , SB, u) = (S 0 , SB)

? * (S 0 , SB, k) = (S 0 , SB)

? * (S 0 , SB, +) = (S 0 , SB)

? * (S 0 , SB, -) = (S 0 , SB)

? * (S 0 , SB, *) = (S 0 , SB)

? * (S 0 , SB, e) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

? * (S 0 ,), ?) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

(S 0 ,),)) = (S 0 , SB)

? * (S 0 ,),;) = (S 0 , SB)

? * (S 0 , -, ?) = (S 0 , UO)

? * (S 0 , -, -) = (S 0 , UO)

? * (S 0 , +, +) = (S 0 , BO)

? * (S 0 , +, ?) = (S 0 , BO)

? * (S 0 , +, *) = (S 0 , BO)

? * (S 0 , -, +) = (S 0 , BO)

? * (S 0 , -, ?) = (S 0 , BO)

? * (S 0 , -, *) = (S 0 , BO)

? * (S 0 , -, -)) = (S 0 , BO)

? * (S 0 , *, +) = (S 0 , BO)

? * (S 0 , *, ?) = (S 0 , BO)

? * (S 0 , *, *) = (S 0 , BO)

? * (S 0 , *, -)) = (S 0 , BO)

? * (S 0 , u, +) = (S 0 , BO)

? * (S 0 , u, ?)= (S 0 , BO)

? * (S 0 , u, *) = (S 0 , BO)

? * (S 0 , u, -)) = (S 0 , BO)

? * (S 0 , k, +) = (S 0 , BO)

? * (S 0 , k, ?) = (S 0 , BO)

? * (S 0 , k, *) = (S 0 , BO)

? * (S 0 , k, -)) = (S 0 , BO)

? * (S 0 , CO, ?) = (S 0 , OP)

? * (S 0 , CO, +) = (S 0 , OP)

? * (S 0 , CO, *) = (S 0 , OP)

? * (S 0 , CO, -) = (S 0 , OP)

? * (S 0 , CO,;) = (S 0 , OP)

? * (S 0 , CO, d) = (S 0 , OP)

? * (S 0 , CO, t) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, *) = (S 0 , OP)

? * (S 0 , ID, ?) = (S 0 , OP)

? * (S 0 , ID, () = (S 0 , OP)

? * (S 0 , ID,)) = (S 0 , OP)

? * (S 0 , ID, u) = (S 0 , OP)

? * (S 0 , ID, k) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, +) = (S 0 , OP)

? * (S 0 , u,)) = (S 0 , I OP)

? * (S 0 , ID1, *) = (S 0 , ID)

? * (S 0 , ID1, ?) = (S 0 , ID)

? * (S 0 , ID1, () = (S 0 , ID)

? * (S 0 , ID1,)) = (S 0 , ID)

? * (S 0 , ID1, u) = (S 0 , ID)

? * (S 0 , ID1, k) = (S 0 , ID)

? * (S 0 , ID1, -) = (S 0 , ID)

? * (S 0 , ID1, +) = (S 0 , ID)

? * (S 0 , u,)) = (S 0 , ID)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, k) = (S 0 , ID)

? * (S 0 , u, *)) = (S 0 , ID)

? * (S 0 , u, -)) = (S 0 , ID)

? * (S 0 , u, +)) = (S 0 , ID)

? * (S 0 , u, d)) = (S 0 , ID)

? * (S 0 , u, t)) = (S 0 , ID)

? * (S 0 , u, =)) = (S 0 , ID)

? * (S 0 , CO, ?) = (S 0 , CO)

? * (S 0 , CO, +) = (S 0 , CO)

? * (S 0 , CO, -) = (S 0 , CO)

? * (S 0 , CO, *) = (S 0 , CO)

? * (S 0 , CO,;) = (S 0 , CO)

? * (S 0 , CO, d) = (S 0 , CO)

? * (S 0 , CO, t) = (S 0 , CO)

? * (S 0 , CO,)) = (S 0 , CO)

? * (S 0 , k, +) = (S 0 , CO)

? * (S 0 , k, -) = (S 0 , CO)

? * (S 0 , k, *) = (S 0 , CO)

? * (S 0 , k,;) = (S 0 , CO)

?? * (S 0 , k, d) = (S 0 , CO)

? * (S 0 , k, t) = (S 0 , CO)

? * (S 0 , k,)) = (S 0 , CO)

? * (S 0 , k, () = (S 0 , CO)

2.2.3 Программная реализация синтаксического анализатора

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

Для восходящего грамматического разбора для детерминированного восходящего распознавателя после приведения ее к нужному виду требуется с использованием функций ПОСЛЕ и СВЕРТ спроектировать магазинный автомат с подробным описанием всех переходов в рамках функции переходов.

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

Такт работы магазинного автомата без чтения входного символа (пустой такт);

Такт работы магазинного автомата с чтением входного символа.

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

Схема программы работы синтаксического анализатора приведена в приложении B на рисунке В.2.

2.2.4 Разработка модуля интерпретации

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

Рассмотрим основные принципы формирования и выполнения постфиксной формы записи выражений.

Основные правила преобразования инфиксной записи выражения в постфиксную заключаются в следующем.

Считанные операнды добавляются к постфиксной записи, операции записываются в стек.

Если операция в вершине стека имеет больший (или равный) приоритет, чем текущая считанная операция, то операция из стека добавляется к постфиксной записи, а текущая операция заносится в стек. В противном случае (при низшем приоритете) происходит только занесение текущей операции в стек.

Считанная открывающая скобка заносится в стек.

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

После считывания всего выражения, оставшиеся в стеке операции добавляются к постфиксной записи.

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

Если лексема является операндом, то она записывается в стек. Если лексема является операцией, то указанная операция выполняется над последними элементами (последним элементом), записанными в стек, и эти элементы (элемент) заменяются в стеке результатом операции.

Если успешно прошли лексический и синтаксический анализы, то мы приступаем к интерпретации. Сначала делаем из слов предложения, затем переводим выражения в постфиксную запись и вычисляем.

Схема работы интерпретатора приведена в приложении B на рисунке В.3.

2.3 Кодирование

Программа реализована на языке C# в среде программирования Visual Studio 2010. Текст программы представлен в приложении А.

В программе реализованно пять классов. С помощью класса MainForn реальзован пользовательский интерфейс. C помощью класса LexAnalysis реализован модуль лексического анализа, SynAnalysis - модуль синтаксического анализа, Intepreter - модуль интерпретации, ProgramisciJakPolska - вспомогательный класс перевода выражений в обратную польскую запись (постфиксную).

Назначение процедур и функций, реализованных в программе, описано в таблицах 6,7,8.

Таблица 6 - Назначение процедур и функций лексического анализа

Подобные документы

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

курсовая работа , добавлен 06.08.2013


Проектирование лексического и синтаксического анализаторов учебного языка. Правила преобразования логических выражений в ПОЛИЗ. Формирование триад, оптимизация их списка. Логическая структура программы. Тестирование модулей транслятора-интерпретатора.

курсовая работа , добавлен 28.05.2013


Общая характеристика и оценка возможностей языка программирования си-шарп, его сходные и отличительные черты от С++ и Java. Разработка с помощью данного языка программирования лексического и синтаксического анализатора. Составление таблиц разбора.

курсовая работа , добавлен 11.06.2010


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

курсовая работа , добавлен 14.06.2010


Написание программы, которая выполняет лексический и синтаксический анализ входного языка программирования, порождает таблицу лексем с указанием их типов и значений, а также строит синтаксическое дерево; текст входного языка вводится с клавиатуры.

курсовая работа , добавлен 23.02.2012


Методика разработки и частичная реализация транслятора для языка "С" с использованием языка "С++", производящего разбиение на минимальные неделимые конструкции языка исходной цепочки символов основываясь на лексике языка. Анализ работы программы.

курсовая работа , добавлен 19.03.2012


Структура, классификация и требования к реализации компилятора. Проектирование и реализация анализирующей части компилятора языка С++. Способы реализации лексического анализа. Алгоритм работы синтаксического анализатора. Принципы программной реализации.

курсовая работа , добавлен 26.01.2013


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

курсовая работа , добавлен 02.07.2011


Методы грамматического разбора. Разработка структуры учебного транслятора на базовом языке программирования Object Pascal в среде объектно-ориентированного визуального программирования Borland DELPHI 6.0 с использованием операционной системы Windows XP.

курсовая работа , добавлен 12.05.2013


Программная реализация настольного приложения с использованием языка программирования C#. Проектирование и структура пользовательского интерфейса, требования к нему и оценка функциональности. Разработка руководства пользователя и его использование.

• Адресный . Функциональное устройство, преобразующее виртуальный адрес (англ. Virtual address) в реальный адрес.
• Диалоговый . Обеспечивает использование языка программирования в режиме разделения времени.
• Многопроходной . Формирует объектный модуль за несколько просмотров исходной программы.
• Обратный . То же, что детранслятор. См. также: декомпилятор, дизассемблер.
• Однопроходной . Формирует объектный модуль за один последовательный просмотр исходной программы.
• Оптимизирующий . Выполняет оптимизацию кода в создаваемом объектном модуле.
• Синтаксически-ориентированный (синтаксически-управляемый). Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.
• Тестовый . Набор макрокоманд языка ассемблера, позволяющих задавать различные отладочные процедуры в программах, составленных на языке ассемблера.

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

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

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

Достоинство компилятора: программа компилируется один раз и при каждом выполнении не требуется дополнительных преобразований. Соответственно, не требуется наличие компилятора на целевой машине, для которой компилируется программа. Недостаток: отдельный этап компиляции замедляет написание и отладку и затрудняет исполнение небольших, несложных или разовых программ.

Другой метод реализации - когда программа исполняется с помощью интерпретатора вообще без трансляции. Интерпретатор программно моделирует машину, цикл выборки-исполнения которой работает с командами на языках высокого уровня, а не с машинными командами. Такое программное моделирование создаёт виртуальную машину, реализующую язык. Этот подход называется чистой интерпретацией. Чистая интерпретация применяется как правило для языков с простой структурой (например, АПЛ или Лисп). Интерпретаторы командной строки обрабатывают команды в скриптах в UNIX или в пакетных файлах (.bat) в MS-DOS также как правило в режиме чистой интерпретации.

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

Существуют компромиссные между компиляцией и чистой интерпретацией варианты реализации языков программирования, когда интерпретатор перед исполнением программы транслирует её на промежуточный язык (например, в байт-код или p-код), более удобный для интерпретации (то есть речь идёт об интерпретаторе со встроенным транслятором). Такой метод называется смешанной реализацией. Примером смешанной реализации языка может служить Perl. Этот подход сочетает как достоинства компилятора и интерпретатора (большая скорость исполнения и удобство использования), так и недостатки (для трансляции и хранения программы на промежуточном языке требуются дополнительные ресурсы; для исполнения программы на целевой машине должен быть представлен интерпретатор). Также, как и в случае компилятора, смешанная реализация требует, чтобы перед исполнением исходный код не содержал ошибок (лексических, синтаксических и семантических).

Трансляция и интерпретация - разные процессы: трансляция занимается переводом программ с одного языка на другой, а интерпретация отвечает за исполнение программ. Однако, поскольку целью трансляции как правило является подготовка программы к интерпретации, то эти процессы обычно рассматриваются вместе. Например, языки программирования часто характеризуются как «компилируемые» или «интерпретируемые», в зависимости от того, преобладает при использовании языка компиляция или интерпретация. Причём практически все языки программирования низкого уровня и третьего поколения, вроде ассемблера, Си или Модулы-2, являются компилируемыми, а более высокоуровневые языки, вроде Python или SQL, - интерпретируемыми.

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

Более того, один и тот же язык программирования может и транслироваться, и интерпретироваться, и в обоих случаях должны присутствовать общие этапы анализа и распознавания конструкций и директив исходного языка. Это относится и к программным реализациям, и к аппаратным - так, процессоры семейства x86 перед исполнением инструкций машинного языка выполняют их декодирование, выделяя в опкодах поля операндов (регистров, адресов памяти, непосредственных значений), разрядности и т. п., а в процессорах Pentium с архитектурой NetBurst машинный код перед сохранением во внутреннем кэше вообще транслируется в последовательность микроопераций.

Цели и задачи дисциплины. Основные понятия и определения. Общие особенности языков программирования и трансляторов. Обобщенная структура транслятора. Варианты взаимодействия блоков транслятора.

Цели и задачи дисциплины

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

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

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

Цель дисциплины: предоставить знания по основам теории языков и формальных грамматик, теории автоматов, методам разработки трансляторов.

Для достижения поставленной цели в ходе преподавания дисциплины решаются следующие задачи:

1. В ходе лекционного курса рассматриваются общие принципы организации процесса трансляции и структуры трансляторов. Изучаются основы теории построения трансляторов.
2. На лабораторных занятиях и в ходе самостоятельной работы осуществляется практическое закрепление полученных теоретических знаний: разрабатывается транслятор для простого языка программирования.

Основные понятия и определения

Большинство рассматриваемых определений заимствовано из [АРНФТСАнгло-русско-немецко-французский толковый словарь по вычислительной технике и обработке данных, 4132 термина. Под. ред. А.А. Дородницына. М.: 1978. 416 с.) ].

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

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

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

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

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

Интерпретатор - программа или устройство, осуществляющее пооператорную трансляцию и выполнение исходной программы . В отличие от компилятора, интерпретатор не порождает на выходе программу на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. Как в компиляторах, так и в интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды. Это делает процесс разработки и отладки программ более гибким. Кроме того, отсутствие выходного машинного кода позволяет не "захламлять" внешние устройства дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любым машинным архитектурам, разработав его только один раз на широко распространенном языке программирования. Поэтому, интерпретируемые языки, типа Java Script, VB Script, получили широкое распространение. Недостатком интерпретаторов является низкая скорость выполнения программ. Обычно интерпретируемые программы выполняются в 50-100 раз медленнее программ, написанных в машинных кодах.

Эмулятор - программа или программно-техническое средство, обеспечивающее возможность без перепрограммирования выполнять на данной ЭВМ программу, использующую коды или способы выполнения операция, отличные от данной ЭВМ . Эмулятор похож на интерпретатор тем, что непосредственно исполняет программу, написанную на некотором языке. Однако, чаще всего это машинный язык или промежуточный код. И тот и другой представляют команды в двоичном коде, которые могут сразу исполняться после распознавания кода операций. В отличие от текстовых программ, не требуется распознавать структуру программы, выделять операнды.

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

Очень часто эмулятор используется для выполнения старых программ на новых вычислительных машинах. Обычно новые компьютеры обладают более высоким быстродействием и имеют более качественное периферийное оборудование. Это позволяет эмулировать старые программы более эффективно по сравнению с их выполнением на старых компьютерах. Примером такого подхода является разработка эмуляторов домашнего компьютера ZX Spectrum с микропроцессором Z80. До сих пор находятся любители поиграть на эмуляторе в устаревшие, но все еще не утратившие былой привлекательности, игровые программы. Эмулятор может также использоваться как более дешевый аналог современных компьютерных систем, обеспечивая при этом приемлемую производительность, эквивалентную младшим моделям некоторого семейства архитектур. В качестве примера можно привести эмуляторы IBM PC совместимых компьютеров, реализованные на более мощных компьютерах фирмы Apple. Ряд эмуляторов, написанных для IBM PC, с успехом заменяют различные игровые приставки.

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

Перекодировщик - программа или программное устройство, переводящие программы, написанные на машинном языке одной ЭВМ в программы на машинном языке другой ЭВМ . Если эмулятор является менее интеллектуальным аналогом интерпретатора, то перекодировщик выступает в том же качестве по отношению к компилятору. Точно также исходный (и обычно двоичный) машинный код или промежуточное представление преобразуются в другой аналогичный код по одной команде и без какого-либо общего анализа структуры исходной программы. Перекодировщики бывают полезны при переносе программ с одних компьютерных архитектур на другие. Они могут также использоваться для восстановления текста программы на языке высокого уровня по имеющемуся двоичному коду.

Макропроцессор - программа, обеспечивающая замену одной последовательности символов другой [Браун ]. Это разновидность компилятора. Он осуществляет генерацию выходного текста путем обработки специальных вставок, располагаемых в исходном тексте. Эти вставки оформляются специальным образом и принадлежат конструкциям языка, называемого макроязыком. Макропроцессоры часто используются как надстройки над языками программирования, увеличивая функциональные возможности систем программирования. Практически любой ассемблер содержит макропроцессор, что повышает эффективность разработки машинных программ. Такие системы программирования обычно называются макроассемблерами.

Макропроцессоры используются и с языками высокого уровня. Они увеличивают функциональные возможности таких языков как PL/1, C, C++. Особенно широко макропроцессоры применяются в C и C++, позволяя упростить написание программ. Примером широкого использования макропроцессоров является библиотека классов Microsoft Foundation Classes (MFC). Через макровставки в ней реализованы карты сообщений и другие программные объекты. При этом, макропроцессоры повышают эффективность программирования без изменения синтаксиса и семантики языка.

Синтаксис - совокупность правил некоторого языка, определяющих формирование его элементов. Иначе говоря, это совокупность правил образования семантически значимых последовательностей символов в данном языке . Синтаксис задается с помощью правил, которые описывают понятия некоторого языка. Примерами понятий являются: переменная, выражение, оператор, процедура. Последовательность понятий и их допустимое использование в правилах определяет синтаксически правильные структуры, образующие программы. Именно иерархия объектов, а не то, как они взаимодействуют между собой, определяются через синтаксис. Например, оператор может встречаться только в процедуре, а выражение в операторе, переменная может состоять из имени и необязательных индексов и т.д. Синтаксис не связан с такими явлениями в программе как "переход на несуществующую метку" или "переменная с данным именем не определена". Этим занимается семантика.

Семантика - правила и условия, определяющие соотношения между элементами языка и их смысловыми значениями, а также интерпретацию содержательного значения синтаксических конструкций языка . Объекты языка программирования не только размещаются в тексте в соответствии с некоторой иерархией, но и дополнительно связаны между собой посредством других понятий, образующих разнообразные ассоциации. Например, переменная, для которой синтаксис определяет допустимое местоположение только в описаниях и некоторых операторах, обладает определенным типом, может использоваться с ограниченным множеством операций, имеет адрес, размер и должна быть описана до того, как будет использоваться в программе.

Синтаксический анализатор - компонента компилятора, осуществляющая проверку исходных операторов на соответствие синтаксическим правилам и семантике данного языка программирования . Несмотря на название, анализатор занимается проверкой и синтаксиса, и семантики. Он состоит из нескольких блоков, каждый из которых решает свои задачи. Более подробно будет рассмотрен при описании структуры транслятора.

Общие особенности языков программирования и трансляторов

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

Языки программирования являются инструментами для решения задач в разных предметных областях, что определяет специфику их организации и различия по назначению. В качестве примера можно привести такие языки как Фортран, ориентированный на научные расчеты, C, предназначенный для системного программирования, Пролог, эффективно описывающий задачи логического вывода, Лисп, используемый для рекурсивной обработки списков. Эти примеры можно продолжить. Каждая из предметных областей предъявляет свои требования к организации самого языка. Поэтому можно отметить разнообразие форм представления операторов и выражений, различие в наборе базовых операций, снижение эффективности программирования при решении задач, не связанных с предметной областью. Языковые различия отражаются и в структуре трансляторов. Лисп и Пролог чаще всего выполняются в режиме интерпретации из-за того, что используют динамическое формирование типов данных в ходе вычислений. Для трансляторов с языка Фортран характерна агрессивная оптимизация результирующего машинного кода, которая становится возможной благодаря относительно простой семантике конструкций языка - в частности, благодаря отсутствию механизмов альтернативного именования переменных через указатели или ссылки. Наличие же указателей в языке C предъявляет специфические требования к динамическому распределению памяти.

Структура языка характеризует иерархические отношения между его понятиями, которые описываются синтаксическими правилами. Языки программирования могут сильно отличаться друг от друга по организации отдельных понятий и по отношениям между ними. Язык программирования PL/1 допускает произвольное вложение процедур и функций, тогда как в C все функции должны находиться на внешнем уровне вложенности. Язык C++ допускает описание переменных в любой точке программы перед первым ее использованием, а в Паскале переменные должны быть определены в специальной области описания. Еще дальше в этом вопросе идет PL/1, который допускает описание переменной после ее использования. Или описание можно вообще опустить и руководствоваться правилами, принятыми по умолчанию. В зависимости от принятого решения, транслятор может анализировать программу за один или несколько проходов, что влияет на скорость трансляции.

Семантика языков программирования изменяется в очень широких пределах. Они отличаются не только по особенностям реализации отдельных операций, но и по парадигмам программирования, определяющим принципиальные различия в методах разработки программ. Специфика реализации операций может касаться как структуры обрабатываемых данных, так и правил обработки одних и тех же типов данных. Такие языки, как PL/1 и APL поддерживают выполнение матричных и векторных операций. Большинство же языков работают в основном со скалярами, предоставляя для обработки массивов процедуры и функции, написанные программистами. Но даже при выполнении операции сложения двух целых чисел такие языки, как C и Паскаль могут вести себя по-разному.

Наряду с традиционным процедурным программированием, называемым также императивным, существуют такие парадигмы как функциональное программирование, логическое программирование и объектно-ориентированное программирование. Надеюсь, что в этом ряду займет свое место и предложенная мною процедурно-параметрическая парадигма программирования [Легалов2000 ]. Структура понятий и объектов языков сильно зависит от избранной парадигмы, что также влияет на реализацию транслятора.

Даже один и тот же язык может быть реализован нескольким способами. Это связано с тем, что теория формальных грамматик допускает различные методы разбора одних и тех же предложений. В соответствии с этим трансляторы разными способами могут получать один и тот же результат (объектную программу) по первоначальному исходному тексту.

Вместе с тем, все языки программирования обладают рядом общих характеристик и параметров. Эта общность определяет и схожие для всех языков принципы организации трансляторов.

1. Языки программирования предназначены для облегчения программирования. Поэтому их операторы и структуры данных более мощные, чем в машинных языках.
2. Для повышения наглядности программ вместо числовых кодов используются символические или графические представления конструкций языка, более удобные для их восприятия человеком.
3. Для любого языка определяется:

• Множество символов, которые можно использовать для записи правильных программ (алфавит), основные элементы.
• Множество правильных программ (синтаксис).
• "Смысл" каждой правильной программы (семантика).

Независимо от специфики языка любой транслятор можно считать функциональным преобразователем F, обеспечивающим однозначное отображение X в Y, где X - программа на исходном языке, Y - программа на выходном языке. Поэтому сам процесс трансляции формально можно представить достаточно просто и понятно:

Формально каждая правильная программа X - это цепочка символов из некоторого алфавита A, преобразуемая в соответствующую ей цепочку Y, составленную из символов алфавита B.

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

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

Связь структуры программы с языком программирования называется синтаксическим отображением .

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

В большинстве языков программирования данное выражение определяет иерархию программных объектов, которую можно отобразить в виде дерева (рис. 1.1.):

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

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>

<множитель> ::= <буква> | (<выражение>)

<буква>

Примечание. Знак "::=" читается как "это есть". Вертикальная черта "|" читается как "или".

Если правила будут записаны иначе, то изменится и иерархическая структура. В качестве примера можно привести следующие способ записи правил:

<выражение> ::= <операнд> | <выражение> + < операнд > | <выражение> * < операнд >

<операнд> ::= <буква> | (<выражение>)

<буква> ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

В результате синтаксического разбора того же арифметического выражения будет построена иерархическая структура, представленная на рис. 1.2.

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

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

Синтаксическая структура, правильная для одного языка, может быть ошибочной для другого. Например, в языке Форт приведенной выражение не будет распознано. Однако для этого языка корректным будет являться постфиксное выражение:

Его синтаксическая структура описывается правилами:

<выражение> ::= <буква> | <операнд> <операнд> <операция>

< операнд > ::= < буква > | < выражение >

< операция > ::= + | *

<буква> ::= a | b | c | d | i | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Иерархическое дерево, определяющее синтаксическую структуру, представлено на рис. 1.3.

Другой характерной особенностью всех языков является их семантика. Она определяет смысл операций языка, корректность операндов. Цепочки, имеющие одинаковую синтаксическую структуру в различных языках программирования, могут различаться по семантике (что, например, наблюдается в C++, Pascal, Basic для приведенного выше фрагмента арифметического выражения).

Знание семантики языка позволяет отделить ее от его синтаксиса и использовать для преобразования в другой язык (осуществить генерацию кода).

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

Обобщенная структура транслятора

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

Учитывая схожесть компилятора и интерпретатора, рассмотрим фазы, существующие в компиляторе. В нем выделяются:

1. Фаза лексического анализа.
2. Фаза синтаксического анализа, состоящая из:

• распознавания синтаксической структуры;
• семантического разбора, в процессе которого осуществляется работа с таблицами, порождение промежуточного семантического представления или объектной модели языка.

Фаза генерации кода, осуществляющая:

• семантический анализ компонент промежуточного представления или объектной модели языка;
• перевод промежуточного представления или объектной модели в объектный код.

Наряду с основными фазами процесса трансляции возможны также дополнительные фазы:

2а. Фаза исследования и оптимизации промежуточного представления, состоящая из:

2а.1. анализа корректности промежуточного представления;
2а.2. оптимизации промежуточного представления.

3а. Фаза оптимизации объектного кода.

Интерпретатор отличается тем, что фаза генерации кода обычно заменяется фазой эмуляции элементов промежуточного представления или объектной модели языка. Кроме того, в интерпретаторе обычно не проводится оптимизация промежуточного представления, а сразу же осуществляется его эмуляция.

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

Обобщенная структура компилятора, учитывающая существующие в нем фазы, представлена на рис. 1.4.

Он состоит из лексического анализатора, синтаксического анализатора, генератора кода, анализатора ошибок. В интерпретаторе вместо генератора кода используется эмулятор (рис. 1.5), в который, кроме элементов промежуточного представления, передаются исходные данные. На выход эмулятора выдается результат вычислений.

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

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

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

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

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

Обобщенная структура синтаксического анализатора приведена на рис. 1.6.

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

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

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

Варианты взаимодействия блоков транслятора

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

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

На основе двух основных вариантов можно также создавать их разнообразные сочетания.

Многопроходная организация взаимодействия блоков транслятора

Данный вариант взаимодействия блоков, на примере компилятора, представлен на рис 1.7.

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

К достоинствам такого подхода можно отнести:

1. Обособленность отдельных фаз, что позволяет обеспечить их независимую друг от друга реализацию и использование.
2. Возможность хранения данных, получаемых в результате работы каждой из фаз, на внешних запоминающих устройствах и их использования по мере надобности.
3. Возможность уменьшения объема оперативной памяти, требуемой для работы транслятора, за счет последовательного вызова фаз.

К недостаткам следует отнести.

1. Наличие больших объемов промежуточной информации, из которой в данный момент времени требуется только небольшая часть.
2. Замедление скорости трансляции из-за последовательного выполнения фаз и использования для экономии оперативной памяти внешних запоминающих устройств.

Данный подход может оказаться удобным при построении трансляторов с языков программирования, обладающей сложной синтаксической и семантической структурой (например, PL/I). В таких ситуациях трансляцию сложно осуществить за один проход, поэтому результаты предыдущих проходов проще представлять в виде дополнительных промежуточных данных. Следует отметить, что сложные семантическая и синтаксическая структуры языка могут привести к дополнительным проходам, необходимым для установления требуемых зависимостей. Общее количество проходов может оказаться более десяти. На число проходов может также влиять использование в программе конкретных возможностей языка, таких как объявление переменных и процедур после их использования, применение правил объявления по умолчанию и т. д.

Однопроходная организация взаимодействия блоков транслятора

Один из вариантов взаимодействия блоков компилятора при однопроходной организации представлено на рис. 1.8.

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

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

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

Чаще всего в однопроходных трансляторах используется другая схема управления, в которой роль основного блока играет синтаксический анализатор (рис. 1.9).

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

К достоинствам однопроходной схемы следует отнести отсутствие больших объемов промежуточных данных, высокую скорость обработки из-за совмещении фаз в едином процессе и отсутствие обращений в внешним запоминающим устройствам.

К недостаткам относятся: невозможность реализации такой схемы трансляции для сложных по структуре языков и отсутствие промежуточных данных, которые можно использовать для комплексного анализа и оптимизации.

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

Комбинированные взаимодействия блоков транслятора

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

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

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

Наряду со схемами, предполагающими замену генератора кода на эмулятор, существуют трансляторы, допускающие их совместное использование. Одна из таких схем представлена на рис. 1.13.

Процесс трансляции, включая и генерацию кода, может быть выполнен за любое число проходов (в примере используется однопроходная трансляция, представленная ранее на ). Однако сформированный объектный код не исполняется на соответствующей ему вычислительной системе, а эмулируется на компьютере с другой архитектурой. Такая схема применяется в среде построенной вокруг языка программировании Java. Сам транслятор генерирует код виртуальной Java-машины, эмуляция которого осуществляется специальными средствами как автономно, так и в среде Internet браузера.

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

Контрольные вопросы и задания

1. Назовите отличия:

• интерпретатора от компилятора;
• компилятора от ассемблера;
• перекодировщика от транслятора;
• эмулятора от интерпретатора;
• синтаксиса от семантики.

1. Расскажите об известных Вам последних разработках языков программирования. Приведите основные характеристики названных языков.
2. Приведите конкретные примеры использования методов трансляции в областях, не связанных с языками программирования.
3. Приведите конкретные примеры компилируемых языков программирования.
4. Приведите конкретные примеры интерпретируемых языков программирования.
5. Приведите конкретные примеры языков программирования, для которых имеются как компиляторы, так и интерпретаторы.
6. Основные достоинства и недостатки компиляторов.
7. Основные достоинства и недостатки интерпретаторов.
8. Опишите основные различия в синтаксисе двух известных Вам языков программирования.
9. Опишите основные различия в семантике двух известных Вам языков программирования.
10. Назовите основные фазы процесса трансляции и их назначение.
11. Назовите специфические особенности однопроходной трансляции.
12. Назовите специфические особенности многопроходной трансляции.
13. Приведите примеры возможных комбинаций однопроходной и многопроходной трансляции. Расскажите о практическом использовании этих схем.