Формальные языки программирования: Формальный язык

Содержание

Что такое формальный язык программирования?

Что означает, что язык программирования является формальным языком программирования? А какие языки являются формальными языками программирования? А что такое неформальные языки программирования?

Я еще не нашел хорошего объяснения.

programming-languages

formal-languages

Поделиться

Источник


Orjanp    

19 апреля 2010 в 16:36

6 ответов

  • Что такое язык компьютерного программирования?

    Рискуя показаться наивным, я задаю этот вопрос в поисках более глубокого понимания концепции языков программирования в целом. Я пишу этот вопрос в назидание себе и другим. Каково полезное определение языка программирования и каковы его основные и необходимые компоненты? Каковы ключевые…

  • что такое язык программирования?

    Википедия говорит: Язык программирования-это машиночитаемый искусственный язык, предназначенный для выражения вычислений, которые могут быть выполнены машиной, в частности компьютером. Языки программирования могут использоваться для создания программ, определяющих поведение машины, для точного…


10

Каждый язык программирования является формальным языком, так что для меня не имеет особого смысла говорить о “formal programming language.” (Или кто-то знает неформальный язык программирования?)

Формальный язык-это язык с математически точными правилами построения. Или, точнее, это набор слов по какому-то алфавиту. Например, если вы возьмете алфавит , состоящий из букв a , b и c, формальный язык над этим алфавитом может быть набором { a , aa , aba , ca }. Конечно, такой язык был бы не очень полезен – дело в том, что с приличным набором правил построения вы можете создать такой язык, как C или PostScript.

Что касается “construction rules,”, то они могут быть формальным grammar (см. grammar для CSS), регулярным выражением (см. Это великолепное regex для адресов электронной почты, определенных RFC 822), автоматом или общим алгоритмом.

Если вы чувствуете, что немного больше не понимаете, не отчаивайтесь, потому что это не очень хорошее объяснение 🙂 За концепцией формальных языков стоит много мыслей. Я бы посоветовал вам попробовать переварить статью в Википедии и поискать больше учебников и книг. Это весело, и вы узнаете много нового о предыстории компиляторов, регулярных выражений, машин Тьюринга и других чудес цифрового человечества.

Поделиться


zoul    

19 апреля 2010 в 17:38


2

Формальные средства четко определены. Каждый язык программирования, который можно использовать для определения исполняемых программ, должен быть четко определен, чтобы машины могли его понять.

Поделиться


mkorpela    

19 апреля 2010 в 16:43


1

Это не «formal language» это формальный метод программирования: Википедия . Это не обязательно должен быть конкретный язык, а скорее способ написания спецификации и проверки кода.

Поделиться


ierdna    

24 сентября 2016 в 16:46

  • Что такое язык программирования?

    Возможный Дубликат : Что такое язык компьютерного программирования? Нет, правда. Я изо всех сил пытался придумать действительно отличное определение. Вот мой дубль до сих пор: Язык программирования-это формальный язык, содержащий синтаксис. Синтаксические правила используются для формирования…

  • Что такое язык программирования «real»?

    Недавно один учитель сказал: PHP-это не настоящий язык программирования, но только дал, на мой взгляд, слабое обоснование: Он не компилируется. Все по сценарию. Он работает не на каждой платформе. Разве PHP не считается языком программирования real? Что такое язык программирования real? Нужно ли…


0

Это выдержка из википедии

«Джон C. Рейнольдс подчеркивает, что языки формальных спецификаций-это такие же языки программирования, как и языки, предназначенные для выполнения. Он также утверждает, что текстовые и даже графические форматы ввода, влияющие на поведение компьютера, являются языками программирования, несмотря на то, что они обычно не являются полными по Тьюрингу, и отмечает, что незнание концепций языка программирования является причиной многих недостатков в форматах ввода»

Поделиться


Diego Dias    

19 апреля 2010 в 16:44


0

Формальные языки-это языки, которые только и думают о своей правильности, ни о чем другом. Это означает, что достаточным и необходимым условием является соблюдение его правил.
Пример правила:

Например. Если мы определим язык для десятичных чисел как {x | конечный набор цифр без ведущих нулей}. (проще говоря, десятичные дроби означают последовательность цифр.)

Поэтому,если язык, содержащий вышеуказанное правило, должен быть формальным, он должен придерживаться данного правила.

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

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

Поделиться


Dilruk    

17 февраля 2013 в 13:09


0

Другие ответы связаны с определением формального языка программирования в соответствии с информатикой. Однако этот ответ связан с определением формального языка программирования в соответствии с социальной (подражательной) наукой.

Согласно dictionary.com , одним из определений ‘formal’ является being in accordance with the usual requirements, customs, etc.; conventional .

Формальный язык программирования-это язык программирования, который широко используется и принимается человеком, говорящим о нем. Таким образом, это предметная область и специфика разговора. Возможно, лучшим способом формулировки является ‘popular’,
традиционный’, ‘mainstream’ или ‘widely-accepted’ язык программирования. Например, в бизнесе и промышленности это относится к SQL , Java , C# , C++ , Python и PHP .

Примерами неформальных языков программирования являются SPL (язык программирования Шекспира), FORTRAN и CoffeeScript . Правильнее сказать, что один язык более условен и, следовательно, формален, чем другой, чем сказать, что один язык является формальным, а другой-неформальным.
В конце концов, Lisp был бы очень неформальным языком программирования для создания веб-сайта, но очень формальным языком программирования для разработки исследований в области искусственного интеллекта.

Поделиться


hexicle    

19 декабря 2017 в 01:51

Похожие вопросы:

В информатике, что такое NOT формальный язык?

В Википедии https:/ / www.wikiwand.com/en / Formal_language я нашел определение формального языка: В математике, информатике и лингвистике формальный язык это набор строк символов, которые могут…

Что такое формальный список параметров в контексте выполнения javascript?

Я хочу знать, что такое формальный список параметров в контексте выполнения javascript. Скажем, например, у меня есть такая функция function test(a, b, c) { var d, e; } Когда эта функция будет…

Что такое параллельный язык?

Из спецификации языка Java: Язык программирования Java™-это универсальный, параллельный, основанный на классах, объектно-ориентированный язык. Что такое параллельный язык?

Что такое язык компьютерного программирования?

