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

1.1. Пример работы
1.2. Установка

	$ cd ~/ # загружаем репозиторий в корень домашней директории
	$ mkdir compiler # создаем папку compiler
	$ cd compiler # заливаем необходимые файлы в compiler из текущего репозитория
	$ ls # содержимое должно быть таким
	bin  compiler  compiler.pro  compiler.pro.user  compiler.sh  main.cpp  main.psx  readme.md  run
	$ gedit ~/.bashrc # добавляем в конец строчки

	alias compiler='run'
	export PATH="$PATH:~/compiler/run/bin"
	закрываем файли и сохраняем его

	$ source ~/.bashrc
	$ cd ~/compiler/
	$ gedit compiler.sh # редактируем путь до компилятора

	меняем строчки:
	cp "$FILE" /home/splincode/Develop/codework/cpp/compiler/main.psx
	cd /home/splincode/Develop/codework/cpp/compiler/bin && make

	на такие:
	cp "$FILE" ~/compiler/main.psx
	cd ~/compiler/bin && make

1.3. Использование

	$ cd ~/myprogram # заходим в любую директорию, в любое место
	$ touch myсode.psx # создаем файл с любым названием

	
	// пишем программу на псевдо-pascal 
	// mycode.psx (pascal next = psx)
	
	// пользовательские функции
	void print(var t) {
		// write, writeln - 
		// стандартные функции вывода
		writeln("", t);
	}

	function asb(var n = 0){
		return (n > 0) ? n : -n;
	}

	program
		var a = -100;
		writeln("|a| = ", abs(a)); 

		var text = "hello world";
		print(text);
	end

	$ сompiler # вызываем компилятор и прописываем файла на компиляцию
	Текущая директория: /home/splincode/myprogram
	Напишите название файла, который хотите скомпилировать: mycode.psx

	$ ./compiler
	|a| = 100
	hello world

Если в синтаксисе присутствуют ошибки, компилятор придупредить об этом. После успешной компиляции, в текущей директории будет доступен бинарный исполняемый файл - compiler

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

При трансляции компьютерной программы адресатом может быть:

• устройство — процессор (трансляция называется компиляцией);
• программа — интерпретатор (трансляция называется интерпретацией).

2.2. Компиляция

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

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

Процесс компиляции, как правило, состоит из нескольких этапов:

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

Достоинства компиляции:

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

Недостатки компиляции:

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

2.3. Интерпретация

Интерпретация — процесс чтения и выполнения исходного кода. Реализуется программой — интерпретатором.

Этапы работы интерпретатора:

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

2.4. Польская нотация

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

+ 3 4

А́рность — количество аргументов, или операндов. Пример, бинарный, тернарный оператор.

Примеры префиксной нотации:

# стандартный вид
(5 − 6) * 7

* (− 5 6) 7

2.5. Инфиксная нотация

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

2 + 2

2.6. Обратная польская запись

Обра́тная по́льская нота́ция (ОПН) — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Также именуется как обратная польская запись, обратная бесскобочная запись (ОБЗ), постфиксная нотация, бесскобочная символика Лукасевича, польская инверсная запись, ПОЛИЗ.

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

Приоритеты:

• ^ высокий
  
• • / средний
    
• • • низкий
      
• ( ) самый низкий
  

2.7. Логика высказываний

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

2.8. Логика предикатов

Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов F и множества предикатных символов P. С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные, так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант.

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

2.9. Логика высших порядков

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

2.10. Редукция

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

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.

λ-исчисление может рассматриваться как семейство прототипных языков программирования. Их основная особенность состоит в том, что они являются языками высших порядков. Тем самым обеспечивается систематический подход к исследованию операторов, аргументами которых могут быть другие операторы, а значением также может быть оператор. Языки в этом семействе являются функциональными, поскольку они основаны на представлении о функции или операторе, включая функциональную аппликацию и функциональную абстракцию. λ-исчисление реализовано Джоном Маккарти в языке Лисп. Вначале реализация идеи λ-исчисления была весьма громоздкой. Но по мере развития Лисп-технологии (прошедшей этап аппаратной реализации в виде Лисп-машины) идеи получили ясную и четкую реализацию.

α-эквивалентность Основная форма эквивалентности, определяемая в лямбда-термах, это альфа-эквивалентность. Например, Λx.x и Λy.y альфа-эквивалентные лямбда-термы и оба представляют одну и ту же функцию (функцию тождества). Термы x и y не альфа-эквивалентны, так как они не находятся в лямбда абстракции.

β-редукция Поскольку выражение Λx. 2 * x + 1 обозначает функцию, ставящую в соответствие каждому x значение 2 * x + 1, то для вычисления выражения

(Λx. 2 * x + 1) 3, в которое входят и аппликация и абстракция, необходимо выполнить подстановку числа 3 в терм
2 * x + 1 вместо переменной x. В результате получается 2 * 3 + 1 = 7.

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