Евгений Зуев: Редкая профессия

Смысл правил разрешения неоднозначностей сводится, по существу, к поразительной фразе, простодушно выведенной в "Зеленой книге": "если конструкция выглядит как объявление, то это и есть объявление. В противном случае это оператор". Иными словами, чтобы разрешить неоднозначность, следует рассмотреть всю конструкцию целиком; фрагмент " T(a) " для анализа недостаточен — за ним сразу может следовать либо точка с запятой, тогда выбор делается в пользу объявления, либо "что-то еще". Например, вся конструкция может выглядеть как " T(a)→m = 7; " или " T(a)++; " — это, конечно, операторы (точнее, операторы-выражения, в терминах стандарта). Ну а как понимать следующее: " T(e)[5]; " или " T(c)=7; "? А это, будьте уверены, еще не самые разительные примеры — загляните в разд. 6.8 Стандарта.

Человеку хорошо, он ко всему привыкает, рано или поздно он разберется, но как заставить анализатор понимать эту чехарду? Пока он не доберется до точки с запятой, он, в общем случае, ничего не сможет сказать о конструкции. Друзья, не пишите объявления, которые невозможно отличить от операторов! Пожалейте компилятор, ему же тяжело! Кроме того, можно запросто ошибиться и самому…

Несколько дней прошли в бесплодных попытках выразить неоднозначности на входном языке YACC. Выход был похоже, только в организации просмотра вперед, причем на заранее не известное количество лексем. Алгоритм разбора, заложенный в YACC, этого делать не умеет. В принципе известны и доступны системы, в которых заявлена подобная возможность, однако мы были ограничены требованием: синтаксический анализатор писать на YACCе, более того, на его версии, сделанной в одном европейском университете… Пришлось пойти на ухищрения и "сломать" классическую схему разбора: делать предварительный анализ еще на уровне разбора лексем и, встретив левую скобку после имени типа (а еще пойди распознай, что идентификатор — имя типа, а не какой-то другой сущности!), "отменять" автоматический анализ и организовывать "ручной" перебор последующих лексем, складывая их про запас в буфер.

Спасибо, в "Зеленой книге" подсказали схему такого анализа. Не знаем, как и благодарить, сами бы ни за что не придумали…

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

Синтаксис языка Си++ неудобен еще и в другом отношении. Если говорить коротко, то прямое использование в формальном описании одного из базовых синтаксических понятий — идентификатора — приводит к тому, что YACC расценивает грамматику языка как некорректную и на ее основе не может построить синтаксический анализатор. Для традиционных языков синтаксическому анализатору для разбора конструкции достаточно информации о том, что в данной позиции этой конструкции может (или должен) находиться идентификатор. Более простые языки сконструированы так, что семантика идентификатора не влияет на корректность синтаксического разбора. Вид программной сущности, обозначаемой этим идентификатором (подпрограмма, переменная, имя типа, исключение, метка и т.п.), смысл данного конкретного вхождения (объявление или использование) — все это выявляется далее, как правило, являясь предметом следующей фазы компиляции — семантического анализа.

Для языка Си++ такая схема не проходит. Чтобы быть в состоянии синтаксически распознать многие конструкции, требовалась семантическая интерпретация имени. Иными словами, на вход синтаксическому анализатору следовало поставлять не абстрактную лексему "идентификатор", а результат анализа того, что именно представляет собой этот идентификатор: "имя типа", "новое имя в объявлении", "имя не-типа в выражении" и т.д. Заметим, что синтаксическому анализатору для Java — непосредственного потомка Си++ — вполне хватает понятия идентификатора без каких-либо уточнений.

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