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