Рискуя показаться наивным, я задаю этот вопрос в поисках более глубокого понимания концепции языков программирования в целом. Я пишу этот вопрос в назидание себе и другим. Каково полезное…

что такое язык программирования?

Википедия говорит: Язык программирования-это машиночитаемый искусственный язык, предназначенный для выражения вычислений, которые могут быть выполнены машиной, в частности компьютером. Языки…

Что такое язык программирования?

Возможный Дубликат : Что такое язык компьютерного программирования? Нет, правда. Я изо всех сил пытался придумать действительно отличное определение. Вот мой дубль до сих пор: Язык…

Что такое язык программирования «real»?

Недавно один учитель сказал: PHP-это не настоящий язык программирования, но только дал, на мой взгляд, слабое обоснование: Он не компилируется. Все по сценарию. Он работает не на каждой платформе….

Чистый объектно-ориентированный язык программирования

Правда ли, что Java не является чистым объектно-ориентированным языком программирования? что такое чистый язык программирования? Является ли smalltalk чистым объектно-ориентированным языком…

Что такое язык программирования ‘D’?

Что такое язык программирования ‘D’? Люди начали разрабатывать приложения с использованием этого языка? кто нашел? Могу ли я узнать больше об этом новом языке программирования?

Что такое звуковой язык программирования?

По данным сайта Dart Dart — это звуковой язык. Что означает sound в приведенном выше предложении? Является ли sound эквивалентом audio (могу ли я обменять их в приведенном выше утверждении)? Я не…

Формальные языки и грамматики / Хабр

Мотивация

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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.

Формальные языки

Коротко говоря, формальный язык — это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.

Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:

  1. Обобщение (абстрагирование). Объекты изучения в математике — это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было

    говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует.

  2. Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.

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

В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.

Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

Итак, формальные языки — это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.

Формальные грамматики

Способ задания языка называет грамматикой этого языка.n}

(здесь n — натуральное число) задает язык L, состоящий из цепочек вида

ab, aabb, aaabbb

и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.

Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик — это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них — окрестностные грамматики, будет описан чуть ниже.

С алгоритмической точки зрения грамматики можно подразделить по способу задания языка. Имеются три основных таких способа (вида грамматик):

  • Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае.

  • Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.

  • Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Интересным представляет вопрос о преобразовании видов грамматики друг в друга. Можно ли, имея порождающую грамматику, построить, скажем, перечисляющую? Ответ — да, можно. Для этого достаточно генерировать цепочки, упорядочив их, скажем по длине и порядку символов. Но превратить перечисляющую грамматику в распознающую в общем случае нельзя. Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.

Окрестностные грамматики

В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.

В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...}. Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций — символ «+». Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами «+» и в конце. Для обозначения начала и конца цепочки введем псевдосимвол «#». Тогда окрестности символа «a» будут следующими: #a+, +a+, +a#. Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ «+» встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a.

Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+. Второй символ «+» входит в цепочку вместе с окрестностью a+a. Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.

Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.

С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.

Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение — «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.

Формальный язык — это… Что такое Формальный язык?

В математической логике и информатике формальный язык — это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.

В теории моделей язык соответствует не языку в информатике, а скорее алфавиту. Язык состоит из множеств символов, функций и отношений вместе с их арностью, а также множество переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.

Определение

Формальный язык может быть определён по-разному, например:

Если алфавит задан как {a, b}, а язык L включает в себя все слова над ним, то слово ababba принадлежит L. Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как e, ε или Λ.

Некоторые примеры формальных языков:

Операции

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что и являются языками, определёнными над некоторым общим алфавитом.

  • Конкатенация (сцепление) содержит все слова, удовлетворяющие форме , где — это слово из , а — слово из .
  • Пересечение содержит все слова, содержащиеся и в , и в .
  • Объединение содержит все слова, содержащиеся или в , или в .
  • Дополнение языка содержит все слова алфавита, которые не содержатся в .
  • Правое отношение содержит все слова , для которых существует слово в такое, что находидось в .
  • Замыкание Клини содержит все слова, которые могут быть записаны в форме , где содержится в и . Следует помнить, что это включает и пустое слово , так как допустимо по условию.
  • Обращение содержит обращённые слова из .
  • Смешение и содержит все слова, которые могут быть записаны в форме , где и являются такими словами, что связь находится в , а являются такими словами, что находятся в .

Список литературы

  • Хопкрофт, Дж., Мотвани, Р., Дж. Ульман. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002 (пер. издания Addison Wesley). ISBN 5-8459-0261-4
  • Серебряков В.А., Галочкин М.П., Гончар Д.Р., Фуругян М.Г. Теория и реализация языков программирования //М.: МЗ-Пресс, 2006 г., 2-е изд. ISBN 94073-094-9.
  • Избранные книги по курсам «Теория и реализация языков программирования» и «Формальные языки трансляций»

Формальные языки и трансляции — Кафедра алгоритмов и технологий программирования

Цель дисциплины:

Курс по формальным языкам и трансляциям призван познакомить студентов с трансляторами и компиляторами. В рамках курса студенты изучают разные грамматики и парсеры и учатся применять их для решения задач. Данный курс полезен и для понимания устройства используемых ими языков программирования. Изучаемый аппарат востребован в других курсах, изучаемых в бакалавриате.

Учебные задачи дисциплины:

  • ознакомление слушателей с задачами, принципами, методами и подходами теории формальных языков и трансляций;
  • приобретение слушателями теоретических знаний, и практических умений и навыков в области формальных языков и трансляций.

 

В результате освоения дисциплины «Формальные языки и трансляции» обучающийся должен:

знать:

  • связь между языками и грамматиками;
  • классификацию языков и грамматик;
  • регулярные языки;
  • детерминированные и недетерминированные конечные автоматы;
  • машину Тьюринга;
  • контекстно-свободные грамматики;
  • восходящие и нисходящие анализаторы;
  • LL(k)-грамматики и анализаторы;
  • LR(k)-грамматики и анализаторы;
  • контекстно-свободные грамматики;
  • контекстно-зависимые грамматики;
  • применение грамматик в современных компиляторах.

уметь:

  • делать правильные выводы из сопоставления результатов теории и эксперимента;
  • определять достаточный для решения задачи класс грамматик;
  • строить грамматику для языка;
  • находить язык, порождаемый грамматикой;
  • строить таблицы LL(k)- и LR(k)-анализаторов;
  • использовать генераторы парсеров для построения анализаторов для грамматики.

