Все грамматики LL являются грамматиками LR, но не наоборот, но я все еще изо всех сил пытаюсь разобраться с различием. Мне любопытны небольшие примеры, если таковые существуют, LR-грамматик, которые не имеют эквивалентного LL-представления.
Пример LR-грамматики, которая не может быть представлена LL?
Ответы (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(1):
S ::= a S | P
P ::= a P b | \epsilon
но нет грамматики LL(k). Причина в том, что LL-грамматика должна решить, следует ли сопоставить пару a+b или нечетное a при просмотре a, в то время как LR-грамматика может отложить это решение до тех пор, пока не увидит b или конец входных данных.
В этом посте на cs.stackechange.com много упоминаний об этом
person
Chris Dodd
schedule
10.01.2012
Это кажется маловероятным. Эта грамматика, похоже, прекрасно соответствует
if/else, то есть statement ::= if (...) statement | if (...) statement else (...) statement. С этим, насколько я знаю, парсеры LL прекрасно справляются.
- person Puppy; 11.01.2012
@DeadMG: Как вы заметили, висячая грамматика else - это тот же шаблон, поэтому это не LL и не может быть правильно обработана любым синтаксическим анализатором LL. Конечно, с написанным от руки синтаксическим анализатором вы можете использовать специальный обходной путь (в данном случае обычно мини-парсер LR), но это не меняет того факта, что грамматика не является LL.
- person Chris Dodd; 11.01.2012
Интересно. Означает ли это, что практически все языки, которые следуют этой конструкции, имеют грамматики, отличные от LL, и практически все генераторы синтаксических анализаторов LL должны иметь обходные пути?
- person Puppy; 11.01.2012
Да. Эта проблема, не связанная с LL, заключается в том, почему многие языки имеют
endif или другой конечный токен, который должен совпадать с if, так как это делает язык снова LL.
- person Chris Dodd; 12.01.2012
@ChrisDodd: извините, но тривиальная грамматика LR (1) неоднозначна, поэтому она не может быть LR:
aab имеет два разных дерева синтаксического анализа с любой из первых двух альтернатив S в корне. Также я бы не сказал, что любая леворекурсивная грамматика является LR, но вы, возможно, хотели сказать, что любая леворекурсивная LR грамматика не является LL.
- person Gunther; 19.09.2012
@Gunther: ой, ты прав - я случайно упростил грамматику; ему нужен второй нетерминал, чтобы разрешить неоднозначность.
- person Chris Dodd; 21.09.2012
