Теория языков программирования (ТЯП)

Введение

Главным строительным материалом, используемым в теории языков программирования (ТЯП), является множество, то есть комплект объектов или компонентов. К примеру, множеством может считаться набор из первой тройки натуральных чисел: {0, 1, 2}. Главным определяющим фактором является принадлежность рассматриваемого объекта к конкретному множеству. При этом, не имеет значения есть ли копии объекта или каким образом появляется объект в множестве. К примеру, множество {0, 2, 1} – это такое же множество, как и в примере выше. Символика (нотация) ∈ означает принадлежность к множеству. Например, запись 1 ∈ {0, 1, 2}, то есть единица принадлежит указанному множеству, является истинной, а 3 ∈ {0, 1, 2} является ложной информацией. В множестве может содержаться бесконечное число компонентов. К примеру, множество, в состав которого входят все натуральные числа (то есть целые неотрицательные числа) и которое обозначается символом N, является бесконечным.

Ещё одним строительным блоком языков программирования является кортеж, то есть упорядоченный набор объектов. Например, (0, 1, 2) считается кортежем, состоящим их трёх компонентов, а кортеж (0, 2, 1), будет уже считаться совершенно другим. В состав кортежей всегда входит не бесконечное число компонентов и их, как правило, не очень много. Комбинация множеств и кортежей даёт в итоге отношения. Отношением является множество, состоящее из кортежей.

{(0, 1), (1,2), (2, 3), (3, 4), …}

Программисты часто применяют отношения, чтобы отобразить входные величины на выходные.

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

1. (0, 1) ∈ R.
2. Для всех натуральных чисел n и m, если (n, m) ∈ R, то (n + 1, m + 1) ∈ R.

Синтаксис языков программирования

При помощи правил, определяющих множества, возможно определить и синтаксис языка программирования. К примеру, требуется определить несложный язык для выполнения арифметических действий с целыми числами. Дадим ему имя Arith. В него будет входить набор выражений типа 1 + 3 и - (5 + 2), обозначим, также, символом Z множество целых чисел. Далее, сформируем набор правил, которые описывают язык Arith:

1. Для любого i ∈ Z справедливо, что i ∈ Arith.
2. Для любого e, если e ∈ Arith, то -e ∈ Arith.
3. Для любого e1 и e2, если e1 ∈ Arith и e2 ∈ Arith, то e1 + e2 ∈ Arith.
4. Для любого e, если e ∈ Arith, то (e) ∈ Arith.

Существует ещё один тип нотации, предназначенный для представления правил, которые определяют языковый синтаксис, а именно форма Бэкуса-Наура (БНФ). Есть несколько версий этой формы. Комплект правил является грамматикой:

• Arith ::= integer
• Arith ::= "-" Arith
• Arith ::= Arith "+" Arith
• Arith ::= "(" Arith ")"

Чтобы сделать определение синтаксиса языка более коротким, можно применять вертикальную черту:

Arith ::= integer | "-" Arith | Arith "+" Arith | "(" Arith ")"

В ТЯП используется один из вариантов БНФ, заменяющий имя, подлежащего определению языка, на переменную, используемую для прохода по компонентам Arith. Тогда введём переменную i в качестве заполнителя для целых чисел, и символ e в качестве заполнителя для компонентов Arith. Тогда грамматика языка будет выглядеть следующим образом:

e ::= i ∣ −e ∣ e + e

Операционная семантика

Выполнить описание языка означает описать, какие будут выполнены действия при пуске программы, выполненной на данном языке. Этим занимается операционная семантика. Для рассматриваемого примера с Arith требуется определить итоговый результат в формате целого числа для любой программы. Как указывалось выше, имеется возможность применения отношений, чтобы отобразить входные данные на результат. Именно таким образом это и делается в ТЯП. Существует разные стили отношений. Одним из них является семантика большого шага (big-step semantics), отображающая программу непосредственно на её итоги. Выполним определение отношения Eval, отображающее компоненты Arith на область целых чисел. К примеру, необходимо выполнение условия (− (2 + −5), 3) ∈ Eval. Данное отношение является бесконечным, поскольку может быть бесконечное число программ, написанных на Arith. Чтобы выполнить определение Eval, можно применить комплект правил. Примем следующее обозначение: e↓i. что означает (e, i) ∈ Eval. Сформируем синтаксически ориентированные правила, при этом каждое такое правило определяет синтаксическое правило языка (их три):

Рисунок 1. Три синтаксических правила. Автор24 — интернет-биржа студенческих работ

Критерии эффективности языков программирования

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

Главными критериями эффективности считаются следующие:

1. Простота прочтения и понимания программного языка.
2. Простота реализации программ, то есть насколько удобен в применении язык для конкретной сферы.
3. Критерий надёжности. Имеется в виду способность языка обеспечить минимум ошибок при выполнении программ.
4. Общая себестоимость жизненного цикла языка программирования.