- •Метод рекурсивного спуска
- •Метод рекурсивного спуска
- •Метод рекурсивного спуска
- •Метод рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
- •О применимости метода рекурсивного спуска
О применимости метода рекурсивного спуска
Тогда при анализе строки baaa функция A() будет вызвана три раза; она прочитает подстроку ааа, хотя третий символ а – это часть подстроки, выводимой из S.
В результате окажется, что baaa не принадлежит языку, порождаемому грамматикой, хотя в действительности это не так.
Проблема заключается в том, что подстрока, следующая за строкой, выводимой из A, начинается таким же символом, как и строка, выводимая из А.
Однако в грамматике G = ({S, A}, {a, b, с}, S, P), где
P: S → bAс A → aA | ε
нет проблем с применением методарекурсивного спуска.
О применимости метода рекурсивного спуска
Выпишем условие, при котором ε-продукция делает неприменимым РС-метод.
Определение 49.
Множество FIRST(A) – это множество терминальных символов, которыми начинаются строки, выводимые из А в грамматике G = (N, T, S, P), то есть
FIRST(A) = { a T| A aα, A N, α (T N)*}.
Определение 50.
Множество FOLLOW(A) – это множество терминальных символов, которые следуют за строками, выводимыми из А в грамматике G = (N, T, S, P), то есть
FOLLOW(A) = {a T | S αAβ, β aγ, A N; α, β, γ (T N)*}.
О применимости метода рекурсивного спуска
Тогда, если FIRST(A)∩FOLLOW(A) ≠ , то метод рекурсивного спуска неприменим к данной грамматике.
Если
A → α1A | ... | αn A | β1 | ... | βm | ε
B → αAβ
и FIRST(A)∩FOLLOW(A) ≠ (из-за вхождения А в правила вывода для В), то можно попытаться преобразоватьтакую грамматику:
B → α A’
A’→ α1A’ | ... | αn A’ | β1β | ... | βm β | β A → α1A | ... | αn A | β1 | ... | βm | ε
Полученная грамматика будет эквивалентна исходной, так как из B по-прежнему выводятся строки вида α{αi}βj β либо α{αi}β.
Однако правило вывода для нетерминального символа A’ будет иметь альтернативы, начинающиеся одинаковыми терминальными символами, следовательно, потребуются дальнейшие преобразования, и успех не гарантирован.
О применимости метода рекурсивного спуска
Метод рекурсивного спуска применим к достаточно узкому подклассу КС-грамматик. Известны более широкие подклассы КС-грамматик, для которых существуют эффективные анализаторы, обладающие тем же свойством, что и анализатор, написанный методом рекурсивного спуска, – входная строка считывается один раз слева направо и процесс разбора полностью детерминирован, в результате на обработкустроки длины n расходуетсявремя cn.
К таким грамматикам относятся LL(k)-грамматики, LR(k)-грамматики, грамматики предшествования и некоторыедругие.