Программы форматированного вывода на печать

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

Статические проверяющие программы

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

Интерпретаторы

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

 

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

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

· «Кремниевые» компиляторы (Silicon Compilers). Такой компилятор имеет исходный язык, схожий с обычным языком программирования. Однако переменные языка представляют не положения в памяти, а логические сигналы (0 или 1) или группы сигналов в коммутируемых линиях.

· Интерпретаторы запросов. Данные интерпретаторы транслируют предикаты, содержащие операторы отношений и логические операторы, в команды поиска в базе данных записей, удовлетворяющих данному предикату. Сейчас, с появлением языка структурированных запросов SQL эта задача даже не просто подобна анализу компилятора, а является таковой.

 

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

В C++, например, существуют так называемые директивы препроцессора, которые начинаются с символа #. Например, #include, которая указывает, что надо подключить модуль, директива #define и другие.

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

Формальные грамматики

Алфавит – конечное непустое множество символов.

begin x:=1 end;

Для языка begin – это один символ. x,:=,1,end,; - тоже символы языка.

 

A – алфавит. A* - множество всех цепочек над данным алфавитом (т.е. составленных из символов алфавита).

Язык можно описать, например, описав все возможные предложения (цепочки) языка.

A = {0,1} - алфавит

L = {01,1,11} – язык.

Цепочка принадлежит языку, если она принадлежит множеству L. Т.е. в данном примере 01 – это предложение языка, а 0 – нет.

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

Для этого нужно описать синтаксис языка.

Синтаксис – это совокупность правил описания правильных структур языка.

Для описания синтаксиса языка используются грамматики.

Грамматика естественным образом описывает иерархическую структуру множества конструкций языка программирования. Например, инструкция if-else в C++ имеет вид

if (выражение) инструкция else инструкция

Используя переменную expr для обозначения выражения и переменную stmt для обозначения инструкции можно записать это структурное правило так:

stmt à if (expr) stmt else stmt

Символ à можно понимать как «может иметь вид». Такое правило называется продукцией (production) или правилом.

 

Грамматикой называется четверка (A,V,P, s), где

A – алфавит терминальных символов.

V – алфавит нетерминальных символов.

P – множество продукций (правил).

s – начальный символ.

G=(A, V, P, s)

 

Правила записываются в следующем виде:

, где

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

 

Нетерминальные символы будем записывать малыми латинскими буквами, а цепочки символов – малыми греческими буквами. Пустую цепочку обозначают символом e.

 

Пусть есть цепочки  и .   -   выводится из , тогда и только тогда, когда

.

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

 

Язык L, порождаемый грамматикой G = (A,V, P, s) – это множество цепочек , которое выводится из начального символа

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

 

Пример:

С помощью этой грамматики можно вывести 0

Можно вывести 0100

 

Грамматик для языка можно построить много.

Две грамматики называются эквивалентными, если они порождают один и тот же язык.

Например, если просто переобозначить символы (например вместо u писать v), получится эквивалентная грамматика.

 

Типы грамматик: