Пишем транслятор или немного о Фортране

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

Скриптовый язык для описания бизнес-логики создавался программистами, не знакомыми с теорией формальных языков. Сей прискорбный факт подтвержден отсутствием описания грамматики как и отсутствием понимания сего понятия у поддерживающих имеющийся транслятор. К счастью, есть описание уровня пользователя, то есть, прикладного программиста. Сам же язык смахивает на помесь язык командных пакетов DOS/Windows и Фортрана, что не мудрено. Язык, в том числе программирования - прямое отражение культуры.

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

Почему вспомнился старый и даже временами добрый Фортран?

Фортран был пионером языков высокого уровня и относится к их второму поколению (в качестве лирики на эту тему см. "Вместо послесловия" к книге "Софтостроение изнутри"). Фортран первоначально создавался, по сути, как макронадстройка над мнемокодом ЭВМ той эпохи (также второе поколение). Представлений о теории формальных языков его создатели не имели, анализаторы делались ad hoc (по месту) и руками. Таким образом, Фортран не влезает ни в LL(1), ни даже в LALR(1)-разборы (1, 2, 3). Как следствие:

  • анализаторы пишутся руками все так же "по месту", полное описание для lex/yacc отсутствует;
  • разрешение LALR-противоречий отодвигается на уровень семантического анализа, а то и на время исполнения. Примеры подобных коллизий приводятся, в том числе, в книге "Ошибки-ловушки при программировании на фортране".

Перечисленное и есть формальный признак отнесения ко второму поколению языков. Начиная же с третьего, сначала проектируется контекстно-свободная грамматика, как правило LL(1), и только потом строится транслятор. Сложность реализации самого транслятора - другой вопрос, но Фортран в этом плане представляет меньше проблем, чем многие языки третьего поколения (отсюда его эффективный двоичный код для вычислительных задач). Суть не в этом.

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

energy := mass * speed ^ 2 / 2

мы получим однозначный ответ, являются ли идентификаторы energy, mass и speed переменными (и какого уровня видимости), константами или именами функций. А также их тип.

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

Классика жанра отложенных коллизий на Фортране

DO 3 I=1.3

Здесь вместо точки должна была стоять запятая, регламентирующая выполнение цикла от 1 до 3. Транслятор же воспринял конструкцию, как оператор присваивания. Это фрагмент реального кода из программы, управлявшей полетом американского космического корабля на Венеру. Ошибка, которая отлавливается языками третьего поколения ещё на этапе компиляции, привела к неудаче в запуске (случай описан у Майерса в книге "Надежность программного обеспечения", М. Мир, 1980).

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