Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

который воспринимает грамматику, проводит любые из преобразований, о

которых только что говорилось, проверяет не являются ли правила рекур-

сивными, и составляет таблицы для грамматики в одной из описываемых да-

лее форм довольно легко.

Для представления грамматики используется списочная структура, на-

зываемая синтаксическим графом. Каждый узел представляет символ S из

правой части и состоит из четырех компонент: ИМЯ, ОПРЕДЕЛЕНИЕ (ОПР),

АЛЬТЕРНАТИВА (АЛТ) и ПРЕЕМНИК (ПРЕМ), где

1. ИМЯ - это сам символ S в некоторой внутренней форме.

2. ОПРЕДЕЛЕНИЕ равно 0, если S - терминал; в противном случае эта

компонента указывает на узел соответствующий первому символу в

перво правой части для S.

3. АЛЬТЕРНАТИВА указывает на первый символ той альтернативы пра-

вой части которая следует за правой частью, содержащей данный

узел (0, если такой правой части нет). Это только для символов

в правых частях.

4. ПРЕЕМНИК указывает на следующий символ правой части (0, если

такого символа нет).

Кроме того, каждый нетерминальный символ представлен узлом, состо-

ящим из одной компоненты, которая указывает а первый символ в первой

правой части, относящейся к этому символу. Примером может служить

рис. 4, на котором изображено расположения компонент узла синтаксическо-

го графа грамматики:

*---------------------------*

| ИМЯ |

*--------*---------*--------*

| ОПР | АЛТ | ПРЕМ |

*--------*---------*--------*

Рис 6. Расположение компонент узла синтаксического