Разница между анализом LL и LR

Насколько я понимаю, контекстно-свободные грамматики можно анализировать по принципу сверху вниз/LL или снизу вверх/LR.

Да, парсинг LL работает сверху вниз. Синтаксический анализ LR обычно считается восходящим синтаксическим анализом, хотя некоторые авторы считают его гибридом нисходящего и восходящего, поскольку он использует контекст о том, что может появиться где в сгенерированном дереве синтаксического анализа.

Правильно ли понимается, что синтаксические анализаторы LL требуют, чтобы грамматики имели строго однозначные правила производства, прежде чем их можно будет проанализировать?

Парсеры LL работают только с однозначными грамматиками. Наиболее распространенные классы синтаксических анализаторов LL (LL(1), LL(*)) работают не со всеми грамматиками и требуют некоторых дополнительных ограничений, помимо однозначности грамматики. Например, синтаксические анализаторы LL(1) не могут обрабатывать левую рекурсию.

И что синтаксические анализаторы LR, с другой стороны, также требуют, чтобы грамматики были однозначными, но вместо того, чтобы переписывать какие-либо неоднозначные правила производства, можно добавить дополнительные правила приоритета к правилам производства, чтобы решить их неоднозначность?

И да и нет. Это правда, что, как и синтаксические анализаторы LL, наиболее распространенные типы синтаксических анализаторов LR (LR(0), SLR(1), LALR(1), LR(1), IELR(1)) требуют, чтобы грамматика была однозначной. Вы правы в том, что многие неоднозначности могут быть разрешены с помощью объявлений приоритета, которые разбивают неоднозначные в противном случае грамматики, но это не может разрешить все неоднозначности. Кроме того, есть некоторые однозначные грамматики, которые не могут быть проанализированы никаким синтаксическим анализатором LR(k).

Но как во все это вписывается взгляд вперед?

Добавление предпросмотра к LL или LR синтаксическому анализатору дает синтаксическому анализатору больше контекста, с которым он может решить, какие продукционные правила применять (для LL синтаксических анализаторов) или смещать или уменьшать (LR синтаксические анализаторы). Интуитивно, возможность увидеть дальше последовательность токенов позволяет синтаксическому анализатору исключить некоторые варианты, которые не могут работать, потому что они не могут соответствовать тому, что будет дальше. Конкретные правила работы этого опережающего просмотра зависят от алгоритма синтаксического анализа; например, LR(2 ) синтаксические анализаторы имеют некоторые нюансы, которые не проявляются в синтаксических анализаторах LR(1). Скорее всего, вы найдете нужную информацию, специально прочитав синтаксический анализ LL(1), синтаксический анализ LR(0) и синтаксический анализ LR(1), и можете использовать это в качестве отправной точки.