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


Рекурсивный спуск


Рассмотрим еще один  “естественный” алгоритм нисходящего СА. Пусть имеется некоторый нетерминальный символ, из которого выводится предложение языка - цепочка терминальных символов. При нисходящем разборе этот нетерминал на первом шаге необходимо заменить на правую часть одного из правил, в котором он присутствует в левой части. Рассмотрим пример:

 

F ::= i | i[E] | c | *E | &E | i.i | (E)

 

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

.

         F

         |

   aaa[jj+46]…      (…i[i+c]…)

 

Для удобства восприятия входная строка приведена и в синтаксических, и в лексических единицах. Тогда единственная проблема состоит в том, чтобы на очередном шаге построения дерева нетерминал  F заменить на правую часть одного из перечисленных  правил. Человек сделает это интуитивно, выбирая правило F::=i[E] - определение элемента массива

.           

                   F

                   |

              i [  E   ]

                   |

 aaa[ jj+46 ]… (i[i+c])

 

после чего оставшаюся часть строки  jj+46 требуется вывести из нетерминала E. Отсюда следует самый простой неформальный алгоритм синтаксического анализа. Для каждой группы правил с общим нетерминалом в левой части пишется процедура, которая по начальным символам терминальной цепочки в состоянии определить, правую часть какого правила следует применить, затем она параллельно просматривает терминальную цепочку и правую часть правила. Если очередные терминальные символы в цепочке и в правиле совпадают, то они оба пропускаются, если нет - это признак синтаксической ошибки. Если в правиле встречается нетерминальный символ, то необходимо вызвать аналогичную процедуру для обработки группы правил, в которой этот нетерминал встречается в левой части.


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



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