О применимости метода рекурсивного спуска
2. Если грамматика не удовлетворяет требованиям применимости метода рекурсивного спуска, то можно попытаться преобразовать ее, то есть получить эквивалентную грамматику, пригодную для анализа этим методом.
a) Если в грамматике есть нетерминалы, правила вывода которых
леворекурсивны, то есть имеют вид
A → Aα1 | ... | Aαn | β1 | ... | βm,
где αi (T N)+, βj (T N)*, i = 1, 2, ..., n; j =1, 2, ..., m, то непосредственно применять РС-методнельзя.
Левую рекурсию всегда можно заменить правой:
A → β1A’ | ... | βm A’ A’→ α1A’ | ... | αn A’ | ε
Будет получена грамматика, эквивалентная данной.
Оприменимости метода рекурсивного спуска
b)если в грамматике есть нетерминал, у которого несколько правил вывода начинаются одинаковымитерминальнымисимволами, то есть имеют вид
A → aα1 | aα2 | ... | aαn | β1 | ... | βm,
где a T; αi, βj (T N)*, то непосредственно применять РС-метод нельзя.
Можно преобразовать правила вывода данного нетерминала, объединив правила с общиминачалами в одно правило:
A → aA’ | β1 | ... | βm A’ → α1 | α2 | ... | αn
Будет получена грамматика, эквивалентная данной.
Оприменимости метода рекурсивного спуска
c)если в грамматике есть нетерминал, у которого несколько правил вывода, и
среди них есть правила, начинающиеся нетерминальными символами, то есть
имеют вид
A → B1α1 | ... | Bnαn | a1β1 | ... | amβm B. .1.→ γ11 | ... | γ1k
Bn → γn1 | ... | γnp,
где Bi N; aj T; αi, βj, γij (T N)*, то можно заменить вхождения нетерминалов Bi их правилами вывода в надежде, что правило нетерминала A станет удовлетворять
требованиям методарекурсивного спуска:
A → γ11 α1 | ... | γ1k α1 | ... | γn1 αn | ... | γnp αn | a1 β1 | ... | am βm
О применимости метода рекурсивного спуска
d) если допустить в правилах
вывода грамматики пустую альтернативу, то есть правила вида
A → a1α1 | ... | anαn | ε ,
то метод рекурсивного спуска может оказаться неприменимым.
Например, для грамматики G = ({S, A}, {a, b}, S, P), где
P: S → bAa
A → aA | ε
РС-анализатор, реализованный по обычной схеме, будет таким:
void S(void) {if (c == ‘b’)
{c = fgetc(fp); A();
if (c != ‘a’) ERROR();} else ERROR();}
void A(void) {if (c == ‘a’)
{c = fgetc(fp); A();}}