mark_ablov Apr 3 2011 at 06:41

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

10 min

27K

Algorithms*

From sandbox

+67

Comments 18

ks_ks Apr 3 2011 at 12:03

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

mark_ablov Apr 3 2011 at 12:24

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

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

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

ks_ks Apr 3 2011 at 12:37

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

copyhold Apr 3 2011 at 14:24

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

+10

humbug Apr 3 2011 at 19:48

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

mark_ablov Apr 4 2011 at 04:24

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

Omgovich Apr 3 2011 at 12:52

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

FrimInc Apr 3 2011 at 13:26

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

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

Alik_Kirillovich Apr 3 2011 at 13:28

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

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

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

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

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

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

mark_ablov Apr 3 2011 at 13:34

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

LokaRo Apr 3 2011 at 13:35

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

OdobenusRosmarus Apr 3 2011 at 16:36

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

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

mark_ablov Apr 3 2011 at 16:46

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

OdobenusRosmarus Apr 3 2011 at 16:42

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

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