Пример грамматики LR, которая не может быть представлена LL?
Вопрос
Все грамматики LL - это грамматики LR, но не наоборот, но я все еще изо всех сил пытаюсь справиться с различием. Мне любопытно о небольших примерах, если таковые имеются, грамматики LR, которые не имеют эквивалентного представления LL.
Решение
Что ж, что касается грамматики, это легко-любая простая левая грамматика-LR (вероятно, LR (1)), а не LL. Итак, грамматика списка как:
list ::= list ',' element | element
является LR (1) (при условии, что производство для элемента), но не LL. Такие грамматики могут быть довольно легко преобразованы в грамматики LL путем левой фактической деятельности и тому подобное, так что это не слишком интересно.
Более интересный интерес представляет языки, которые являются LR, но не LL - это язык, для которого существует грамматика LR (1), но нет грамматики LL (K) для любой k. Примером являются вещи, которые нуждаются в дополнительных матчах по следам. Например, язык любого количества a
символы, за которыми следуют тот же номер или меньше b
символы, но не больше b
S - {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 есть много ссылок на это