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

Электрик сделает електрику дома Новосибирск и пригороде. Русский электрик.

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


Например, процедура обработки нетерминала F для правила F::=i[E] вызывает процедуру обработки нетерминала E, который в свою очередь может вызвать процедуру обработки нетерминала F. Поэтому данный метод получил название РЕКУРСИВНОГО СПУСКА.

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

 

int F()             // результат вычисления F

{

int v,n;            // результат промежуточных вычислений

switch(s[i])     

      {

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

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

case ‘c’: i++; v = значение_константы_c; break;

case ‘i’: i++;

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

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

{ v=значение_поля_s[i]_переменной_s[i-2]; i++;}

else error(); }

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

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

{ v=значение_элемента_n_массива_s[i-2]; i++; }

else error(); }

else { v=значение_переменной_s[i];i++; }

break;

} return v; }

 

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

 

T ::= T * F | T / F | F

 

Эти правила генерируют цепочки вида F * F / F * F / F с переменным количеством нетерминалов F и знаками операций “*,/ ” между ними. Очевидно, процедура для нетерминала T должна распознавать циклическую последовательность таких символов и завершать распознавание, когда во входной цепочке ей встретится очередной символ, отличный от “*,/ ”.




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



Книжный магазин