Как известно, один и тот же синтаксис может быть представлен различными грамматиками. Они эквивалентны между собой, поскольку распознают одно и то же множество цепочек (Как известно, проблема эквивалентности формальных грамматик алгоритмически неразрешима, т.е. невозможно разработать алгоритм, устанавливающий эквивалентность двух произвольных грамматик). Мы уже видели, что требования к грамматикам восходящего и нисходящего разбора также различны. Различны и технологически подходы к реализации одних и тех же элементов синтаксиса (повторений, необязательных элементов синтаксиса и т.п.). Поэтому получается, что в различных грамматиках при разборе одного и того же предложении будут строиться различные деревья, но результат трансляции (например, последовательность выполняемых операций в выражении) должен быть если не одинаковым, то эквивалентным.
Поэтому задача семантического анализа состоит в том, чтобы извлечь из формально построенного синтаксического дерева содержательную информацию о структуре программы. И делается это всегда уникальным способом, отражающим смысл каждого правила формальной грамматики, примененного при построении данного дерева.
Кроме того, существует семантическая связь между элементами
синтаксиса, реализуемыми различными правилами. Например, описание типа
переменной в Си вида int a,b=5,c[10] синтаксически
реализуется группой правил, задающих цикл описания отдельных переменных, а
общий тип и полученный список определяется отдельным правилом. Но между ними
имеется связь, состоящая в том, что семантика типа int распространяется на все элементы списка. Отсюда имеем
различные варианты реализации семантических процедур:
если
синтаксическая единица реализуется в одном правиле, то ее семантическая
обработка., а также генерация кода или интерпретация могут быть выполнены независимой
семантической процедурой. Взаимодействие с другими процедурами происходит по
указанной выше схеме: процедура использует ссылки на семантику символов правой
части (потомков поддерева для этого правила), формирует и возвращает ссылку на
семантику левой части (корневой вершины поддерева). То же самое можно сказать и
способе передачи сгенерированного кода или результата интерпретации;
если синтаксическая
единица реализуется несколькими правилами, то такая стройная картина
нарушается. Например, может потребоваться более сложное взаимодействие семантических
процедур (не только вверх-вниз по дереву, но и между смежными вершинами и т.п.).
Для передачи результатов между процедурами могут использоваться не только
ссылки на записи в семантических таблицах, но и более сложные структуры данных.
В приведенном выше примере правила, соединяющее общий тип описания (int) со списком переменных, имеет вид X::=TL и получает от первого нетерминала ссылку в семантической таблице типов, а от второго нетерминала множество ссылок (массив, список) на записи в семантической таблице переменных. Семантическая процедура правила должна дополнить все цепочки описаний типа данных в этом множестве записей указанным общим типов (причем по семантике определения типа данных в Си он должен быть дописан в конец цепочки).