Пример грамматики LR, которая не может быть представлена ​​LL?

Question

Все грамматики LL - это грамматики LR, но не наоборот, но я все еще изо всех сил пытаюсь справиться с различием. Мне любопытно о небольших примерах, если таковые имеются, грамматики LR, которые не имеют эквивалентного представления LL.

Answer 1

Что ж, что касается грамматики, это легко-любая простая левая грамматика-LR (вероятно, LR (1)), а не LL. Итак, грамматика списка как:

list ::= list ',' element | element

является LR (1) (при условии, что производство для элемента), но не LL. Такие грамматики могут быть довольно легко преобразованы в грамматики LL путем левой фактической деятельности и тому подобное, так что это не слишком интересно.

Более интересный интерес представляет языки, которые являются LR, но не LL - это язык, для которого существует грамматика LR (1), но нет грамматики LL (K) для любой k. Примером являются вещи, которые нуждаются в дополнительных матчах по следам. Например, язык любого количества a символы, за которыми следуют тот же номер или меньше b символы, но не больше bS - {a^ib^j | i> = j}. Есть тривиальная грамматика LR (1):

S ::= a S | P
P ::= a P b | \epsilon

Но нет LL (K) грамматики. Причина в том, что грамматике LL должна решить, соответствует ли пара A+B или нечетное A при просмотре A, в то время как грамматика LR может отложить это решение, пока не увидит B или конец ввода.

Эта почта на cs.stackechange.com есть много ссылок на это