Разработка компиляторов
Условия использования метода рекурсивного спуска
Метод рекурсивного спуска без возвратов можно использовать только для грамматик, правила которых удовлетворяют следующему условию: первого символа каждого правила должно быть достаточно для того, чтобы определить, какое правило применимо в данном случае. Более точно это условие можно формализовать путем определения множества 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 <
