Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2020-10-20 | 129 |
5.00
из
|
Заказать работу |
Цель работы: изучение нисходящего метода разбора предложений, основанного на порождающей 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.
ОПРЕДЕЛЕНИЕ: множества символов, по которым при синтаксическом разборе входной строки производится выбор того или иного порождающего правила, называются множествами направляющих символов или направляющими множествами.
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!