Разработка компиляторов

       

Условия использования метода рекурсивного спуска


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

Определение. Для КС-грамматики G и цепочки w, состоящей из терминальных и нетерминальных символов, определим множество FIRST k (w) следующим образом:

FIRST k (w) = {x | w =>* xv, |x| = k или w =>* x, |x| < k}, где k - натуральное число.

Иными словами, множество FIRST k (w) состоит из всех терминальных префиксов длины k терминальных цепочек, выводимых из w.

Пример. Рассмотрим грамматику, порождающую подмножество типов языка Pascal.

Для этой грамматики мы имеем:

FIRST1 (simple) = {integer, char, num} FIRST1 (^id) = {^} FIRST1 (array [simple] of type) = { array }

Понятно, что если цепочка w состоит только из терминалов, то FIRST k (w) - это первые k символов цепочки w , если |w| >= , или это сама цепочка w, если |w| < k <



Содержание раздела