Учебное пособие: Разработка в структурно логической схемы микропроцессора

Правая часть порождающего правила начинается с терминала.

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

Для того что бы грамматика была, необходимым условием является множеством символам предшественников не должно пересекаться. Грамматику называют Ll(1) если для каждого не терминала появляющегося в левой части более одного раза множества направляющих символов соответствующих правил не пересекаются. Возникает вопрос, все ли грамматики. Существует ли алгоритмы, определяющие свойства. Однако, грамматику, можно преобразовать что бы она стала Ll(1).

Что бы заменить левую рекурсию на правую мы упорядочиваем не терминалы.

Факторизация – во многих ситуациях грамматику не обладающих признаками Ll(1) можно преобразовать в грамматику Ll(1). Процесс факторизации нельзя автоматизировать, распространив его на общий случай.

Лекция 07.12.07

Ll(1) – грамматика

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

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

1 столбец – направляющие символы (терминал)

2 столбец – поле перехода, обычно дает следующий элемент для обработки (номер строки). Если значение поля возврата, не окажется истинной, то адрес следующего элемента берется из стека. Это соответствует концу правила.


3 столбец – направляющие символы, переход




Терминал

Переход

Принимать

стек

возврат

ошибка

1

Begin

2

f

f

f

t

2

Begin

3

t

К-во Просмотров: 365
Бесплатно скачать Учебное пособие: Разработка в структурно логической схемы микропроцессора