Каковы основные преимущества и недостатки парсинга LL и LR?

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

Я сопоставлю разбор LL и LR по ряду критериев:

сложность

LL побеждает здесь, руки вниз. Вы можете легко написать LL-парсер. Фактически, это обычно делается: компилятор Microsoft C # - это рукописный анализатор рекурсивного спуска (источник здесь , ищите комментарий, сделанный Патриком Кристиансеном - пост в блоге также очень интересен).

LR-анализ использует довольно нелогичный метод для анализа текста. Это работает, но мне потребовалось некоторое время, чтобы обернуть голову, как это работает точно. Поэтому написание такого парсера вручную затруднительно: вы бы более или менее реализовали генератор парсера LR.

всеобщность

Здесь побеждает LR: все языки LL являются языками LR, но языков LR больше, чем языков LL (язык является языком LL, если его можно анализировать с помощью синтаксического анализатора LL, и язык является языком LR, если его можно анализировать с парсер LR).

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

Есть однозначные языки, которые не являются языками LR, но они довольно редки. Вы почти никогда не сталкиваетесь с такими языками. Тем не менее, у LALR есть несколько проблем.

LALR более или менее полезен для LR-парсеров, чтобы уменьшить размер таблиц. Таблицы для парсера LR обычно могут быть огромными. Парсеры LALR отказываются от возможности разбирать все языки LR в обмен на меньшие таблицы. Большинство парсеров LR на самом деле используют LALR (хотя не секретно, что обычно можно найти именно то, что он реализует).

LALR может жаловаться на конфликты «сдвиг-уменьшение» и «уменьшение-уменьшение». Это вызвано взломом таблицы: она объединяет похожие записи вместе, что работает, потому что большинство записей пустые, но когда они не пусты, возникает конфликт. Ошибки такого рода не являются естественными, сложными для понимания, и исправления обычно довольно странные.

Ошибки компиляции и исправление ошибок

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

Кроме того, при разборе LL восстановление после ошибок намного проще. Если вход не анализируется правильно, вы можете попытаться немного пропустить и выяснить, правильно ли анализируются остальные входные данные. Например, если какой-то оператор программирования имеет неправильный формат, вы можете пропустить его и проанализировать следующий оператор, чтобы можно было отловить более одной ошибки.

С использованием LR-парсера это намного сложнее. Вы можете попытаться расширить свою грамматику, чтобы она принимала ошибочный ввод и печатала ошибки в областях, где что-то пошло не так, но это обычно довольно сложно сделать. Вероятность того, что вы получите грамматику не-LR (или не-LALR), также возрастает.

скорость

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

связи

Вот ссылка на сайт, также контрастирующий с LL и LR. Ищите секцию около основания.

Здесь вы можете найти разговор о различиях. Неплохо было бы критически взглянуть на высказанные там мнения, хотя там идет какая-то священная война .

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