УДК 519.685.3 СПОСОБ УСТРАНЕНИЯ КОНФЛИКТОВ ТИПА «ПЕРЕХОД-ВЫХОД» В СИНТАКСИЧЕСКИХ ДИАГРАММАХ Ю. Д. <...> Рассматривается задача эквивалентного преобразования синтаксических диаграмм в детерминированные синтаксические диаграммы. <...> Предложен способ и алгоритм устранения конфликтов типа «переход-выход». <...> Это позволит расширить класс синтаксических диаграмм, которые можно преобразовать в детерминированные синтаксические диаграммы. <...> Ключевые слова: формальный язык, синтаксическая диаграмма, эквивалентные преобразования, детерминированная синтаксическая диаграмма. <...> This paper presents the problem of equivalent transformation of syntax diagrams into deterministic syntax diagrams. <...> This method expanded the class of syntax diagrams, which can be transformed to deterministic syntax diagrams. <...> ВВЕДЕНИЕ Синтаксические диаграммы представляют собой наглядный, интуитивно понятный, графический способ задания синтаксиса языка, используется для документирования языков программирования [1, 2] и в проектировании трансляторов [3–7]. <...> Для построения трансляторов линейной сложности [8, 9] используются детерминированные синтаксические диаграммы (ДСД). <...> Исходные СД могут не принадлежать классу ДСД, поэтому, для синтеза программ-распознавателей линейной сложности, их нужно преобразовать в ДСД. <...> Но не любую СД можно преобразовать в ДСД, так как даже проблема распознавания, существует ли для данной СД, не являющейся ДСД, эквивалентная ей ДСД, неразрешима (в противном случае была бы разрешима проблема распознавания, существует ли для данной КС-грамматики, не являющейся LL(1)-грамматикой, эквивалентная ей LL(1)-грамматика, неразрешимость кото© Рязанов Ю. Д., 2015 рой показана в [8]). <...> В работе [10] определены причины (конфликты типа «переход-переход» и «переход-выход»), по которым СД не являются детерминированными и описан способ разрешения конфликтов типа «переход-переход». <...> Это позволит расширить класс исходных СД, которые можно преобразовать в детерминированные синтаксические диаграммы. <...> В ней заглавными буквами обозначены нетерминалы <...>