The problem of constructing parsers from syntax diagrams with multiport components (SD) is solved. An algorithm for constructing a parser based on the GLL algorithm is proposed, which results in the compact representation of the input chain parse forest. The proposed algorithm makes it possible to build parsers based on the SD of an arbitrary structure and does not require preliminary SD transformations. We introduce the concepts of “inference tree” and “parsing forest” for SD and describe the data structures used by the parser, such as a graph-structured stack, a parser descriptor, and a compact representation of the parsing forest. The algorithm for constructing parsers based on SD is described and an example of parser constructing is given.
Download file
Counter downloads: 44
- Title Building parsers based on syntax diagrams with multiport components
- Headline Building parsers based on syntax diagrams with multiport components
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 55
- Date:
- DOI 10.17223/20710410/55/8
Keywords
parsing, syntax diagrams with multiport components, parse forestAuthors
References
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.

Building parsers based on syntax diagrams with multiport components | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 55. DOI: 10.17223/20710410/55/8
Download full-text version
Counter downloads: 157