Беступиковый алгоритм расширенного синтаксического анализа и его приложение к языкам программирования для квантовых компьютеров
- Авторы: Кишкан В.В.1, Сафонов К.В.2
-
Учреждения:
- Восточно-Сибирский техникум туризма и сервиса
- Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнёва
- Выпуск: Том 7, № 2 (2020)
- Страницы: 42-48
- Раздел: Статьи
- URL: https://journals.eco-vector.com/2313-223X/article/view/529778
- DOI: https://doi.org/10.33693/2313-223X-2020-7-2-42-48
- ID: 529778
Цитировать
Открытый доступ
Доступ предоставлен
Аннотация
При разработке перспективных языков программирования, предназначенных для обеспечения работы суперкомпьютеров, в том числе квантовых, возникает необходимость исследований, связанных с тестированием разрабатываемого языка в условиях, когда парсеры для него еще не существуют. В частности, в процессе разработки языка программирования для квантового компьютера возникает необходимость провести синтаксический анализ (разбор) некоторой программы, написанной на новом языке программирования, принадлежащем, как и все языки программирования, классу контекстно-свободных языков (кс-языков). Проблема синтаксического анализа мономов кс-языков возникла в 50-60-х гг. прошлого века, однако в ее постановке имеются некоторые разночтения, в связи с чем возникает необходимость уточнить формулировку этой проблемы. В связи с этим будем называть расширенной проблемой синтаксического анализа проблему разработки беступикового (безостановочного, безвозвратного) алгоритма, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, которые образуют грамматику кс-языка, а также найти сразу все выводы этого монома, если такие существуют. Описание вывода монома понимается следующим образом: необходимо определить, какие продукции из грамматики кс-языка, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. В статье разработан беступиковый алгоритм решения расширенной проблемы синтаксического анализа, основанный на методе иерархии маркированных скобок. Маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок ее использования. В алгоритме используется метод последовательных приближений для решения система уравнений Хомского-Шютценберже, ассоциированной с грамматикой кс-языка. Разработанный алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.
Ключевые слова
Полный текст
Об авторах
Владимир Владимирович Кишкан
Восточно-Сибирский техникум туризма и сервисастарший преподаватель Красноярск, Российская Федерация
Константин Владимирович Сафонов
Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнёва
Email: safonovkv@rambler.ru
д-р физ.-мат. наук, профессор; заведующий кафедрой Красноярск, Российская Федерация
Список литературы
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 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.
Дополнительные файлы
