Буква R в системе парсинга LR

Question

Я пытаюсь понять, как работает анализ LR. L означает, что синтаксический анализатор читает входной текст в одном направлении без резервного копирования; это направление обычно слева направо в каждой строке и сверху вниз по строкам полного входного файла.

R означает, что синтаксический анализатор производит самый правый вывод в обратном порядке. моя проблема с R, я не могу понять, что это значит.

просто я знаю самый правый вывод для этого грамматика: E → E + E | E * E | (E) | Я бы

как следует:

E → E + E → E + E * E → E + E * id3 → E + id2 * id3 → id1 + id2 * id3

Спасибо.

Answer 1

Парсер LR обнаруживает самый правый вывод в обратном направлении. Таким образом, в вашем примере производные, которые он обнаружил бы, были бы в следующем порядке:

stack • input          derivation
-----------------      ----------
• id1 + id2 * id3      E → id1
E + • id2 * id3        E → id2
E + E * • id3          E → id3
E + E * E •            E → E * E
E + E •                E → E + E 
E •