Комментарии 17
«Можно вогнать анализатор в ступор неоднозначностью описания языка.»
Например, как?
Например, как?
Очень просто. Есть у нас язык, который представляет из себя последовательность символов 'a' неопределенной длины. Примеры конструкций языка — a, aaaa, aaa....aaa.
Грамматика его крайне проста:
Так вот, здесь LR(0)-парсер спасует из-за того, что состояние номер 1 (сразу после начального) будет таким:
И когда начнём строить таблицы, то получим то, что для этого состояния применимо и свертка (по правилу 1), и перенос (по правилу 2).
Грамматика его крайне проста:
Так вот, здесь LR(0)-парсер спасует из-за того, что состояние номер 1 (сразу после начального) будет таким:
И когда начнём строить таблицы, то получим то, что для этого состояния применимо и свертка (по правилу 1), и перенос (по правилу 2).
Молодец, отличная статья.
Тема, кстати, для меня сейчас очень актуальна.
Тема, кстати, для меня сейчас очень актуальна.
Про неоднозначность описания языка я бы опустил момент, потому что она может вогнать в ступор не только LR-анализатор, но и многие другие алгоритмы, хорошие и разные, а так же некоторых высших приматов.
И да, вы забыли уточнить, что конечный автомат имеет (кеп) конечное число состояний.
И да, вы забыли уточнить, что конечный автомат имеет (кеп) конечное число состояний.
Не нашел простого и внятного описания данного алгоритма на русском языке.
Ну, почему, на русском есть книги. Например:
- Ахо, Сети, Ульман, «Компиляторы. Принципы, технологии, инструменты», глава «4.7. LR-анализаторы» (это, как раз, русский перевод приведенной Вами книги).
- Рейуорд-Смит, «Теория формальных языков», глава «8.2. LR (0)-грамматики».
Возможно, также, есть в этих книгах, но их сейчас нет под рукой и точно я не уверен:
- М.В. Мозговой (rg_software), «Классика программирования — алгоритмы, языки, автоматы, компиляторы» (там точно есть что-то про LR-грамматики, но насчет именно LR(0) я не помню).
- Хопкрофт, Мотвани, Ульман, «Введение в теорию автоматов, языков и вычислений».
За статью спасибо, многим пригодится.
ключевое слово — простого :)
В Dragon book'e всё же довольно много математики и формальных определений, да и есть несколько моментов, которые можно оптимизировать с точки зрения программирования. К примеру — в книге предлагается использовать не таблицу переходов, а функцию GOTO, с таким описанием, что я не сразу и въехал что от меня хотят.
В Dragon book'e всё же довольно много математики и формальных определений, да и есть несколько моментов, которые можно оптимизировать с точки зрения программирования. К примеру — в книге предлагается использовать не таблицу переходов, а функцию GOTO, с таким описанием, что я не сразу и въехал что от меня хотят.
«Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.» Мы в свое время в ВУЗе по этой книжке писали для MINI Basic компилятор. В ней настолько все полно описано, хотя в некоторых местах есть ошибки. Но куда уж без них!
Покрывает множество языков. То есть если вы придумали язык и описали его, то с большой долей вероятности LR-анализатор его сможет обработать.
С большой долей вероятности вам придется подпиливать грамматику под тот тип парсера, который вы выбрали. Причем что для LL, что для LR.
Класс грамматик которые обрабатывает LR включает в себя все грамматики, обрабатываемые LL.
То есть условия использования LL строже, и значит для LR придётся допиливать куда меньше.
А так да, грамматика сложнее Hello World'a (арифметические операции) скорее всего будет нуждаться в доработке, но часто не столь существенной.
Само собой это всё сферические кони в вакууме, и без конкретных примеров говорить трудно.
То есть условия использования LL строже, и значит для LR придётся допиливать куда меньше.
А так да, грамматика сложнее Hello World'a (арифметические операции) скорее всего будет нуждаться в доработке, но часто не столь существенной.
Само собой это всё сферические кони в вакууме, и без конкретных примеров говорить трудно.
Синтаксические ошибки обнаруживаются так быстро как это возможно. Сразу же как встречается символ, который не соответствует предыдущему входному потоку, мы можем вывести ошибку об этом.
Вот это крайне спорно. Как правило для LR приходится прилагать дополнительные усилия, чтобы ошибки указывались на самый левую лексему ошибочной части.
Жаль, что совсем не упомянуто про packrat.
Эх, без картинок вообще ничего не понятно…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Пишем LR(0)-анализатор. Простыми словами о сложном