О взаимосвязи синтаксиса и семантики

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

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

Кроме того, существует семантическая связь между элементами синтаксиса, реализуемыми различными правилами. Например, описание типа переменной в Си вида int a,b=5,c[10] синтаксически реализуется группой правил, задающих цикл описания отдельных переменных, а общий тип и полученный список определяется отдельным правилом. Но между ними имеется связь, состоящая в том, что семантика типа int распространяется на все элементы списка. Отсюда имеем различные варианты реализации семантических процедур:

В приведенном выше примере правила, соединяющее общий тип описания (int) со списком переменных, имеет вид X::=TL и получает от первого нетерминала ссылку в семантической таблице типов, а от второго нетерминала множество ссылок (массив, список) на записи в семантической таблице переменных. Семантическая процедура правила должна дополнить все цепочки описаний типа данных в этом множестве записей указанным общим типов (причем по семантике определения типа данных в Си он должен быть дописан в конец цепочки).