Отношения между символами в формальных грамматиках

3.3. Отношения между символами в формальных грамматиках

Любая ФГ продуцирует бесконечное множество предложений языка. Но, поскольку в них присутствуют внутренние закономерности (обусловленные самой грамматикой), то и между различными символами (как терминальными, так и нетерминальными) существуют отношения, которые характеризуют их взаимное положение в синтаксическом дереве.

Здесь мы рассмотрим отношения, которые устанавливаются между нетерминальным символом (промежуточной вершиной ДСА) и терминальными символами – конечными вершинами в текущем поддереве и смежных поддеревьях. Для каждого из нетерминалов входящие в отношение терминальные символы образуют множество. Есть несколько видов множеств, каждому из них можно дать не только формальное определение, но и содержательное название и графическую интерпретацию:

1. множество FIRST - «Первых из…»;

2. множество LAST – «Последних из…»;

3. множество FOLLOW – «Следующих за…» или последователей.

Множество 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. Если очередной символ Ai является терминальным, то он включается в множество (Ai Î FIRST*(U)) и цикл просмотра завершается.

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

5. Если AiÞ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

Множество FOLLOW и алгоритм его построения. Легко заметить, что множество FIRST связано с построением дерева «в глубину и влево». Образно говоря, оно представляет собой «левый нижний край» дерева, вернее, множества деревьев, выводимых из исходного нетерминала (на рисунке изображена сдвоенная вершина для вариантов построения цепочек U®T®*T и U®T®A®a ). С применением аннулирующих правил связано другое «перемещение» - вправо от текущего нетерминала с определением смежных символов. Такое движение «вдоль по правой части правила» с погружением в поддеревья нетерминальных вершин позволяет определить свойство смежности двух символов или следования одного символа за другим. Формально множество последователей FOLLOW для заданного нетерминального символа U определяется как множество терминальных символов, которые могут находиться вслед за U в произвольной промежуточной цепочке, выводимой из Z.

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

1. Просматриваются правые части всех правил грамматики, для каждого найденного символа T выполняются следующие действия;

2. Правая часть просматривается от символа, следующего за T, до первого терминала (или до конца);

3. Если очередной символ Ai является терминальным, то он включается в множество (Ai Î FOLLOW(T)) и цикл просмотра прекращается;

4. Если очередной символ Ai является нетерминалом, то для него строится множество FIRST*(Ai), которое добавляется к FOLLOW(T), т. е. FIRST*(Ai) Í FOLLOW(T);

5. Если нетерминал Ai является аннулирующим, т. е. может порождать пустые цепочки, то происходит переход к следующему символу правой части, иначе просмотр завершается;

6. Если при выполнении п.2-5 мы дошли до конца правой части правила, т. е. оно от символа T до конца состоит только из аннулирующих нетерминалов (либо этот символ является последним), то необходимо подняться вверх по дереву к последователю левой части, т. е. FOLLOW(M) Í FOLLOW(T), где M –нетерминал левой части.

Замечания по алгоритмам построения FIRST и FOLLOW. Несмотря на то, что множества FIRST и FOLLOW различны по своей сути, их алгоритмы практически идентичны. Единственная разница состоит в следующем:

- при построении FIRST нетерминал ищется в левых частях правил и просматриваются правые части целиком;

- при построении FOLLOW нетерминал ищется в правых частях правил и они просматриваются от найденного символа до конца. Кроме того, при построении FOLLOW всегда учитывается окружающий контекст, т. е. по окончании цикла просмотра правой части производится построение FOLLOW для нетерминала левой. Для FIRST выделяется как контекстный (FIRST), так и неконтекстный (FIRST*) варианты.

Пример построения множеств FIRST и FOLLOW для простой грамматики. Если Вы заметили, алгоритмы построения похожи, только FIRST ищет нетерминал в левых частях, а FOLLOW – в правых. Граф-схема связей правил и множеств тоже аналогична.

Z:: N#

N:: UM

M:: ,UM | M:: e

U:: aSK

S:: aS | S:: e

K:: [N] | K:: e

Для начала определим аннулирующие нетерминалы грамматики, таковыми являются K и S, имеющие аннулирующие правила. Поскольку нет правых частей, состоящих исключительно из аннулирующих нетерминалов, то все другие таким свойством не обладают.

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

· если аннулирующее правило используется для ограничения повторения последовательности символов (в паре с другими правилами, обозначающими его продолжение), то множество FOLLOW для нетерминала левой части представляет ответ на вопрос: «Какие символы ограничивают повторение элемента синтаксиса, или служат признаком такого окончания»?

· если аннулирующее правило используется для обозначения необязательного элемента синтаксиса, то множество FOLLOW для нетерминала левой части представляет ответ на вопрос: «Какие символы могут находиться на месте отсутствующего элемента синтаксиса»?

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

Z :: LU#

U :: +LU | e

L :: BaSK

S :: aS | e

B :: *B | e

K :: [LU]| e

Приведенная грамматика продуцирует цепочки вида a+*a[*aaa+a] – имена, состоящие из символов a, соединенные в цепочки знаком + (термы). Цепочка может состоять из одного терма. Перед каждым может находиться любое количество (в том числе – нулевое) символов *, вслед за ним могут находиться квадратные скобки с аналогичной цепочкой.

Неформальным обоснованием множеств служит знание о возможных вариантах размещения в строке синтаксиса, соответствующего нетерминалу. Например, множество FOLLOW(L) представляет собой символы, следующие за термом вида **aaa[…], он может быть как внутренним элементом суммы (символ-последователь «+» ), так и последним элементом суммы в скобках (символ-последователь «]» ) или в строке в целом (символ конца строки «#»).