Тип публикации: статья из журнала

Год издания: 2020

Идентификатор DOI: 10.17223/2226308X/13/32

Ключевые слова: расширенная проблема синтаксического анализа, контекстно-свободный язык, сложность алгоритма, extended parsing problem, context-free language, complicity of algorithm

Аннотация: Уточняется формулировка расширенной проблемы синтаксического анализа: разработать беступиковый алгоритм, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, образующих грамматику контекстно-свободного языка программирования, а также описать сразу все выводы этого монома, если такие существуют. Описание вывода монома состоит в следующем: определить, какие продукции из грамматики языка, сколько раз и в каком порядке применяются, что равносильно построению всех деревьев вывода. Предложен алгоритм решения расширенной проблемы синтаксического анализа, основанный на иерархии маркированных скобок; маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок их использования. Алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма. 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.

Журнал: Прикладная дискретная математика. Приложение

Выпуск журнала: № 13

Номера страниц: 108-111

ISSN журнала: 2226308X

Место издания: Томск

Издатель: Национальный исследовательский Томский государственный университет

• Кишкан Владимир Владимирович (Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнёва)
• Сафонов Константин Владимирович (Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнёва)

• РИНЦ (eLIBRARY.RU)