Синтаксический анализ программ методом интегральных представлений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/39

Синтаксический анализ программ методом интегральных представлений

Предложен новый метод синтаксического анализа мономов контекстно-свободного языка как модели языков программирования, основанный на интегральном представлении синтаксического полинома программы. При этом показано, что интеграл фиксированной кратности по циклу позволяет найти синтаксический полином монома (программы) с неограниченным числом символов, что даёт новый подход к проблеме синтаксического анализа. Предполагается, что интеграл по циклу может быть вычислен с помощью теории вычетов.

Syntax analysis of programs by the method of integral representations.pdf Одной из важных проблем, связанных с разработкой систем и языков программирования, является проблема синтаксического анализа программ [1]. Как известно, большинство языков программирования является кс-языками, которые можно представить в виде формального степенного ряда (ФСР), поэтому каждая программа, написанная на языке программирования, может рассматриваться как моном соответствующего ФСР. В связи с этим рассмотрим проблему синтаксического анализа мономов кс-языка. Для того чтобы сформулировать её, рассмотрим подробнее систему полиномиальных уравнений Хомского - Щутценберже, которая определяет кс-язык. Как известно [1, 2], грамматика кс-языка является множеством правил подстановки Zj ^ qj1(z,x), ..., Zj ^ j(z,x), j = 1,...,n, где j(z,x) является мономом от некоммутативных символьных переменных с числовым коэффициентом, равным единице. Правила подстановки можно применять к начальному символу z1, а затем к другим мономам в любом порядке неограниченное число раз, что позволяют выводить новые «правильные» мономы, образующие кс-язык. В [3] предложен метод мономиальных меток, который позволяет провести беступиковый синтаксический анализ монома v от терминальных символов x1,... , xm. Метод состоит в следующем. Сначала каждое правило подстановки Zj ^ j(z,x) заменяется правилом zj ^ tjkj (z, x), имеющим мономиальную метку j, которая является символом из расширенного алфавита, и для новых правил вывода рассматривается Исследование выполнено при финансовой поддержке РФФИ и Правительства Красноярского края в рамках научного проекта № 17-47-240318. соответствующая система уравнений Хомского - Щутценберже: Zj = Q*(z,x,t) d= tjiqji(z,x)+ ... + j j (z,x), j = 1,...,n. (1) (2) Решение этой системы можно получить методом последовательных приближений в виде ФСР, в том числе в виде ФСР представлена первая компонента решения те z1 = z1 (x,t) = Е(z!,Wi) Wi, где w - мономы от символов x1,..., xm, t11, t12,... , tnpn • Синтаксический анализ монома v кс-языка z1 (x) можно провести следующим образом. Считывая мономы степени degx(v) относительно символов x1,... , xm и пропуская символы j, можно установить, есть ли среди них моном v, а значит, можно ли вывести его с помощью системы продукций. При этом каждая мономиальная метка j, содержащаяся в таком мономе, показывает, что при его выводе использовалось правило zj ^ tjfcj(z,x). В самом деле, из системы уравнений (1) и метода последовательных приближений нетрудно видеть, что, применяя это правило вывода к моному, мы умножаем его слева на символ j. Следовательно, мономиальные метки монома решают проблему его синтаксического анализа, показывая, какие правила вывода кс-языка и сколько раз использовались при выводе этого монома, с точностью до порядка их применения. Информацию о мономиальных метках монома можно получить в виде (п+т)-крат-ного интеграла по циклу, где числа n и m не зависят от степени монома и равны числу нетерминальных и терминальных символов грамматики кс-языка соответственно. Рассмотрим коммутативный образ [4] ФСР (2) (3) ci(z1 (x,t)) = E Sa(t)xa, сгруппированный по степеням xa в кратный ряд Гартогса [5, 6]. Назовём синтаксическим полиномом монома v относительно кс-языка z1(x) = = z1 (x,e) коэффициент sa(t) ряда Гартогса (3), такой, что xa = ci(v). Мономиальные метки, содержащиеся в некоммутативных мономах кс-языка, не исчезают при переходе от ФСР (2) к его коммутативному образу (3) и сохраняются в виде мономов синтаксических полиномов, поскольку все коэффициенты ФСР (3) являются целыми положительными числами [7, 8]. Следовательно, если синтаксический полином монома относительно кс-языка равен нулю, то моном не принадлежит этому языку. Следующая теорема даёт принципиальную возможность получить синтаксические полиномы sa(t) в виде кратного интеграла по циклу, который может быть вычислен с помощью многомерных вычетов. Теорема 1. При всех t, достаточно близких к нулю, и всех мультииндексах а синтаксический полином sa(t) задаётся равенствами Sa(t) 1 Г z1 det(^ij - (ci(Q*(z, x,t)))Z ) dz Л dx 1 / 1 г дЦаН /z1 det(- (ci(Q*(z,x,t)))) dz, Yz хГх Sa(t) где Yz = (N = • • • = |zn| = e} и Гх = {|xi| = ... = |xm| = 8} -циклы интегрирования; 0 < 8 < e < 1; dz = dz1 Л ... Л dzn; dx = dx1 Л ... Л dxm; xa+I = x^1+1 ■ • • • ■ xmm+1; a! = «1! ■ ... ■ am!; (z - ci(Q*(z,x,t))) = (z1 - ci(Q1(z, x, t))) ■ ... ■ (zn - ci(Qn(z,x,t))); dIMI Qai+...+am = т; a~1-; 8ij - дельта Кронекера. dxa ox^ ■ ... ■ dxm Формулы (4) и (5) позволяют эффективно осуществлять синтаксический анализ монома, находя его синтаксический полином. Так, кратный интеграл (4) можно вычислить как повторный, используя формулу Коши и разложение в степенной ряд подынтегральной функции.