владеть:

  • навыками самостоятельной работы в современных программных комплексах;
  • навыками освоения большого объёма информации;
  • навыками использования генераторов синтаксических анализаторов.

ФОРМАЛЬНЫЙ ЯЗЫК — это… Что такое ФОРМАЛЬНЫЙ ЯЗЫК?

  • ФОРМАЛЬНЫЙ СТЕПЕННОЙ РЯД
  • ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ

Смотреть что такое «ФОРМАЛЬНЫЙ ЯЗЫК» в других словарях:

  • формальный язык — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN formal language …   Справочник технического переводчика

  • Формальный язык — Не следует путать с формальным стилем речи. В математической логике и информатике формальный язык это множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и …   Википедия

  • Формальный язык —         то же, что Формализованный язык. Иногда под термином «Ф. я.» понимают также формальную систему (См. Формальная система) …   Большая советская энциклопедия

  • ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ — формальный язык, распознаваемый машиной, множество всех тех слов, при работе над к рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек рой Тьюринга… …   Математическая энциклопедия

  • Язык программирования — искусственный (формальный) язык, предназначенный для записи алгоритмов. Язык программирования задается своим описанием и реализуется в виде специальной программы: компилятора или интерпретатора. По английски: Programming language Синонимы:… …   Финансовый словарь

  • ЯЗЫК ПРОГРАММИРОВАНИЯ — это совокупность набора символов (алфавита) системы, правил образования (синтаксис) и истолкования конструкции из символов (семантика) для задания алгоритмов с использованием символов естественного языка. В самом общем виде формальный язык… …   Большая политехническая энциклопедия

  • язык концептуальной схемы — Формальный язык для описания концептуальной схемы, ее составных частей и действий над ними. [ГОСТ 34.320 96] Тематики базы данных EN conceptual schema language …   Справочник технического переводчика

  • ЯЗЫК ПРОГРАММИРОВАНИЯ — формальный язык для описания данных (информации) и алгоритма (программы) их обработки на ЭВМ. Основу Я. п. составляют алгоритмические языки. Первыми Я. п. были внутренние машинные языки, представляющие собой системы команд конкретной ЭВМ,… …   Большой энциклопедический политехнический словарь

  • формальный синтаксис — 3.4.1 формальный синтаксис: Спецификация точно сформулированных предложений формального языка с применением формальной грамматики. Примечание 1 Формальный язык это машинно ориентированный язык с интерпретированием. Примечание 2 Формальная… …   Словарь-справочник терминов нормативно-технической документации

  • Язык (значения) — Язык: В Викисловаре есть статья «язык» Язык  знаковая система для обмена информацией. Естественный язык  сформи …   Википедия

Книги

  • Системный подход и общая теория систем, А.И. Уемов. В монографии рассматриваются философские проблемы системных исследований, значение системного подхода для изучения сложных явлений действительности, для практики, излагается один из вариантов… Подробнее  Купить за 2003 руб
  • Архитектура. Элементы, формы, материалы, Франческа Прина. Данный том энциклопедии исследует развитие гражданского, военного, жилищного и религиозного зодчества на протяжении более чем двух тысячелетий. Книга объясняет формальный язык архитектуры,… Подробнее  Купить за 892 руб
  • Архитектура: элементы, формы, материалы, Прина Ф.. 65279;Данный том энциклопедии исследует развитие гражданского, военного, жилищного и религиозного зодчества на протяжении более двух тысячелетий. Книга объясняет формальный язык… Подробнее  Купить за 660 руб

Другие книги по запросу «ФОРМАЛЬНЫЙ ЯЗЫК» >>

Формальный язык


Формальный язык в математической логике, информатике и лингвистике — множество конечных слов над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык строится из множеств символов, функций и отношений вместе с их арностью, а также множества переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.


1. Определение
Формальный язык может быть определён по-разному, например:
Словами, распознаваемыми некоторым конечным автоматом.
Словами, порождёнными БНФ-конструкцией.
Словами, порождёнными регулярным выражением.
Простым перечислением слов, входящих в данный язык.{n}} означает, что a {\displaystyle a} повторяется n {\displaystyle n} раз;


2. Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что L 1 {\displaystyle L_{1}} и L 2 {\displaystyle L_{2}} являются языками, определёнными над некоторым общим алфавитом.
Дополнение языка L 1 {\displaystyle L_{1}} содержит все слова алфавита, которые не содержатся в L 1 {\displaystyle L_{1}}.
Объединение L 1 ∪ L 2 {\displaystyle L_{1}\cup L_{2}} содержит все слова, содержащиеся в L 1 {\displaystyle L_{1}} или в L 2 {\displaystyle L_{2}}.
Смешение L 1 {\displaystyle L_{1}} и L 2 {\displaystyle L_{2}} содержит все слова, которые могут быть записаны в форме v 1 w 1 v 2 w 2. v n w n {\displaystyle v_{1}w_{1}v_{2}w_{2}.v_{n}w_{n}}, где n ≥ 1 {\displaystyle n\geq 1} и v 1., v n {\displaystyle v_{1}.,v_{n}} являются такими словами, что связь v 1.{*}} содержит все слова, которые могут быть записаны в форме w 1 w 2. w n {\displaystyle w_{1}w_{2}.w_{n}}, где w i {\displaystyle w_{i}} содержится в L 1 {\displaystyle L_{1}} и n ≥ 0 {\displaystyle n\geq 0}. Следует помнить, что это включает и пустое слово ϵ {\displaystyle \epsilon }, так как n = 0 {\displaystyle n=0} допустимо по условию.
Конкатенация сцепление L 1 L 2 {\displaystyle L_{1}L_{2}} содержит все слова, удовлетворяющие форме v w {\displaystyle vw}, где v {\displaystyle v} — это слово из L 1 {\displaystyle L_{1}}, а w {\displaystyle w} — слово из L 2 {\displaystyle L_{2}}.
Правое отношение L 1 / L 2 {\displaystyle L_{1}/L_{2}} содержит все слова v {\displaystyle v}, для которых существует слово w {\displaystyle w} в L 2 {\displaystyle L_{2}} такое, что v w {\displaystyle vw} находилось в L 1 {\displaystyle L_{1}}.
Пересечение L 1 ∩ L 2 {\displaystyle L_{1}\cap L_{2}} содержит все слова, содержащиеся и в L 1 {\displaystyle L_{1}}, и в L 2 {\displaystyle L_{2}}.

