Беступиковый алгоритм расширенного синтаксического анализа и его приложение к языкам программирования для квантовых компьютеров
(Стр. 42-48)

Чтобы читать текст статьи, пожалуйста, зарегистрируйтесь или войдите в систему
Аннотация:
При разработке перспективных языков программирования, предназначенных для обеспечения работы суперкомпьютеров, в том числе квантовых, возникает необходимость исследований, связанных с тестированием разрабатываемого языка в условиях, когда парсеры для него еще не существуют. В частности, в процессе разработки языка программирования для квантового компьютера возникает необходимость провести синтаксический анализ (разбор) некоторой программы, написанной на новом языке программирования, принадлежащем, как и все языки программирования, классу контекстно-свободных языков (кс-языков). Проблема синтаксического анализа мономов кс-языков возникла в 50-60-х гг. прошлого века, однако в ее постановке имеются некоторые разночтения, в связи с чем возникает необходимость уточнить формулировку этой проблемы. В связи с этим будем называть расширенной проблемой синтаксического анализа проблему разработки беступикового (безостановочного, безвозвратного) алгоритма, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, которые образуют грамматику кс-языка, а также найти сразу все выводы этого монома, если такие существуют. Описание вывода монома понимается следующим образом: необходимо определить, какие продукции из грамматики кс-языка, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. В статье разработан беступиковый алгоритм решения расширенной проблемы синтаксического анализа, основанный на методе иерархии маркированных скобок. Маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок ее использования. В алгоритме используется метод последовательных приближений для решения система уравнений Хомского-Шютценберже, ассоциированной с грамматикой кс-языка. Разработанный алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.
Образец цитирования:
Кишкан В.В., Сафонов К.В., (2020), БЕСТУПИКОВЫЙ АЛГОРИТМ РАСШИРЕННОГО СИНТАКСИЧЕСКОГО АНАЛИЗА И ЕГО ПРИЛОЖЕНИЕ К ЯЗЫКАМ ПРОГРАММИРОВАНИЯ ДЛЯ КВАНТОВЫХ КОМПЬЮТЕРОВ. Computational nanotechnology, 2: 42-48.
DOI: 10.33693/2313-223X-2020-7-2-42-48
Список литературы:
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. М.: Мир, 1978. 352 с.
Ахо А., Лам М., Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструментарий. М.: Вильямс, 2008.
Гинзбург С. Математическая теория контекстно-свободных языков. М. Мир, 1970. 325 с.
Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра, языки, программирование. Киев: Наукова думка, 1974. 328 с.
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2006.
Сафонов К.В. О возможности вычислительного распознавания контекстно-свободных языков // Вычислительные технологии. 2005. Т. 10 (4). С. 91-98.
Тюгашев А.А. Основы программирования. Ч. I. СПб.: Ун-т ИТМО. 2016.
Хантер Р. Основные концепции компиляторов. М.: Вильямс, 2002.
Хомский Н., Шютценберже М.Н. Алгебраическая теория контекстно-свободных языков // Кибернетический сборник. Нов. серия. 1966. Вып. 3. С. 195-242.
Doh K.-G., Kim H., Schmidt D.A. Abstract LR-Parsing. Berlin; Heidelberg: Springer, 2011. Pр. 90-109.
Kishkan V.V., Safonov K.V., Tsarev R.Yu. Syntactical analysis of context-free languages taking into account the order of application of productions // Journal of Physics: Conference Series. 2019. Vol. 1333. P. 032072.
Salomaa A., Soittola M. Automata-theoretic aspects of formal power series. NY: Springer-Verlag, 1978. 288 p.
Pingali K., Bilardi G. A graphical model for context-free grammar parsing. Heidelberg; Berlin: Springer, 2015.
Scott E., Johnstone A. GLL parsing // Electronic Notes in Theoretical Computer Science. 2009. Vol. 253 (7).
Verbitskaia E., Grigorev S., Avdyukhin D. Relaxed parsing of regular approximations of string-embedded languages. Cham: Springer International Publishing. 2016. Pp. 291-302.
Ключевые слова:
алгоритм синтаксического анализа, квантовый компьютер, syntactical analysis algorithm, quantum computer.