Множество FIRST и алгоритм его построения

Формально множество FIRST для заданного нетерминального символа U определяется как множество терминальных символов, с которых может начинаться цепочка, выводимая из U, т.е.

m  FIRST(U): U => mb

Графическая интерпретация – в деревьях с корневой вершиной U символы FIRST(U) – это крайние правые терминальные символы дерева. Соответственно, если U в грамматике обозначает некоторый элемент синтаксиса (выражение, оператор, определение, список параметров и т.п.), то множество FIRST(U) на самом деле является ответом на вопрос: «С чего может начинаться (выражение, оператор, определение, список параметров)»? Такое содержательное понимание позволяет в простых случаях построить множество FIRST, просто просматривая все возможные последовательности выводов, (учитывая на содержательном уровне продуцируемые правилами повторы и вложенности). Например:

Z:: U#

U:: U, T | T

T:: *T | A

A:: Aa | a

1. FIRST(U): U=> U, T=> U, T, T=> T, …, T

Символ U производит цепочку, состоящую из нетерминалов T, разделенных запятыми.

2. T=> *T=> **T *   FIRST(U)

3. T=> Aa=> Aaa=> Aaaa=> aaaa a    FIRST(U)

Символ T производит цепочку «звездочек», пока не заменится на символ A, который производит цепочку символов a. Таким образом, T порождает последовательность «звездочек» (возможно, пустую), за которой следует последовательность символов a. Отсюда FIRST(U)={a, *}.

Если формализовать просмотр возможных правил подстановки, то можно предложить простой рекурсивный алгоритм построения множества FIRST для заданного нетерминала U:

· Просматривается грамматика и выбираются правила с символом U в левой части;

· Если в правой части находится терминальный символ, то он добавляется к множеству, т.е. U:: ab => a FIRST(U);

· Если в правой части находится нетерминальный символ, то для него также строится множество FIRST, которое включается в FIRST(U), т.е.. U:: Vb => FIRST(V)   FIRST(U).

На практике здесь удобно использовать рекурсивную функцию, которая возвращает строку символов множества FIRST, тем более, что принцип рекурсии достаточно ясно отражает суть происходящих событий: для решения задачи с заданным параметром U требуется решить аналогичную задачу с другим значением входного параметра. Кроме того, следует учесть рекурсивное «зацикливание» алгоритма для прямой или косвенной левосторонней рекурсии (например, для правила U:: U, T). С этой целью рекурсивные вызовы должны передавать ссылку на строку, содержащую все нетерминалы, для которых FIRST на данный момент уже строится.

Влияние аннулирующих правил. Множество FIRST^*. Описанная выше идиллия нарушается, как только в грамматике появляются правила (нетерминалы), которые могут порождать пустые цепочки, или аннулирующие правила (нетерминалы). Если такой нетерминал встречается в цепочке при построении множества FIRST, то он может быть пропущен, и тогда «на первое место» выходит следующий за ним символ правила, для которого справедливы все те же действия. Кроме того, аннулирующий нетерминал может порождать пустую цепочку, а может и не порождать, что тоже усложняет алгоритм. Давайте же разберемся.

Для начала определим, когда нетерминал является аннулирующим. Здесь необходимо учесть, что пустая цепочка может быть произведена не только непосредственно правилом U:: e, но и последовательностью выводов U=> e. Свойство «аннулируемости» может быть определено рекурсивно и аналогично вычислено простым рекурсивным алгоритмом:

· нетерминал U порождает пустую цепочку, если имеется правило U:: e, а также,

· если имеется правило вида U:: ABC, в правой части которого находятся только аннулирующие нетерминалы.

Еще один момент связан с возможностью быть аннулирующим самого нетерминала U, для которого строится FIRST. Это означает, что сам нетерминал может порождать пустую цепочку, но тогда «на первое место» выходит окружение (контекст), в котором может находиться нетерминал U. Поэтому нам придется рассмотреть два случая: множество FIRST^*(U), построенное без учета контекста, и FIRST(U), учитывающий окружение соответствующего нетерминала. Алгоритм построения FIRST^*(U):

1. Просматривается грамматика и выбираются правила с символом U в левой части и непустой правой частью;

2. Выполняется цикл просмотра символов правой части выбранного правила(до первого терминала или до конца);

3. Если очередной символ A_i является терминальным, то он включается в множество (A_i  FIRST^*(U)) и цикл просмотра завершается.

4. Для очередного нетерминала A_i строится множество FIRST^*(A_i), которое тоже добавляется к FIRST^* (U), т.е. FIRST^*(A_i)  FIRST^* (U).

5. Если A_i=> e, т.е. нетерминал является аннулирующим, то происходит переход к следующему символу правой части, иначе цикл просмотра завершается.

Особенности построения FIRST(U), учитывающего окружение (контекст) нетерминала, легко можно увидеть на синтаксическом дереве (см. рисунок выше). Если нетерминальная вершина U порождает пустое поддерево, то необходимо подняться вверх по дереву и найти те терминалы, которые могут следовать за U. Ниже мы обсудим все подробности построения множества последователей или FOLLOW(U). А пока заметим, что алгоритм построения FIRST(U) дополняется еще одним пунктом:

6. Если же при выполнении п.3-5 мы дошли до конца правой части правила, т.е. оно состоит только из аннулирующих нетерминалов, то необходимо подняться вверх по дереву к последователю левой части, т.е. FOLLOW(U)  FIRST(U).

Пример для грамматики без аннулирующих правил. Чтобы «вручную» отследить выполнение рекурсивного алгоритма, можно построить граф-схему (дерево) связей правил и множеств. В его вершины нужно помещать множества FIRST, вычисляемые для символов, и правила, на основе которых они вычисляются. Так выглядит граф-схема для нетерминала уже использованной грамматики:

Z:: U#

U:: U, T | T

T:: *T | A

A:: Aa | a