Дата публикации:


05-16-2020

Дата последнего обновления:


05-16-2020

Преимущества изучения формальных языков | Статья в журнале «Молодой ученый»

Библиографическое описание:


Смирнова, А. Ю. Преимущества изучения формальных языков / А. Ю. Смирнова. — Текст : непосредственный // Молодой ученый. — 2020. — № 17 (307). — С. 29-32. — URL: https://moluch.ru/archive/307/69233/ (дата обращения: 13.08.2021).



Человек, который хочет начать программировать, обращается в интернет, с вопросом: «С чего начать изучение программирования?» В данной анализируется, какие преимущества может получить программист, изучив формальные языки как до освоения первого языка высоко уровня, так и после.

Ключевые слова: язык, язык программирования, правило грамматики, синтаксис языка

В современном мире информационно-компьютерные технологии используются повсеместно. Вследствие этого есть потребность как в самих технологиях, так и в людях, программистах, которые создают программные продукты или их поддерживают. [1] Профессия программиста набирает всё большую популярность, поскольку актуальна и обладает низким порогом вхождения.

Человек, который хочет начать программировать, обращается в интернет, с вопросом: «С чего начать изучение программирования?» Большинство людей советуют начать с конкретного языка программирования, если быть точнее, с курсов по этому языку. [2] В случае, если вопросом интересуется ребёнок, то таким языком является Scratch, если интересуется взрослый, то в зависимости от интересующей его области программирования предлагается наиболее простой язык. Дополнительно советуют углублённо изучать информатику, математику и английский язык в школе и соответствующие им предметы в университете.

В данной статье рассматриваются основные понятия из области формальных языков, а также даётся ответ на вопрос, какие преимущества получит обучающийся, изучив данную область даже до освоения конкретного языка программирования высокого уровня.

Формальный язык — это созданный человеком, искусственный, язык, характеризующийся чёткими и однозначными правилами построения выражений и их интерпретации. [3] В основе формального, как и любого другого языка, лежит алфавит. Алфавит представляет собой конечный набор символов для обмена информацией. Далее описывается и синтаксис языка, т. е. правила построения конкретных выражений.

Наиболее эффективным способом формального описания языков программирования являются грамматики. [4] Грамматикой называется следующая четверка: терминальных символов, нетерминальных символов, правил грамматики и начального символа. Проведя параллель с вышеописанным, терминальные и нетерминальные символы составляют алфавит языка, стартовый символ так же принадлежит алфавиту, синтаксисом языка являются правила грамматики.

За счёт использования формальных грамматик можно описать любой язык программирования. [5] Если проанализировать все языки, можно заметить, что во всех есть некие общие конструкции, некоторые из которых приведены ниже:

  1. Операторы ветвления. Представляют собой выражение вида: if then else
  2. Операторы цикла. Отличаются от условных тем, что действия внутри повторяются до тех пор, пока выполняются определённые условия. Могут выглядеть, например, следующим образом: while {… }
  3. Операторы ввода и вывода. Предназначены для ввода или вывода данных в программу. Например, оператор вывода может выглядеть следующим образом: write ()
  4. Операторы для задания переменных или констант в программу.
  5. Операторы для написания функций или методов

Из вышеприведенного анализа можно поговорить о преимуществах изучения формальных языков.

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

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

Независимо от времени обучения, знание формальных языков позволяет:

  1. Получить информацию о базовых конструкциях языка, а следовательно, сократить число ошибок связанных с непониманием базовых конструкций
  2. Получить более глубокое представление о работе компиляторов, трансляторов, интепретаторов.
  3. Получить базовую информацию, необходимую для написания собственного языка программирования или среды разработки
  4. Сократить время освоения новых языков, о чём было сказано выше.

Поговорив о преимуществах, следует отметить и недостатки, которые так же важно учитывать:

  1. Изучение формальных языков не подходит для детей. Дети больше приспособлены для обучения в игровой форме, что реализует язык Scratch. К сожалению, формальные языки берут свою основу в математике, что для юных обучающихся может показаться достаточно сложным.
  2. Могут оттолкнуть взрослого обучающегося. Такая вероятность существует из-за того, что формальные конструкции покажутся слишком сложными и неинтересными, из чего человек может сделать вывод, что и языки программирования будет очень сложно освоить.

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

Литература:

  1. Университет Синергия [Электронный ресурс] / Образование// Образование по специальности /// Актуальность профессии программист в 21 веке. Режим доступа: https://synergy.ru/about/education_articles/speczialnosti/kakie_programmisty_naibolee_vostrebovany
  2. Как стать программистом [Электронный ресурс] / Как стать программистом с нуля самостоятельно. Режим доступа: http://itman.in/kak-stat-programmistom-s-nulya-samostoyatelno/
  3. Мультиурок [Электронный ресурс] / Формализованные (формальные) языки. Режим доступа: https://multiurok.ru/files/formalizovannyie-formal-nyie-iazyki.html
  4. Афанасьев А. Н. Формальные языки и грамматики: Учебное пособие. — Ульяновск: УлГТУ, 1997. — 84с.
  5. Братчиков И. Л. Синтаксис языков программирования / Под ред. С. С. Лаврова. — М.: Наука, 1975. — 262с.

Основные термины (генерируются автоматически): язык, язык программирования, правило грамматики, синтаксис языка, изучение программирования, преимущество.

Формальная семантика языков программирования

Сводка

