Разработка синтаксического анализатора предложений, порожденных LL(1)- грамматикой

 

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

 

Теоретический материал, необходимый для выполнения лабораторной работы

 

ПОНЯТИЕ СИНТАКСИЧЕСКОГО АНАЛИЗА ПРЕДЛОЖЕНИЙ.

Задача синтаксического анализатора – распознавание предложений рассматриваемого языка и их структуры. Это означает, что шаги порождения (т.е. непосредственные выводы) должны реконструироваться при прочтении входной цепочки синтаксическим анализатором.

 

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

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

Различают две стратегии разбора предложений: нисходящую (сверху вниз) и восходящую (Снизу вверх).Это два метода построения синтаксических деревьев.

При нисходящем разборе дерево строится от корня (начального символа) вниз к висячим вершинам.

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

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

 

LL (I)-ГРАММАТИКА

 

LL(I)-грамматика допускает безвозвратный синтаксический анализ путем просмотра на один символ вперед.

Прежде чем определить LL(I)-грамматику более точно, рассмотрим понятие S-грамматики.

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

Продукции S-грамматики удовлетворяют следующим требованиям:

А) правая часть каждой продукции начинается с терминала;

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

 

ПРИМЕР S-грамматики:

(1) <S> -> p<X>

(2)  <S> -> q<Y>

(3)  <X> -> a<X>b

(4)  <X> ->x

(5)  <Y> -> a<Y>d

(6)  <Y>-> y

 

При разборе предложения языка, определенного S-грамматикой,всегда можно точно определить,какую продукцию нужно применить на каждом этапе разбора. Например, на первом этапе разбора, мы должны определить, какое из правил мы должны применить – первое или второе: если анализируемая цепочка начинается с символа p, то – первое правило, если с q – второе и т.д.

LL(I)-грамматика является обобщением S-грамматики, но принцип обобщения позволяет строить аналогичные нисходящие анализаторы.

Правые части в LL(I)-грамматике не обязательно должны начинаться с терминальных символов, но заданный вариант какого-либо правила может дать начало только строкам, начинающимся с одного терминального символа из конкретного множества терминалов.

  

Например:

 

(1) <S> -> <R><Y>

(2) <S>-> <T><Z>

(3) <R> -> p<X>b

(4) <T> -> q<Y>d

(5) <X> -> …

(6) <Y> -> …

 

Из рассмотрения представленных правил можно заключить, что правило <S> -> <R><Y> нужно применить при нисходящем разборе, когда просматриваемым символом входной строки является символ p. Аналогично порождающее правило <S>-> <T><Z> должно применяться в том случае, если таким символом является терминальный символ q.

 

ОПРЕДЕЛЕНИЕ: множества символов, по которым при синтаксическом разборе входной строки производится выбор того или иного порождающего правила, называются множествами направляющих символов или направляющими множествами.