Помощь в понимании парсеров LR (1), генерации таблицы? Любые другие ресурсы?

Question

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

Answer 1

приличные конспекты ...

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

(включая Гото и действия таблиц)

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

Answer 2

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

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

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

[LHS RHS1 DOT RHS2 RHS3 ... RHSN] 

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

[LHS RHS1 RHS2 DOT RHS3 ... RHSN ] 

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

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