13

Л А Б О Р А Т О Р Н А Я Р А Б О Т А № 2

Приведение грамматики к виду ll(1)

Цель – поиск направляющих символов сконструированной КС-грамматики языка и преобразование ее к виду LL(1).

1. ОСНОВНЫЕ СВЕДЕНИЯ

   Рассмотрим более подробно группу КС-грамматик, так как они являются наиболее универсальными и поэтому более пригодны в качестве основы для описания языков программирования, а, следовательно, и для фазы синтаксического анализа ( разбора ) компиляции.

КС-грамматики, в свою очередь, делятся на три класса:

1. s-грамматики;

2. Q-грамматики;

3. LL(1)-грамматики.

Появление данной классификации КС-грамматик связано со следующей проблемой.

Попытаемся на основе грамматики

<S> - <T>

- <S> + <T>

<T> - id

- <T>  id

осуществить вывод (разбор) предложения аb + cd + e (рис.1).

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

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

Рис. 1. Вывод (разбор) предложения аb + cd + e

Таким образом, чем сложнее грамматика, тем более долгим и запутанным становится алгоритм разбора предложения.

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

Именно такими свойствами обладают S, Q, LL(1)-грамматики.

S-грамматика

КС-грамматика называется S-грамматикой (разделенной или простой) тогда и только тогда, когда выполняются следующие два условия:

1. Правая часть правила начинается терминальным символом.

2. Различные альтернативны одного правила начинаются разными Т-символами.

Грамматика :

1. <S> - a b <R>

2. 2. - b <R> b <S>

3. <R> - a

2. 4. - b <R>

является S-грамматикой, так как отвечает условиям принадлежности. Можно заметить, что на основе грамматики такого вида легко построить вывод любого предложения, потому что на любом шаге возможно спрогнозировать, какое из предложений нужно использовать.

Такой прогноз осуществляется благодаря тому, что в начале правой части каждого правила находится терминальный символ. А так как для разных альтернатив одного правила Т-символы различны, то всегда можно выбрать необходимый.

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

Для s-грамматик это множество составляет множество непосредственно первых терминальных символов:

НАПР(i) = НПерв (i)

Q-грамматики

КС-грамматика называется Q-грамматикой тогда и только тогда, когда выполняются следующие два условия:

1. Правая часть каждого правила представляет собой  (пустую) -строку, либо начинается с Т-символами.

2. Множества выбора разных альтернатив правила не пересекаются.

Приведенная ниже грамматика отвечает поставленным условиям. От S-грамматики она отличается только наличием пустой строки (-строки).

1. <S> - a <A> <S>

2. - b

3. <A> - c <A> <S>

4. - 

-строка может использоваться при разборе предложения в двух случаях:

1. Либо для завершения циклической структуры вывода.

2. Либо, если ни один символ из множества выбора для непустых правил не подходит в качестве выводимого символа.

Множества направляющих символов для Q-грамматики:

НАПР(i) = НПерв(i) , для непустых правил,

След(i) , для -правил.

Таким образом, для пустой строки тоже существует множество символов выбора, так называемых символов-следователей, на основании которого возможно применение -правила в двух описанных выше условиях.

Например, выведем из приведенной Q-грамматики цепочку aacbb, которая принадлежит языку, определяемому данной грамматикой (рис.2).

Для данной КС-грамматики с начальным символом <S> и нетерминала ( <X> - НТ-символ, одной из альтернатив которого является -строка ) определим СЛЕД (<X>) как множество Т-символов, которые могут следовать за <X> в какой-либо промежуточной цепочке, выводимый из <S>. Это множество называется множеством следующих за <X> терминалов.

Рис. 2. Вывод цепочки, принадлежащей языку

Анализируя пример, можно установить, что после нетерминала <A> могут идти только Т-символы a и b, т.е.

СЛЕД ( <A> ) = {a,b}.