Help understanding LR(1) parsers, table generation? Any other resources?

Question

I am currently taking a compilers class and I am having a hard time understanding LR(1) parsing algorithms using the action/goto table and also how to hand generate these tables. Right now we are using Engineering a Compiler by Cooper and Torczon as our class text book and I have also read the wikipedia pages on table generation but I still do not understand the concepts. If possible can anyone recommend any other book that explains parsing well or an online resource? I would think many universities would have good online resources/slides on the subject but I have no idea on where to start looking. Thanks!

Answer 1

The books are always hard to read because of the algorithm details. Greek symbols and abstract operations are hard to interpret unless you already know what they mean.

The way I learned how to do this, was to write a tiny grammar (simple expression, assignment statement, if then statement, sequence of statements), and then hand simulate the algorithm. Get a really big piece of paper. Draw the starting configuration state with just the goal symbol and dot [ G = DOT RHS1 ... RHSM ]. Then process the unprocessed states, following the algorithm in detail; write down what each greek symbol represents at that moment. As you gain confidence, you'll get a better feeling and it will go faster.

Essentially what you are going to do is, for each item I

 [LHS RHS1 DOT RHS2 RHS3 ... RHSN] 

in a state, push the dot in item one place to right to produce a new item

 [LHS RHS1 RHS2 DOT RHS3 ... RHSN ]

draw a new state on your paper new state with that item as the seed, fill out the item core with lookahead sets based on FIRST(RHS3), expand the state, and repeat.

This will take you several hours the first time you try it. Worth every second. Use a pencil!

Answer 2

some decent lecture notes...

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

Understanding and Writing Compilers has a section, What are the True Advantages of LR(1) Analysis?

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

(also available freely online)

Here is a link to a decent summary, although explanation is lacking.

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

more lecture notes...

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

and notes here...

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

(including goto and action tables)

Sorry I can't explain personally, I'm not too sure myself. Maybe you will find a kind, more knowledgeable soul around.