Алгоритм решения расширенной проблемы синтаксического анализа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/32

Алгоритм решения расширенной проблемы синтаксического анализа

Уточняется формулировка расширенной проблемы синтаксического анализа: разработать беступиковый алгоритм, который позволяет установить, может ли данный моном быть выведен при помощи системы продукций, образующих грамматику контекстно-свободного языка программирования, а также описать сразу все выводы этого монома, если такие существуют. Описание вывода монома состоит в следующем: определить, какие продукции из грамматики языка, сколько раз и в каком порядке применяются, что равносильно построению всех деревьев вывода. Предложен алгоритм решения расширенной проблемы синтаксического анализа, основанный на иерархии маркированных скобок; маркировка скобок показывает, за какой продукцией они закреплены, и позволяет проследить порядок их использования. Алгоритм имеет простую программную реализацию, дана также оценка сложности алгоритма.

An algorithm for solving the extended parsing problem.pdf При разработке перспективных языков программирования, в том числе предназначенных для обеспечения работы суперкомпьютеров, включая квантовые, возникает необходимость исследовать контекстно-свободные языки (кс-языки) и контекстно-свободные грамматики (кс-грамматики). Один из аспектов связан с проблемой синтаксического анализа (разбора) выражений, написанных на языке программирования. Обычно для синтаксического анализа используются специальные программы - пар-серы, разработанные применительно к тому или иному языку программирования и основанные на определённых алгоритмах разбора. Однако в ситуации, когда разрабатывается и тестируется новый язык программирования, никаких парсеров ещё нет. Когда необходимо провести синтаксический анализ некоторого выражения относительно совокупности грамматических правил, находящихся в стадии разработки, могут быть полезными различные алгоритмы, в том числе имеющие высокую сложность - как правило, анализируются выражения ограниченной длины, и в этом случае высокая сложность алгоритма не играет решающей роли. Если длина тестируемой программы не слишком велика, сложность алгоритма синтаксического разбора может быть даже выше экспоненциальной - важно лишь, чтобы алгоритм был вполне конструктивным и допускал простую программную реализацию. Отметим, что практически все известные в настоящее время языки программирования являются кс-языками, порождёнными кс-грамматиками, и потому кс-язык является адекватной математической моделью любого языка программирования, в которой правильным программам отведена роль мономов кс-языка. Проблема синтаксического анализа мономов кс-языка возникла на заре теории языков программирования в 50-60-х годах прошлого века. Удивительно, но до настоящего времени в формулировке проблемы сохраняются разночтения, в связи с чем возникает необходимость уточнить её, а именно: рассмотрим кс-язык, порождённый кс-грамматикой, которая представляет собой систему правил вывода (продукций) Zj ^ Qji (z,x), ..., Zj ^ QjPj (z,x), j = 1, ...,n, (1) где qjk(z,x) -мономы от некоммутативных символов алфавита z1 ...,zn, x1,...,xm с числовым коэффициентом равным 1. Символы x1, . . . , xm из второй группы называются терминальными символами и образуют словарь кс-языка. Применительно к языкам программирования терминальными символами являются цифры, буквы, вспомогательные знаки, а также состоящие из них «блоки», обозначающие, например, операторы языка программирования. Символы первой группы z1,... ,zn называются нетерминальными, поскольку не присутствуют явно в тексте программ, а играют вспомогательную роль, участвуя в кс-грамматике как совокупности продукций, порождающих кс-язык. По правилам грамматики формируются мономы от терминальных символов x1,...,xm, которые интерпретируются как правильные предложения языка [1, 2]. Такие мономы рассматриваются как корректные, в отличие от произвольных мономов, которые могут не соответствовать правилам грамматики, а значит, являются некорректными. Вывод корректных мономов кс-языка с помощью системы продукций (1) осуществляется так: продукции сначала применяются к начальному символу z1, а затем к другим получающимся мономам неограниченное число раз и в любом порядке, что позволяют продуцировать новые мономы от терминальных и нетерминальных символов. Вывод заканчивается, когда получается моном только от терминальных символов - это и есть корректный моном языка, дальнейший вывод из него невозможен, поскольку продукции применимы только к нетерминальным символам. Все корректные мономы образуют соответствующий кс-язык. В проблеме синтаксического анализа мономов кс-языка выделяют две составляющие: первая часть, называемая проблемой принадлежности или этапом синтаксического контроля, состоит в том, чтобы определить, принадлежит ли данный моном рассматриваемому кс-языку, т. е. может ли быть получен из начального символа z1 при помощи продукций; вторая часть проблемы - описание синтаксической структуры монома. Такое описание понимается в литературе по-разному. Так, различные авторы при постановке проблемы синтаксического анализа допускают следующие варианты: требуется разработать алгоритм для того, чтобы установить, какие правила подстановки и сколько раз использовались при выводе данного монома, при этом порядок использования правил подстановки не имеет значения; какие правила подстановки, сколько раз и в каком порядке использовались при выводе этого монома, т. е. построить хотя бы один из возможных выводов монома [2]. Как видно, для полного решения проблемы синтаксического анализа необходимо построить сразу все возможные выводы монома, если таких несколько. Кроме того, исследователи уделяют большое внимание тому, чтобы разработать беступиковый алгоритм синтаксического анализа мономов кс-языка [1, с. 248]). В связи с этим будем называть расширенной проблемой синтаксического анализа мономов кс-языка проблему разработки беступикового алгоритма, который позволяет установить, может ли моном быть выведен при помощи системы продукций кс-языка (решить проблему принадлежности), а также найти сразу все выводы этого монома; описание вывода монома будем понимать следующим образом: определить, какие продукции, сколько раз и в каком порядке применяются для вывода этого монома, что равносильно построению всех деревьев вывода. Синтаксический анализ монома, проводимый в соответствии с этим алгоритмом, будем называть расширенным синтаксическим анализом (алгоритм 1). Для решения расширенной проблемы синтаксического анализа рассмотрим расширенную систему уравнений Хомского - Шютценберже, которая имеет вид = Qj(z,x,t) = Ы qji(z,x) ] + • • • + j[ j(z,x) L j =1 ... Решение этой системы можно получить методом последовательных приближений [2]: z(fc+1)(x,t) = Q*(z(fc)(x,t),x,t); k = 0,1,...; z(0) = 0. (2) В результате решение получается в виде формальных степенных рядов те zj = zj(x, t) = Y,{z*j,wi) wi, j = 1,..., n, i=0 где wi - мономы от символов x1,... ,xm,t11 ,t12,... ,tnpn с числовыми коэффициентами (z*,wi), содержащие также систему открывающихся и закрывающихся скобок. Алгоритм 1. Решение расширенной проблемы синтаксического анализа Вход: моном (программа) w степени (длины) N. 1: Проводим N итераций метода последовательных приближений (2) для решения соответствующей расширенной системы уравнений Хомского - Шютценберже. 2: Перебираем все полученные в шаге 1 мономы степени N, определяя те из них, которые, с точностью до множителей tjk, совпадают с мономом w. Если таких мономов нет, то моном w вывести невозможно; если есть, то они дают решение расширенной проблемы синтаксического анализа в соответствии со следующим шагом. 3: Считываем все найденные в шаге 2 мономы слева направо, устанавливая иерархию маркированных скобок (по признаку сравнения скобок - внутренняя или внешняя) и определяя тем самым порядок применения продукций при выводе монома w. Теорема 1. Сложность алгоритма 1 равна O \\^NgdJ, где g и d - некоторые целые числа. Несмотря на то, что сложность данного алгоритма высокая, он может быть использован для синтаксического анализа применительно к языку программирования, находящемуся в стадии разработки.

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

расширенная проблема синтаксического анализа, контекстно-свободный язык, сложность алгоритма, extended parsing problem, context-free language, complicity of algorithm

Авторы

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

Ссылки

Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1973.
Salomaa A. and Soitolla M. Automata-Theoretic Aspects of Formal Power Series. N.Y.: Springer Verlag, 1978.
 Алгоритм решения расширенной проблемы синтаксического анализа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/32

Алгоритм решения расширенной проблемы синтаксического анализа | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/32