Пример грамматики 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^i b^j | я>= j } Есть тривиальная грамматика LR:

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

но без грамматики LL(k). Причина в том, что грамматика LL должна решить, соответствовать ли паре a + b или нечетному a при взгляде на a, в то время как грамматика LR может отложить это решение до тех пор, пока не увидит b или конец ввода.

Этот пост на cs.stackechange.com содержит множество ссылок на эту тему.