Навигация по AST

Продолжаю возиться с синтаксическим анализом.

Основное преимущество, которое даёт использование AST по сравнению с техникой разбора снизу вверх (bottom-up parsing) – это возможность отложить анализ разобранного текста «на потом». Это может быть удобно по разным причинам. В случае Win32.Utf8 это удобно тем, что требования к анализатору формируются прямо в процессе работы над проектом. По большому счёту я понятия не имею, что получиться в конечном итоге. :-)

Удобство использования AST в значительной степени зависит от того, насколько хорошо реализована навигация по дереву. После давешнего эксперимента с отображением дерева в виде XML, использование XPath для навигации по дереву просто напрашивалось. Однако, после первых экспериментов с XPath выяснилось, что «канонический» XPath не очень хорошо подходит для этой задачи. Проблема заключается в рекурсивной природе AST. Например:

struct _FOO_BAR  {
    int member;
} foobar;

Этот код породит AST примерно такой структуры:

<translation_unit>
 ...
 <declaration>
  ...
  <declaration>
   ...
  </declaration>
  ...
 </declaration>
 ...
</translation_unit>

При этом внешний узел «declaration» соответствует определению переменной «foobar», а внутренний – определению члена структуры «member». Все узлы в этом примере разделены заранее неизвестным числом промежуточных узлов.

Написать XPath, который выберет только внешний «declaration», но не выберет внутренний возможно, но не просто. Задача еще более усложняется, если учесть, что количество вложенных узлов «declaration» может быть произвольным, а начальный узел может находится в середине дерева. Иными словами, задача состоит в том, чтобы выбрать все узлы с определённым именем, которые встретились первыми на пути от начального узла до каждого из его листьев.

Эту закавыку можно обойти двумя способами.

1. Расширить стандартный XPath осью «grandchild», которая и будет реализовывать нужный алгоритм поиска;

2. Модифицировать парсер таким образом, чтобы в процессе разбора повторяющиеся узлы заменялись на узлы с уникальными именами.

Очевидно, что второй способ накладывает дополнительные ограничения на структуру AST, что никак не способствует облегчению жизни программиста. Соответственно, пришлось убедиться на практике, что написать прямолинейную (и неоптимизированную) реализацию XPath совсем не сложно. :-) Это, конечно, не полноценная реализация XPath, но чтобы правильно обработать выражение вроде примера ниже её вполне хватает.

# Найти все функции с именами, заканчивающимися на 'W'.
grandchild-or-self::declaration/init_list_declaration/Declarator[Function][substring(@name, string-length(@value), 1) = 'W']