mark_ablov 3 апр 2011 в 02:41

Пишем LR(0)-анализатор. Простыми словами о сложном

10 мин

28K

Алгоритмы *

Из песочницы

+67

Комментарии 18

ks_ks 3 апр 2011 в 08:03

«Можно вогнать анализатор в ступор неоднозначностью описания языка.»
Например, как?

mark_ablov 3 апр 2011 в 08:24

Очень просто. Есть у нас язык, который представляет из себя последовательность символов 'a' неопределенной длины. Примеры конструкций языка — a, aaaa, aaa....aaa.
Грамматика его крайне проста:

Так вот, здесь LR(0)-парсер спасует из-за того, что состояние номер 1 (сразу после начального) будет таким:

И когда начнём строить таблицы, то получим то, что для этого состояния применимо и свертка (по правилу 1), и перенос (по правилу 2).

ks_ks 3 апр 2011 в 08:37

Круто. Теперь я чувствую себя умным. :D

copyhold 3 апр 2011 в 10:24

А я, блин, наоборот :(

humbug 3 апр 2011 в 15:48

А вы не могли бы поправить грамматику и сделать ее однозначной?

mark_ablov 4 апр 2011 в 00:24

достаточно во втором правиле в правой части поменять A и a местами.

Omgovich 3 апр 2011 в 08:52

Молодец, отличная статья.
Тема, кстати, для меня сейчас очень актуальна.

FrimInc 3 апр 2011 в 09:26

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

И да, вы забыли уточнить, что конечный автомат имеет (кеп) конечное число состояний.

Alik_Kirillovich 3 апр 2011 в 09:28

Не нашел простого и внятного описания данного алгоритма на русском языке.

Ну, почему, на русском есть книги. Например:

Ахо, Сети, Ульман, «Компиляторы. Принципы, технологии, инструменты», глава «4.7. LR-анализаторы» _{(это, как раз, русский перевод приведенной Вами книги)}.
Рейуорд-Смит, «Теория формальных языков», глава «8.2. LR (0)-грамматики».

Возможно, также, есть в этих книгах, но их сейчас нет под рукой и точно я не уверен:

М.В. Мозговой (rg_software), «Классика программирования — алгоритмы, языки, автоматы, компиляторы» _{(там точно есть что-то про LR-грамматики, но насчет именно LR(0) я не помню)}.
Хопкрофт, Мотвани, Ульман, «Введение в теорию автоматов, языков и вычислений».

За статью спасибо, многим пригодится.

mark_ablov 3 апр 2011 в 09:34

ключевое слово — простого :)
В Dragon book'e всё же довольно много математики и формальных определений, да и есть несколько моментов, которые можно оптимизировать с точки зрения программирования. К примеру — в книге предлагается использовать не таблицу переходов, а функцию GOTO, с таким описанием, что я не сразу и въехал что от меня хотят.

LokaRo 3 апр 2011 в 09:35

«Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.» Мы в свое время в ВУЗе по этой книжке писали для MINI Basic компилятор. В ней настолько все полно описано, хотя в некоторых местах есть ошибки. Но куда уж без них!

OdobenusRosmarus 3 апр 2011 в 12:36

Покрывает множество языков. То есть если вы придумали язык и описали его, то с большой долей вероятности LR-анализатор его сможет обработать.

С большой долей вероятности вам придется подпиливать грамматику под тот тип парсера, который вы выбрали. Причем что для LL, что для LR.

mark_ablov 3 апр 2011 в 12:46

Класс грамматик которые обрабатывает LR включает в себя все грамматики, обрабатываемые LL.
То есть условия использования LL строже, и значит для LR придётся допиливать куда меньше.
А так да, грамматика сложнее Hello World'a (арифметические операции) скорее всего будет нуждаться в доработке, но часто не столь существенной.
Само собой это всё сферические кони в вакууме, и без конкретных примеров говорить трудно.

OdobenusRosmarus 3 апр 2011 в 12:42

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

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