УДК 519.685.3 ПРЕОБРАЗОВАНИЕ НЕДЕТЕРМИНИРОВАННЫХ СИНТАКСИЧЕСКИХ ДИАГРАММ В ДЕТЕРМИНИРОВАННЫЕ Ю. Д. <...> Рассматривается задача эквивалентного преобразования синтаксических диаграмм в детерминированные синтаксические диаграммы. <...> Определены причины (конфликты), по которым диаграмма может быть недетерминированной и предложен способ и алгоритм устранения конфликтов типа «переход - переход». <...> Ключевые слова: формальный язык, синтаксическая диаграмма, эквивалентные преобразования, детерминированная синтаксическая диаграмма. <...> ВВЕДЕНИЕ Одним из удобных способов спецификации формальных языков является синтаксическая диаграмма (СД), которую впервые применил Н. <...> СД используются как для документирования языков программирования, так и при проектировании обработчиков языков (распознавателей, трансляторов, интерпретаторов) [2–4]. <...> Для класса детерминированных СД (ДСД) [5, 6] существуют алгоритмы синтеза МП-распознавателей с одним и множеством состояний [7] рекурсивных и нерекурсивных программ-распознавателей линейной сложности [5, 8]. <...> Исходные СД могут не принадлежать классу ДСД, поэтому, для синтеза программ-распознавателей линейной сложности, их нужно преобразовать в ДСД. <...> Но не любую СД можно преобразовать в ДСД, так как даже проблема распознавания, существует ли для данной СД, не являющейся ДСД, эквивалентная ей ДСД, неразрешима (в противном слу© Рязанов Ю. Д., 2015 ОСНОВНЫЕ ПОНЯТИЯ вать пятеркой D ( , , , , ), Синтаксическую диаграмму будем зада= T N GS F где T – конечное множество терминалов; N – конечное множество нетерминалов; SN ∈ – начальный нетерминал; G (, )VE= – ориентированный граф, где ВЕСТНИК ВГУ, СЕРИЯ: СИСТЕМНЫЙ АНАЛИЗ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, 2015, № 1 139 чае была бы разрешима проблема распознавания, существует ли для данной КС-грамматики, не являющейся LL (1)-грамматикой, эквивалентная ей LL (1)-грамматика, неразрешимость которой показана в [9]). <...> В данной работе определяются причины (конфликты), по которым СД не <...>