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


 


Владельцы патента RU 2515684:

БОЧАРНИКОВ Дмитрий Николаевич (RU)

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

 

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

В настоящее время для создания разных частей комплексных программных систем используются различные языки программирования высокого уровня: универсальный язык программирования (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(n3), т.е. время разбора, пропорциональное кубу размера входного текста.

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

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

Указанный технический результат достигается за счет того, что в способе синтаксического анализа языка программирования, основанном (способе) на табличном 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.



 

Похожие патенты:

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

Изобретение относится к области динамической двоичной трансляции. Техническим результатом является обеспечение эффективной технологии для выполнения динамической двоичной трансляции из архитектуры системы команд ("ISA") с большим количеством регистров в ISA с меньшим количеством регистров.

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

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

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

Изобретение относится к вычислительным системам, информационным технологиям. .

Изобретение относится к средствам компиляции программного кода. .

Изобретение относится к системам программной транзакционной памяти. .

Изобретение относится к области компьютерных пользовательских интерфейсов. .

Изобретение относится к области обработки цифровых данных. .

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

Изобретение относится к области обработки данных при семантическом анализе текстовых данных и построении семантической модели документов. .

Изобретение относится к области обработки данных, а более конкретно к высокопроизводительному и при этом очень гибкому механизму синтаксического анализа/компоновки.

Изобретение относится к области для определения разборчивости символа. .

Изобретение относится к обработке естественно-языковых текстов и может быть использовано для автоматизации поиска необходимых документов в большой их коллекции. .

Изобретение относится к идентификации перефразирования в тексте. .

Изобретение относится к области информационных технологий, а именно к индексации текста. Техническим результатом является повышение точности построения индексов текстов на естественных языках. В способе автоматизированной семантической индексации текста на естественном языке сегментируют текст на элементарные единицы первого уровня (слова) и на предложения. Формируют единицы второго уровня (нормализованные словоформы). Подсчитывают частоту встречаемости каждой единицы первого уровня для соседних единиц первого уровня и объединяют последовательности слов в единицы третьего уровня (устойчивые сочетания слов). Выявляют в каждом предложении семантически значимый объект и его атрибут (единицы четвертого уровня). Выявляют в каждом предложении семантически значимые отношения между семантически значимыми объектами, а также между семантически значимыми объектами и атрибутами. Выявляют частоты встречаемости единиц второго и третьего уровней. Формируют для каждого семантически значимого отношения множество триад (единицы пятого уровня). Индексируют на множестве сформированных триад по отдельности все связанные семантически значимыми отношениями семантически значимые объекты с их частотами встречаемости, все атрибуты с их частотами встречаемости и все сформированные триады. 5 з.п. ф-лы, 2 ил., 23 табл.
Наверх