Поскольку семантическая составляющая передается «вверх по дереву», а нисходящий анализ строит его наоборот, сверху вниз, то включение семантической компоненты в синтаксический анализ потребует «хитрых» решений. Рассмотрим некоторые из них:
при
программировании распознавателя методом рекурсивного спуска «обратный ход» семантики
соответствует передаче результата рекурсивной функции, каковой является каждый
распознаватель. Результатом работы каждого распознавателя является ссылка
(указатель, индекс) на описание семантики распознаваемого нетерминала в
семантических таблицах. Текущий распознаватель, получая в таком виде семантику нетерминалов правой
части правила, формирует из них собственную результирующую семантику (возможно,
создавая новые записи в семантических таблицах) и возвращает ее в качестве
собственного результата;
при
использовании автоматного распознавателя (магазинного автомата), который не
строит дерево, а обходит его сверху
вниз, можно в качестве промежуточного уровня построить структуру данных,
соответствующую синтаксическому дереву. После чего дерево в терминальные
вершины помещаются ссылки на первичную семантику, выполнятся рекурсивный обход
дерева, в каждой нетерминальной вершине вызывается семантическая процедура, соответствующая
нетерминалу этой вершины. Способ формирования семантики «снизу вверх» аналогичен
применяемому в рекурсивном спуске.
Построение синтаксического дерева в явном виде в магазинном автомате нуждается в пояснении. Для этого:
каждый нетерминал, содержащийся в стеке, имеет
ссылку (указатель) на свою вершину –
корень недостроенного поддерева;
при замене в
стеке левой части правила на правую для нетерминалов (и терминалов тоже) правой
части создаются вершины дерева, ссылки на них помещаются в нетерминалы стека и
вершину, связанную с нетерминалом левой части;
таким
образом, нисходящему применению любого правила соответствует достраивание
поддерева, определяемого этим правилом.
