Задачи по программированию по курсу ЯПиМТ. Родионова Т.Е. - 27 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

27
зывают также распознавателем, так как она распознает только цепочки рассматриваемой
грамматики. Если в процессе вывода цепочки правила грамматики применяются только к
самому левому нетерминалу, говорят, что получен левый разбор цепочки. Аналогично оп-
ределяется правый разбор цепочки.
Различают два класса алгоритмов разбора контекстно-свободных грамматик:
- низходящий;
- восходящий.
К первому классу относятся те, которые строят деревья выводов, начиная с корня и
вершин, соответствующих наиболее крупным синтаксическим единицам. Вэтомслучае
входная цепочка просматривается многократно. Этот класс алгоритмов наиболее универ-
сален, к нему относятся LL-грамматики.
Одним из широко известных и легко реализуемых детерминированных методов
разбора сверху – вниз является рекурсивный спуск. Такойанализаторсодержитпоодной
рекурсивной процедуре для каждого нетерминала. Каждая такая процедура осуществляет
разбор фраз, выводимых из нетерминала. Процедура сообщает, с какого места данной про-
граммы следует начать поиск фразы, выводимой из рассматриваемого нетерминала. Про-
цедура сравнивает программу в указанном месте с правыми частями правил для нетерми-
нала и вызывает по мере необходимости другие процедуры.
Большое количество контекстно-свободных языков можно описать с помощью
LL(k) – грамматики, по которой можно построить детерминированный синтаксический
анализатор, работающий по принципу сверху – вниз.
Две буквы L означают, что строки разбираются слева направо и используются ле-
вые выводы. Цифра k означает количество предварительно просмотренных символов.
Пример 1: Рассмотрим LL(1) - грамматику:
(1) S → aAS
(2) S → b
(3) A → a
(4) A → bSA
Работой алгоритма разбора руководит управляющая таблица, в которой содержатся:
- правая часть применяемого правила;
- маркер выброса
символа из стека;
- маркер допуска
цепочки символов;
- маркер ошибки
.
Столбцы управляющей таблицы озаглавливаются терминалами данной грамматики с учетом пустой
строки, а строки - возможными верхними символами магазина (стека) и специальным символом конца стека
($).
Управляющая таблица для заданной грамматики имеет вид:

Страницы