An algorithm for solving the extended parsing problem

He 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 ), where g and d are some integers, however, the algorithm has a simple software implementation.

Keywords

Authors

References