Беступиковый алгоритм расширенного синтаксического анализа и его приложение к языкам программирования для квантовых компьютеров : научное издание

Описание

Тип публикации: статья из журнала

Год издания: 2020

Идентификатор DOI: 10.33693/2313-223X-2020-7-2-42-48

Ключевые слова: алгоритм синтаксического анализа, квантовый компьютер, syntactical analysis algorithm, quantum computer

Аннотация: При разработке перспективных языков программирования, предназначенных для обеспечения работы суперкомпьютеров, в том числе квантовых, возникает необходимость исследований, связанных с тестированием разрабатываемого языка в условиях, когда парсеры для него еще не существуют. В частности, в процессе разработки языка программирования Показать полностьюдля квантового компьютера возникает необходимость провести синтаксический анализ (разбор) некоторой программы, написанной на новом языке программирования, принадлежащем, как и все языки программирования, классу контекстно-свободных языков (кс-языков). Проблема синтаксического анализа мономов кс-языков возникла в 50-60-х гг. прошлого века, однако в ее постановке имеются некоторые разночтения, в связи с чем возникает необходимость уточнить формулировку этой проблемы. В связи с этим будем называть расширенной проблемой синтаксического анализа проблему разработки беступикового (безостановочного, безвозвратного) алгоритма, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, которые образуют грамматику кс-языка, а также найти сразу все выводы этого монома, если такие существуют. Описание вывода монома понимается следующим образом: необходимо определить, какие продукции из грамматики кс-языка, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. В статье разработан беступиковый алгоритм решения расширенной проблемы синтаксического анализа, основанный на методе иерархии маркированных скобок. Маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок ее использования. В алгоритме используется метод последовательных приближений для решения система уравнений Хомского-Шютценберже, ассоциированной с грамматикой кс-языка. Разработанный алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма. When developing promising programming languages designed to support the work of supercomputers, including quantum ones, there is a need for research related to testing the developed language under conditions when parsers do not yet exist for it. In particular, in the process of developing a programming language for a quantum computer, it becomes necessary to parse a certain program written in a new programming language, which, like all programming languages, belongs to the class of context-free languages (cf-languages). The problem of syntactical analysis of the monomials of cf-languages was posed in the 50-60s of the last century, however, there are some discrepancies in its formulation, and therefore there is a need to clarify the formulation of this problem. In this regard, we will call the expanded problem of parsing the problem of developing a stupid (non-stop, irrevocable) algorithm that allows establishing whether a given monomial can be deduced using a system of products that form a cf-language grammar, and also find all the conclusions of this monomial at once if the latter exists. The description of the monomial inference is understood as follows: it is necessary to determine for which products from the grammar of the cf-language, how many times and in what order they are used to derive this monomial, which is equivalent to constructing all the output trees. The article has developed a deadlockless algorithm for solving the extended problem of parsing, based on the method of hierarchy of marked brackets. The marked brackets order shows what products they are assigned to, and allows you to trace the order of its use. The algorithm uses the method of successive approximations to solve the Chomsky-Schützenberger system of equations associated with the cf-language grammar. The developed algorithm has a simple software implementation; an assessment of the complexity of the algorithm is also given.

Ссылки на полный текст

Издание

Журнал: Computational Nanotechnology

Выпуск журнала: Т. 7, 2

Номера страниц: 42-48

ISSN журнала: 2313223X

Место издания: Moscow

Издатель: ООО "Издательский дом "Юр-ВАК"

Персоны

  • Кишкан Владимир Владимирович (Восточно-Сибирский техникум туризма и сервиса)
  • Сафонов Константин Владимирович (Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнёва)

Вхождение в базы данных