Теория и реализация языков программирования: различия между версиями

Материал из ВикиФизтех
Перейти к навигации Перейти к поиску
imported>Андрей Гущин
(Создание предмета)
imported>Дмитрий Русланович Гончар
 
(не показано 88 промежуточных версий 2 участников)
Строка 2: Строка 2:
 
|Читается на кафедрах=Кафедра математических основ управления
 
|Читается на кафедрах=Кафедра математических основ управления
 
}}
 
}}
 +
Курс «Теория и реализация языков программирования» (ТРЯП) посвящён изучению теории формальных языков (ТФЯ) и ряду её применений в программировании, из которых основное внимание уделено построению компиляторов.
 +
 +
== О содержании курса ==
 +
Сама теория формальных языков возникла в середине ХХ века, в том числе в связи с изучением возможностей машинного перевода с одного языка на другой, в ходе чего ещё раз была отмечена неоднозначность естественных языков (русского, немецкого, китайского и т.д.) как существенная сложность для решения этой задачи, а заодно сформулированы условия построения формальных языков, с помощью которых можно будет качественно более точно и однозначно обмениваться данными в т.ч. в технических системах.
 +
 +
Такие формальные языки были созданы. Среди них не только множество языков программирования, но и входные языки САПР, метаязыки описания больших данных и т.д.
 +
 +
ТФЯ изучает две большие задачи:
 +
# '''как породить (описать) всевозможные допустимые цепочки данного формального языка''' (к примеру, формально правильные программы языка программирования, допустимые цепочки входных данных при тестировании сложной программы, у которой достаточно часто меняются как её коды, так и, возможно, структура обрабатываемых данных, состав правильно построенной СБИС или иной сложной технической системы вплоть до самолёта, правильную молекулу или вещество (ген в молекулярной биологии, лекарственное средство, имеющее заданный набор лечебных воздействий и не имеющее известных отрицательных последствий применения, в т.ч. в различном биохимическом окружении), непротиворечивую систему законодательных актов (на уровне компании, отрасли, государства) и т.д.)
 +
# '''как распознать цепочки из заданного языка''' (синтаксически правильные программы для ЭВМ, искомые цепочки для поисковиков программ-обозревателей интернета, программы поддержки секвенирования генома  (каждый ген также может быть представлен как цепочка знаков или своего рода слова из допустимого языка Природы для данного вида) и т.д.
 +
 +
== ТРЯП на Физтехе ==
 +
Исторически сложилось так, что на ФУПМе студентам предлагают изучать только приложения ТФЯ, связанные с программированием. Задача разработки разновидностей курса, учитывающего познавательные потребности студентов с других факультетов (прежде всего, ФРТК) не ставится, а их возможное участие в изучении курса с получением соответствующих зачётов и экзаменов затруднено (отчасти, возможно, и потому, что предлагавшийся в середине 2000-х в течение пары лет очный вариант курса по выбору для студентов иных факультетов не собирал минимально необходимого числа желающих).
 +
 +
Из других факультетов МФТИ подобный курс некоторое время читался на [[ФИВТ]] и другой командой преподавателей (требования преподавателей ФУПМа к студентам ФИВТ в деканате последнего показались слишком строги).
 +
 +
В предисловии к своей известной книге ''А. Ахо'' и ''Дж. Ульман''<ref>''А. Ахо, Дж. Ульман'' «Теория синтаксического анализа, перевода и компиляции». Т. 1. пер. с англ. под ред. В.М. Курочкина. М.: Мир, 1978. С. 9</ref> писали «''Чтение курса по этой книге рекомендуется сопровождать лабораторными работами по программированию, в ходе которых должны быть спроектированы и реализованы какие-то части компилятора. В конце некоторых разделов книги приведены упражнения на программирование, которые можно использовать в этих лабораторных работах''».
 +
 +
Но количество выделенных для курса часов и общая высокая учебная нагрузка на студентов по сию пору не позволяет это осуществить. В тоже время для интересующихся студентов разработан и доступен разработанный [[Серебряков Владимир Алексеевич|В.А. Серебряковым]] пакет программ к курсу ТРЯП на Java (ссылка ниже).
 +
 +
=== Основатели и первые преподаватели ===
 +
