КОМПЬЮТЕРНАЯ ЛИНГВИСТИКА И ОБРАБОТКА ЕСТЕСТВЕННОГО ЯЗЫКА УДК 519.685.3 СИНТЕЗ РАСПОЗНАВАТЕЛЕЙ С МАГАЗИННОЙ ПАМЯТЬЮ ПО ДЕТЕРМИНИРОВАННЫМ СИНТАКСИЧЕСКИМ ДИАГРАММАМ Ю. Д. <...> Рассматриваются вопросы использования синтаксических диаграмм при проектировании программ обработки формальных языков. <...> Предложены алгоритмы синтеза МП-распознавателей с одним и с конечным множеством состояний по детерминированной синтаксической диаграмме. <...> ВВЕДЕНИЕ Классическая технология проектирования программ обработки контекстно-свободных языков предполагает задание языка в виде КС-грамматики, преобразование ее в МП-распознаватель и его программную реализацию [1–2]. <...> Более наглядным способом описания языка являются синтаксические диаграммы (СД) [3]. <...> В данной работе предлагаются алгоритмы преобразования детерминированных СД в МП-распознаватели с одним и с конечным множеством состояний. <...> ОСНОВНЫЕ ПОНЯТИЯ вать четверкой D , ,,T N GS) [4], где ∈ – начальный нетерминал; G (, )VE= Синтаксическую диаграмму будем зада= ( T – конечное множество терминалов; N – конечное множество нетерминалов; SN – ориентированный граф, где © Рязанов Ю. Д., 2014 где Vвход T – множество точек входа, VN; в =ход V – множество терминальных вершин; N V – конечное множество узлов; Vвыход VN; выход где = входных дуг; ( E ab a V b V∈ выход ∈ выходных дуг; ( ство дуг, выходящих из узлов; ( TN, ство дуг, входящих в узлы; ( E ab a V b V∈ – множество -дуг, соединяющих узлы. <...> Компонента именуется соответствующим нетерминалом, имеет только одну точку входа и одну точку выхода и конечное множество вершин других типов. <...> Точки входа и выхода на диаграмме компоненты не изображаются. <...> Нетерминальная вершина изображается прямоугольником, в который вписан нетерминальный символ. <...> В точку входа не входит ни одна дуга и выходит конечное множество дуг (входные дуги компоненты). <...> Из точки выхода не выходит ни одна дуга и входит конечное множество дуг (выходные дуги компоненты). <...> Каждая дуга, за исключением входных <...>