2020-04-07
171
Дерево разбора программы может оказаться избыточно детальным для последущей обработки. Например, если у нас имеется оператор цикла
while (n > 0)
{
if (n%2)
y = y*x;
x = x*x;
n = n / 2;
}
то синтаксическое дерево для этого цикла может иметь примерно следующий вид:
| ... |
| оператор |
| ... |
| цикл |
| while |
| ( |
| выр |
| ) |
| оператор |
| блок |
| конст |
| прост-выр |
| слаг |
| множ |
| > |
| конст |
| прост-выр |
| слаг |
| множ |
| { |
| } |
| послед |
| оператор |
| послед |
| условный |
| ... |
| ... |
| ... |
| ... |
| ... |
| ... |
| ... |
Такое дерево несомненно полезно, если мы, например, занимаемся рефакторингом и собираемся осуществлять синтаксические преобразования. Однако, если нас интересует смысл программы, то нам уже не интересны подробности о том, что в записи оператора цикла или условного оператора имеются скобки, что последовательность операторов заключается в фигурные скобки, а также вся последовательность промежуточных правил вывода типа "выр прост-выр слаг множ...", которая вполне возможно имела лишь вспомогательный характер в задании грамматики языка. По-существу, нам интересно лишь то, что есть оператор цикла, у которого есть условие и тело, состоящее из трёх операторов, для каждого из которых нужны аналогичные сведения. Таким образом мы абстрагируемся от того, как именно в языке записываются те или иные конструкции и выделяем лишь их существенные свойства и связи. В результате можно сформулировать так называемый абстрактный синтаксис, в котором каждое понятие означает синтаксическую категорию, для каждой альтернативы понятия указан её тип, а также перечень именованных и типизированных атрибутов и связей. Естественно, что для абстрактного синтаксиса становятся неуместными вопросы приоритета операций, однозначности, устойчивости и т.п. Абстрактный синтаксис языка, на котором записана приведенная выше программа, может иметь следующий вид:
программа::= оператор*
оператор::= (while условие:выр тело:оператор*)
| (if условие:выр то:оператор* иначе:оператор*)
| (присв получатель:перем источник:выр)
выр::= (перем имя:строка)
| (конст знач:число)
| (биноп оп:(+,-,...) левое:выр правое:выр)
Абстрактный синтаксис можно рассматривать как набор правил для формирования дерева абстрактного синтаксиса, в котором каждая вершина помечена типом вершины и значениями атрибутов, а дуги - именами составных частей. Например, дерево абстрактного синтаксиса того же цикла будет иметь следующий вид:
| ... |
| правое |
| левое |
| тело |
| условие |
| биноп оп:">" |
| перем имя:"n" |
| конст знач:"0" |
| условие |
| условие |
| то |
| иначе |
| источник |
| получатель |
| ... |
| ... |
| ... |
| ... |
| ... |
| if |
| присв |
| while |
Нарисовав такое дерево, мы неявно ввели конкретный синтаксис для языка абстрактного синтаксиса, хотя он и имеет графическую форму. То же дерево может быть изображено и в текстовой форме, которой мы будем придерживаться в дальнейшем:
(while
условие:(биноп оп:">" левое:(перем имя:"n") правое:(конст знач:"n"))
тело:{(if
условие:(биноп оп:">"
левое:(перем имя:"n")
правое:(конст знач:"0")))
то:{(присв
получатель:(
перем имя:"y"
источник:(биноп оп:"*"
левое:(перем имя:"y")
правое:(перем имя:"y")))}
иначе:{})
(присв
получатель:(
перем имя:"x"
источник:(биноп оп:"*"
левое:(перем имя:"x")
правое:(перем имя:"x")))
(присв
получатель:(
перем имя:"n"
источник:(биноп оп:"-"
левое:(перем имя:"n")
правое:(конст знач:"1")))})
Фигурные скобки здесь означают список элементов, получающийся из грамматической конструкции ненулевой итерации.
При переходе от конкретного синтаксиса к абстракному возможны также различные преобразования, связанные с минимизацией количества абстрактных понятий. Например, все формы цикла заменяются одной, у условного оператора добавляется отсутствующая иначе-часть, явным образом вставляются все умолчательные действия и т.п.
7.4 Контекстно-зависимый анализ
Некоторые свойства синтаксиса языка зависят от контекста и не могут быть описаны контекстно-свободными грамматиками. Но даже в тех случаях, когда такое описание возможно, оно может оказаться неоправданно сложно. Пусть, например, понятие X определено как последовательность понятий (разделов) A, B, C, D и E, некоторые из которых могут повторяться:
X::= (A | B | C | D | E)*
но так, чтобы выполнялись следующие ограничения:
· Должен появиться либо раздел A, либо раздел B, но не более одного раза.
· Раздел C может появляться только если указан раздел B
· Все разделы E могут появляться, если указан раздел A, но после всех разделов D.
Мы можем изменить грамматику, введя вспомогательные понятия XA – «X, в котором есть A», XB – «X, в котором есть B», XBC – «X, в котором B появляется до C», XCB - «X, в котором С появляется до B», XEA – «X, в котором хотя бы одно E появляется до A», XAE – «X, в котором все E появляются после A»
X::= XA | XB
XA::= XAE | XEA
XAE::= D* A D*E*
XEA::= D*E+ A E*
XB::= XBC | XCB
XBC::= D* B D* С D*
XCB::= D* C D* B D*
Хотя преобразованная грамматика в точности выполняет указанные ограничения, она существенно затрудняет понимание, да и с точки зрения реализации может оказаться менее эффективной. Поэтому в подобных случаях обычно ограничения оставляют в виде дополнительных условий к грамматике, предполагая, что они будут проверяться дополнительным проходом по дереву разбора.
Отдельного прохода требует идентификация объектов, то есть сопоставление определений именованных объектов – переменных, типов, функций, и т.п. - с их использованиями. Обычным требованием здесь является то, что для каждого использования должно быть хотя бы одно определение. Если язык допускает более одного определения, то они должны не противоречить друг другу. Формально контекстные ограничения такого вида могут быть описаны, например, атрибутными грамматиками [АхоУльман].
В некоторых случаях, синтаксическая структура фразы может зависеть от результатов идентификации. Например, в языке Алгол 68 предложение
.A x:= 2
может означать описание переменной x с начальным значением 2, если А описан как тип, а может - присваивание 2 по адресу (.A x), если A определена как операция, вырабатывающая адрес. Аналогичная ситуация возникает и в языке C, где конструкция
x * y;
может оказаться либо оператором, вычисляющим выражение x*y, если x - переменная, либо описанием переменной y типа указатель на x, если x описан ранее как тип.
Наиболее существенную часть контекстно-зависимого анализа составляет статический анализ типов, то есть определение (вывод) типов объектов и выражений и проверка типовой правильности. Далее мы ещё обсудим понятие системы типов в языках программирования[7].
Семантика
Теперь, когда разобрана структура программы и установлены все связи между объектами и их типы, мы можем приступать к семантике, то есть определению того, что делает данная программа. Формальное описание семантики - весьма сложная задача, и поэтому зачастую разработчики языка ограничиваются словесными описаниями. Естественно, это оставляет вероятным неоднозначное и неполное толкование, со всеми вытекающими из этого последствиями. Например, две разные реализации одного и того же языка могут работать по-разному. То же относится и к любым инструментам, опирающимся на семантику: анализу, верификации и т.п. С другой стороны, если формальное описание оказывается таким сложным, что обычный программист не может в нём разобраться или не хочет тратить на это своё время, то он вообще остаётся беспомощным. К тому же, неформальное - совсем не обязательно означает неточное или неполное.
Далее мы кратко опишем несколько подходов к формальному описанию семантики на примере рассмотренного ранее простого языка, в котором есть только присваивания, переменные и циклы, а выражения строятся из переменных, констант и бинарных операций.