Формальная семантика языков программирования предоставляет основные математические методы, необходимые для тех, кто начинает изучение семантики и логики языков программирования. Эти методы позволят студентам изобретать, формализовать и обосновывать правила, с помощью которых можно рассуждать о различных языках программирования. Хотя лечение является элементарным, некоторые из затронутых тем взяты из недавних исследований, в том числе жизненно важная область совпадения.Книга содержит множество упражнений, от простых до мини-проектов. Начиная с базовой теории множеств, структурная операционная семантика вводится как способ определения значения языков программирования и связанных с ними методов доказательства. Денотационная и аксиоматическая семантика проиллюстрирована на простом языке while-программ, и приведены доказательства эквивалентности операционной и денотационной семантики, а также правильности и относительной полноты аксиоматической семантики. Включено доказательство теоремы Гёделя о неполноте, которое подчеркивает невозможность достижения полностью полной аксиоматической семантики.Он поддерживается приложением, в котором дается введение в теорию вычислимости на основе while-программ. После изложения теории предметной области рассматриваются семантика и методы доказательства для нескольких функциональных языков. Самый простой язык — это рекурсивные уравнения с оценкой как по значению, так и по имени. Эта работа распространяется на языки с высшими и рекурсивными типами, включая обработку нетерпеливых и ленивых лямбда-исчислений. Повсюду подчеркивается связь между денотационной и операционной семантикой, и приводятся доказательства соответствия между операцией и денотационной семантикой.Обработка рекурсивных типов — одна из наиболее сложных частей книги — основана на использовании информационных систем для представления доменов. Книга завершается главой о языках параллельного программирования, сопровождаемой обсуждением методов определения и проверки недетерминированных и параллельных программ.

Твердый переплет

Из печати

ISBN: 9780262231695
384 с. | 7 дюймов x 9 дюймов

Мягкая обложка

70 долларов.00

Икс

ISBN: 9780262731034
384 с. | 7 дюймов x 9 дюймов

Авторы

Глинн Винскель

Глинн Винскель — профессор компьютерных наук Орхусского университета, Дания.

языков программирования: синтаксис

языков программирования: синтаксис

COS 441- Синтаксис — 6 февраля 1996 г.

Язык программирования — это формальный язык, используемый для передачи алгоритмов.
как от программиста к программисту, так и от программиста к машине.Формальный
язык состоит из:

  • набор символов;
  • правила формирования срока;
  • правила преобразования терминов в термины.

Некоторые языки программирования общего назначения включают C, C ++, PASCAL и Ada.
Некоторые специальные языки: TEX, Post-Script, JAVA Byte-Code, TCP / IP и
возможно, WIN32S API.

Чтобы эффективно использовать язык программирования, мы должны изучать и понимать его с помощью
три перспективы:

  • Синтаксис — набор символов и правил для формирования терминов.
  • Семантика — правила преобразования терминов в термины.
  • Прагматика — использование определенных конструкций языка.

Вот три способа выражения «увеличить i-й элемент массива x»
на разных языках программирования.

(а) x [i] = x [i] + 1; [C]
(b) (vector-set! x i (+ (vector-ref x i) 1)) [Схема]
(c) x [i] = x [i] + 1; [Джава]

Эти выражения имеют примерно следующую семантику.

(a) если i находится в пределах x, то x [i]

Несмотря на очевидное сходство выражений C и Java, язык Java
семантика выражений ближе к Scheme, чем C.

Теперь рассмотрим выражение «приращение x [0] через x [N]». В C мы пишем:

 
 
для (i = N; i> = 0; i--)
    х [я] = х [я] + 1;
 
В Scheme мы пишем совсем другое:
(определите natural-foreach
   (лямбда (ж п)
      (cond ((> = n 0) (начало
                         (ж п)
                         (натуральный-foreach f (- n 1)))))))
(определите inc-x (lambda (i)
   (векторный набор! x i (+ (vector-ref x i) 1))))
(естественная складка пр-х N)
 
Наконец, в Java мы, вероятно, напишем что-то похожее (с
 тот же синтаксис), что и в C.Прагматика C / Java предполагает использование итераций, в то время как
 в схеме мы используем рекурсию.
 Большинство курсов по языкам программирования изучают различные языки программирования,
 в основном охватывают синтаксис, а на семантику остается совсем немного времени. Вместо,
 мы будем использовать только Scheme, что позволит нам быстро перейти к семантическому
 вопросы. Мы будем использовать официальных переводчиков и потратим немного времени на поиск
 по прагматическим вопросам.
 Этот курс НЕ научит вас:
  •  любые практические языки программирования; ни
  •  как реализовать высокопроизводительные языки программирования.
 Но он научит вас:
  •  как быстро выучить новый язык программирования;
  •  как выбрать язык программирования под ту или иную задачу;
  •  как проектировать и строить интерпретаторы;
  •  больше о языках программирования, чем разработчики самых популярных
     языки когда-нибудь узнают.
 Синтаксис 
Чтобы упростить понимание и анализ синтаксиса языка, мы разделяем
 синтаксис на трех уровнях: лексические элементы, контекстно-свободный синтаксис,
 и контекстно-зависимый синтаксис.В английском языке буквы образуют слова, образующие предложения. В языках программирования
 символы образуют токены, которые образуют термины. Токены — это лексические элементы.
 Лексический анализ 