Курс был создан среди первых факультетских курсов после образования ФУПМа руководителем лаборатории программирования (позже – одного из отделов) ВЦ АН СССР к.ф.-м.н. Владимиром Михайловичем Курочкином [1926-1999], под руководством которого были созданы компиляторы с языка «Алгол» для отечественных БЭСМ-2 и БЭСМ-6, языка «Алгамс» и проведён целый ряд других разработок в этой области, многие из которых широко и успешно использовались в нашей стране.
 +
 +
Среди первых преподавателей курса, известных также как авторы первого учебного пособия по ТРЯП, вышедшего в МФТИ в 1973 г. (2-е изд. – 1978 г.), проф. [[Столяров Лев Николаевич|Л.Н. Столяров]], доц. Б.Г. Сушков и чл.-корр. РАН [[Флёров Юрий Арсениевич|Ю.А. Флёров]].
 +
 +
Лекции по курсу до конца 1990-х годов читал сам В.М. Курочкин.
 +
 +
В начале 2000-х его преемником стал ученик Владимира Михайловича проф. [[Серебряков Владимир Алексеевич|В.А. Серебряков]].
 +
 +
== Об особенностях преподавания ==
 +
Возникшая в середине прошлого века наука в соответствии с новыми потребностями и возможностями вычислительных техники и технологий продолжала развиваться и дальше. Это отражалось и на содержании читаемых разделов, явилось одной из причин подготовки и выпуска нового учебного пособия по ТРЯП (автор - В.А. Серебряков и др.) в 2003 г., весьма заметно отличающегося по программе от учебных пособий 1970-х годов. 
 +
 +
За прошедшие со времени 2-го издания этого пособия (2006 г.) годы, в том числе и под влиянием знакомства с переведёнными в начале 2000-х новыми зарубежными пособиями по близким курсам, изучения представленных в сети новых научных трудов по данному направлению и опыта преподавания по новой программе, у команды преподавателей собрался материал для дальнейшего пополнения состава изучаемых алгоритмов. В связи в том числе с тем, что с начала 2000-х годов курс (в связи с уплотнением учебного графика) из годового стал семестровым, некоторые традиционные разделы курса при этом стали изучаться менее подробно, а какие-то (включая традиционные в течение многих десятилетий с основания курса НС-грамматики) вообще исключены из семестровых контрольных и экзаменов.
 +
 +
Также это привело и к тому, что не все разделы читаемого в настоящее время лекционного курса отражены в пособии В.А. Серебрякова и соавт. Размещение конспектов по некоторым дополнениям курса в сети см. ниже.
 +
 +
== См. также ==
 +
=== Первые преподаватели курса ===
 +
