Geodesic
Building parsers based on syntax diagrams with multiport components
Prikladnaâ diskretnaâ matematika, no. 1 (2022), pp. 102-119
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2022},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_1_a7/}
}
TY  - JOUR
AU  - Yu. D. Ryazanov
AU  - S. V. Nazina
TI  - Building parsers based on syntax diagrams with multiport components
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 102
EP  - 119
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_1_a7/
LA  - ru
ID  - PDM_2022_1_a7
ER  - 
%0 Journal Article
%A Yu. D. Ryazanov
%A S. V. Nazina
%T Building parsers based on syntax diagrams with multiport components
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 102-119
%N 1
%U http://geodesic.mathdoc.fr/item/PDM_2022_1_a7/
%G ru
%F 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/

[1] Grau E. A., “Recursive processes and ALGOL translation”, Comm. ACM, 4 (1961), 10–15 | DOI | Zbl

[2] Scott E., Johnstone A., “GLL parsing”, Electr. Notes Theor. Comput. Sci., 253 (2010), 177–189 | DOI

[3] Scott E., Johnstone A., “GLL parse-tree generation”, Sci. Comput. Programming, 78 (2013), 1828–1844 | DOI

[4] Ryazanov Yu. D., “Minimization syntax diagrams with multiport components”, Prikladnaya Diskretnaya Matematika, 2018, no. 41, 85–97 (in Russian) | Zbl

[5] Ryazanov Yu. D., Seval'neva M. N., “The analysis of syntax diagrams and automatic generation of linear-time programs-recognizer”, Belgorod State University Scientific Bull. Ser. History. Political Science. Economics. Inform. Technologies, 2013, no. 8, 128–136 (in Russian)

[6] Ryazanov Yu. D., Kramarenko P. V., Graph method for parsing syntax diagrams, 2014 (in Russian)

[7] Polyakov V. M., Ryazanov Yu. D., “Algorithm for not recursive linear-time programs-recognizer design from deterministic syntax diagrams”, Bull. BSTU named after V. G. Shukhov, 2013, no. 6, 194–199 (in Russian)

[8] Ryazanov Yu. D., “Converting nondeterministic syntax diagrams to deterministic ones”, Bull. Voronezh State University. Ser. Systems Analysis and Inform. Technology, 2015, no. 1, 139–147 (in Russian)

[9] Ryazanov Yu. D., “Method for resolving conflicts of type “shift — reduce” in syntax diagrams”, Bull. Voronezh State University. Ser. Systems Analysis and Inform. Technology, 2015, no. 4, 130–137 (in Russian)

[10] Tomita M., Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publ., 1985

[11] 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), 249–257