Ниже приведены некоторые токены Scheme:
  •  строка цифр
  •  «персонажи …»
  •  ‘`#f #t’ () # \ a
  •  строки букв, цифр и символов, например — + * — @ $ и т. Д.
Последний элемент этого списка называется «идентификаторами». Синтаксис схемы для
 идентификаторы более либеральны, чем у многих других языков; Например,
  + ,  a + b  и  -a * 2  — все идентификаторы.
  Помимо:  Комментарии обычно удаляются языковым процессором.
 при лексическом анализе; то есть пока языковой процессор преобразует
 поток вводимых символов в поток токенов. Комментарии схемы начинаются
 с точкой с запятой и до конца строки.
 Контекстно-свободный синтаксис 
Рассмотрим простой язык запросов. На английском языке мы
 определить запрос как список слов, НЕ запрос или (запрос И запрос).
 Чтобы быть более точным, давайте определим запросы, используя математику (в частности, теорию множеств):
Запрос = {w1... wN | w1, ..., wN в Word}
      U {НЕ q | q в запросе}
      U {(q1 И q2) | q1, q2 в запросе}
 
Для определения контекстно-свободного синтаксиса языков программирования мы часто используем специальный
 язык более лаконичный. Он называется BNF (Backus Naur Form):
Запрос :: = Word * | НЕ запрос | (Запрос И Запрос)
 
В терминалах BNF токены — это символы, которые не отображаются слева от
 оператор :: =. В приведенном выше примере И, (,) и НЕ являются терминалами.
 Запрос — единственный нетерминальный.Ну, почти.
 Word — это действительно нетерминал, который мы не удосужились определить.
BNF может описывать только контекстно-свободные языки. Следующий набор условий невозможен
 описывать в БНФ.
Квери = {w1 ... wN | w1, ..., wN в Word}
      U {НЕ q | q в Квери}
      U {(q1 И q1) | q1 в Квери}
 
AND-Kwery требует, чтобы обе его руки были одинаковыми. Этот набор условий
  контекстно-зависимый : выбор Kwery для размещения в дыре
 члена  (q1 AND [])  (где [] обозначает отверстие)
 не может быть сделано без знания контекста, окружающего дыру.В частности, мы должны знать, что такое q1, потому что для получения действительного значения Kwery
 мы можем поместить в отверстие только q1.
 Чтение 
  •  Маленький интриган (вся книга)
  •  EOPL (Основы языков программирования) Глава 1
 Упражнение 
  •  Напишите программу на C, которая объявляет массив x, инициализирует его и увеличивает
     каждый элемент.
  •  Напишите программу на схеме, которая делает то же самое.
  •  Напишите программу на C, которая делает это с помощью рекурсии.
% PDF-1.3
 %
 417 0 объект>
 эндобдж
xref
 417 75
 0000000016 00000 н.
 0000003159 00000 н.
 0000003358 00000 п.
 0000001796 00000 н.
 0000003409 00000 н.
 0000003537 00000 н.
 0000004010 00000 н.
 0000004052 00000 н.
 0000004197 00000 н.
 0000004342 00000 п.
 0000004537 00000 н.
 0000004942 00000 н.
 0000012167 00000 п.
 0000012567 00000 п.
 0000012854 00000 п.
 0000013219 00000 п.
 0000017930 00000 п.
 0000018315 00000 п.
 0000018551 00000 п.
 0000018604 00000 п.
 0000018914 00000 п.
 0000023051 00000 п.
 0000023444 00000 п.
 0000023639 00000 п.
 0000024182 00000 п.
 0000024735 00000 п.
 0000025166 00000 п.
 0000025917 00000 п.
 0000026664 00000 н.
 0000027264 00000 н.
 0000027689 00000 п.
 0000035245 00000 п.
 0000035651 00000 п.
 0000037953 00000 п.
 0000038320 00000 п.
 0000039323 00000 п.
 0000039808 00000 п.
 0000047235 00000 п.
 0000047622 00000 п.
 0000047989 00000 п.
 0000048042 00000 п.
 0000048381 00000 п.
 0000048584 00000 н.
 0000048727 00000 н.
 0000049319 00000 п.
 0000049549 00000 п.
 0000049907 00000 н.
 0000055972 00000 п.
 0000056352 00000 п.
 0000056529 00000 п.
 0000056742 00000 п.
 0000057578 00000 п.
 0000057869 00000 п.
 0000057944 00000 п.
 0000058148 00000 п.
 0000058604 00000 п. O} p_H_Z` #%
 Модули обучения Школы информатики: Семантика формального языка программирования 
 Семантика формального языка программирования 
 Домашняя страница курса информатики CS4 / MSc / TPG, осень 2007 г.
Лектор курса: Джон
 Лонгли.
 Мне можно написать по адресу [email protected].
 Я живу в JCMB, комн. 2603 (тел. 505140).
 Ссылка на оф.
 Модуль
 Страница описания курса.
 Лекции проходят в Appleton Tower Room 5.03 по вторникам и пятницам в 9 утра.
 начиная с пятницы 21 сентября.
  В пятницу, 5 октября, лекций не будет. 
 Я устрою так, чтобы в конце курса уместилась еще одна лекция.
 Цели конечно 
Формальная семантика для языка программирования — это математически точная
 описание предполагаемых , что означает  каждой конструкции в языке.В отличие от формального  синтаксиса  для языка, который сообщает нам, какой
 последовательности символов — это правильно составленные программы,
 формальная семантика   говорит нам, что программы на самом деле будут делать
 когда мы их запускаем.
 Идеи семантики важны для разработчиков языков,
 составители компиляторов и программисты;
 они также служат основой для математических доказательств правильности  
 программ. Цель этого курса — познакомить с различными
 подходы к формальной семантике (операциональная, денотационная и аксиоматическая),
 иллюстрируя их с помощью очень простого императива, функционального,
 и объектно-ориентированные языки.
 Предпосылки 
Формально никакие предварительные знания семантики языка программирования не будут
 предполагается, хотя после выполнения семантики языка UG3 
 и внедрение  конечно было бы преимуществом.
 По сравнению с курсом LSI,
 в нынешнем курсе будет меньше на реализацию
 техники и многое другое по логике и теории.
 Между двумя курсами будет некоторое совпадение
 (в основном основной материал по семантике императивных языков),
 хотя я, наверное, буду кататься довольно быстро
 над этим материалом в первых лекциях.
 Курс также потребует немного знаний в обязательном порядке,
 функциональные и объектно-ориентированные языки. Если вы использовали Java
 или, например, C ++, который позаботится о первом и последнем из них.
 Кроме того, некоторый опыт работы с типизированным функциональным языком, таким как
 Желателен стандартный ML или Haskell (например, CS3
  Функциональное программирование и спецификация, курс ).
 Если у вас нет этого опыта, возможно, вам понадобится
 сделайте небольшое дополнительное исследование.Некоторые задания могут включать в себя написание небольших фрагментов
 Стандартный код в стиле ML.
 Наконец, курс носит чисто математический характер.
 Никаких особых математических знаний не ожидается, но некоторые естественные
 математические способности будут полезны, и вам нужно будет почувствовать
 в целом комфортно работать с математическими понятиями и обозначениями.
 Программа 
(не обязательно в том порядке, в котором будут затронуты темы)
  Общие понятия: 
 Синтаксис против семантики.Формальная и неформальная семантика.
 Операционный, денотационный и аксиоматический подходы.
 Адекватность, полная абстракция и полнота.
  Операционная семантика: 
 Семантика большого шага для простого императивного языка:
 определение отношения оценки с помощью формальных правил.
 Расширения с ошибками времени выполнения, побочными эффектами и вводом / выводом.
 Соглашения об исключениях и состояниях.
 Понятия наблюдательной эквивалентности.
 Сравнение динамического и статического масштабирования; статическая семантика.
 Простой язык с блочной структурой.Тип безопасности.
 Статическая семантика простого объектно-ориентированного языка.
  Денотационная семантика: 
 Денотационная интерпретация императивного языка.
 Различия между операционной и денотационной семантикой.
 Адекватность и композиционность.
 Полные частичные заказы, рекурсия и фиксированные точки.
 Монотонность и непрерывность как свойства вычислимых операций.
 Простой функциональный язык; его денотационная и операционная семантика.
 Звонок по имени в сравнении с вызовом по значению.Статическая и динамическая привязка.
  Дополнительные темы: 
 Введение в семантику игры.
 Денотационная семантика объектно-ориентированных языков.
 Оценка 
