2014-02-13
1077
Метасимволы
Понятие языка программирования (неформально)
ВВЕДЕНИЕ
Языки программирования и методы трансляции
(1 часть)
1 Понятие языка программирования (неформально) 1
2 Эволюция языков программирования. 3
3 Классификация языков программирования. 8
4 Среда программирования. 8
4.1 Понятие среды программирования. 9
4.2 Техника разработки программ. 9
4.3 Классификация ошибок в программе. 10
4.4 Отладка. 10
5. Основные виды языков программирования. 11
6 Лямбда-исчисление как формализация функциональных языков. 14
7 Лямбда-исчисление как формальная система. 15
7.1 Свободные и связанные переменные. 16
7.2 Подстановки. 17
7.3 Конверсия. 17
7.4 Равенство лямбда-термов. 18
7.5 Экстенсиональность. 18
7.6 Редукция лямбда-термов. 19
7.7 Редукционные стратегии. 20
8 Комбинаторы.. 21
9 Лямбда-исчисление как язык программирования. 23
9.1 Представление данных в лямбда-исчислении. 23
9.1.1 Булевские значения и условия. 23
9.1.2 Пары и кортежи. 24
9.1.3 Натуральные числа. 25
|
|
|
9.2 Рекурсивные функции. 27
9.3 Именованные выражения. 28
10 Типы.. 30
10.1 Типизированное лямбда-исчисление. 32
10.1.1 Базовые типы.. 32
10.1.2 Типизации по Черчу и Карри. 33
10.1.3 Формальные правила типизации. 34
10.2 Полиморфизм. 34
10.2.1 let-полиморфизм. 34
10.2.2 Наиболее общие типы.. 35
10.3 Сильная нормализация. 36
11 Отложенные вычисления. 37
12 Классы типов. 41
13 Монады.. 43
Язык программирования это система обозначений для описания вычислений.
ЯП = алфавит + синтаксис + семантика.
Алфавит это символы для записи конструкций языка.
Синтаксис это правила записи конструкций языка.
Семантика это смысл конструкций языка.
Способы задания синтаксиса
Формы Бэкуса-Наура (БНФ)
Синтаксические диаграммы
Формы Бэкуса - Наура
Разработаны Джоном Бэкусом в 1960 г. и использованы Петером Науром для описания синтаксиса языка программирования Алгол-60.
БНФ включают:
Терминальные символы, которые образуют алфавит языка.
Нетерминальные символы – заключаются в угловые скобки <...>и используются для обозначения синтаксических конструкций языка. Например, <двоичное число>, <метка>, <арифметическое выражение>
| - или,
::= - по определению.
Пример: множество целых чисел:
<целое число>::= <целое без знака> | + <целое без знака> | - <целое без знака>
<целое без знака>::= <цифра>|<целое без знака > <цифра>
<цифра>::= 0|1|2|3|4|5|6|7|8|9
Две последние формы дают пример рекурсии в БНФ
[…] - повторение символа 0 или 1 раз
{…} - повторение символа произвольное число раз (в т.ч. нуль)
Пример: РБНФ
Множество целых чисел:
<целое число>::= [ + | - ] <целое без знака>
<целое без знака>::= <цифра> {<цифра>}
|
|
|
<цифра>::= 0|1|2|3|4|5|6|7|8|9
Синтаксические диаграммы
Синтаксические диаграммы это графическое изображение БНФ (Никлаус Вирт).
Нетерминальные символы изображаются в виде прямоугльников.
Терминальные символы изображаются в виде овалов.
Метасимволы заменяются композициями направленных дуг.
Пример: множество целых чисел:
Имеет место эквивалентность БНФ и синтаксических диаграмм.
