Библиографическое описание:Алгоритм решения расширенной проблемы синтаксического анализа : научное издание / В. В. Кишкан, К. В. Сафонов. - Текст : непосредственный // Прикладная дискретная математика. Приложение. - 2020. - № 13. - С. 108-111. - ISSN 2226-308X. - ISSN 2411-2313, DOI 10.17223/2226308X/13/32.
Аннотация:Уточняется формулировка расширенной проблемы синтаксического анализа: разработать беступиковый алгоритм, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, образующих грамматику контекстно-свободного языка программирования, а также описать сразу все выводы этого монома, если такие существуют. Описание вывода монома состоит в следующем: определить, какие продукции из грамматики языка, сколько раз и в каком порядке применяются, что равносильно построению всех деревьев вывода. Предложен алгоритм решения расширенной проблемы синтаксического анализа, основанный на иерархии маркированных скобок; маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок их использования. Алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.
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<sup>d</sup> ), where g and d are some integers, however, the algorithm has a simple software implementation.