* [https://ru.wikipedia.org/wiki/Курочкин,_Владимир_Михайлович_(учёный) В.М. Курочкин] (о нём и его научных трудах) в Википедии
 +
* [https://ru.wikipedia.org/wiki/Сушков,_Борис_Григорьевич Б.Г. Сушков] (о нём) в Википедии
 +
 +
=== Книги и учебные пособия в сети ===
 +
* [http://www.mou.mipt.ru/fund.html Задание, программа и учеб. пос. по курсу ТРЯП] на портале каф. МОУ.
 +
* ''Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г.'' [http://trpl7.ru/t-books/_TRYAPBOOK_pdf.pdf Теория и реализация языков программирования: учеб. пос.] М., МЗ-Пресс, 2003. (2-е изд., 2006 г.) – электр. версия в сети с разреш. авторов.
 +
* [http://trpl7.ru/Conspectus/MyHill-Nerode_theorem.pdf  Теорема Майхилла-Нероуда (необх. и дост. условие регулярности языка)] консп. лекции проф. В.А. Серебрякова (2018 г.).
 +
* [http://trpl7.ru/AutoLang.htm Пакет программ к курсу ТРЯП] (В.А. Серебрякова) – пробный выпуск.
 +
* [http://www.rubtsov.su/fl_course18/index Материалы по ТРЯП] преп. курса [[Рубцов Александр Александрович|А.А. Рубцова]]
 +
* ''Мартыненко Б.К.'' [http://trpl7.ru/t-books/Martin/Martinenko_FLT_Cont.htm Языки и трансляции: учеб. пос.] СПб.ГУ, 2002 г. (ранее было разм. на странице автора на портале СПб.ГУ).
 +
* ''Шень А. Х.'' [https://www.mccme.ru/free-books/shen/shen-progbook.pdf Программирование: теоремы и задачи]. М.: МЦНМО, 2004. (разм. на портале МЦНМО с разр. автора) – здесь можно посмотреть алгоритм Кнута-Морриса-Пратта.
 +
* [http://trpl7.ru/t-books/RegExpr_Aho_Ullman.pdf Уравнения с регулярными коэффициентами] (консп. из Ахо-Ульмана (1978), 4 с.)
 +
 +
=== более ранние издания ===
 +
* ''Курочкин В. М., [[Столяров Лев Николаевич|Столяров Л. Н.]], Сушков Б. Г., [[Флёров Юрий Арсениевич|Флёров Ю. А.]]'' [http://trpl7.ru/t-books/guides.htm Теория и реализация языков программирования: Курс лекций] М., МФТИ, 1973. (2-е изд., 1978 г.) – электр. версия в сети с разреш. авторов.
 +
 +
=== В библиотеке МФТИ ===
 +
* ''Ахо А., Сети Р., Ульман Дж.'' Компиляторы. Принципы, технологии, инструменты. М., СПб.,  Киев: Вильямс, 2001. (10 шт.)
 +
* ''Хопкрофт Дж., Мотвани Р., Ульман Дж.'' Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. (16 шт.)
 +
* ''Ахо А., Лам М., Сети Р., Ульман Дж.'' Компиляторы. Принципы, технологии и инструментарий. М., СПб., Киев: Вильямс, 2011. 1184 c. (добавлен большой раздел о параллельных методах компиляции – для семестрового курса на 2-м году обучения мало актуально, а вес большой).
 +
 +
=== более ранние издания ===
 +
* ''А. Ахо, Дж. Ульман''. Теория синтаксического анализа, перевода и компиляции. Т. 1. Пер. с англ. ''В. Н. Агафонова'' под ред. ''В. М. Курочкина''. М.: Мир, 1978. 614 с. (имеются только в чит. зале)
 +
* ''А. Ахо, Дж. Ульман''. Теория синтаксического анализа, перевода и компиляции. Т. 2. Пер. с англ. ''А. Н. Бирюкова'' и ''В. А. Серебрякова'' под ред. ''В. М. Курочкина''. М.: Мир, 1978. 487 с.
 +
 +
{{Предмет преподают}}
 
{{комментарии}}
 
{{комментарии}}

Текущая версия от 23:36, 23 августа 2021

Теория и реализация языков программирования
Читается на кафедрах Кафедра математических основ управления

Курс «Теория и реализация языков программирования» (ТРЯП) посвящён изучению теории формальных языков (ТФЯ) и ряду её применений в программировании, из которых основное внимание уделено построению компиляторов.

О содержании курса[править | править код]

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

Такие формальные языки были созданы. Среди них не только множество языков программирования, но и входные языки САПР, метаязыки описания больших данных и т.д.

ТФЯ изучает две большие задачи:

  1. как породить (описать) всевозможные допустимые цепочки данного формального языка (к примеру, формально правильные программы языка программирования, допустимые цепочки входных данных при тестировании сложной программы, у которой достаточно часто меняются как её коды, так и, возможно, структура обрабатываемых данных, состав правильно построенной СБИС или иной сложной технической системы вплоть до самолёта, правильную молекулу или вещество (ген в молекулярной биологии, лекарственное средство, имеющее заданный набор лечебных воздействий и не имеющее известных отрицательных последствий применения, в т.ч. в различном биохимическом окружении), непротиворечивую систему законодательных актов (на уровне компании, отрасли, государства) и т.д.)
  2. как распознать цепочки из заданного языка (синтаксически правильные программы для ЭВМ, искомые цепочки для поисковиков программ-обозревателей интернета, программы поддержки секвенирования генома (каждый ген также может быть представлен как цепочка знаков или своего рода слова из допустимого языка Природы для данного вида) и т.д.

ТРЯП на Физтехе[править | править код]

Исторически сложилось так, что на ФУПМе студентам предлагают изучать только приложения ТФЯ, связанные с программированием. Задача разработки разновидностей курса, учитывающего познавательные потребности студентов с других факультетов (прежде всего, ФРТК) не ставится, а их возможное участие в изучении курса с получением соответствующих зачётов и экзаменов затруднено (отчасти, возможно, и потому, что предлагавшийся в середине 2000-х в течение пары лет очный вариант курса по выбору для студентов иных факультетов не собирал минимально необходимого числа желающих).

Из других факультетов МФТИ подобный курс некоторое время читался на ФИВТ и другой командой преподавателей (требования преподавателей ФУПМа к студентам ФИВТ в деканате последнего показались слишком строги).

В предисловии к своей известной книге А. Ахо и Дж. Ульман[1] писали «Чтение курса по этой книге рекомендуется сопровождать лабораторными работами по программированию, в ходе которых должны быть спроектированы и реализованы какие-то части компилятора. В конце некоторых разделов книги приведены упражнения на программирование, которые можно использовать в этих лабораторных работах».

Но количество выделенных для курса часов и общая высокая учебная нагрузка на студентов по сию пору не позволяет это осуществить. В тоже время для интересующихся студентов разработан и доступен разработанный В.А. Серебряковым пакет программ к курсу ТРЯП на Java (ссылка ниже).

Основатели и первые преподаватели[править | править код]

Курс был создан среди первых факультетских курсов после образования ФУПМа руководителем лаборатории программирования (позже – одного из отделов) ВЦ АН СССР к.ф.-м.н. Владимиром Михайловичем Курочкином [1926-1999], под руководством которого были созданы компиляторы с языка «Алгол» для отечественных БЭСМ-2 и БЭСМ-6, языка «Алгамс» и проведён целый ряд других разработок в этой области, многие из которых широко и успешно использовались в нашей стране.

Среди первых преподавателей курса, известных также как авторы первого учебного пособия по ТРЯП, вышедшего в МФТИ в 1973 г. (2-е изд. – 1978 г.), проф. Л.Н. Столяров, доц. Б.Г. Сушков и чл.-корр. РАН Ю.А. Флёров.

Лекции по курсу до конца 1990-х годов читал сам В.М. Курочкин.

В начале 2000-х его преемником стал ученик Владимира Михайловича проф. В.А. Серебряков.

Об особенностях преподавания[править | править код]

Возникшая в середине прошлого века наука в соответствии с новыми потребностями и возможностями вычислительных техники и технологий продолжала развиваться и дальше. Это отражалось и на содержании читаемых разделов, явилось одной из причин подготовки и выпуска нового учебного пособия по ТРЯП (автор - В.А. Серебряков и др.) в 2003 г., весьма заметно отличающегося по программе от учебных пособий 1970-х годов.

За прошедшие со времени 2-го издания этого пособия (2006 г.) годы, в том числе и под влиянием знакомства с переведёнными в начале 2000-х новыми зарубежными пособиями по близким курсам, изучения представленных в сети новых научных трудов по данному направлению и опыта преподавания по новой программе, у команды преподавателей собрался материал для дальнейшего пополнения состава изучаемых алгоритмов. В связи в том числе с тем, что с начала 2000-х годов курс (в связи с уплотнением учебного графика) из годового стал семестровым, некоторые традиционные разделы курса при этом стали изучаться менее подробно, а какие-то (включая традиционные в течение многих десятилетий с основания курса НС-грамматики) вообще исключены из семестровых контрольных и экзаменов.

Также это привело и к тому, что не все разделы читаемого в настоящее время лекционного курса отражены в пособии В.А. Серебрякова и соавт. Размещение конспектов по некоторым дополнениям курса в сети см. ниже.

См. также[править | править код]

Первые преподаватели курса[править | править код]

Книги и учебные пособия в сети[править | править код]

более ранние издания[править | править код]

В библиотеке МФТИ[править | править код]

  • Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты. М., СПб., Киев: Вильямс, 2001. (10 шт.)
  • Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002. (16 шт.)
  • Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии и инструментарий. М., СПб., Киев: Вильямс, 2011. 1184 c. (добавлен большой раздел о параллельных методах компиляции – для семестрового курса на 2-м году обучения мало актуально, а вес большой).

более ранние издания[править | править код]

  • А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 1. Пер. с англ. В. Н. Агафонова под ред. В. М. Курочкина. М.: Мир, 1978. 614 с. (имеются только в чит. зале)
  • А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. Т. 2. Пер. с англ. А. Н. Бирюкова и В. А. Серебрякова под ред. В. М. Курочкина. М.: Мир, 1978. 487 с.

Предмет преподают[править код]

Раньше преподавали

Комментарии:

Loading comments...
  1. А. Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции». Т. 1. пер. с англ. под ред. В.М. Курочкина. М.: Мир, 1978. С. 9