ИНФ.0102.А\ПРЕДМЕТЫ\ТЯП

Конспект лекций по ТЕОРИИ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ.
Преподаватель: Дюсембаев Ануар Ермаханович

Версия для печати

ПРЕДМЕТЫ

> .. > Вернуться к списку предметов

11.02.2002
Введение в теорию языков программирования и методы трансляции.
Язык программирования - информационная технология. Примеры языков программирования: Pascal, Basic, C++, Java, Fortran, Algol и т.д. В общей сложности языков и их диалектов более 3.5 тысяч.
Термин "информатика"Употребляется в русском языке с начала 80-х годов.
Рис. 1. Наглядное сравнение наук информатики и Computer Science

Рис. 1. Наглядное сравнение наук информатики и Computer Science

"Информатика" и "Computer Science" - почти одна и та же наука.
Язык вляется средством общения. В том числе и языки программирования.
Искуственные языки. Примеры искусственных языков: язык нот, язык химических формул, язык глухонемых (язык жестов), код Морзе.
При изучении языков возникает 2 вопроса:

какого рода информация передается с помощью языка;
какими средствами она передается;

Язык программирования - это средство общения человека с машиной и человека с человеком, но через машину. На языке программирования происходит запись алгоритмов для решения задачи.
Класс языков, ориентированных на решение задач вычислительной математики, называется процедурным классом языков программирования. Нечеткое программирование, нечеткие языки программирования. Примеры: язык Пойя, Cobol.
Процедурный стиль программирования.
Существует другой клас языков, непохожий на процедурный класс, класс функциональных языков. например, LISP (автор языка: Маккарти).
Процедурные языки. Типичные представители - REFAL, Snobol.
Логические языки. Пример: Prolog.

??.02.2002
НЕТ КОНСПЕКТА.

??.02.2002
Важный аспект - не только обнаружить, что в программе есть ошибки, но еще и локализовать их. Локализовать - найти "минимальные" конструкции в программе, в которых допущены ошибки.
ДЛя транслятора наши программы являются цепочками символов. Но при этом не каждая цепочка допустимых символов является правильной фразой языка (программой языка).
Язык БНФ служит для задания синтаксиса многих языков программирования.
Запишем БНФ формы для языка чисел.

<число>::=<число без знака>|+<число без знака>|-<число без знака>
<число без знака>::=<десятичное число>|<порядок>|<десятичное число><порядок>
<десятичное число>::=<число без знака>|<правильная дробь>|<целое без знака><правильная дробь>
<порядок>::=e<целое>
<правильная дробь>::=.<целое без знака>
<целое>::=<целое без знака>|+<целое без знака>|-<целое без знака>
<целое без знака>::=<цифра>|+<целое без знака>|-<целое без знака>
Левая часть определяется через правую, содержащую левую. Это называется "рекурсивное определение"
<цифра>::={0|1|2|3|4|5|6|7|8|9}

+1.5e-3
<число>, +<число без знака>, +<десятичное число><порядок>, +<десятичное число>e<целое>, +<десятичное число>e-<целое без знака>, +<десятичное число>e-<цифра>, +<десятичное число>e-3, +<целое без знака><правильная дробь>e-3, +<цифра><правильная дробь>e-3, +1<правильная дробь>e-3, +1.<цифра>e-3, +1.5e-3
Как оказалось, наша цепочка числ верна.
Есть основания полагать, что система правил БНФ задает точные значения чисел. Видно, что эта система правил порождает все правильные цепочки. но, может быть, этот язык кроме правильных порождает еще и неправильные? Если мы возьмем любую неправильную цепочку, например: +1..5e-3, то наступит шаг при выполнении данной цепочки, когда дальнейшие действия будут неопределены.
Что включает в себя язык БНФ для нашего случая: языка чисел?

Символы языка чисел (его алфавит):
{0;1;2;3;4;5;6;7;8;9;+;-;.;e}
Синтаксические конструкции языка чисел.
{<число>; <число без знака>; <десятичное число>; <порядок>; и т.д.}

С одной стороны - это понятие, а с другой - это куски текстов. Запись синтаксических конструкций в виде текстов неудобна для работы с ними, хотя удобна для понимания человеком. Сделаем модификацию БНФ-форм.
Заменим тексты вместе со скобками на буквы:

<число>	Ч
<число без знака>	Н
<десятичное число>	Д
<правильная дробь>	М
<целое без знака>	Б
<целое>	Ф
<порядок>	П
<цифра>	Ц

Сделаем еще модификации этих форм: вместо "::=" будем использовать "→", "|" убираем совсем. Теперь запишем те же формы в виде правил:

26.02.2002
Элементы семантики присутствуют уже в формах БНФ и, соответственно, правила грамматики, потому что эти правила писались со смыслом.
Вопрос для самостоятельной подготовки: откуда берутся терминальные символы?
Ответ (дан на лекции): они берутся из алфавита того языка, который мы хотим описать.
В дополнение к грамматике в теории языков существуют также так называемые контекстные условия, которые, наряду с грамматикой, задают синтаксис. Например, запрет на использование ключевых слов в качестве индентификаторов; любая переменная, используемая во многих трансляторах, обязательно должна быть объявлена заранее.
При переходе от текущей цепочки w_i к следующей цепочке w_i+1

Сайт управляется системой uCoz