Грамматика и синтаксический анализ сверху вниз

Question

Некоторое время я пытался узнать, как работают парнеры LL, и, если я это правильно понимаю, при написании парсера с рекурсивным спусканием сверху вниз я должен создать функцию для каждого не- символ терминала. Так что для этого примера:

S -> AB 
A -> aA|ε 
B -> bg|dDe 
D -> ab|cd 

я должен был бы создать функцию для каждого S, A, B и D, как это:

Token B() 
{ 
    if (Lookahead(1) == 'b') 
    { 
     Eat('b'); 
     Eat('g'); 
    } 
    else if (Lookahead(1) == 'd') 
    { 
     Eat('d'); 
     D(); 
     Eat('e'); 
    } 
    else 
    { 
     Error(); 
    } 

    return B_TOKEN; 
} 

Но тогда я пытаюсь сделать то же самое с следуя грамматику, которую я создал, чтобы генерировать тот же язык (а | б | в) * регулярное выражение:

S -> Ma 
M -> aM|bM|cM|ε 

Это дает мне следующие функции:

Token S() 
{ 
    char Ch = Lookahead(1); 
    if (Ch == 'a' || Ch == 'b' || Ch == 'c') 
    { 
     M(); 
     Eat('a'); 
    } 
    else 
    { 
     Error(); 
    } 

    return S_TOKEN; 
} 

Token M() 
{ 
    char Ch = Lookahead(1); 
    if (Ch == 'a' || Ch == 'b' || Ch == 'c') 
    { 
     Eat(ch); 
     M(); 
    } 

    return M_TOKEN; 
} 

И это не кажется хорошим, потому что для ввода «bbcaa» M будет потреблять все, и после этого S не найдет последний «a» и не сообщит об ошибке, даже если грамматика принимает его. Похоже, что M отсутствует в случае с ε, или, может быть, это неправильно, но я не уверен, как с этим справиться. Может ли кто-нибудь помочь?

Answer 1

Поведение прогностического анализатора сверху вниз точно так же, как вы отмечаете в своем вопросе. Другими словами, ваша вторая грамматика не подходит для синтаксического анализа сверху вниз (с односторонним взглядом). Многие грамматики нет; который включает любую грамматику, в которой невозможно предсказать, какое производство использовать на основе конечного вида.

В этом случае, если вы должны были искать два токена вместо одного, вы могли бы разрешить конфликт; M должен предсказать ε производство на упреждающей выборке END, и aM производства на всех остальных двух лексем lookaheads где первый маркер .