zabika.ru   1 ... 5 6 7 8 9

Модульность спецификации трансляции

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

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

+start: NUMBER (PLUS NUMBER)* ;

до грамматики

+start: mult_part (PLUS mult_part)* ;

mult_part: NUMBER (STAR NUMBER)* ;

Как видно, требуется способ заменить в первом правиле токены NUMBER на нетерминалы mult_part, и добавить новое правило mult_part. Для реальных случаев наподобие этого нужен достаточно сложный язык описания расширений правил. Один из способов это сделать и соответствующий язык описаны в работах [4] и [5].

В простых случаях может быть достаточно просто возможности заменять одно правило другим, с тем же именем. Этот подход, например, реализован в инструменте ANTLR [14]. Другой — если встречается правило с таким же именем, то продукция второго правила добавляется к первому в качестве альтернативы. В теории контекстно-свободных языков такой способ естественно получается из определения контекстно-свободной грамматики. Правила определены множеством, и в теории порядок не имеет значения, хотя на практике иногда важен. Такой подход тоже встречается в генераторах синтаксических анализаторов, например в Menhir.

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

LeaveLast


Оставляет последнее по порядку правило из правил с одинаковыми именами.

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

MergeAlter


Объединяет правила с одинаковыми именами знаком альтернативы.

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

Парсеры спецификаций трансляции


Парсеры спецификаций трансляции, так называемые фронтенды, преобразуют исходный код спецификации трансляции, заданный в формате некоторого инструмента, во внутреннее представление YaccConstructor. При этом получившееся внутреннее представление должно быть максимально подобно исходному коду. Работу по его трансформации для приведения в формат другого инструмента выполняют уже преобразования внутреннего представления. Далее описываются реализованные в рамках работы модули.

AntlrFrontend


Парсер грамматики в формате ANTLR.

Язык F# не поддерживается инструментом ANTLR, поэтому на данный момент фронтенд можно использовать только для реинжиниринга грамматик без атрибутов. Решение поддерживать формат было принято ввиду популярности инструмента и большого числа написанных спецификаций трансляций для него.

Реализован компонент с помощью генератора синтаксических анализаторов FsYacc в связке с лексером FsLex. Особенностью стало то, что в ANTLR спецификация лексера задается в том же файле, что и парсера, поэтому во внутреннее представление в комментарий в заголовке выносятся все лексемы, которые необходимо описать в лексере целевого инструмента.

Фронтенд был протестирован на грамматиках языка C, CSS 2.1, URL.

FsYaccFrontend


Парсер спецификации трансляции в формате FsYacc.

FsYacc — реализация классического генератора Yacc для языка F#. Как и Yacc, имеет очень простой язык. По большей части повторяет возможности ocamlyacc до такой степени, что в FsYacc можно использовать спецификации трансляции, написанные для ocamlyacc. Как правило, в качестве лексера к нему используется FsLex.

В YaccConstuctor парсер FsYacc написан на языке Yard, который транслируется в FsYacc с помощью самого инструмента, а именно фронтенда YardFrontend, генератора FsYaccPrinter и необходимых преобразований.


<< предыдущая страница   следующая страница >>