Я пытаюсь понять самый левый вывод в контексте алгоритма синтаксического анализа LL. Этот link объясняет это с точки зрения генератора . т. е. показывает, как следовать самому лексическому выводу, чтобы генерировать определенную последовательность токенов из набора правил.Иллюстрировать самый левый вывод в потоке токенов
Но я думаю об обратном направлении. Учитывая поток токенов и набор правил грамматики, как найти правильные шаги для применения набора правил самым левым дериватором?
Давайте продолжать использовать следующую грамматику из вышеуказанной ссылке:
И данной лексемы последовательности: 1 2 3
Один из способов заключается в следующем:
1 2 3
-> D D D
-> N D D (rewrite the *left-most* D to N according to the rule N->D.)
-> N D (rewrite the *left-most* N D to N according to the rule N->N D.)
-> N (same as above.)
Но есть и другие способы применения правил грамматики:
1 2 3 -> DDD -> NDD -> NND -> NNN
ИЛИ
1 2 3 -> DDD -> NDD -> NND -> НН
Но только первый вывод заканчивается в одном не-терминале.
По мере увеличения длины последовательности токенов может быть еще много способов. Я думаю, вывести правильную происходящие шаги необходимы 2 предпосылок:
- отправного/корень правило
- лексемы последовательность
Дав эти 2, что алгоритм, чтобы найти производя шаги? Должны ли мы сделать окончательный результат одиночный non-terminal?
Возможно, мое редактирование делает мой ответ более ясным. Если нет, спросите :) – rici