Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2020-10-20 | 128 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!