Понедельник, 21.09.2020, 22:14
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 9
Гостей: 9
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ

Формальное описание языков программирования
19.01.2016, 12:21

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

Одновременно с созданием BNF известнейший лингвист, философ и политический публицист Ноам Хомский создал свою теорию грамматики, известную как иерархия Хомского. В рамках этой теории грамматики и языки, их порождающие, делятся на четыре типа в зависимости от их условной сложности. К типу 3 относятся регулярные грамматики, которые являются наиболее строгими. К типу 2 относятся контекстно-свободные грамматики, которые можно описать посредством BNF.

К типу 1 относятся контекстно-зависимые грамматики, к типу 0 — неограниченные грамматики. Каждая следующая обладает большей выразительностью, чем грамматики предыдущих типов. Иерархия Хомского связана с вычислительной мощностью. Вычислительная система общего назначения способна распознавать фразы на любом языке с грамматикой типа 0. К этой категории вычислительных систем относятся машина Тьюринга и лямбда-исчисление. Конечные автоматы являются вычислительными системами типа 3.

Несколько лет спустя швейцарский ученый Никлаус Вирт, лауреат премии Тьюринга и создатель множества языков, описал синтаксис языка Pascal с помощью синтаксических диаграмм и расширенной формы Бэкуса — Наура, EBNF (Extended BNF). Эти нотации не являются более выразительными, чем BNF, однако в настоящее время они широко используются, так как существуют программы, автоматически генерирующие распознаватели синтаксиса по его заданному описанию.



Лингвист Ноам Хомский, создатель иерархии грамматик, носящей его имя.


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

Первой из предложенных была VDL (Vienna Definition Language), созданная в венской лаборатории IBM для формального определения языка PL/I. Она состоит из двух частей: транслятора, выстраивающего абстрактное синтаксическое дерево для программы на языке PL/I, и интерпретатора, который указывает, как следует исполнять или интерпретировать программу, соответствующую этому дереву. Эта семантика называется операционной семантикой и является крайне подробной. Так как язык PL/I очень объемен, беспорядочен и изобилует частными случаями, его формальная спецификация также очень объемна и сложна для понимания. За свои размеры она получила шутливое название VTD — Vienna Telephone Directory («Венский телефонный справочник»). Тем не менее создание этой спецификации стало важным достижением в данной области.

Работы в венской лаборатории были продолжены, и появилась вторая, улучшенная версия спецификации — VDM (англ. Vienna Development Method — венский метод разработки), содержащая несколько особых свойств для создания спецификаций императивных языков. Эта спецификация была создана в 1982 году как объединение точек зрения Динеса Бьёрнера и Клиффа Джонса, которые легли в основу двух школ программирования — датской и английской соответственно. VDM использовался для созданий спецификаций языков Pascal и Алгол-60, а также для подмножества языка Ада’79.

С другой стороны, выдающийся американский ученый Роберт Флойд в 1967 году показал, как можно оценить корректность программы с помощью утверждений (assertions), помещенных в определенные участки программы. Каждое утверждение — это логическая формула, устанавливающая некое отношение между переменными программы. Утверждение остается истинным по завершении программы и устанавливает связь между ее входными и выходными значениями. Метод Флойда улучшил и дополнил британский логик Чарльз Хоар, изложив его в виде набора аксиом и правил вывода, связанных с построением языков программирования, и дав определение аксиоматической семантике. В 1973 году Хоар и Вирт опубликовали аксиоматическую спецификацию подмножества языка Pascal. Во время работы над ней они обнаружили некоторые недостатки в языке и исправили их, создав новую, улучшенную версию Pascal. В следующем году Хоар и Лоуэр изучили возможность одновременного использования аксиоматической и операционной семантики. Эдсгер Дейкстра представил понятие слабейшего предусловия в 1973 году.



Дональд Кнут (слева) и Гэрман Цапф обсуждают свойства новой компьютерной типографики. Стэнфордский университет, Калифорния, 1980 год.


Существуют и другие способы описания семантики языка. В 1968 году силами Дональда Кнута, одного из самых уважаемых специалистов в области вычислительных систем, известного своим чувством юмора, была создана атрибутивная грамматика.

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

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

Категория: АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 529 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru