Требование детерминированного распознавания

Else

Begin

Begin

if Ch = '^ ' then begin

NextCh;

Number;

end;

end;

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

Последняя распознающая процедура — для «Целого». И в этом случае тоже можно преобразовать исходную диаграмму (см. рис. 19), отделив блок, соответствующий первой цифре (обязательной), от остальных блоков (рис. 23).

Рис.23 Синтаксическая диаграмма «Целое»

Предусматривать отдельную распознающую процедуру для «почти терминального символа» «цифра» неразумно. Проще и наглядней непосредственно проверять принадлежность очередного знака множеству цифр.

procedure Number; { Целое }

if Ch in ['0'..'9'] then

NextCh

Error('Число начинается не с цифры');

while Ch in ['0'..'9'] do

NextCh;

end;

Распознаватель готов. Осталось только расположить в программе написанные процедуры в правильном порядке — описание процедуры поместить перед ее вызовом. Поскольку рекурсии в этом примере нет, сделать это легко.

На рассмотренном примере мы продемонстрировали, что синтаксический анализатор методом рекурсивного спуска можно написать «почти так же быстро, как мы вообще можем писать»

Уже в ходе предыдущего рассмотрения можно было заметить, что рекурсивный спуск позволяет построить анализатор не для любой КС-грамматики.

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

Множество направляющих символов first(D) ветви D синтаксической диаграммы образуют терминальные символы, которые могут встретиться первыми при движении по диаграмме вдоль этой ветви.

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

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

Чтобы алгоритм работал без возвратов, а выбор направления движения по диаграмме выполнялся однозначно, должно соблюдаться требование детерминированного распознавания:

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

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

Возьмем, например, диаграмму, показанную на рис. 21. На ней две точки ветвления. Первая — на входе в диаграмму, вторая — на выходе.

В первом разветвлении три ветви. Множества направляющих символов этих ветвей:

[' +' ] — верхняя ветвь;

[' 0'.. ' 9', 'х']— средняя ветвь;

[' -' ] — нижняя ветвь.

Как видим, эти множества не пересекаются.

В правой точке происходит ветвление на два направления. Одно ведет на выход из диаграммы, множество направляющих символов этой ветви состоит из символа «конец текста»: [^]. Другая ветвь соответствует очередному витку цикла, ее множество направляющих символов равно [' +', ' -' ].

Пересечения множеств снова нет.

Дата добавления: 2014-01-05