Способ синтаксического анализа языка программирования с расширяемой грамматикой

Способ синтаксического анализа языка программирования с расширяемой грамматикой

Реферат

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

В настоящее время для создания разных частей комплексных программных систем используются различные языки программирования высокого уровня: универсальный язык программирования (general-purpose programming language) для написания программного обеспечения для широкого круга прикладных задач и проблемно-ориентированные (domain specific) языки программирования для решения специфических задач. Так, для описания элементов графического пользовательского интерфейса удобнее всего использовать декларативный язык типа HTML или XML. Бизнес логика приложений обычно описывается на объектно-ориентированных языках программирования. Для проверки правильности структурированных текстовых данных, таких, как телефонные номера, адреса электронной почты или даты, используются языки программирования со встроенной поддержкой грамматических конструкций подъязыка регулярных выражений (например, язык perl).

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

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

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

Известны (Патент №2103728, «Способ преобразования входной программы транслятора и устройство для его осуществления») и (Патент №2115158, «Способ и устройство для достоверной оценки семантических признаков в синтаксическом анализе при проходе вперед слева направо») технические решения, относящиеся к синтаксическому анализу в компиляторах языков высокого уровня. Однако в первом из них решается задача быстрого доступа к актуальным значениям идентификаторов в дереве трансляции, а во втором - семантическая проверка во время синтаксического анализа.

Наиболее близким техническим решением, принятым за прототип, является известный (А. Ахо, Р. Сети, Дж. Ульман, разд. 4.7 «Компиляторы: принципы, технологии и инструменты» Пер. с англ. - М.: Издательский дом «Вильяме», 2003 г.) способ синтаксического анализа языков программирования, при котором для рассчитанного на заранее определенную (фиксированную) грамматику языка программирования с помощью специальных инструментальных средств (компиляторов) строят канонические LR (1) таблицы синтаксического анализа, которые ложатся в основу синтаксического анализатора и по которым во время фазы синтаксического анализа компилятор распознает, каким грамматическим правилам языка программирования соответствует тот или иной фрагмент исходного текста.

Данный способ синтаксического анализа отличается большой скоростью (O(n), т.е. время разбора пропорционально первой степени размера исходного текста), достаточно широким классом распознаваемых грамматик и удобной обработкой ошибок, однако он не позволяет динамически менять грамматику языка программирования во время работы компилятора, поскольку синтаксический анализ осуществляется не по самой грамматике, а по специальным таблицам, построенным на ее основе.

Известны также способы синтаксического анализа контекстно-свободных языков, не требующие предварительного построения таблиц, но при этом значительно менее эффективные. Например, способ синтаксического анализа, известный как алгоритм Эрли (А. Ахо, Дж. Ульман, т.1, раздел 4.2.2 «Теория синтаксического анализа, перевода и компиляции», пер. с англ. - М.: Издательство «Мир», 1978) имеет скорость O(n³), т.е. время разбора, пропорциональное кубу размера входного текста.

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

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

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

Среди всех способов табличного синтаксического анализа выделятся семейство, так называемых, LR способов с общими (или очень близкими) таблицами синтаксического анализа, преимущество которых заключается в наиболее широком классе распознаваемых грамматик. Указанное семейство включает в себя способы (алгоритмы) LR(0), SLR, LR(1), LALR(1), LR(k), LALR(k) (при k>1), отличающиеся друг от друга построением множеств, так называемых, строк предпросмотра (lookahead string), которые синтаксический анализатор просматривает вперед по тексту, чтобы выбрать нужное правило грамматики, соответствующее текущему фрагменту распознаваемой программы. Поскольку структура таблиц и стека (программная структура, используемая в процессе работы синтаксического анализатора) анализаторов LR не зависит от метода построения строк предпросмотра, то предложенный способ синтаксического анализа будет работать для всех способов семейства LR.

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

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

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

В частном случае исполнения заявленного способа синтаксического анализа каждая из директив расширения грамматики располагается внутри грамматической конструкции расширения грамматики "grammar" ранее конструкции "объявления типов" (грамматические конструкции определения классов, структур и т.п. в объектно-ориентированных языках).

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

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

Синтаксический анализатор с возможностью динамической модификации таблиц компиляции может быть использован в фазе синтаксического анализа для компилятора или интерпретатора практически любого языка программирования.

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

Возьмем для примера две директивы расширения грамматики:

- typedecl - директива расширения грамматики для добавления конструкций, эквивалентных конструкциям объявления типа (class и struct) и

- member - директива расширения грамматики для добавления конструкций, эквивалентных конструкциям объявления членов типа.

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

grammar Forms {

typedecl Window=><MemberModifiers>"window"<ldentifier><ClassBody>

{

<MemberModifiers>"class"<ldentifier>":"Form<ClassBody>

}

member Caption=><MemberModifiers>"caption"<StringLiteral>";"

{

<MemberModifiers>"string"m_Caption"="<StringLiteral>";"

}

}

В этом примере вводится новая грамматическая конструкция Window для описания окон пользовательского интерфейса, которая будет компилироваться в класс, производный от библиотечного класса System.Windows.Forms.Form, и конструкция Caption, которая будет компилироваться в член класса типа string с заданным начальным значением.

В данном примере нижеследующий код, использующий грамматическую конструкцию window, является конструкцией объявления типа.

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

public window MainFrame

{

private caption "Main Frame";

}

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

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

1. Способ синтаксического анализа по п.1, отличающийся тем, что основывается на синтаксическом анализе LR(1).

2. Способ синтаксического анализа по п.1, отличающийся тем, что основывается на синтаксическом анализе LALR(1).

3. Способ синтаксического анализа по п.1, отличающийся тем, что основывается на синтаксическом анализе SLR.

4. Способ синтаксического анализа по п.1, отличающийся тем, что основывается на синтаксическом анализе LR(k), k>1.

5. Способ синтаксического анализа по п.1, отличающийся тем, что основывается на синтаксическом анализе LALR(k), k>1.