Ключевые слова

коммутативный образ, формальный степенной ряд, синтаксический анализ, интегральное представление, formal power series, commutative image, syntactical analysis, integral representation

Авторы

ФИООрганизацияДополнительноE-mail
Сафонов Константин ВладимировичСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёвадоктор физико-математических наук, профессор, заведующий кафедройsafonovkv@rambler.ru
Колбасина Ирина ВалерьевнаСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёвааспиранткаkabaskina@yandex.ru
Егорушкин Олег ИгоревичСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёвастарший преподавательolegegoruschkin@yandex.ru
Всего: 3

Ссылки

Egorushkin O. I., Kolbasina I. V., and Safonov K. V. On solvability of systems of symbolic polynomial equations // Журн. СФУ. Сер. Матем. и физ. 2016. Т. 9. Вып. 2. С. 166-172.
Егорушкин О. И., Колбасина И. В., Сафонов К. В. О совместности систем символьных полиномиальных уравнений и их приложении // Прикладная дискретная математика. Приложение. 2016. №9. С. 119-121.
Safonov K. V. On power series of algebraic and rational functions in Cn // J. Math. Analysis Appl. 2000. V. 243. P. 261-277.
Сафонов К. В. Об условиях алгебраичности и рациональности суммы степенного ряда // Матем. заметки. 1987. Т. 41. Вып.3. С. 325-332.
Семёнов А. Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик // Доклады АН СССР. 1973. №212. С. 50-52.
Сафонов К. В., Егорушкин О. И. О синтаксическом анализе и проблеме В. М. Глушкова распознавания контекстно-свободных языков Хомского // Вестник Томского государственного университета. 2006. Приложение № 17. С. 63-67.
Salomaa A. and Soitolla M. Automata-Theoretic Aspects of Formal Power Series. N.Y.: Springer Verlag, 1978.
Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1973.
 Синтаксический анализ программ методом интегральных представлений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/39

Синтаксический анализ программ методом интегральных представлений | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/39