5.2. Языки и грамматики простого предшествования

Одна из центральных проблем детерминированного восходящего синтаксического анализа состоит в однозначном определении основы – самой левой подцепочки сентенциальной формы, которую требуется редуцировать на данном этапе разбора. Хотелось бы, “перемещаясь” по цепочке слева направо и рассматривая одновременно только два соседних символа, суметь определить, нашли ли мы хвост основы (конец редуцируемой части). А затем, продвигаясь назад к левому концу найти голову основы, опять таки анализируя лишь два соседних символа. То есть мы сталкиваемся с такой задачей: если задана сентенциальная форма . . . x y . . . (где x, y    ), то всегда ли x – хвост основы, или x и y принадлежат основе, или возможны другие варианты? Для решения этой задачи требуется еще до начала разбора исследовать грамматику языка и принять решения относительно каждой пары символов x и y.

Пусть x, y     грамматики G. Предположим, что в языке, определяемом G, при выводе цепочки языка существует сентенциальная форма . . . x y . . . . На некотором этапе разбора либо x, либо y, либо оба символа одновременно должны войти в основу. При этом возникают три различных варианта:

U

. . . . . . x y . .

Рис. 5.5

1). x – часть основы, а точнее ее хвост, а y в основу не входит. Эту ситуацию мы будем обозначать x  y и говорить, что x больше, а, более строго, x предшествует y, так как x редуцируется раньше, чем y. Заметим, что x в этом случае должен быть последним, хвостовым, самым правым символом в правой части некоторого правила грамматики U  . . . x (рис. 5.5). Отметим также, что основа располагается слева от y, и следовательно y должен быть терминалом, так как имеет место канонический разбор.

U

. . . . x y . . . .

Рис. 5.6

2). Оба символа входят в основу. При этом говорят, что x и y имеют одинаковое отношение предшествования, они редуцируются одновременно и изображают это отношение: xy . Очевидно, что в грамматике при этом имеет место правилоU  . . . x y . . . (рис. 5.6).

U

. . x y . . . . . .

Рис. 5.7

3). y – часть основы, а точнее ее голова, а x в основу не входит. Эта ситуация обозначается x  y и можно говорить, что x меньше y или x следует за y. При этом символ y должен быть первым, самым левым в правой части некоторого правила U  y . . . (рис. 5.7).

Если сентенциальной формы . . . x y . . . при выводе цепочек в грамматике G не существует, то мы будем считать что между упорядоченной парой символов (x, y) не определено отношение предшествования (обозначим этот факт как xy).

Заметим, что ни одно из определенных выше отношений не является симметричным: из xy вовсе не следует, что y x , и уж тем более x  y не свидетельствует о том, что y  x .

Пример 5.8.

Рассмотрим в качестве примера грамматику G5 со следующим множеством продукций:

S  bMb M  (L  a L  Ma)

Языку L, порождаемому грамматикой G5, принадлежат цепочки: bab , b(aa)b , b((aa)a)b , b(((aa)a)a)b и т.д.

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

На первый взгляд может показаться, что трудно найти все отношения предшествования между символами грамматики. Создается впечатление, что для этого необходимо построить массу синтаксических деревьев. Да и где гарантия, что все отношения уже найдены?

Дадим более строгие определения отношениям предшествования с тем, чтобы формализовать алгоритм их выявления. Прежде всего определим множество самых левых L(U) и самых правых R(U) символов грамматики для нетерминала U:

L(U) = {x | x      ( (U  x) or  (U  U₁)  (x  L(U₁))},

где здесь и далее U, U₁, U₂   (нетерминалы), а ,   (  )^ (любые цепочки из терминалов и нетерминалов, возможно пустые).

R(U) = {x | x      ( (U  x) or  (U   U₁)  (x  R(U₁))},

Иными словами, символы, которые записаны слева во всех правых частях правил (альтернативах) нетерминала U и составляют множество самых левых символов U – L(U). И далее, если левым символом U является нетерминал U₁, то левыми для U будут и все самые левые символы U₁ (L(U₁)L(U)). Множество R(U) определяется аналогично.

Пример 5.9. На рис. 5.9 а представлена таблица самых левых и самых правых символов для нетерминалов грамматики, рассматриваемой в качестве примера 5.8 в данном разделе. На рис. 5.9 б приведена матрица предшествования – наиболее удобная форма представления отношений предшествования между символами грамматики.



Матрица предшествования с рис. 5.9 б формировалась на основании следующих определений отношений предшествования: