Являются ли синтаксические анализаторы LL(1) более эффективными для префиксного кодирования, а LR(1) более эффективными для постфиксного?

Стоимость синтаксического анализа строгого выражения до (или после) порядка тривиальна при использовании методов «сверху вниз» или «снизу вверх». Он затмит любые другие задачи, даже лексический анализ. Крошечные различия в скорости будут результатом деталей реализации, а не алгоритмической стратегии.

Нет смысла использовать синтаксический анализатор LR(1), поскольку вам не нужен токен упреждающего представления ни для предварительного, ни для последующего порядка, предполагая, что представление является чисто предварительным/послезаказным. LR(0) было бы просто отлично. Вы вряд ли найдете полезный генератор синтаксического анализатора LR(0), но если вы хотите написать синтаксический анализатор от руки, этот факт упростит вашу задачу.

Игнорируя LL(1) и LR(1) на данный момент, вы обычно анализируете такие виды выражений, запуская свой собственный код синтаксического анализа. Вы будете поддерживать стек ранее проанализированных и оцененных подвыражений, а затем неоднократно либо извлекать два верхних элемента из стека и объединять их (если вы читаете другой оператор), либо помещать что-то в стек (если вы читаете число).

Есть несколько способов реализовать этот стек. Вы можете сделать стек явной структурой данных стека, где вы сканируете ввод слева направо и вставляете и извлекаете элементы по мере необходимости. По стилю это ближе всего к тому, как работает парсер LR(1), поскольку вы будете думать в терминах сдвига (вталкивания) и сокращения (выталкивания). В качестве альтернативы вы можете использовать рекурсивный алгоритм и использовать стек вызовов вместо явного стека, что по духу ближе к тому, как работает синтаксический анализ LL(1).

Парсинг LL(1) и LR(1) в этом случае, если вы заботитесь только о чистой производительности, кажется полным излишеством. Они предназначены для обработки больших классов общих грамматик, и накладные расходы на таблицы, вероятно, будут снижать вашу производительность. Я бы просто написал код двумя разными способами (явный стек/снизу вверх и неявный стек/сверху вниз) и посмотрел, какой из двух на самом деле окажется быстрее.

В этой статье Разоблачение тайны синтаксического анализа LL и LR, подтверждает мою интуицию:

Польская и обратная польская нотации, на мой взгляд, напрямую соответствуют разбору LL и LR соответственно.