От абака к цифровой революции

Одновременно с созданием 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 году силами Дональда Кнута, одного из самых уважаемых специалистов в области вычислительных систем, известного своим чувством юмора, была создана атрибутивная грамматика.