Оцениваемая курсовая работа будет состоять из трех листов с упражнениями, которые будут
 выдается во время курса. Они будут состоять из карандаша и бумаги.
 упражнения. Сроки подачи заявок будут следующими:
  •  Лист 1: пятница, 12 октября, 9 утра (на лекции, если хотите).
  •  Лист 2: вторник, 13 ноября, 9:00
  •  Лист 3: вторник, 14 декабря, 16.00
Для студентов CS4 и MSc каждый лист упражнений будет содержать 10%
 общий зачет курса; на экзамен возьмут 70%.
 Для аспирантов оценка будет основываться на любых частях
 листы упражнений, которые вы выполняете, плюс участие в лекциях.
 Рекомендуемая литература 
Следующее будет подходящим в качестве основного текста для курса.
 Однако в предыдущие годы студенты на практике обнаружили, что
 конспектов лекций было достаточно.
  •  Г. Винскель,  Формальная семантика языков программирования:
     введение     , MIT Press, 1993.
Также рекомендуется следующее, вероятно, все еще лучшее
 пример существующего формального определения языка.
 Хотя это не совсем легкое чтение ….
  •  Р. Милнер, М. Тофте, Р. Харпер и Д. Маккуин,
      Определение стандарта ML (пересмотренное) , MIT Press, 1997.
 Конспект лекций и раздаточный материал 
(Мета-заметка: одна лекционная заметка обычно содержит материал для одной лекции,
 но я не буду строго придерживаться практики одной лекции за лекцию.)
 ВНИМАНИЕ! Для конспектов лекций и листов с упражнениями, которые я не передал
 пока нет в лекциях, вот версии, которые я использовал в прошлом году.
 В этом году они, вероятно, не сильно изменятся, но это не гарантировано.
 Как только я раздаю лекцию или лист упражнений, версия
 здесь гарантированно будет версия этого года.
  •  Примечание 1. Что такое формальная семантика?
  •  Примечание 2: Цели формальной семантики
  •  Примечание 3: Операционная семантика
     повелительный язык
  •  Примечание 4: Семантика IMP: мелкие детали
  •  Примечание 5: язык с ошибками времени выполнения
  •  Примечание 6: язык с побочными эффектами
  •  Примечание 7: Статическая семантика: область видимости и
     правила набора
  •  Примечание 8: Механизмы оценки и связывания
  •  Примечание 9: Расширенный пример: фрагмент Java
  •  Примечание 10: Введение в денотационную семантику
  •  Примечание 11: Соответствие и его последствия
  •  Примечание 12: Полные частичные заказы (CPO)
  •  Примечание 13: простой функциональный язык
  •  Примечание 14: Операционная семантика PCF
  •  Примечание 15: Полная абстракция и универсальность
  •  Примечание 16: Дополнительные типы данных и рассуждения о
     программы
  •  Примечание 17: Введение в семантику игры (в печати)
 Что такое формальное строгое определение языка программирования? 
 Я думаю, что очень сложно дать определение, которое было бы одновременно общим, формальным и не слишком общим.И я не думаю, что видел попытки. Тем не менее, это попытка математического определения.
 Язык программирования   состоит из набора программ $ P $ таких, что каждый элемент $ P $ конечен и для каждого элемента $ p $ из $ P $ существует тройка $ m (p) = (I, O, f) $ такое, что $ I $ и $ O $ — множества, а $ f $ — отношение между $ I $ и $ O $, такое, что для каждого $ I $ существует по крайней мере один связанный $ O $.
 Идея состоит в том, что $ m (p) $ — это значение программы $ p $, $ I $ — это набор входных данных, $ O $ — это набор результатов, $ f $ дает для каждого входа набор возможные результаты, которые могут возникнуть в результате этого ввода.
 Обратите внимание, что элементы $ I $ и $ O $ не обязательно должны быть конечными. Ограничение конечности элементов $ P $ является произвольным, и я помещаю его только туда, потому что не думаю, что язык программирования, имеющий бесконечно большие программы, был бы очень полезен. Ограничение, заключающееся в том, что для каждого входа должен быть хотя бы один результат, является условием здоровья «без чудес». Это означает, что нам нужен один или несколько результатов для представления незавершенности, по крайней мере, когда программа не может (или не должна) завершаться для некоторых входов.
 Вот три возражения против этого определения.
  Это слишком общее:  Одна проблема с этим определением (и я подозреваю, что его можно улучшить) состоит в том, что многие вещи, которые мы не считаем языками программирования, могут быть приспособлены к нему. Вот два примера
  •  HTML (без JavaScript) — это язык программирования по этому определению. Некоторые люди скажут, что это неправильно, потому что HTML — это язык форматирования, а не язык программирования.
  •  Мы можем представить себе язык программирования, содержащий программу $ h $ такую, что $ m (h) = (T, \ {true, false \}, f) $, где $ T $ — это множество всех машин Тьюринга, а $ f $ отображает $ t \ in T $ в $ true $, если $ t $ останавливается при запуске на пустой ленте, и отображает $ t $ в $ false $, если $ t $ не останавливается при запуске на пустой ленте; некоторые люди скажут, что это не язык программирования.
 В ответ вы можете ввести дополнительные ограничения по мере необходимости. Например, вы можете определить набор всех языков программирования, полных по Тьюрингу, сделав соответствующие уточнения.
  Это недостаточно общее:  Для некоторых вещей, которые кажутся языками программирования, может потребоваться некоторая изобретательность, чтобы встроить их в эту структуру. Например, для вероятностного языка программирования результатами должны быть распределения вероятностей. Лучше всего отказаться от этого определения и использовать подходящее обобщение отношений.Аналогичные замечания применимы к квантовым вычислениям.
 Ответ состоит в том, что приведенные примеры показывают, что может быть неудобно подогнать некоторые языки под определение.
  Упускается из виду, что у языков программирования есть варианты:  Реальные определения языков программирования часто параметризованы. Например, в C  int i = 10 * 1000 * 1000 * 1000;  имеет неопределенное поведение в некоторых реализациях и хорошо определено в других; это зависит от выбора, который остается за исполнителем.Мое определение не отражает эту идею.
 Ответ состоит в том, что легко обобщить определение, добавив еще один вход в функцию $ m $, представляющую вариант языка, или (по Каррингу) думать о языке, подобном C, как о функции от набора вариантов до язык того типа, который определен здесь.
 Три книги, которые исследуют идеи в этом направлении:
  •  Хоар и Хе,  Объединение теорий программирования 
  •  Francez,  Программа проверки 
  •  Hehner,  Практическая теория программирования 
 Являются ли все возможные языки программирования формальной системой? 
 Конечно, да, и в основном они описаны как есть.
 Фактически, большинство языков программирования были определены с использованием машины Тьюринга, которые не являются формальной системой, которую вы определили, но они представляют собой своего рода модель вычислений, определяемую с использованием формального языка. Тогда грамматика, аксиомы или сложное правило вывода (как ожидается для формальной системы) не требуются.
 Формальную систему можно рассматривать как подмножество машины Тьюринга с дополнительными свойствами. Скажем иначе, вы можете определить язык программирования с использованием машины Тьюринга в качестве модели вычислений, но не полностью соответствовать определению формальной системы.
 Я хотел бы добавить, что правило вывода, необходимое для определения формальной системы, — это больше, чем простое правило (с которым вы можете столкнуться, например, в C или, проще говоря, в ASM), но мы должны гарантировать, что любая сложная формулировка этого правила может быть разрешима. Значит, у нас должно быть правило вывода, которое опирается на прочную логическую основу.
 Принимая во внимание аксиому, нам снова нужно больше, чем набор из  начальных фактов , разделяющих истину среди программ, но мы наиболее гарантируем с математической точки зрения, что эти аксиомы, смешанные с правилом вывода, предоставят нам вычислительную структуру, которая должна быть согласованной. (аксиомы, смешанные с правилом вывода, не должны приводить к неожиданному поведению программы или противоречию) и завершены (никакая формула, выраженная с использованием аксиомы и правила вывода, не должна быть неразрешимой).
 В большинстве случаев эти требования применяются не к самому языку, а к его системе типов, чтобы обеспечить безопасность во время компиляции за счет полноты и согласованности, которые, как было сказано ранее, вытекают из правил вывода и аксиомы (Истина по построению это вам нравится).
 В заключение, все языки программирования являются формальными языками, как сама программа пишется с использованием формального языка, но они не обязательно должны быть формальной системой, вопреки математической теории, такой как теория чисел, абстрактная алгебра, теория категорий, которые также выражаются формальным языком, но на этот раз с целью сформировать формальную систему.
 Почему так важно функциональное программирование.
 Формальная семантика языков программирования 
 Формальная семантика языков программирования
 
 Вольфганг Шрайнер 
 326.514, SS 1999, начало: 11.3.1999 
, чт 16: 30-18: 00, T1010
 
 Хотя синтаксис   языка программирования всегда формально
 уточнил, не менее важный аспект определения его
  означает, что  часто оставляется для естественного языка, что неоднозначно и
 оставляет вопросы открытыми.Чтобы понять неотъемлемые свойства
 язык (например, для создания компилятора), мы должны иметь более глубокий
 понимание. Цель формальной семантики — выявить
  сущность  языка под его синтаксической поверхностью.
 В этом курсе представлены некоторые основные методы определения значения языков.
 и программы и обсуждает их отношения:
  Операционная семантика 
 Язык программирования определяется
  правил редукции , которые описывают, как начальное состояние
 программа шаг за шагом переводится в конечное состояние.Это мнение
 наиболее полезно для понимания динамического поведения языка, например,
  для построения интерпретатора .
  Денотационная семантика 
 Язык программирования определяется
  оценочная функция , отображающая программу в математический объект
 что считается его смыслом. Этот вид наиболее полезен для
 понимание внутренней логики языка, например, для рассуждений 
 о его свойствах .
  Аксиоматическая семантика 
 Язык программирования определяется
  утверждений о правильности , которые описывают, как делать выводы о
 интерфейс ввода / вывода программы.Этот вид наиболее полезен для
 понимание внешних эффектов языка, например,  для проверки
 программа .
 Ожидается, что студенты разработают небольшие упражнения и представят их в
 учебный класс. Это включает разработку спецификаций семантики исполняемых файлов в
 система  CafeOBJ .
  Денотационная семантика I 
 (на основе Шмидта)
  Операционная семантика 
 (Бумажные копии Винскеля)
  •  Операционная семантика IMP
  •  Доказательство эквивалентности языковых конструкций.
  •  Денотационная семантика IMP.
  •  Эквивалентность семантик.
  Денотационная семантика II 
 (на основе Шмидта)
  Языки с контекстами 
 (на основе Шмидта)
  Аксиоматическая семантика 
 Язык утверждений, семантика утверждений, правила проверки, корректность.
  Принципы языкового дизайна 
 Языки с типами, абстракцией, параметризацией, соответствием,
 квалификация.
  Разные темы 
 Продолжения, исключения, возврат, сопрограммы, неограниченное ветвление.
  Императивный интерпретатор (PostScript) 
 Разработайте небольшой императивный язык программирования, разработайте его денотационный
 семантика и реализовать интерпретатор для этого языка.
  Решение Java (zip-файл) 
 Автор: Юрген Хартл.
  Глинн Винскель 
  Формальная семантика языков программирования —
 Введение , Основы вычислительной серии, MIT Press,
 Кембридж, Массачусетс, 1994.
  Дэвид А. Шмидт 
  Денотационная семантика — Методология для
 Развитие языка , Аллин и Бэкон, Бостон, Массачусетс, 1986.
  Дэвид А. Шмидт 
  Структура типизированных языков программирования ,
 Основы вычислительной серии, MIT Press,
 Кембридж, Массачусетс, 1994.
 
 Поддержкой: Wolfgang Schreiner
 
 Последняя модификация: 2 июля 1999 г. 
 [Вверх]
 [RISC-Linz] [Университет]
 [Поиск]
 .
Добавить комментарий 
Ваш адрес email не будет опубликован. Обязательные поля помечены *