double arrow

Дополнительные метасимволы (расширение БНФ (РБНФ))


Метасимволы

Понятие языка программирования (неформально)

ВВЕДЕНИЕ

Языки программирования и методы трансляции

(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



Синтаксические диаграммы

Синтаксические диаграммы это графическое изображение БНФ (Никлаус Вирт).

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

Терминальные символы изображаются в виде овалов.

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

Пример: множество целых чисел:

Имеет место эквивалентность БНФ и синтаксических диаграмм.







Сейчас читают про: