Geodesic
An algorithm for solving the extended parsing problem
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 108-111.

Voir la notice de l'article provenant de la source Math-Net.Ru

The statement of the extended problem of parsing is being clarified: to develop a deadlock algorithm that allows one to establish whether a given monomial can be derived using the system of productions that form the grammar of a context-free programming language, and also describe all the derivations of this monomial, if they exist. The description of the monomial derivation is as follows: to determine which productions from the grammar of the language, how many times and in what order are used to derive this monomial, which is equivalent to the construction of all output trees. The paper proposes an algorithm for solving the extended problem of parsing, based on a hierarchy of marked brackets; labeling of brackets shows what productions they are assigned to, and allows you to trace the order of their use. The complexity of this algorithm is equal to $O(Ng^{d^{N}})$, where $g$ and $d$ are some integers, however, the algorithm has a simple software implementation.
Keywords: extended parsing problem, context-free language, complicity of algorithm. 
@article{PDMA_2020_13_a31,
     author = {V. V. Kishkan and K. V. Safonov},
     title = {An algorithm for solving the extended parsing problem},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {108--111},
     publisher = {mathdoc},
     number = {13},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a31/}
}
TY  - JOUR
AU  - V. V. Kishkan
AU  - K. V. Safonov
TI  - An algorithm for solving the extended parsing problem
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 108
EP  - 111
IS  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a31/
LA  - ru
ID  - PDMA_2020_13_a31
ER  - 
%0 Journal Article
%A V. V. Kishkan
%A K. V. Safonov
%T An algorithm for solving the extended parsing problem
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 108-111
%N 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a31/
%G ru
%F PDMA_2020_13_a31
V. V. Kishkan; K. V. Safonov. An algorithm for solving the extended parsing problem. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 108-111. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a31/

[1] Glushkov V. M., Tseitlin G. E., Yuschenko E. L., Algebra. Yazyki. Programmirovanie, Naukova dumka, Kiev, 1973 | MR

[2] Salomaa A., Soitolla M., Automata-Theoretic Aspects of Formal Power Series, Springer Verlag, N.Y., 1978 | MR | Zbl