|
РАЗРАБОТКА АРХИТЕКТУРЫ КВАНТОВЫХ КОМПЬЮТЕРОВ НА НОВЫХ ПРИНЦИПАХ, СОЗДАНИЕ НОВОГО КВАНТОВОГО ПРОГРАММИРОВАНИЯ
Беступиковый алгоритм расширенного синтаксического анализа и его приложение к языкам программирования для квантовых компьютеров
В. В. Кишканa, К. В. Сафоновb a Восточно-Сибирский техникум туризма и сервиса
b Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнёва
Аннотация:
При разработке перспективных языков программирования, предназначенных для обеспечения работы суперкомпьютеров, в том числе квантовых, возникает необходимость исследований, связанных с тестированием разрабатываемого языка в условиях, когда парсеры для него еще не существуют. В частности, в процессе разработки языка программирования для квантового компьютера возникает необходимость провести синтаксический анализ (разбор) некоторой программы, написанной на новом языке программирования, принадлежащем, как и все языки программирования, классу контекстно-свободных языков (кс-языков). Проблема синтаксического анализа мономов кс-языков возникла в 50-60-х гг. прошлого века, однако в ее постановке имеются некоторые разночтения, в связи с чем возникает необходимость уточнить формулировку этой проблемы. В связи с этим будем называть расширенной проблемой синтаксического анализа проблему разработки беступикового (безостановочного, безвозвратного) алгоритма, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, которые образуют грамматику кс-языка, а также найти сразу все выводы этого монома, если такие существуют. Описание вывода монома понимается следующим образом: необходимо определить, какие продукции из грамматики кс-языка, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. В статье разработан беступиковый алгоритм решения расширенной проблемы синтаксического анализа, основанный на методе иерархии маркированных скобок. Маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок ее использования. В алгоритме используется метод последовательных приближений для решения система уравнений Хомского-Шютценберже, ассоциированной с грамматикой кс-языка. Разработанный алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.
Ключевые слова:
алгоритм синтаксического анализа, квантовый компьютер.
Поступила в редакцию: 05.05.2020
Образец цитирования:
В. В. Кишкан, К. В. Сафонов, “Беступиковый алгоритм расширенного синтаксического анализа и его приложение к языкам программирования для квантовых компьютеров”, Comp. nanotechnol., 7:2 (2020), 42–48
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cn298 https://www.mathnet.ru/rus/cn/v7/i2/p42
|
Статистика просмотров: |
Страница аннотации: | 118 | PDF полного текста: | 18 | Список литературы: | 1 |
|