УДК 519.682.1 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ И ОПТИМИЗАЦИЯ АЛГОРИТМА НИСХОДЯЩЕГО РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ ДЛЯ PEG-ГРАММАТИК Д. И. <...> В статье рассматривается двухпроходная модификация алгоритма нисходящего разбора с ограниченными возвратами для PEG-грамматик с семантическими вставками. <...> Получены экспериментальные данные эффективности алгоритма на примере языка Java. <...> Предлагаются подходы сокращения потребляемой памяти, необходимой для хранения промежуточных результатов разбора. <...> Ключевые слова: нисходящий синтаксический разбор с ограниченными возвратами, PEGграмматики, генератор синтаксических анализаторов, оптимизация. <...> The article describes two-pass modification of top-down parsing algorithm with limited backtracking for PEG-grammars with semantics entries, experimental results of this algorithm for Java language and methods to reduce memory usage for storing intermediate parsing results. <...> Keywords: top-down syntax parsing with limited backtracking, PEG-grammars (Parsing Expression Grammars), parser generator, optimization. <...> ВВЕДЕНИЕ щего разбора данные альтернативы испытываются по порядку, независимо от того, были ли успешными в данной позиции предыдущие альтернативы или нет. <...> Такой алгоритм может затрачивать на разбор экспоненциальное время. <...> Кроме того, данный алгоритм не гарантирует единственность разбора входной строки. <...> Избавиться от указанных недостатков позволяет простая модификация данного алгоритОтличительной чертой алгоритмов нисходящего синтаксического анализа является их целенаправленность, т.е. на каждом шаге анализа в таком алгоритме присутствует цель – распознать часть входной строки в соответствии с текущем испытываемым выражением из правой части какого-либо правила грамматики языка. <...> Благодаря этому свойству алгоритмы нисходящего синтаксического анализа более естественны для человека, в отличие от алгоритмов восходящего или смешанного анализа. <...> Предположим, что нам необходимо распознать некоторую часть входной строки с применением правила (нетерминала) A, который состоит из нескольких альтернатив a1 , a2 , ., an . <...> В случае нисходя© Соломатин <...>