Связь между LR(0), LL(0), LALR(1) и т. Д.?

Question

Я действительно изо всех сил пытаюсь понять отношения между:

• LR (0)
• LL(0)
• LALR (1)
• SLR (1)
• LR (1)
• LL (1)

Я почти уверен, что LALR (1) и SLR (1) являются подмножествами LR (1), но я заблудился о других. Они все эксклюзивные? Является ли LL(0) подмножеством LL(1)?

Спасибо

Answer 1

Правила содержания следующие:

• Каждая грамматика LR(0) также является SLR(1), но не все грамматики SLR (1) являются LR(0).
• Каждая грамматика SLR (1) также является LALR(1), но не все грамматики LALR (1) являются SLR(1).
• Каждая грамматика LALR (1) также является LR (1), но не все грамматики LR (1) являются LALR(1).
• Каждая грамматика LL (1) также является LR (1), но не все грамматики LR (1) являются LL (1).
• Каждая грамматика LL(0) также является LR(0), SLR(1), LALR(1), LR(1) и LL(1). (LL(0) грамматики в основном бесполезны; подробности см. В этом вопросе).

Также бывает, что каждый язык, имеющий грамматику LR (1), также имеет грамматику LR(0), при условии, что вы заканчиваете грамматику, хотя грамматика не гарантированно будет красивой.