Прежде всего нужно установить, какие нетерминалы могут генерировать пустую строку. Для этого создадим одномерный массив, где каждому нетерминалу соответствует один элемент. Любой элемент массива может принимать одно из трех значений: YES, NO или UNDECIDED. Вначале все элементы имеют значение UNDECIDED. Мы просматриваем грамматику столько раз, сколько требуется для того, чтобы каждый элемент принял значение YES или NO.

При первом просмотре исключаются все порождающие правила, содержащие терминалы. Если это приводит к исключению всех порождающих правил для какого-либо нетерминала, соответствующему элементу массива присваивается значение NO. Затем для каждого порождающего правила с е в правой части тому элементу массива, который соответствует нетерминалу в левой части, присваивается значение YES, и все порождающие правила для этого нетерминала исключаются из грамматики.

Если требуются дополнительные просмотры (т.е. значения некоторых элементов массива имеют все еще значение UNDECIDED), выполняются следующие действия:

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

2. Каждый нетерминал в правой части порождающего правила, который может генерировать пустую строку, стирается из правила. В том случае, когда правая часть правила становится пустой, элементу массива, соответствующему нетерминалу в левой части, присваивается значение YES, и все порождающие правила для этого нетерминала исключаются из грамматики.

Этот процесс продолжается до тех пор, пока за полный просмотр грамматики не изменится ни одно из значений элементов массива. Если допустить, что вначале грамматика была «чистой» (т. е. все нетерминалы могли генерировать конечные или пустые строки), то теперь все значения элементов массива будут установлены на YES или NO. Рассмотрим этот процесс на примере грамматики

1. A->XYZ 7. Q->aa

2. X->PQ 8. Q->e

3. Y->.RS 9. S->cc

4. R->TU 10. T->dd

5. P->e 11.U->ee

6. P->a 12. Z->e

После первого прохода массив будет таким, как показано в табл 4.1, а грамматика сведется к следующей:

1. A->XYZ

2. X->PQ

3. Y->RS 4.R->TU Таблица 4.1

U-UNDECIDED (НЕРЕШЕННЫЙ) Y-YES (ДА)

N - NO (НЕТ)

После второго прохода массив станет таким, как показано в табл. 4.2, а грамматика примет вид 1. A->XY

Таблица 4.2

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

P->QR Q->qR

можно заключить, что Q есть непосредственный предшественник Р, а q - непосредственный предшественник Q. В матрице предшественников для каждого нетерминала отводится строка, а для каждого терминала и нетерминала - столбец. Если нетерминал А, например, имеет в качестве непосредственных предшественников В и С, в А-ю строку в В-м и С-м столбцах помещаются единицы (табл. 4.4).

Таблица4.4.

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

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

P->QR Q->qV

можно заключить, что q есть символ (не непосредственного) предшественника Р. Или же, как вытекает из матрица: непосредственнтх предшественников, единица в Р-й строке Q-ro столбца и единица в Q-й строке q-го столбца свидетельствуют о том, что если мы хотим сформировать полную матрицу предшественников (а не только непосредственных), нам нужно поместить единицу в Р-ю строку q-го столбца. В обобщенном варианте, когда в (i,j/)-й позиции и в (),к)-й позиции стоят единицы, нам следует поставить единицу в (i,k)-m позицию. Пусть, однако, и в (к,1)-й позиции также стоит единица. Тогда этот процесс рекомендуется выполнить вновь, чтобы поставить единицу в -ю позицию, и повторять его до тех пор, пока не будет таких случаев, когда в -и позиции и в (),к)-й позиции появляются единицы, а в (i,k)-й позиции - нет.

Приведенный выше алгоритм иллюстрируется множеством порождающих правил:

A->BC B->XY X->aa

из котортх легко ввести три единица: в матрицу непосредственнтх предшественников и путем дедукции еще три единицы - в полную матрицу предшествования в соответствии с тем, что X является не непосредственнтм предшественником А, а а - не непосредственнтм предшественником В, а также А (табл. 4.5). В таблице не непосредственные предшественники co *.

Таблица 4.5.

A B C ... X Y

а ...

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