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

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

Текущая версия от 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