Ответ 1
Хорошо, что касается грамматик, то его простая - простая левая рекурсивная грамматика - LR (вероятно, LR (1)), а не LL. Итак, грамматика списка вроде:
list ::= list ',' element | element
- LR (1) (при условии, что для элемента есть произведение), но не LL. Такие грамматики можно довольно легко преобразовать в грамматики LL с помощью левого факторинга и т.д., Поэтому это не слишком интересно.
Более интересны ЯЗЫКИ, которые являются LR, но не LL - это язык, для которого существует грамматика LR (1), но не LL (k) для любого k. Примером могут быть вещи, которые нуждаются в необязательных совпадениях. Например, язык любого числа символов a, за которым следует одно и то же число или меньше символов b, но не более b - {a ^ я b ^ j | я >= j}. Там тривиальная грамматика LR (1):
S ::= a S | P
P ::= a P b | \epsilon
но не LL (k) грамматика. Причина в том, что грамматика LL должна решить, следует ли сопоставлять пару a + b или нечетное a при просмотре a, тогда как грамматика LR может отложить это решение до тех пор, пока не увидит b или конец ввода.
В этом сообщении на cs.stackechange.com есть много ссылок об этом