В матрице достижимости единицы соответствуют вершинам, между которыми есть соединительные пути(табл. 4.6 и 4.7).

Таблица 4.6 Таблица 4.6

Матрица смежности Матрица достижимости

Читатель, вероятно, знаком с алгоритмом выполнения транзитивного замыкания по алгоритму Уоршалла[56].

Приведем версию этого алгоритма на Алголе 68. Вначале массив А представляет собой матрицу смежности (или содержит непосредственных предшественников), а в конце трансформируется в матрицу достижимости(или включает всех предшественников). Считается, что индексы в А начинаются с 1.

proc Warshall=(ref[.]int A) void:

begin int upb1=1upb A, upb2=2upbA

for i to upb1

do for j to upb1

do if a[i,j]=1 then

for k to upb2

do if A[j,k]=1 then

A[i,k]=1 fi

od fi

Может показаться, что данной процедуре потребуется внешний цикл, чтобы повторять процесс до тех пор,пока в А не произойдут изменения. Однако по теореме Уоршалла [56] это не является необходимым. Алгоритму Уоршалла для построения nxn матрицы нужно время, пропорциональное п3. Тем не менее с помощью работы Стразена [53] можно доказать, что существует алгоритм, которому нужно время, пропорциональное п2*81. Можно также воспользоваться относительно неплотным характером матрицы непосредственных предшественников и получить более эффективный алгоритм [21].

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

определенным нетерминалом. Поэтому мы строим матрицу следования из порождающих правил грамматики. Например, как вытекает из правила

S->ABC

В может следовать за А, и элемент (А, В) в матрице следования имеет значение 1. Аналогичным образом С может следовать за В, и элемент (В, С) устанавливается на 1. Если В генерирует пустой символ, то естественно заключить, что С может следовать за А, и элемент (А, С) устанавливается на 1. Менее явно правила

P->QR Q->VU

позволяют сделать вывод о том, что R следует за U или, в более общем виде (на основании второго правила), что «любой символ, следующий за Q, следует и за U».

Заметим также, что если, например, В следует за A и b есть предшественник В, то b следует и за А. Таким образом, матрицу предшествования можно использовать для того, чтобы вывести больше символов-следователей и соответственно нарастить матрицу следования.

На основании массива пустых строк, матрицы предшествования и матрицы следования можно проверить признак LL(1). Там, где в левой части более чем одного правила появляется нетерминал, необходимо вычислять направляющие символы различных альтернативных правых частей. Если для каких-либо из этих нетерминалов различные множества направляющих символов не являются непересекающимися, грамматика окажется не LL(1). В противном случае она будет LL(1).

В результате преобразования, выполненного в начале разд. 4.2, грамматика, которая не являлась LL(1)-грамматикой, была преобразована в нее (см. варианты для DECLIST и STATELIST), а именно:

PROGRAM->begin DECLIST comma STATELIST end

DECLIST->d X

X->semi DECLIST

X->e

STATEL/ST->s Y Y->semi STATELIST Y->e

С целью проверки признака LL(1) этой грамматики образуем различные матрицы (табл. 4.8 - 4.10). Необходимо только рассмотреть варианты для X и Y.

Таблица 4.1

Массив пустых строк

Полная матрица предшествования Таблица 49

PR0 GRAM

PR0GRAM STATELIST

DECLIST X Y Begin d s comma

semi end

LIST

STA TELIST X

Матрица следования Таблица 4.10

PROGRAM

STATELIST

DECLIST X Y Begin d s comma semi end

Первый вариант для X имеет множество направляющих символов {semi}. Второй вариант - пустая строка, поэтому нам нужно выяснить, что может следовать за X. Единственным символом-следователем служит comma, так что множеством направляющих символов будет {comma}. Множества направляющих символов являются непересекающимися, следовательно, нарушения условия LL(1) в отношении порождающих правил для нетерминала X нет. Аналогичным образом можно показать, что множествами направляющих символов для Y будут {semi} и {end}, и поэтому мы имеем дело с LL(I) -грамматикой.

4.4. LL(1)-ЯЗЫКИ

Мы уже убедились в том, что существует алгоритм для определения признака LL(1) -грамматики. В этой связи возникают два вопроса:

1. Все ли языки обладают LL(1) -грамматикой?

2. Если нет, то существует ли алгоритм для определения свойства LL(1) языка (т.е. можно ли его генерировать с помощью LL(1)-грамматики) или нет?

Ответ на первый вопрос отрицательный. Например, язык {аоа в {0, /}*}}

генерированный грамматикой с правилами