Синтаксический и семантический анализ: вместе или отдельно?

Ещё одна проблема, с которой мы столкнулись, проектируя начальные этапы обработки исходного текста в «новом» компиляторе, - это способ организации синтаксического разбора. Если коротко, вопрос стоял так: делать «ручной» разбор, то есть непосредственно программировать распознавание синтаксических конструкций исходной программы, либо сконструировать такой анализатор автоматически, используя какой-либо доступный генератор распознавателей (например, YACC или Bison)?

У меня было сильное искушение сделать все вручную, методом рекурсивного спуска, благо, опыта было достаточно. В пользу такого варианта говорил и опыт создателей известного компилятора фирмы Edison Design Group, в котором используется «ручной» парсер[1]. Тем не менее в результате обсуждений было принято решение сохранить архитектуру старого, «бельгийского» компилятора и использовать одну из свободно доступных версий УЛСС.

Схема разработки, диктуемая семейством УЛСС, заключается в следующем: грамматика входного языка описывается при помощи специальной нотации (во времена моей профессиональной юности подобная нотация называлась «метасинтаксический язык» или просто «метаязык»). Из этого описания посредством стандартного компонента («метасинтаксический транслятор» или просто «метатранслятор») генерируется распознаватель, представляющий собой программу на языке реализации (в первоначальной версии YACC это был Си), которая объединяется с другими компонентами компилятора. Вот принципиальная схема: вертикальные стрелки обозначают процесс построения компилятора, а горизонтальные - использование построенного компилятора. Имейте в виду, что это именно принципиальная схема: некоторые компоненты здесь опущены для целей большей наглядности.

Кратко коснёмся преимуществ описанной схемы, а также ее недостатков и проблем, вызываемых её применением.

Основное и в конечном счёте решающее преимущество этой схемы, с точки зрения общей архитектуры компилятора, заключается в явном разделении различных компонентов компилятора, то есть в повышении его модульности. Синтаксис языка, представленный в очень наглядном, а потому в удобном для сопровождения виде, оказывается сосредоточенным в относительно компактном текстовом файле. Это описание (которое, между прочим, имеет и самостоятельную ценность, представляя собой однозначную спецификацию входного языка) легко отделяется от других компонентов компилятора (как от лексической части, так и от алгоритмов семантической обработки);

сгенерированный анализатор автоматически обеспечивает взаимодействие анализатора с этими компонентами.

Нужно пояснить: один из известных недостатков «ручного» синтаксического разбора заключается как раз в том, что «синтаксическая» часть (собственно разбор конструкций входного языка согласно его синтаксису) и «семантическая» часть (генерация для конструкций входного языка соответствующего синтаксического дерева с всесторонней проверкой его корректности) при таком подходе неизбежно оказываются перемешанными в пределах одного программного текста. Капсуляция семантических действий в пакет подпрограмм решает эту проблему только частично и работает лишь в очень небольших, «учебных» компиляторах, описываемых в книгах.

Вот короткий простой фрагмент формального описания языка, иллюстрирующий сказанное. На рисунке в упрощённом виде представлены правила, описывающие объявление класса Си++.

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

Замечание 2008 года. Интересная вещь: через много лет после принятия решений, описываемых здесь, мне всё-таки удалось достаточно эффективно отделить синтаксис и семантику без использования YACC, в рамках традиционного рекурсивного парсера! Но, правда, должно было пройти десять лет! © Об этом проекте я собираюсь подробно написать в отдель-

ном книге.

Другое преимущество подхода с формальным описанием синтаксиса связано со сравнительно небольшими временными затратами на разработку грамматического описания входного языка. Даже учитывая сложность Си++ и необходимость существенной переработки его синтаксиса (об этом ниже), сделать работоспособное описание грамматики оказалось существенно быстрее и легче, чем вручную программировать разбор всех синтаксических конструкций входного языка. Имея некоторый навык «метапрограммирования», можно создать работающую грамматику реального ЯП с нуля за несколько дней (другое дело, что для получения этого навыка придётся потратить не один год на практическое освоение метасредств ©).

Однако проектное решение такой, в некотором смысле фундаментальной, важности не может не иметь и своих теневых аспектов. Преодолевая недостатки, присущие описанной схеме, пришлось решать множество сопутствующих проблем.

Во-первых, YACC-подобный генератор оказался не в состоянии корректно воспринять синтаксис Си++ в том виде, в котором он представлен в Стандарте. Правда, на это мы и не слишком рассчитывали: он и не предназначен для генерации распознавателей, а служит только целям презентации, и, кроме того, он явно слишком общий и содержит ряд принципиальных неоднозначностей (краткое обсуждение этих неоднозначностей приведено в предыдущей части). Стало быть, синтаксис языка должен быть (и был) специально подготовлен и существенно переработан относительно оригинального - по существу, переписан заново.

Во-вторых, хотя класс грамматик, воспринимаемых YACC’om, достаточно широк и соответствует многим реальным языкам программирования, тем не менее оригинальный синтаксис Си++ даже после переработки «не вмещается» в этот класс. Следовательно, приходится специально адаптировать его (упрощать), чтобы генератор смог сформировать по нему корректный синтаксический распознаватель. Однако модификация синтаксиса неизбежно влияет на «соседние» компоненты, прежде всего на лексический анализатор! Дело в том, что адаптация неизбежно подразумевает введение дополнительных грамматических правил, а также новых лексем. Новые лексемы появляются либо в результате агрегации нескольких исходных лексем в одну (например, все знаки операций класса присваивания обрабатываются совершенно одинаково, и потому можно заменить всю группу соответствующих лексем на единственную), либо, наоборот, из-за необходимости детализировать некоторые лексемы излишне общего характера. Так, лексема «идентификатор» оказалась слишком «абстрактной», и вместо нее пришлось вводить целый класс более «конкретных» лексем («имя типа», «имя не-типа», «новое имя» и т. д.). Естественно, это потребовало усложнить алгоритм лексического анализа, который мог бы идентифицировать и поставлять парсеру такие детализированные лексемы.

Следующая проблема коренится в способе организации интерфейса сгенерированного анализатора с остальными компонентами компилятора. Кратко об этом способе можно сказать следующее: во- первых, сложный, во-вторых, устаревший.

Так, например, на вход анализатору должен подаваться целочисленный код очередной лексемы: синтаксический анализатор оперирует именно кодами лексем. Однако целочисленного кода лексемы явно недостаточно для целей компиляции в целом: нам хотелось бы знать о лексеме гораздо больше, в частности её координаты по входному тексту, включая имя исходного файла (последнее необходимо, так как исходный текст может быть скомпонован из различных файлов). К тому же мы реально получаем эту информацию от лексана! Эту дополнительную информацию приходится хранить где-то отдельно и передавать последующим компонентам компилятора каким-то другим путём (например, через глобальные переменные). Естественно, все это усложняет общую организацию компилятора.

Ещё больше неудобств доставляет взаимодействие анализатора с семантическими процедурами компилятора. Ситуация здесь следующая. Чтобы передать в некоторую синтаксическую конструкцию информацию, полученную в результате разбора другой конструкции (например, при переходе от обработки низкоуровневой конструкции к более общей), приходится использовать так называемый семантический стек - базовую структуру разбора.

Состав и структура семантической информации, возникающей в ходе разбора той или иной конструкции, определяются её смыслом и для различных конструкций сильно различаются. Поэтому, чтобы воспользоваться общим «хранилищем» такой информации - семантическим стеком, приходится искусственно подгонять эти структуры к формату стека. Каждый элемент стека описан посредством Си-объединения (union). Чтобы обеспечить передачу информации, приходится специально определять различные структуры-варианты этого объединения и заполнять их семантической информацией в процессе синтаксического разбора. Таких структур набирается штук тридцать; большинство из них не имеет самостоятельной ценСинтаксический и семантический анализ: вместе или отдельно?

139

ности, они нужны только для целей передачи информации из парсера в семантические функции. На рисунке ниже в упрощённом виде приведена часть описания семантического стека:

Большинство имён в каждом варианте этого объединения обозначает те самые структуры, которые используются для передачи информации в семантические функции. Соответственно, семантические функции, принимающие эту информацию, имеют в качестве параметров те же самые структуры. Содержимое этих «мелких» структур целиком определяется удобством сбора информации из синтаксических конструкций; структуры нужны только для такой передачи и, как правило, нигде больше в компиляторе не используются. В результате сейчас мы имеем более трёх десятков таких «подсобных» структур, и все семантические процедуры оказываются логически связанными с типами из семантического стека анализатора.

Некоторое усовершенствование этой неуклюжей схемы было бы возможно при использовании объектно-ориентированного подхода: можно было бы определить элемент семантического стека как некоторый (возможно, абстрактный) класс, а все «реальные» структуры наследовать от этого класса. Но чуть более внимательный анализ показывает, что на самом деле улучшение здесь больше стилистическое: производные классы - это, по сути, те же временные структуры, что и в прежней схеме. Кроме того, такое решение возможно только в случае, когда язык реализации поддерживает ООП. «Родной» YACC или Bison основан на Си, и потому никаких классов там нет.

Однако следующее поколение инструментов, основанных на YACC, например GPPG, который реализован на С#, - это, конечно, допускает. (В GPPG есть и некоторые другие усовершенствования, которые возникли из-за более широкого спектра возможностей языка реализации.)

Замечание 2012 года. Справедливости ради следует сказать, что сейчас многие генераторы парсеров - это относится и к GPPG, и к СОСО, и к ANTLR, да и к последним версиям Bison - содержат средства, позволяющие если не полностью избежать, то хотя бы минимизировать большинство обсуждаемых проблем. То же относится и к генераторам лексических компонентов вроде flex - механизм их взаимодействия с парсерами стал значительно более разнообразным. Допускаю, что теперь вполне возможно организовать более гибкое взаимодействие лексического анализатора с парсером (это замечание относится к случаю из следующей главки).

  • [1] Немного позднее команда разработчиков компилятора g++, к моему немалому удивлению, тоже переписала парсер на принципах рекурсивногоспуска, отказавшись от использования Бизона.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >