УМЕНЬШЕНИЕ КОЛИЧЕСТВА КОМПОНЕНТ ДЕТЕРМИНИРОВАННОЙ СИНТАКСИЧЕСКОЙ ДИАГРАММЫ НА ОСНОВЕ СИЛЬНОЙ ЭКВИВАЛЕНТНОСТИ (90,00 руб.)

Научно-технический журнал УДК 519.682.1 Ю.Д. РЯЗАНОВ УМЕНЬШЕНИЕ КОЛИЧЕСТВА КОМПОНЕНТ ДЕТЕРМИНИРОВАННОЙ СИНТАКСИЧЕСКОЙ ДИАГРАММЫ НА ОСНОВЕ СИЛЬНОЙ ЭКВИВАЛЕНТНОСТИ В статье решается задача преобразования детерминированной синтаксической диаграммы в эквивалентную, содержащую меньшее число компонент. <...> Для этого вводится понятие отношения сильной эквивалентности на множестве компонент диаграммы. <...> Предлагается алгоритм проверки принадлежности пары компонент отношению сильной эквивалентности и алгоритм уменьшения количества компонент с использованием этого отношения. <...> Приводится пример, показывающий, что применение предложенных алгоритмов позволяет существенно сократить объем диаграммы. <...> Ключевые слова: формальный язык; синтаксическая диаграмма; отношение сильной эквивалентности; уменьшение количества компонент. <...> ВВЕДЕНИЕ Одним из наглядных способов задания формального языка является синтаксическая диаграмма (СД) [1]. <...> Две различные СД, содержащие различное число компонент, могут определять один и тот же язык. <...> В статье решается задача преобразования исходной СД в эквивалентную, содержащую меньшее число компонент, с использованием отношения сильной эквивалентности на множестве узлов, которое будет определено ниже. <...> ОСНОВНЫЕ ПОНЯТИЯ С целью обеспечения возможности описания алгоритма преобразования определим СД пятеркой D = (T, N, S, G, F), где T – конечное множество терминалов; N – конечное множество нетерминалов; SN – начальный нетерминал; G = (V, E) – ориентированный граф, где V = VT  VN  Vu  Vвход  Vвыход, где Vвход – множество точек входа, |Vвход| = |N|; VT – множество терминальных вершин; VN – множество нетерминальных вершин; Vu – конечное множество узлов; Vвыход – множество точек выхода, |Vвыход| = |N|; E = E1  E2  E3  E4  E5, где E1  {(a, b) | aVвход, bVu} – множество входных дуг; E2  {(a, b) | aVu, bVвыход} – множество выходных дуг; E3  {(a, b) | aVu, bVTVN} – множество дуг, выходящих из узлов; E4  {(a, b) | aVTVN, bVu} – множество <...>