В основном при анализе рекурсивного спуска каждый нетерминал в грамматике переводится в процедуру, а затем внутри каждой процедуры, которую вы проверяете, чтобы увидеть, соответствует ли текущий токен, который вы просматриваете, тому, что вы ожидаете увидеть в правой частинетерминальный символ, соответствующий процедуре, если он все же продолжает применять продукцию, если нет, то вы столкнулись с ошибкой и должны предпринять какое-то действие.
Так что в вашем случае, как вы упомянули вышеу вас будут процедуры: S(), L() и E(), я приведу пример того, как можно реализовать L(), а затем вы можете попробовать S() и E() самостоятельно.
Также важно отметить, что вам понадобится какая-то другая программа для токенизации ввода для вас, тогда вы можете просто запросить у этой программы следующий токен из вашего ввода.
/**
* This procedure corresponds to the L non-terminal
* L -> 'end'
* L -> ';' S L
*/
public void L()
{
if(currentToken == 'end')
{
//we found an 'end' token, get the next token in the input stream
//Notice, there are no other non-terminals or terminals after
//'end' in this production so all we do now is return
//Note: that here we return to the procedure that called L()
getNextToken();
return;
}
else if(currentToken == ';')
{
//we found an ';', get the next token in the input stream
getNextToken();
//Notice that there are two more non-terminal symbols after ';'
//in this production, S and L; all we have to do is call those
//procedures in the order they appear in the production, then return
S();
L();
return;
}
else
{
//The currentToken is not either an 'end' token or a ';' token
//This is an error, raise some exception
throw new IllegalTokenException(
"Procedure L() expected an 'end' or ';' token "+
"but received: " + currentToken);
}
}
Теперьвы пробуете S() и E() и отправляете обратно.
Также, как указывает Кристофер, в вашей грамматике есть что-то, что называется висящим другим,Имеется в виду, что у вас есть производство, которое начинается с одной и той же вещи до определенного момента:
S -> if E then S
S -> if E then S else S
Таким образом, возникает вопрос, видит ли ваш парсер токен 'if', какое производство он должен выбрать для обработки ввода?Ответ в том, что он понятия не имеет, какой из них выбрать, потому что в отличие от людей, компилятор не может заглянуть во входной поток для поиска токена «else».Эту простую проблему можно решить, применив правило, известное как левый факторинг, очень похожее на то, как вы бы учли проблему алгебры.
Все, что вам нужно сделать, - это создать новый нетерминальный символ S '(S-prime), чья правая сторона будет содержать фрагменты необычных произведений, поэтому ваши S постановки no становятся:
S -> if E then S S'
S' -> else S
S' -> e
(e is used here to denote the empty string, which basically means there is no
input seen)