Помогите понять парсеры LR (1), генерацию таблиц? Любые другие ресурсы? - PullRequest
10 голосов
/ 04 марта 2011

В настоящее время я учусь на классе компиляторов, и мне трудно разобраться в алгоритмах синтаксического анализа LR (1) с использованием таблицы action / goto, а также о том, как вручную генерировать эти таблицы.Прямо сейчас мы используем проектирование компилятора Купера и Торчона в качестве учебного пособия для своего класса, и я также читал страницы Википедии о создании таблиц, но я до сих пор не понимаю концепции.Если возможно, кто-нибудь может порекомендовать любую другую книгу, которая хорошо объясняет синтаксический анализ или онлайн-ресурс?Я думаю, что во многих университетах есть хорошие онлайн-ресурсы / слайды по этой теме, но я не знаю, с чего начать.Спасибо!

Ответы [ 2 ]

9 голосов
/ 05 марта 2011

Книги всегда трудно читать из-за деталей алгоритма. Греческие символы и абстрактные операции трудно интерпретировать, если вы уже не знаете, что они означают.

Способ, которым я научился это делать, заключался в том, чтобы написать крошечную грамматику (простое выражение, оператор присваивания, если затем оператор, последовательность операторов), а затем рука имитирует алгоритм . Получите действительно большой лист бумаги. Нарисуйте начальное состояние конфигурации только с помощью символа цели и точки [G = DOT RHS1 ... RHSM]. Затем обработайте необработанные состояния, подробно следуя алгоритму; запишите, что каждый греческий символ представляет в данный момент. Когда вы обретете уверенность, вы почувствуете себя лучше, и все пойдет быстрее.

По сути, то, что вы собираетесь делать, для каждого элемента, который я

 [LHS RHS1 DOT RHS2 RHS3 ... RHSN] 

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

 [LHS RHS1 RHS2 DOT RHS3 ... RHSN ]

нарисуйте новое состояние на вашей бумаге, новое состояние с этим элементом в качестве начального числа, заполните ядро ​​элемента наборами прогнозных данных на основе FIRST (RHS3), разверните состояние и повторите.

Это займет у вас несколько часов при первой попытке. Стоит каждую секунду. Используйте карандаш!

3 голосов
/ 04 марта 2011

некоторые достойные конспекты лекций ...

http://cs.oberlin.edu/~jdonalds/331/lecture14.html

Понимание и написание компиляторов содержит раздел «Каковы истинные преимущества анализа LR (1)?»

http://www.amazon.com/Understanding-Writing-Compilers-Yourself-Macmillan/dp/0333217322

(также доступно бесплатно в Интернете)

Вот ссылка на приличное резюме, хотя объяснение отсутствует.

http://arantxa.ii.uam.es/~modonnel/Compilers/LR1Summary.pdf

больше лекционных заметок ...

http://www.cs.umd.edu/class/spring2011/cmsc430/lectures/lec07.pdf

и примечаний здесь ...

http://cobweb.ecn.purdue.edu/~smidkiff/ece495S/files/handouts/w3w4bBW.pdf

(включая таблицы переходов и действий)

Извините, я не могу объяснить лично, я не слишком уверен в себе.Может быть, вы найдете добрую, более знающую душу вокруг.

...