2

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

LL: object '{' pairs(1) pair STRING ':' value(1) STRING pairs_tail(2) '}'

И LR: '{' STRING ':' STRING value(1) pair pairs_tail(2) pairs(1) '}' object

Для потока токенов: { STRING : STRING }

Собственно, это и есть весь ответ на вопрос или я что-то упустил?

1
  • 1
    Если не ошибаюсь, то вот в таком: if (a) if(b) doX(); else doY(); - один из них распарсит так if (a) { if(b) doX(); else doY(); }, а другой так: if (a) { if(b) doX(); } else doY();.
    – Qwertiy
    11 дек 2019 в 12:57

1 ответ 1

3

Есть два ответа. Первый касается сложности подготовки грамматики.

LL-анализаторы не умеют разбирать леворекурсивные правила.

LR-грамматика может содержать правила, где expression выражается через определение, самым левым нетерминалом в которым также является expression.

expression ::= expression + expression
             | expression - expression
             | expression * expression
             | expression / expression
             | term
             ;

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

expression ::= term tail
             ;

tail       ::= + expression
             | - expression
             | * expression
             | / expression
             |
             ;

Такие преобразования тривиальны, но трудоёмки. Они незаметны программисту, который пользуется языком программирования, поэтому о разнице здесь говорить не приходится.

То, что может заметить программист, это разница в языках, которые допускает грамматика.

Поэтому второй ответ — про разницу в языках, которую не убрать никакими преобразованиями.

Во-первых, для LL-грамматик k имеет значение. Бывают языки, которые можно описать грамматикой LL(k + 1), но нельзя LL(k). Для LR грамматик все языки можно привести к LR(1).

Пример LL(k) языка при k > 1. Предположим, в нашем языке мы можем записывать списки чисел:

foo = 123 34 564 234 23 354

Но язык также позволяет работать с двухмерным и и трёхмерными векторами. Чтобы обозначить такой вектор, мы должны записать суффикс vecза последним числом.

point2d = 100 200 vec
point3d = 50 40 30 vec

Вектор point2d сможет разобрать грамматика LL(3), а point3d — грамматика LL(4). Почему? Потому что надо прочитать 3 или 4 токена, чтобы понять, с чем мы работаем — со списком произвольной длины или вектором длины 2 или 3.

Посмотрите этот ответ на вопрос, там ссылка на книгу, где разобраны подобные примеры.

Теперь пример языка, который сможет разобрать грамматика LR(1), но не сможет LL(k).

Предположим, в нашем языке мы можем записывать приход и доход товаров на склад.

balance = I I I I I O O O

Каждый I означает приход, а каждый O — расход. Согласен, странный способ записи, но все нестранные задачи вполне могут быть записаны с помощью грамматики LL(1).

Главное правило: количество расходов O может быть меньше, чем количество приходов I, или равно ему, но не может быть больше. Отрицательных остатков на складе не бывает.

LR(1) грамматика для такого синтаксиса выглядит так:

balance ::= I balance
          | pair
          ;

pair    ::= I pair O
          |
          ;

А вот LL(k) грамматики для него нет ни при каком k.

Вот ответ, где приведён похожий пример.

В действительности, не обязательно проверять корректность конструкций с помощью грамматики. Мы можем сделать LL(1), которая прочитает все I и все O, а потом руками проверить, что количество I больше или равно количеству O.

Кроме того, инструкции современных языков программирования описываются грамматикой LL(1).

Выбор между LL и LR зачастую объясняется тем, что LL(1) грамматику можно закодировать вручную, а для LR обычно требуется инструментальное средство наподобие yacc. yacc требует освоения и опыта, но он позволяет ускорить работу над компилятором, если вы регулярно расширяете язык.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.