Курс Основы построения трансляторов

программирование для детей Электрик сделает электромонтажные работы в коттедже в Новокузнецке и пригороде. Русский электрик.

Рекурсивный спуск - часть 2


Для понимания вышесказанного рассмотрим фрагмент программы:

 

char s[80];      // входная цепочка терминалов

int      i;      // текущий терминальный символ

void F()

{

switch(s[i])

      {

case ‘*’: i++; E(); break;

case ‘&’: i++; E(); break;

case ‘c’: i++; break;

case ‘(‘: i++; E();

if (s[i]==’)’) i++; else error(); break;

case ‘i’: i++;

if (s[i]==’.’)

{ i++; if (s[i]==’i’) i++;

else error(); }

else if (s[i]==’[’)

{ i++; E(); if (s[i]==’]’) i++;

else error(); }

else i++;

break;

      }}

 

индекс i является указателем на текущий нетерминальный символ во входной строке (цепочке). Каждая процедура, анализируя очередной символ, продвигает этот указатель вперед, если в выбранной правой части правила находится такой же символ, в противном случае информирует о синтаксической ошибке. Например, в правой части правила F::=i[E] после символа “[” и нетерминала E следует символ “]”. Последний и проверяется в процедуре анализа после вызова процедуры анализа нетерминала E.  Если он действительно присутствует в строке как текущий символ, то он пропускается

 

      if (s[i])==’]’) i++; else error();

 

если в правой части правила имеется нетерминал, то в тот момент, когда в просматриваемом фрагменте строки “наступает очередь” этого нетерминала, вызывается процедура, которая должна производить этот анализ для группы правил с этим нетерминалом в левой части. Например, после анализа цепочки терминалов “i[” выясняется, что речь идет о правиле  F::=i[E], тогда для выполнения анализа выражения в скобках необходимо просто вызвать процедуру E().

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

выбор одного из правил F::=i | i.i | i[E] производится по первым двум символам (одного здесь не достаточно).

 

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


Начало  Назад  Вперед