Building parsers based on syntax diagrams with~multiport components
Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 102-119
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
Keywords:
parsing, syntax diagrams with multiport components, parse forest.
@article{PDM_2022_1_a7,
author = {Yu. D. Ryazanov and S. V. Nazina},
title = {Building parsers based on syntax diagrams with~multiport components},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {102--119},
publisher = {mathdoc},
number = {1},
year = {2022},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2022_1_a7/}
}
Yu. D. Ryazanov; S. V. Nazina. Building parsers based on syntax diagrams with~multiport components. Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 102-119. http://geodesic.mathdoc.fr/item/PDM_2022_1_a7/