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

При разработке перспективных языков программирования, предназначенных для обеспечения работы суперкомпьютеров, в том числе квантовых, возникает необходимость исследований, связанных с тестированием разрабатываемого языка в условиях, когда парсеры для него еще не существуют. В частности, в процессе разработки языка программирования для квантового компьютера возникает необходимость провести синтаксический анализ (разбор) некоторой программы, написанной на новом языке программирования, принадлежащем, как и все языки программирования, классу контекстно-свободных языков (кс-языков). Проблема синтаксического анализа мономов кс-языков возникла в 50-60-х гг. прошлого века, однако в ее постановке имеются некоторые разночтения, в связи с чем возникает необходимость уточнить формулировку этой проблемы. В связи с этим будем называть расширенной проблемой синтаксического анализа проблему разработки беступикового (безостановочного, безвозвратного) алгоритма, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, которые образуют грамматику кс-языка, а также найти сразу все выводы этого монома, если такие существуют. Описание вывода монома понимается следующим образом: необходимо определить, какие продукции из грамматики кс-языка, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. В статье разработан беступиковый алгоритм решения расширенной проблемы синтаксического анализа, основанный на методе иерархии маркированных скобок. Маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок ее использования. В алгоритме используется метод последовательных приближений для решения система уравнений Хомского-Шютценберже, ассоциированной с грамматикой кс-языка. Разработанный алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.