Одно из важнейших направлений системного программирования - разработка языков программирования и создание компиляторов для них. Практика и теория привели к выводу, что наиболее удобными для этого механизмами следует считать контекстно-свободные языки (КС-) и атрибутные грамматики. Причина этого, повидимому, лежит в том, что КС-грамматики и атрибуты хорошо согласованы с психологическими аспектами осмысливания языковых конструкций и работы с ними.
Однако, сложность алгоритмического процессирования этих довольно широких понятий привели к тому, что на практике они используются в разных задачах с различного рода ограничениями, часто конфликтующими между собой. Это в значительной степени затрудняет использование естественных классов объектов таких, как LR(1)-грамматики и атрибутные грамматики.
Широкие возможности для описания семантики языков, включающие задание контекстных свойств, законов перевода с одного языка (исходного) на другой (объектный), оптимизация кода и многие другие предполагает использование самых разнообразных зависимостей между атрибутами. В то же время, все атрибутные зависимости базируются на КС-синтаксисе исходного языка. Поэтому любое изменение КС-грамматики для придания ей свойств, облегчающих, например, синтаксический анализ, может вызвать неудобство с точки зрения описания семантики и др.
Поэтому порочной следовало бы признать укоренившуюся практику использования для задания синтаксиса LALR(1)-грамматик как неоправданно сужающую класс грамматик и подменяющую естественный класс LR(1)-грамматик искусственным, чисто техническим и довольно бессодержательным понятием LALR.
Один из результатов работы состоял в том, чтобы показать, что переход к LR(1)-грамматикам нигде не усложняет процесс обработки грамматик и работы с языком. В работе [1] приводится критерий того, что грамматика является LR(1), причем он не сложнее, чем критерий LALR(1). Построение анализатора при выполнении критерия проводится стандартным методом и по сравнению с LALR(1) требуется лишь дополнительная оптимизация автомата. Методы оптимизации подробно описаны в известной монографии Ахо и Ульмана, и можно показать (даже странно, что в упомянутой монографии это не сделано), что в том случае, когда исходная грамматика была LALR(1), построенный стандартным для LR(1) способом и оптимизированный затем анализатор будет по всем характеристикам не хуже, чем анализатор, построенный методом LALR(1). Хотя этот результат нов и фактически является одним из аргументов, оправдывающих всю идею отказа от LALR(1) в пользу LR(1), мы сочли нецелесообразным публиковать в изолированном виде лишь его, и отложили до публикации обоснования и описания всей системы.
Другим важным элементом как системы построения трансляторов, так и самого транслятора являются методы обработки атрибутной грамматики и вычисления атрибутов транслятором. Разработан [2] и математически обоснован алгоритм вычисления атрибутов, обладающий существенными преимуществами по сравнению со всеми до сих пор предлагавшимися методиками обработки атрибутов. Основная его черта состоит в том, что он применим к любой (естественно, незацикленной) атрибутной грамматике, не накладывая на грамматику никаких ограничений, не связан с каким-то фиксированным порядком обхода дерева вывода, и может быть использован даже в процессе синтаксического анализа и построения дерева. В [2] приведены также варианты этого алгоритма, ориентированные на экономию памяти и времени его работы.
- Курочкин В.М. Критерий LR(1)-грамматики // Программирование. 1993. N. 4. с. 26-28. Москва. Наука.
- Курочкин В.М. Алгоритмы вычисления атрибутов в атрибутных грамматиках // Программирование. 1995. N. 3. с. 3-8. Москва. МАИК Наука.
