ГлавнаяАрхивПостроение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами

Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/8

Рассматривается задача построения синтаксических анализаторов по синтаксическим диаграммам с многовходовыми компонентами (СД). Предлагается основанный на алгоритме GLL алгоритм построения синтаксического анализатора, результатом работы которого является компактное преставление леса разбора входной цепочки. Предложенный алгоритм позволяет строить синтаксические анализаторы по СД произвольной структуры и не требует предварительных преобразований СД. Построенные синтаксические анализаторы могут применяться для анализа любых контекстно-свободных языков, включая недетерминированные и неоднозначные. Вводятся понятия «дерево вывода» и «лес разбора» для СД, описываются структуры данных, используемые анализатором, такие, как стек с графовой структурой, дескриптор синтаксического анализатора, компактное представление леса разбора. Описывается алгоритм построения синтаксических анализаторов по СД и приводится пример построения такого анализатора.
  • Title Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами
  • Headline Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 55
  • Date:
  • DOI 10.17223/20710410/55/8
Ключевые слова
синтаксический анализ, синтаксические диаграммы с многовходовыми компонентами, лес разбора
Авторы
Ссылки
Grau E. A. Recursive processes and ALGOL translation // Comm. ACM. 1961. V. 4. P. 10-15.
Scott E. and Johnstone A. GLL parsing // Electr. Notes Theor.Comput. Sci. 2010. V. 253. P. 177-189.
Scott E. and Johnstone A. GLL parse-tree generation // Sci.Comput. Programming. 2013. V. 78. P. 1828-1844.
Рязанов Ю.Д. Минимизация синтаксических диаграмм с многовходовыми компонентами // Прикладная дискретная математика. 2018. №41. С. 85-97.
Рязанов Ю.Д, Севальнева М. Н. Анализ синтаксических диаграмм и синтез программ-распознавателей линейной сложности // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. 2013. №8. С. 128-136.
Рязанов Ю. Д., Крамаренко П. В. Графовый способ анализа синтаксических диаграмм // Научный электронный архив. 2014. http://econf.rae.ru/article/8214.
Поляков В. М., Рязанов Ю. Д. Алгоритм построения нерекурсивных программ-распознавателей линейной сложности по детерминированным синтаксическим диаграммам // Вестник БГТУ им. В. Г. Шухова. 2013. №6. С. 194-199.
Рязанов Ю. Д. Преобразование недетерминированных синтаксических диаграмм в детерминированные // Вестник Воронежского госуниверситета. Сер. Системный анализ и информационные технологии. 2015. №1. С. 139-147.
Рязанов Ю. Д. Способ устранения конфликтов типа «переход - выход» в синтаксических диаграммах // Вестник Воронежского госуниверситета. Сер. Системный анализ и информационные технологии. 2015. №4. С. 130-137.
Tomita M. Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publ., 1985.
Tomita M. Graph-structured stack and natural language parsing // 26th Ann. Meeting of the Association of Computational Linguistics, 7-10 June 1988, Buffalo, New York, USA. P. 249-257.
Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/8
Построение синтаксических анализаторов на основе синтаксических диаграмм с многовходовыми компонентами | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/8