Библиотека сайта rus-linux.net
Среда времени выполнения динамических языков и языки Iron
Глава 8 из книги "Архитектура приложений с открытым исходным кодом", том 2.
Оригинал: The Dynamic Language Runtime and the Iron Languages
Автор: Jeff Hardy
Перевод: Н.Ромоданов
8.4. Синтаксический анализ
Лексический анализатор языка IronPython находится в классе IronPython.Compiler.Tokenizer, а парсер — в классе IronPython.Compiler.Parser. Лексический анализатор представляет собой конечный автомат, написанный вручную, который распознает ключевые слова, операторы и имена языка Python и создает соответствующие лексемы. Каждая лексема сопровождается дополнительной информацией (например, значение константы или имени), а также для того, чтобы было проще вести отладку, указывается, где в исходном была найдена лексема. Затем парсер берет этот набор лексем и сравнивает их с грамматикой языка Python с тем, чтобы поверить, соответствует ли этот набор правильным конструкциям языка Python.
Синтаксический анализатор языка IronPython представляет собой синтаксический анализатор рекурсивного спуска вида LL(1) (LL(1) recursive descent parser). Анализатор будет анализировать входящую лексему и, если лексема допустима, вызвать функцию, либо будет возвращать ошибку, если это не так. Анализатор рекурсивного спуска собран из набора взаимно рекурсивных функций; в конечном итоге эти функции реализуют конечный автомат, в котором каждая новая лексема вызывает переход между состояниями. Точно также, как и лексический анализатор, парсер языка IronPython написан вручную.
С другой стороны в языке IronRuby используются лексический и синтаксический анализаторы, сгенерированные генератором анализаторов Gardens Point Parser Generator (GPPG). Парсер описан в файле Parser.y (Languages/Ruby/Ruby/Compiler/Parser/Parser.y), являющимся файлом в формате yacc, в котором на высоком уровне с помощью правил (rules), задающих грамматику, описана грамматика языка IronRuby. После этого генератор GPPG берет файл Parser.y и строит фактически используемые функции и таблицы парсера в результате получается парсер вида LALR(1), использующий в своей работе таблицы. Созданные таблицы представляют собой длинные массивы целых чисел, где каждое целое представляет собой состояние; в таблице по текущему состоянию и текущей лексеме определяется, какое состояние будет следующим. Анализатор рекурсивного спуска языка IronPython читается довольно легко, тогда как сгенерированный парсер языка IronRuby прочитать невозможно. Таблица переходов огромна (540 различных состояний и более 45 000 переходов), и вручную ее изменить практически невозможно.
В конечном счете, это компромисс разработки — парсер языка IronPython достаточно прост с тем, чтобы его можно было изменять вручную, но достаточно сложный, поскольку он скрывает структуру языка. Парсер языка IronRuby, с другой стороны, позволяет гораздо легче понять структуру языка, находящегося в файле Parser.y, но теперь он зависит от стороннего инструментального средства, в котором применяется специальный (хотя и известный) язык конкретной прикладной области, в котором могут быть свои собственные ошибки или особенности. В данном случае команда разработчиков языка IronPython не хотела быть зависимой от внешнего инструментального средства, тогда как команда разработчиков языка IronRuby не возражала против этого.
Однако совершенно ясно, насколько на каждом этапе для анализа важны конечные автоматы. Для любой задачи синтаксического анализа независимо от того, насколько она будет простой, конечный автомат всегда выдает правильный ответ.
Прим.пер.: В данном случае приводится описание лишь конкретных реализаций. В общем случае возможностей конченого автомата может оказаться недостаточной для реализации грамматик вида LL(1) и LALR(1). Что же касается правильности ответов, выдаваемых конечными автоматами, то они ровно настолько правильные, насколько правильно построена таблица переходов конечного автомата, причем это не зависит от того, будет ли эта таблица построена вручную в виде вызовов взаимно рекурсивных функций, либо она будет описана в виде грамматики, которая затем преобразуется в длинные массивы целых чисел.
Результатом работы синтаксического анализатора для любого языка является абстрактное синтаксическое дерево (AST). В нем на высоком уровне описывается структура программы, при этом каждый узел отображается непосредственно в конструкции языка - оператор или выражение. С этими деревьями можно манипулировать во время выполнения, часто для того, чтобы перед компиляцией оптимизировать программу. Впрочем, дерево AST некоторого языка связана с конкретным языком, а среда DLR должна работать с деревьями, в которых нет никакого конструкций конкретного языка, а содержатся только общие конструкции.
Продолжение статьи: Деревья выражений