Все грамматики LL являются грамматиками LR, но не наоборот, но я все еще изо всех сил пытаюсь разобраться с различием. Мне любопытно, какие малые примеры, если таковые имеются, грамматик LR, которые не имеют эквивалентного представления LL.Пример грамматики 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^i b^j | i> = j}. Существует тривиальная грамматика LR (1):
S ::= a S | P
P ::= a P b | \epsilon
, но не грамматика LL (k). Причина в том, что грамматика LL должна решить, следует ли сопоставлять пару a + b или нечетное a при просмотре a, тогда как грамматика LR может отложить это решение до тех пор, пока не увидит b или конец ввода.
This post на cs.stackechange.com имеется множество ссылок об этом
Это кажется весьма маловероятным. Эта грамматика, кажется, соответствует 'if/else' просто отлично, т. Е.' Statement :: = if (...) statement | if (...) statement else (...) statement'. Это, насколько мне известно, обрабатывается LL-парсерами просто отлично. – Puppy
@DeadMG: Как вы заметили, грамматика болтающегося остатка - это тот же шаблон, поэтому его не LL и нельзя обрабатывать с помощью любого анализатора LL. Разумеется, с помощью рукописного анализатора вы можете использовать одноразовый обходной путь (обычно это парный анализатор LR для этого случая), но это не меняет того факта, что грамматика не LL –
Интересно. Означает ли это, что практически все * языки, следующие за этой конструкцией, имеют не-LL-грамматики, и практически все генераторы парсеров LL должны иметь обходные пути? – Puppy