Какое производственное правило я должен использовать для уменьшения при анализе снизу вверх?

Question

Пока что мое понимание алгоритма анализа снизу вверх таково.

1. сдвинуть токен в стек
2. проверка стека сверху, если некоторые элементы, включая верх, могут быть уменьшены по производственному правилу
3. если элементы можно уменьшить, вытолкните и нажмите левую часть производственного правила.
4. продолжайте эти шаги до тех пор, пока top не станет символом начала, а следующий вход не будет EOF

Итак, чтобы подкрепить мой вопрос грамматикой примера,

S → aABe

A → Abc
A → b
B → d

если у нас есть строка ввода как

abbcde $

мы сместим a в стек и поскольку не существует производственного правила, которое уменьшает a, мы сдвигаем следующий токен b. Тогда мы можем найти правило производства A → b и уменьшить b до A.

Тогда мой вопрос такой. У нас в стеке aA, а следующий ввод - b. Тогда как синтаксический анализатор может определить, уменьшаем ли мы b до A, ожидаем ли мы c и используем правило A → Abc?

Ну, конечно, уменьшение b до A в этот момент приводит к ошибке. Но как парсер узнает в этот момент , что нам следует ждать c?

Извините, если что-то пропустил во время учебы.

Answer 1

Это отличный вопрос, и он будет рассмотрен в следующей части вашего курса.

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

Различныеалгоритмы разбора объясняют конструкцию этого черного ящика.Обратите внимание, что одно из возможных решений состоит в том, чтобы раскошелиться на реальность и попробовать оба действия параллельно, но более распространенным решением является обработка грамматики для определения того, как предсказать правильное действие.