СИНТАКСИЧЕСКИЙ АНАЛИЗ ПРОГРАММ

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

Пример. Рассмотрим язык арифм. выражений, порожденный грамматикой (см. Грамматика порождающая), система правил которого имеет вид

где Е — аксиома грамматики; — терминальные символы; — нетерминальные символы. Проанализируем цепочку

Очевидно, цепочка (4) является правильной, т. к. в данной грамматике существует вывод

Этому выводу соответствует «дерево» (рис.), которое в лингвистике наз. «деревом» синтаксического анализа (д. с. а.).

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

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

«Дерево» синтаксического анализа.

Так, для рассмотренного выше примера, в цепочке (4) на основании правила (2) производится замена подцепочки нетерминальным символом 2; затем на основании правила (3) вхождения символа b заменяются нетерминальным символом и, наконец, в силу правила (1), полученная цепочка сворачивается в аксиому. Оба типа стратегии наз. левосторонними, поскольку общий порядок обработки символов в цепочке — слева направо.

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

Лит.: Гинзбург С. Математическая теория контекстно-свободных языков. Пер. с англ. М., 1970 [библиогр. с. 310—319]; Фельдман Дж., Грис Д. Системы построения трансляторов. Пер! с англ. «Алгоритмы и алгоритмические языки», 1971, в. 5. Г. Е. Цейтлин.